More Web Proxy on the site http://driver.im/

Article

Free access

NIFDY: a low overhead, high throughput network interface

Authors:

Timothy Callahan,

Seth Copen GoldsteinAuthors Info & Claims

ISCA '95: Proceedings of the 22nd annual international symposium on Computer architecture

Pages 230 - 241

https://doi.org/10.1145/223982.224434

Published: 01 May 1995 Publication History

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

[1]

A. Agarwal. Limits on interconnection network performance. IEEE Transactions on Parallel and Distributed Systems, vol.2(no.4):398-412, Oct. 1991.

Digital Library

[2]

E.A. Brewer and B.C. Kuszmaul. Howto get good performance from the CM-5 data network. In Proceedings Eighth btternational Parallel Processing Symposium, pages 858-67. IEEE Comput. Soc. Press, 1994.

Digital Library

[3]

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.

[4]

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.

[5]

David E. Culler, Andrea Dusseau, Seth Copen Goldstein, Arvind Krishnamurthy, Steven Lumetta, Thorsten yon Eicken, and Katherine Yelick. Parallel programming in Split-C. In Proc. Supercomputing 93, Portland, Oregon, November 1993.

Digital Library

[6]

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.

[7]

W.J. Dally. Virtual-channel flow control. In Proceedings. The 17th Annual International Symposium on Computer Architecture, pages 60-8. IEEE Comput. Soc. Press, 1990.

Digital Library

[8]

W.J. Dally. Express cubes: improving the performance ofk-ary n-cube interconnection networks. IEEE Transactions on Computers, vol.40(no.9): 1016-23, Sept. 1991.

Digital Library

[9]

A. DeHon, F. Chong, M. Becker, E. Egozy, H. Minsky, S. Peretz, and Jr. Knight, T.E Metro: a router architecture for high-performance, short-}haul routing networks. In Proceedings the 21st Annual international Symposium on Computer Architecture, pages 266-77. IEEE Comput. Soc. Press, 1994.

Digital Library

[10]

Andrea Carol Dusseau. Modeling parallel sorts with LogP on the CM-5. Technical Report UCB//CSD-94- 829, University of California at Berkeley, May 1994.

Digital Library

[11]

V. Jacobson. Congestion avoidance and control. In Computer Communication Review, pages 314-29, Aug. 1988.

Digital Library

[12]

R. Jain. Congestion control in computer networks: issues and trends. IEEE Network, vol.4(no.3):24-30, May 1990.

Digital Library

[13]

Vijay Karamcheti and Andrew A. Chien. Software overhead in messaging layers: Where does the time go? In Proc. of 6th Int. Conf. on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, October 1994.

Digital Library

[14]

J.H. Kim, Ziqiang Liu, and A.A. Chien. Compressionless routing: a framework for adaptive and faulttolerant routing. In Proceedings the 21st Annual International Symposium on Computer Architecture, pages 289-300. IEEE Comput. Soc. Press, 1994.

Digital Library

[15]

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.

[16]

S. Konstantinidou and L. Snyder. Chaos router: architecture and performance. In Computer Architecture News, pages 212-21, May 1991.

Digital Library

[17]

C.E. Leiserson, Z.S. Abuhamdeh, D.C. Douglas, C.R. Feynmann, M.N. Ganmukhi, J.V. Hill, W.D. Hillis, B.C. Kuszmaul, M.A. St. Pierre, D.S. Wells, M.C. Wong, Shaw-Wen Yang, and R. Zak. The network architecture of the connection machine CM-5. In SPAA 92. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 272-85. ACM, 1992.

Digital Library

[18]

Richard Martin. Personal Communication.

[19]

K.K. Ramakrishnan and R. Jain. A binary feedback scheme for congestion avoidance in computer networks. A CM Transactions on Computer Systems, vol.8(no.2): 158-81, May 1990.

Digital Library

[20]

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.

Digital Library

[21]

S.L. Scott and G.S. Sohi. Using feedback to control tree saturation in multistage interconlaection networks. In 16th Annual International Symposium on Computer Architecture, pages 167-76. IEEE Co mput. Soc. Press, 1989.

Digital Library

[22]

Thorsten von Eicken. Active Messages: an Efficient Communication Architecture for Multiprocessors. PhD thesis, University of California at Berkeley, December 1993.

Digital Library

Cited By

Akella ABenson TChandrasekaran BHuang CMaggs BMaltz DDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)A Universal Approach to Data Center Network DesignProceedings of the 16th International Conference on Distributed Computing and Networking10.1145/2684464.2684505(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684505
Daneshtalab MEbrahimi MLiljeberg PPlosila JTenhunen H(2013)A systematic reordering mechanism for on-chip networks using efficient congestion-aware methodJournal of Systems Architecture10.1016/j.sysarc.2012.01.00259:4-5(213-222)Online publication date: Apr-2013
https://doi.org/10.1016/j.sysarc.2012.01.002
Fattah MDaneshtalab MLiljeberg PPlosila J(2012)Transport layer aware design of network interface in many-core systems7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC)10.1109/ReCoSoC.2012.6322895(1-7)Online publication date: Jul-2012
https://doi.org/10.1109/ReCoSoC.2012.6322895
Show More Cited By

