Fault-tolerant routing algorithm for wormhole routed meshes
Journal
Parallel Computing
Journal Volume
26
Journal Issue
4
Pages
455-465
Date Issued
2000
Date
2000
Author(s)
Sui, Pao-Hwa
Abstract
We investigate fault-tolerant routing schemes which aim at using low number of virtual channels in wormhole-routed mesh networks. The faults under consideration are rectangular block faults, which are suitable for modeling faults on board level in networks with grid structures. There is no restriction on the number of faults. The concepts of f-ring and f-chain are used in our scheme. Messages are routed minimally when not blocked by faults and are routed along the boundaries of the faults encountered. Only three virtual channels and local knowledge of faults are required for our routing scheme to be correct, deadlock- and livelock-free. By allocating virtual channels to messages carefully, all virtual channels have the potential to be used by messages; hence, none of the virtual channels and its associated hardware is wasted.
Other Subjects
Algorithms; Communication channels (information theory); Computer networks; Computer system recovery; Fault tolerant computer systems; Parallel processing systems; Theorem proving; Deadlock free; Mesh networks; Virtual channel; Wormhole routing; Data communication systems
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
21.pdf
Size
145.21 KB
Format
Adobe PDF
Checksum
(MD5):d3e3faadf2c4e1c85ab8efd2fefb2495