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

fYear

1999

fDate

36465

Firstpage

395

Lastpage

403

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Defect and Fault Tolerance in VLSI Systems, 1999. DFT '99. International Symposium on

Conference_Location

Albuquerque, NM

ISSN

1550-5774

Print_ISBN

0-7695-0325-x

Type

conf

DOI

10.1109/DFTVS.1999.802907

Filename

802907