Index Terms

NIFDY: a low overhead, high throughput network interface

Recommendations

NIFDY: a low overhead, high throughput network interface
Special Issue: Proceedings of the 22nd annual international symposium on Computer architecture (ISCA '95)

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 ...
SQUID: a practical 100% throughput scheduler for crosspoint buffered switches

Crosspoint buffered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms and achieve better performance than bufferless crossbar switches. Crosspoint buffered switches have a buffer at each ...
Excess buffer requirement for EPD schemes in ATM networks

It is known that the performance of TCP over ATM can be significantly degraded if the bandwidth is occupied by cells belonging to packets that are already corrupted by cell loss due to buffer overflow. The Early Packet Discard (EPD) mechanism is a well ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '95: Proceedings of the 22nd annual international symposium on Computer architecture

July 1995

426 pages

ISBN:0897916980

DOI:10.1145/223982

Chairman:
David A. Patterson
Univ. of California, Berkeley

ACM SIGARCH Computer Architecture News Volume 23, Issue 2
Special Issue: Proceedings of the 22nd annual international symposium on Computer architecture (ISCA '95)
May 1995
412 pages
ISSN:0163-5964
DOI:10.1145/225830
Chairman:
David A. Patterson
Univ. of California, Berkeley
Issue’s Table of Contents

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS\TCCA: TC on Computer Arhitecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISCA95

Sponsor:

SIGARCH
IEEE-CS\TCCA

ISCA95: International Conference on Computer Architecture

June 22 - 24, 1995

S. Margherita Ligure, Italy

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
399
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)12

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Akella ABenson TChandrasekaran BHuang CMaggs BMaltz DDas SKrishnaswamy DKarkar SKorman AKumar MPortmann MSastry S(2015)A Universal Approach to Data Center Network DesignProceedings of the 16th International Conference on Distributed Computing and Networking10.1145/2684464.2684505(1-10)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1145/2684464.2684505
Daneshtalab MEbrahimi MLiljeberg PPlosila JTenhunen H(2013)A systematic reordering mechanism for on-chip networks using efficient congestion-aware methodJournal of Systems Architecture10.1016/j.sysarc.2012.01.00259:4-5(213-222)Online publication date: Apr-2013
https://doi.org/10.1016/j.sysarc.2012.01.002
Fattah MDaneshtalab MLiljeberg PPlosila J(2012)Transport layer aware design of network interface in many-core systems7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC)10.1109/ReCoSoC.2012.6322895(1-7)Online publication date: Jul-2012
https://doi.org/10.1109/ReCoSoC.2012.6322895
(2005)An efficient on-chip NI offering guaranteed services, shared-memory abstraction, and flexible network configurationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.83949324:1(4-17)Online publication date: Jan-2005
https://doi.org/10.1109/TCAD.2004.839493
Izu CMiguel-Alonso JGregorio J(2005)Evaluation of interconnection network performance under heavy non-uniform loadsProceedings of the 6th international conference on Algorithms and Architectures for Parallel Processing10.1007/11564621_46(396-405)Online publication date: 2-Oct-2005
https://dl.acm.org/doi/10.1007/11564621_46
R"dulescu ADielissen JGoossens KRijpkema EWielage P(2004)An Efficient On-Chip Network Interface Offering Guaranteed Services, Shared-Memory Abstraction, and Flexible Network ConfigurationProceedings of the conference on Design, automation and test in Europe - Volume 210.5555/968879.969205Online publication date: 16-Feb-2004
https://dl.acm.org/doi/10.5555/968879.969205
Radulescu ADielissen JGoossens KRijpkema EWielage P(2004)An efficient on-chip network interface offering guaranteed services, shared-memory abstraction, and flexible network configurationProceedings Design, Automation and Test in Europe Conference and Exhibition10.1109/DATE.2004.1268998(878-883)Online publication date: 2004
https://doi.org/10.1109/DATE.2004.1268998
Brown JGrossman JKnight TRosenberg AMaggs B(2002)A lightweight idempotent messaging protocol for faulty networksProceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures10.1145/564870.564912(248-257)Online publication date: 10-Aug-2002
https://dl.acm.org/doi/10.1145/564870.564912
Baydal ELopéz PDuato J(2002)Congestion Control Based on Transmission TimesEuro-Par 2002 Parallel Processing10.1007/3-540-45706-2_109(781-790)Online publication date: 20-Aug-2002
https://doi.org/10.1007/3-540-45706-2_109
Baydal ELopez PDuato J(2001)A congestion control mechanism for wormhole networksProceedings Ninth Euromicro Workshop on Parallel and Distributed Processing10.1109/EMPDP.2001.904965(19-26)Online publication date: 2001
https://doi.org/10.1109/EMPDP.2001.904965
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents