The interaction between virtual channel flow control and adaptive routing in wormhole networks

ABSTRACT

Multiprocessor interconnection networks based on low dimensional mesh or torus topologies and employing wormhole switching have become increasingly popular. Two concepts that have been proposed to improve the performance of such networks are Virtual Channel Flow Control (VCFC) and adaptive routing. Some previous studies have, however, found the latter technique to yield disappointing performance under uniform traffic patterns, while in this work we show that the former technique may result in degraded performance under certain non-uniform traffic patterns. This paper studies the interaction between VCFC and adaptive routing. It is shown that each of these techniques may yield unsatisfactory performance only when used in isolation, and that through their appropriate combination uniformly improved performance can be achieved. The consistent performance improvement and the magnitude of the performance improvement in some cases offers compelling motivation for implementing a combination of VCFC and adaptive routing in future machines.

REFERENCES

• 1: A. Agarwal, Limits on Interconnection Network Performance, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.398-412, October 1991 [doi>10.1109/71.97897]
• 2: H. G. Badr , S. Podar, An Optimal Shortest-Path Routing Policy for Network Computers with Regular Mesh-Connected Topologies, IEEE Transactions on Computers, v.38 n.10, p.1362-1371, October 1989 [doi>10.1109/12.35831]
• 3: Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140902]
• 4: Rajendra V. Boppana , Suresh Chalasani, A comparison of adaptive wormhole routing algorithms, Proceedings of the 20th annual international symposium on Computer architecture, p.351-360, May 16-19, 1993, San Diego, California, United States
• 5: Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, Proceedings of the 19th annual international symposium on Computer architecture, p.268-277, May 19-21, 1992, Queensland, Australia
• 6: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 7: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 8: José Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1320-1331, December 1993 [doi>10.1109/71.250114]
• 9: W. J. Dally , H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.466-475, April 1993 [doi>10.1109/71.219761]
• 10: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Proceedings of the 19th annual international symposium on Computer architecture, p.278-287, May 19-21, 1992, Queensland, Australia
• 11: C.J. Glass and L.M. Ni, "Adaptive Routing in Mesh- Connected Networks", Technical Report MSU-CPS- ACS-45, M~higan State University, Oct. 1991.
• 12: C. R. Jesshope , P. R. Miller , J. T. Yantchev, High performance communications in processor networks, Proceedings of the 16th annual international symposium on Computer architecture, p.150-157, April 1989, Jerusalem, Israel
• 13: Daniel H. Linder , Jim C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, IEEE Transactions on Computers, v.40 n.1, p.2-12, January 1991 [doi>10.1109/12.67315]
• 14: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 15: G.F. Pfister and V.A. Norton, "Hot Spot Contention and Combining in Mult~tage Interconnection Networks", IEEE Transactions on Computers, Vol. 34, No. 10, Oct. 1985, pp. 943-948.
• 16: L. Schwiebert , D. N. Jayasimha, Optimal fully adaptive wormhole routing for meshes, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.782-791, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169835]
• 17: C. Su and K.G. Shin, "Adap~ve Deadlock-Free Routing in Multicomputers U~ng Only One Extra Virtual Channel", Proceedings of the 1993 International Conference on Parallel Processin~ Aug. 1993, Vol. I, pp. 227-231.
• 18: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Design, Experimentation, Measurement, Performance, Theory