Title :
Reconfiguration of two-dimensional meshes embedded in faulty hypercubes
Author :
Nakano, Sumito ; Kamiura, Naotake ; Hata, Yutaka ; Matsui, Nobuyuki
Author_Institution :
Dept. of Comput. Eng., Himeji Inst. of Technol., Hyogo, Japan
Abstract :
In this paper we discuss the reconfiguration of two-dimensional meshes embedded in hypercubes with link and/or node failures. First, we assume that only the link failures may occur. Our method consists of two stages. The first stage assigns dimensions of hypercube to two directions of mesh so that the losses of rows or columns would be as small as possible. The second stage establishes the mesh communication by assigning the Cartesian product of two Gray code sequences to every node. We generate these sequences with a depth-first search or generic algorithm. This method can be applied to node failures by regarding a faulty node as a node whose links are entirely faulty. Our simulation results show that our method can reconfigure large meshes with short computation time
Keywords :
genetic algorithms; graph theory; hypercube networks; sequences; Cartesian product; Gray code sequences; depth-first search algorithm; embedded 2D mesh reconfiguration; faulty hypercubes; generic algorithm; link failures; mesh communication; node failures; two-dimensional meshes; Computational modeling; Embedded computing; Genetic algorithms; Hamming distance; Hypercubes; Parallel algorithms; Reflective binary codes;
Conference_Titel :
Defect and Fault Tolerance in VLSI Systems, 1999. DFT '99. International Symposium on
Conference_Location :
Albuquerque, NM
Print_ISBN :
0-7695-0325-x
DOI :
10.1109/DFTVS.1999.802907
