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.
Type de document :
Communication dans un congrès
Ching-Hsien Hsu; Xiaoming Li; Xuanhua Shi; Ran Zheng. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. Springer, Lecture Notes in Computer Science, LNCS-8147, pp.194-206, 2013, Network and Parallel Computing. 〈10.1007/978-3-642-40820-5_17〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01513763
Contributeur : Hal Ifip <>
Soumis le : mardi 25 avril 2017 - 14:33:30
Dernière modification le : mardi 25 avril 2017 - 14:35:50
Document(s) archivé(s) le : mercredi 26 juillet 2017 - 14:05:04

Fichier

978-3-642-40820-5_17_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Guiyuan Jiang, Jigang Wu, Jizhou Sun. Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays. Ching-Hsien Hsu; Xiaoming Li; Xuanhua Shi; Ran Zheng. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. Springer, Lecture Notes in Computer Science, LNCS-8147, pp.194-206, 2013, Network and Parallel Computing. 〈10.1007/978-3-642-40820-5_17〉. 〈hal-01513763〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

25