%0 Conference Proceedings
%T Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays
%+ School of Computer Science and Technology [Tianjin]
%A Jiang, Guiyuan
%A Wu, Jigang
%A Sun, Jizhou
%Z Part 3: Session 3: Parallel Architectures
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 10th International Conference on Network and Parallel Computing (NPC)
%C Guiyang, China
%Y Ching-Hsien Hsu
%Y Xiaoming Li
%Y Xuanhua Shi
%Y Ran Zheng
%I Springer
%3 Network and Parallel Computing
%V LNCS-8147
%P 194-206
%8 2013-09-19
%D 2013
%R 10.1007/978-3-642-40820-5_17
%K Interconnection network
%K reconfiguration
%K rerouting scheme
%K fault tolerant
%K algorithm
%Z Computer Science [cs]Conference papers
%X In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration considered in this paper is to reorganize fault-free PEs from a processor array with faults to a logical array of regular mesh topology by changing the interconnections among PEs. This paper presents the efficiency of the flexible rerouting scheme to maximize the usage of the fault-free PEs, by developing an efficient reconfiguration algorithm without backtracking. The proposed algorithm constructs each logical columns from left to right on candidate PE sets. It updates the candidate sets by excluding the PEs which cannot be used, once a logical column is formed. Also, it is proved that the proposed heuristic algorithm is able to generate the maximum-size logical array in linear time. Experimental results show that 123 logical columns can be constructed on 256 ×256 host arrays with fault density of 30%, resulting in an improvement of 51% in comparison to the previous algorithm by which only 82 logical columns can be produced. Furthermore, our algorithm is able to generate target arrays with harvest over 56% on host arrays with fault density of 50%, while the previous work cited in this paper fails to construct any target array in this case.
%G English
%2 https://inria.hal.science/hal-01513763/document
%2 https://inria.hal.science/hal-01513763/file/978-3-642-40820-5_17_Chapter.pdf
%L hal-01513763
%U https://inria.hal.science/hal-01513763
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-NPC
%~ IFIP-LNCS-8147