Increasing network bandwidth on meshes

ABSTRACT

In bandwidth limited computers, such as meshes and tori, it is important to achieve high bandwidth across the bisection. Traditional techniques achieve bandwidth in the range of 30–70%. We show how to use barriers, in particular Integrated Network Barriers to achieve high bandwidth utilization which is arbitrarily close to 100%. This technique also provides low latency and fairness to processors. Moreover, it works globally and therefore is not dependent on local approximations of network traffic.

REFERENCES

• ACC+90: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• Ahu90: M. Ahuja, Flush primitives for asynchronous distributed systems, Information Processing Letters, v.34 n.1, p.5-12, February 1990 [doi>10.1016/0020-0190(90)90222-J]
• BC93: 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
• BGSS90: Yitzhak Birk, Phillip B. Gibbons, Jorge L. C. Sanz, and Danny Soroker. A simple mechanism for efficient barrier synchronization in MIMD machines. In Proceedings of the 1990 International Conference on Parallel Processing, 1990.
• BP93: Gianfranco Bilardi , Franco P. Preparata, Horizons of Parallel Computation, Brown University, Providence, RI, 1993
• Cor91: intel Corporation. A touchstone delta system description. Technical report, Intel, 1991.
• GL92: 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
• Hil85: W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
• KK79: P. Kermani and Leonard Kleinrock. Virtual cut-through: A new computer communication switching technique. Computer Networks, 3, 1979.
• KP86: Manoj Kumar and Gregory F. Pfister. The onset of hot spot contention, in International Conference on Parallel Processing, pages 28-34, August 1986.
• LR79: S.S. Lain and M. Reiser. Congestion control of store-and-forward networks by input buffer limits- an analysis. IEEE Trans. on Communications, 27(1), January 1979.
• NWD93: Michael D. Noakes , Deborah A. Wallach , William J. Dally, The J-machine multicomputer: an architectural evaluation, Proceedings of the 20th annual international symposium on Computer architecture, p.224-235, May 16-19, 1993, San Diego, California, United States
• Ran87: Abhiram G. Ranade. How to emulate shared memory. In Proceedings on FOCS, pages 185- 194, 1987.
• SAF+88: C. L. Seitz , W. C. Athas , C. M. Flaig , A. J. Martin , J. Seizovic , C. S. Steele , W-K. Su, The architecture and programming of the Ametek series 2010 multicomputer, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.33-37, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62302]
• Smi81: Burton J. Smith. Architecture and applications of the HEP multiprocessor computer system. Real Time Signal Processing IV, Proceedings of SPIE, 298:241-248, 1981.
• SS89: S. L. Scott , G. S. Sohi, Using feedback to control tree saturation in multistage interconnection networks, Proceedings of the 16th annual international symposium on Computer architecture, p.167-176, April 1989, Jerusalem, Israel
• SS93: Jon A. Solworth , Jerry Stamatopoulos, Integrated Network Barriers for D-Dimensional Meshes, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.179-190, January 20-22, 1993

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Measurement, Performance, Theory