This paper provides necessary and sufficient conditions for deadlock-free unicast and multicast routing with the path-based routing model in interconnection networks which use the wormhole switching technique. The theory is developed around three central concepts: channel waiting, False Resource Cycles, and valid destination sets. The first two concepts are suitable extensions to those developed for unicast routing by two authors of this paper; the third concept has been developed by Lin and Ni. The necessary and sufficient conditions can be applied in a straightforward manner to prove deadlock freedom and to find more adaptive routing algorithms for collective communication. The latter point is illustrated by developing two routing algorithms for multicast communication in 2-D mesh architectures. The first algorithm uses fewer resources (channels) than an algorithm proposed in the literature but achieves the same adaptivity. The second achieves full adaptivity for multicast routing.
|Number of pages||8|
|Journal||IEEE Symposium on Parallel and Distributed Processing - Proceedings|
|State||Published - 1996|
|Event||Proceedings of the 1996 8th IEEE Symposium on Parallel and Distributed Processing - New Orleans, LA, USA|
Duration: Oct 23 1996 → Oct 26 1996
ASJC Scopus subject areas
- Engineering (all)