Improving parallel system performance by changing the arrangement of the network links

ABSTRACT

The Midimew network is an excellent contender for implementing the communication subsystem of a high performance computer. This network is an optimal 2D topology in the sense there are no other symmetric direct networks of degree 4 with a lower average distance or diameter. In fact, it reduces the diameter of the well known torus network by approximately □2. Although the topology was proposed and analyzed a decade ago, the lack of simple deadlock avoidance mechanisms prevented its utilization up to date. This study solved this drawback by applying the Bubble switching mechanism, a low cost deadlock-avoidance strategy developed by the authors. Moreover, by using routing tables we can configure our Virtual Cut-Through adaptive router to implement either a torus or a Midimew network. Thus, we can exploit the topological advantages of Midimew networks by simply changing the disposition of the wrap-around connections of its torus counterpart, without increasing the network implementation cost. To prove this assertion, we have carried out a thorough evaluation, from the hardware cost of the router to the parallel system performance under real loads.

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: Ramón Beivide , Enrique Herrada , José L. Balcázar , Agustin Arruabarrena, Optimal Distance Networks of Low Degree for Parallel Computers, IEEE Transactions on Computers, v.40 n.10, p.1109-1124, October 1991 [doi>10.1109/12.93744 ]
• 3: A. Chien, "A cost and Speed Model for k-ary n-cube wormhole router", In Proc. of Hot Interconnects, August 1993.
• 4: 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]
• 5: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599 ]
• 6: M.Galles, "Scalable Pipelined Interconnect for Distributed Endpoint Routing: The SGI Spider Chip", Proc. of Hot Interconnects IV, August 1996.
• 7: J.R. Jump. "NETSIM Reference Manual". Rice University Electrical and Computer Engineering Department, March 1993.
• 8: Francis C. M. Lau , Guihai Chen, Optimal Layouts of Midimew Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.9, p.954-961, September 1996 [doi>10.1109/71.536939 ]
• 9: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 10: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510 ]
• 11: A. Nowatzyk, G. Aybay, M. Browne, E. Kelly, M. Parkin, B. Radke, and S. Vishin "The S3.mp Scalable Shared Memory Multiprocessor", Int Conf on Parallel Processing, August 1995.
• 12: Vijay S. Pai , Parthasarathy Ranganathan , Sarita V. Adve, RSIM: Rice simulator for ILP multiprocessors, ACM SIGARCH Computer Architecture News, v.25 n.5, p.1, Dec. 1997 [doi>10.1145/271014.271015]
• 13: V. S. Pai, "RSIM Reference Manual. Version 1.0". Department of Electrical and Computer Engineering, Rice University. Technical Report 9705. July 1997.
• 14: J.M. Prellezo, V. Puente, J.A. Gregorio, R. Beivide, "SICOSYS: an into(connection network simulator for parallel computers," available at http:llwww.atc.unican.esl REPORTS/TR-ATC2-UC98.1xlf, June 1998.
• 15: V. Puente , R. Beivide , J. A. Gregorio , J. M. Prellezo , J. Duato , C. Izu, Adaptive Bubble Router: A Design to Improve Performance in Torus Networks, Proceedings of the 1999 International Conference on Parallel Processing, p.58, September 21-24, 1999
• 16: S.Scott and G. Thorson, "The Cray T3E Network: Adaptive Routing in a High Performance 3D Toms", Hot Interconnects IV, August 1996.
• 17: C.L.Seitz, "Concurrent VLSI architectures", IEEE Trans. on Comp., C-33, pp. 1247-1265, December 1984.
• 18: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional 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)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.6 Internetworking
          Subjects: Routers

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Measurement, Performance, Theory