Research On Fault-tolerance Mapping Algorithm Based On Critical Tasks For NoC

Mapping algorithm has become a hot research field for NoC in recent years.At present,Semiconductor technology feature size reduction and the improvement of chip integration,promote the complexity and performance of NoC.At the same time,it has brought a greater challenge to the reliability mapping of NoC.In order to guarantee the reliability of the application mapping,fault-tolerant technology for NoC has become an important aspect of NoC research.A Fault-Tolerance Mapping Algorithm based on Critical Tasks(FTMA-CTs)is proposed in this paper.The algorithm can not only improve the reliability of the mapping process,but also reduce the total energy consumption of the system.In FTMA-CTs mapping Algorithm,mapping is divided into two stages:mapping from virtual topology to physical topology and mapping from task graph to virtual topology.Among them,the virtual topology to the physical topology of the mapping stage,this paper uses the Hungarian algorithm to solve the one-to-one mapping problemof virtual core to physical core.The task graph to the virtual topology of the mapping stage,Firstly,the task graph based on node is transformed into the enhanced task graph based on nodes and edges.Then,the critical path of the task graph is found by the path delay and the system delay,make further efforts to find critical tasks.Then the task graph with critical tasks is divided into clusters,and the clustering algorithm(AP)is adopted.In the clustered task graph mapping to the virtual topology,the improved branch and bound algorithm is adopted.The proposed algorithm increases two boundaries based on the original branch and bound algorithm.Through these two boundaries continue to prune the branches of the tree.so as to further reduce the number of feasible solution,finally use the improved branch and bound algorithm can efficiently and quickly obtained a better mapping scheme.Finally,the simulation of energy consumption with improved Nirgam simulator is carried out.through compared with the annealing method was proposed by Zhang et al and the greedy algorithm based on redundancy core was proposed by Yue et al.The performance of FTMA-CTs mapping algorithm is analyzed.The results show that the FTMA-CTs mapping algorithm can not only improve the reliability of the application mapping,but also can reduce the execution time and the system energy consumption.