Optimization And Design Of High Reliability Parallel Heterogeneous Multi-Core Systems

In the design of hard real-time systems,high reliability,high performance and low cost are critical but conflicting demands.To deal with the trade-off between high performance and low cost,heterogeneous multi-core architectures such as MultiProcessor System on Chip(MPSoC)are commonly employed.To provide a fair balance between high performance and high reliability,checkpointing techniques are typically employed to recover the system from faults by loading the correct information saved at “checkpoint” with light time overhead.While checkpointing techniques can reduce the time of recovery when faults occur,it will increase the execution time of applications in fault-free cases since it needs to create checkpoints.Also,the implementation of checkpointing technique on the novel non-volatile memory(NVM)based systems needs to consider the write endurance problem of NVM.Our objective is to design high performance and reliable application specific systems using the checkpointing technique.In order to improve the system performance,we further employ pipelining technique in our design.In the design of such systems,we need to carefully determine three functions:(1)due to limited resources,tasks in the application need to be partitioned into different pipeline stages,called Application Partition;(2)due to the heterogeneity in the MPSoC,tasks have various execution times on different cores.Hence,we need to determine which core to execute each task,called Core Assignment;(3)in order to guarantee the system reliability while preserve the system performance and the lifetime of NVM,we need to determine the time to create checkpoint and minimize the number of checkpoints as much as possible,called Checkpoint Placement.We first propose an Integer Linear Programming(ILP)model to obtain the optimal application partition,core assignment,checkpoint placement,i.e.,to obtain the optimal solution of above problem.However,due to the large computational complexity of ILP model,it can only obtain optimal solution for small instances.Hence,we give a theorem to indicate the property of optimal solution and further proposed an efficient optimal algorithm.Experimental results show that,our algorithm can obtain optimal solution in seconds while ILP cannot generate any solution when the number of tasks in the application exceeds 11 in a reasonable amount of time(24 hours).Our algorithm can fully explore the solution space,when compared with other algorithms,we can reduce 44% number of checkpoints on average.Owing to the efficiency of the algorithm,we can obtain the Pareto Front in the design space,which can provide more design choice for designers.