NIFDY: a low overhead, high throughput network interface

ABSTRACT

In this paper we present NIFDY, a network interface that uses admission control to reduce congestion and ensures that packets are received by a processor in the order in which they were sent, even if the underlying network delivers the packets out of order. The basic idea behind NIFDY is that each processor is allowed to have at most one outstanding packet to any other processor unless the destination processor has granted the sender the right to send multiple unacknowledged packets. Further, there is a low upper limit on the number of outstanding packets to all processors.We present results from simulations of a variety of networks (meshes, tori, butterflies, and fat trees) and traffic patterns to verify NIFDY's efficacy. Our simulations show that NIFDY increases throughput and decreases overhead. The utility of NIFDY increases as a network's bisection bandwidth decreases. When combined with the increased payload allowed by in-order delivery NIFDY increases total bandwidth delivered for all networks. The resources needed to implement NIFDY are small and constant with respect to network size.

REFERENCES

• Aga91: 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]
• BK94: Eric A. Brewer , Bradley C. Kuszmaul, How to Get Good Performance from the CM-5 Data Network, Proceedings of the 8th International Symposium on Parallel Processing, p.858-867, April 01, 1994
• BT89: R.G. Bubenik and J.S. Turner. Performance of a broadcast packet switch. IEEE Transactions on Communications, vol.37(no.l):60-9, Jan. 1989.
• CBLK94: ET. Chong, E.A. Brewer, ET. Leighton, and T.E Knight, Jr. Building a better butterfly: The Multiplexed Multibutterfly. In Proc. International Symposium on Parallel Architectures, Algorithms, and Networks, Kanazawa, Japan, December 1994.
• CDG+93: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• Cul94: David E. Culler. Multithreading: Fundamental limits, potential gains, and alternatives. In R.A. Iannuci, G.R. Gao, Jr. Halstead, R.H., and B. Smxth, editors, Multithreaded Computer Architecture, chapter 6, pages 97- 138. Kluwer Academic Publishers, 1994.
• Dal90: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• Dal91: William J. Dally, Express Cubes: Improving the Performance of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.40 n.9, p.1016-1023, September 1991 [doi>10.1109/12.83652]
• DCB+94: A. DeHon , F. Chong , M. Becker , E. Egozy , H. Minsky , S. Peretz , T. F. Knight, Jr., METRO: a router architecture for high-performance, short-haul routing networks, Proceedings of the 21ST annual international symposium on Computer architecture, p.266-277, April 18-21, 1994, Chicago, Illinois, United States
• Dus94: Andrea C. Dusseau, Modeling Parallel Sorts with LogP on the CM-5, University of California at Berkeley, Berkeley, CA, 1994
• Jac88: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• Jai90: R. Jain. Congestion control in computer networks: issues and trends. IEEE Network, vol.4(no.3):24-30, May 1990.
• KC94: Vijay Karamcheti , Andrew A. Chien, Software overhead in messaging layers: where does the time go?, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.51-60, October 05-07, 1994, San Jose, California, United States
• KLC94: J. H. Kim , Z. Liu , A. A. Chien, Compressionless routing: a framework for adaptive and fault-tolerant routing, Proceedings of the 21ST annual international symposium on Computer architecture, p.289-300, April 18-21, 1994, Chicago, Illinois, United States
• KMCL93: H.T. Kung, Robert Morris, Thomas Chaaruhas, and Dong Lin. Use of link-by-link flow control in maximizing atm networks performance: Simulation results. In Proceedings IEEE Hot Interconnects Symposium '93, August 1993.
• KS91: S. Konstantinidou , L. Snyder, Chaos router: architecture and performance, ACM SIGARCH Computer Architecture News, v.19 n.3, p.212-221, May 1991
• LAD+92: Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
• Mar: Richard Martin. Personal Communication.
• RJ90: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• SBB+91: M.D. Schroeder, A.D. Birrell, M. Burrows, H. Murray, R.M. Needham, T.L. Rodeheffer, E.H. Satterthwaite, and C.P. Thacker. Autonet: a high-speed, selfconfiguring local area network using point-to-point links. IEEE Journal on Selected Areas in Communications, vol.9(no.8):1318-35, Oct. 1991.
• 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
• vE93: Thorsten Helmut Von Eicken , David E. Culler , John Wawrzynek, Active messages: an efficient communication architecture for multiprocessors, 1993

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

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: Packet-switching networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Design, Performance