Abstract
We propose a remapping algorithm to tolerate the failures of Processing Elements (PEs) on Multiprocessor System-on-Chip. A new graph modeling is proposed to precisely define the increase of communication cost among PEs after remapping. Our method can be used not only to repair faults but also to improve the communication cost of given initial mapping results. Experimental results show that under multiple failures, the communication cost by our method is 43.59% less on average compared with that by previous work [1] using the same number of spare PEs. Moreover, the communication cost is further reduced by 4.16% after applying our method to initial mappings produced by NMAP [2].