A fault-tolerant routing algorithm for wormhole routed meshes

✍ Scribed by Pao-Hwa Sui; Sheng-De Wang

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 145 KB
• Volume: 26
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00113-1

✦ Synopsis

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 livelockfree. 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.