Message routing in HARTS with faulty components
- 7 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors develop a routing scheme in two steps for a wrapped hexagonal mesh, called HARTS (hexagonal architecture for real-time systems), which ensures the delivery of every message as long as there is a path between its source and destination. The scheme can also detect the nonexistence of a path between a pair of nodes in a finite amount of time. Moreover, the scheme requires each node in HARTS to know only the state (faulty or not) of each of its own links. The performance of the simple routing scheme is simulated for three- and five-dimensional H-meshes while the physical distribution of faulty components is varied. It is shown that a shortest path between the source and the destination of each message is taken with a high probability, and a path, if one exists, is usually found very quickly.Keywords
This publication has 8 references indexed in Scilit:
- A microprogrammable VLSI routing controller for HARTSPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Hyperswitch network for the hypercube computerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Addressing, routing, and broadcasting in hexagonal mesh multiprocessorsIEEE Transactions on Computers, 1990
- Routing and broadcasting in faulty hypercube computersPublished by Association for Computing Machinery (ACM) ,1988
- Message routing in an injured hypercubePublished by Association for Computing Machinery (ACM) ,1988
- Adaptive packet routing in a hypercubePublished by Association for Computing Machinery (ACM) ,1988
- Distributed fault-tolerance for large multiprocessor systemsPublished by Association for Computing Machinery (ACM) ,1980
- Algorithm 97: Shortest pathCommunications of the ACM, 1962