Skip to Main content Skip to Navigation
Conference papers

Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01513763
Contributor : Hal Ifip <>
Submitted on : Tuesday, April 25, 2017 - 2:33:30 PM
Last modification on : Monday, February 25, 2019 - 12:44:08 PM
Long-term archiving on: : Wednesday, July 26, 2017 - 2:05:04 PM

File

978-3-642-40820-5_17_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Guiyuan Jiang, Jigang Wu, Jizhou Sun. Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.194-206, ⟨10.1007/978-3-642-40820-5_17⟩. ⟨hal-01513763⟩

Share

Metrics

Record views

78

Files downloads

222