Embedding of rings in 2-D meshes and tori with faulty nodes

To increase the reliability of networks embedded in meshes or tori and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in meshes and tori are necessary, In this paper, we present algorithms for embedding a ring in a mesh-type and torus-type multiprocessor network in the event of node failures, In our approach, a mesh or torus is partitioned into 4 x 4 submeshes, Subgraphs (rings and linear arrays) are mapped in each submesh and then merged to form a large ring. Using this approach, we obtain the following results in a torus. Given any f less than or equal to 2 faulty nodes, a ring which is optimal can be found in a mesh, Also, given any f less than or equal to 4 faulty nodes, a ring which is optimal can be found in a torus. Furthermore, given f less than or equal to 4 faulty nodes, a Hamiltonian cycle can be found in a torus if and only if the number of even faulty nodes is equal to the number of odd faulty nodes. Even and odd refer to the sum of the node's coordinates.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1997-08
Language
ENG
Keywords

HYPERCUBES; ARRAYS

Citation

JOURNAL OF SYSTEMS ARCHITECTURE, v.43, no.9, pp.643 - 654

ISSN
1383-7621
DOI
10.1016/S1383-7621(96)00120-8
URI
http://hdl.handle.net/10203/4889
Appears in Collection
CS-Journal Papers(저널논문)
  • Hit : 459
  • Download : 4
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 5 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0