Abstract
An efficient fully adaptive wormhole routing algorithm for n-dimensional meshes is developed in this paper. The routing algorithm provides full adaptivity at a cost of one additional virtual channel per physical channel irrespective of the number of dimensions of the network. The algorithm is based on dividing the network graph into two acyclic graphs that contain all of the physical channels in the system. Virtual channels are classified as either waiting or nonwaiting channels. Busy channels that a message waits for to become available are classified as waiting channels, otherwise they are classified as nonwaiting channels. Thus, a message considers nonwaiting channels first to reach its destination. If all nonwaiting channels are busy, the message considers waiting channels. Messages acquire waiting channels in two phases. In each phase, waiting channels belonging to one acyclic network graph are traversed. This 2-phase routing algorithm could be either minimal or nonminimal. However, in this paper we concentrate on minimal routing. It is demonstrated that this adaptive routing algorithm can utilize the virtual paths (channels) between any two nodes more efficiently than any of the present algorithms with the same hardware requirement.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings - International Conference on Distributed Computing Systems |
| Publisher | IEEE |
| Pages | 589-596 |
| Number of pages | 8 |
| State | Published - 1994 |
| Event | Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems - Poznan, Pol Duration: Jun 21 1994 → Jun 24 1994 |
Other
| Other | Proceedings of the 1994 IEEE 14th International Conference on Distributed Computing Systems |
|---|---|
| City | Poznan, Pol |
| Period | 6/21/94 → 6/24/94 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture