Performance evaluation of a new routing strategy for irregular networks with source routing

ABSTRACT

Networks of workstations (NOWs) are becoming increasingly popular as a cost-effective alternative to parallel computers. Typically, these networks connect processors using irregular topologies, providing the wiring flexibility, scalability, and incremental expansion capability required in this environment. In some of these networks, messages are delivered using the up*/down* routing algorithm [9]. However, the up*/down* routing scheme is often non-minimal. Also, some of these networks use source routing [1]. With this technique, the entire path to destination is generated at the source host before the message is sent.In this paper we develop a new mechanism in order to improve the performance of irregular networks with source routing, increasing overall throughput. With this mechanism, messages always use minimal paths. To avoid possible deadlocks, when necessary, routes between a pair of hosts are divided into sub-routes, and a special kind of virtual cut-through is performed at some intermediate hosts. We evaluate the new mechanism by simulation using parameters taken from the Myrinet network. We show that the current routing schemes used in Myrinet can be improved by modifying only the routing software without increasing its overhead significantly and, most importantly, without modifying the network hardware. The benefits of using the new routing scheme are noticeable for networks with 16 or more switches, and increase with network size. For 32 and 64-switch networks, throughput is increased on average by a factor ranging from 1.3 to 3.3.

REFERENCES

• 1: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 2: 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
• 3: 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]
• 4: Improving Routing Performance in Myrinet Networks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.27, May 01-05, 2000
• 5: GM protocol, 'http://www.myri.com/GM'
• 6: J. Kim and A. Chien, "An evaluation of the planar/adaptive routing," in Proc. Jth IEEE Int. Syrup. Parallel Distributeed ProcesSing, 1992
• 7: P. R. Miller, "Efficient communications for fine-grain distributed computers," Ph.D. Thesis, Southampton University, 1991.
• 8: Myrinet, 'M2-CB-35 LAN cables, http://www.myri.com/myrinet/product _list .html'
• 9: M. D. Schroeder et al., "Autonst: A high-speed, self-configuring local area network using point-to-point links," Technical Report SRC research report 59, DEC, April 1990.
• 10: S. L. Scott , J. R. Goodman, The Impact of Pipelined Channels on k-ary n-Cube Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.2-16, January 1994 [doi>10.1109/71.262584]
• 11: R. Sheifert, "Gigabit Ethernet," in Addison-Wesley, ISBN: 0-201-18553-9, April 1998.
• 12: F. Silla , J. Duato, Improving the Efficiency of Adaptive Routing in Networks with Irregular Topology, Proceedings of the Fourth International Conference on High-Performance Computing, p.330, December 18-21, 1997
• 13: Federico Silla , Manuel P. Malumbres , Antonio Robles , Pedro López , José Duato, Efficient Adaptive Routing in Networks of Workstations with Irregular Topology, Proceedings of the First International Workshop on Communication and Architectural Support for Network-Based Parallel Computing, p.46-60, February 01-02, 1997

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Workstations

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

Keywords:
irregular topologies, minimal routing, networks of workstations, source routing, wormhole switching