Path Selection for Message Passing in a Circuit-Switched Multicomputer
✍ Scribed by Sunggu Lee; Jong Kim
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 297 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
may be performed at an intermediate node as soon as the header of the message arrives with the destination information. Thus, with cut-through, only an on-line flit buffer is required to examine the message header at each intermediate node. If cut-throughs are established through all intermediate nodes, a circuit is established to the destination, and the switching method resembles traditional circuit switching.
If the message header is blocked at an intermediate node because the requested outgoing channel is unavailable, the message is buffered in the on-line flit buffers at each node along the path up to the current node, thus resulting in communication delays. An experimental communication study on an iPSC/860 by Bokhari [1] showed that when two packets have to share a common channel, the communication delay of the blocked packet doubles. In addition, because of this blocking possibility, it is impossible to tell how long a given message will take, given that the exact communication patterns are not known in advance.
This paper investigates the idea of completely eliminating (or minimizing) blocking for communicating nodes by preselecting a set of paths such that contention for the use of common channels is eliminated (or minimized). This concept is useful not only for multicomputer wormhole routing, but for minimum-delay communication using circuit switching or packet switching. This problem has been dealt with previously as ''traffic routing '' in [4] and ''path assignment'' in [9]. However, we use a more direct formalization of this problem that results in a better heuristic solution, as demonstrated by our simulation results in Section 4.
The efficient solution of this problem is particularly important for periodic real-time applications. Hard real-time applications, such as automobile or factory control, in which deadline misses can lead to catastrophic consequences, are typically programmed to operate periodically, as execution times must be completely predictable. Predictable (and minimum-delay) communication time is possible if all inter-task communication occurs with no blocking at intermediate nodes. This requirement can be met by finding a set of contention-free paths for all communicating nodes, i.e., a set of paths such that none of the paths have any edges in common.
This paper addresses the problem of finding a set of