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

Article

Free access

A router architecture for real-time point-to-point networks

Authors:

Jennifer Rexford,

Kang G. ShinAuthors Info & Claims

ISCA '96: Proceedings of the 23rd annual international symposium on Computer architecture

Pages 237 - 246

https://doi.org/10.1145/232973.232998

Published: 01 May 1996 Publication History

Abstract

Parallel machines have the potential to satisfy the large computational demands of emerging real-time applications. These applications require a predictable communication network, where time-constrained traffic requires bounds on latency or throughput while good average performance suffices for best-effort packets. This paper presents a router architecture that tailors low-level routing, switching, arbitration and flow-control policies to the conflicting demands of each traffic class. The router implements deadline-based scheduling, with packet switching and table-driven multicast routing, to bound end-to-end delay for time-constrained traffic, while allowing best-effort traffic to capitalize on the low-latency routing and switching schemes common in modern parallel machines. To limit the cost of servicing time-constrained traffic, the router shares packet buffers and link-scheduling logic between the multiple output ports. Verilog simulations demonstrate that the design meets the performance goals of both traffic classes in a single-chip solution.

References

[1]

L. R. Welch and K. Toda, "Architectural support for real-time systems: Issues and trade-offs," in Proc. International Workshop on Real-Time Computing Systems and Applications, December 1994.

[2]

M. W. Mutka, "Using rate monotonic scheduling technology for real-time communications in a wormhole network,ss in 1-'roc. Workshop on 1-'arallel and Dsstmbuted Real- Time Systems, April 1994.

[3]

J.-P. Li and M. W. Mutka, "Priority based real-time communication for large scale wormhole networks," in Proc. International Parallel Processing Symposium, pp. 433-438, April 1994.

Digital Library

[4]

A. Saha, "Simulator for real-time pax~llel processing architectures," in Proc. IEBE Annual Simulation Symposium, pp. 74-83, April 1995.

Digital Library

[5]

K. Toda, K. Nishida, E. Takahashi, N. Michell, and Y. Yamaguchi, "Design and implementation of a priority forwarding router chip for real-time interconnection networks," International Journal of Mini and Microcomputers, vol. 17, no. 1, pp. 42-51, 1995.

[6]

R. Games, A. Kanevsky, P. Krupp, and L. Monk, "Realtime communications scheduling for massively parallel processors," in Proc. Real. Time Technology and Applications Symposium, pp. 76-85, May 1995.

Digital Library

[7]

R. S. Raji, "Smart networks for control," IEEE Spectrum, vol. 31, pp. 49-55, June 1994.

Digital Library

[8]

C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne, "Real-time communication in packetswitched networks," Proceedings of the IEEE, vol. 82, pp. 122-139, January 1994.

[9]

D. D. Kaaadlur, K. G. Shin, and D. Ferrari, "Real-time communication in multi-hop networks," !EEE Trans. on Parallel and Distributed Systems, vol. 5, pp. 1044- 1056, October 1994.

Digital Library

[10]

H. Zhang, "Providing end-to-end performance guarantees using non-work-conserving disciplines," Computer Communications, vol. 18, pp. 769-781, October 1995.

Digital Library

[11]

Y. Ofek and M. Yung, "The integrated MetaNet architecture: A switch-based multimedia LAN for parallel computing and real-time traffic," in Proc. 1EEE 1NFO- COM, pp. 802-811, 1994.

[12]

W. J. Dally and C. L. Seitz, "The torus routing chip," Journal of Distributed Computing, vol. 1, no. 3, pp. 187- 196, 1986.

[13]

R. L. Cruz, "A calculus for network delay, part I: Network elements in isolation," IEEE Trans. Information Theory, vol. 37, pp. 114-131, January 1991.

[14]

Q. Zheng and K. G. Shin, "On the ability of establishing real-time channels in point-to-point packet-switched networks," IEEE Trans. Communications, pp. 1096- 1105, February/March/April 1994.

[15]

C. L. Liu ~nd J. W. L~yl~nd, "Scheduling algorithm~ for multiprogramming in a hard real-time environment," Journal of the A CM, vol. 20, pp. 46-61, January 1973.

Digital Library

[16]

J. Rexford and K. G. Shin, "Support for multiple classes of traffic in multicomputer routers," in Proc. Parallel Computer Routing and Communication Workshop, pp. 116-130, May 1994.

Digital Library

[17]

W. Dally, "Virtual-channel flow control," IEEE Trans. Parallel and Distributed Systems, vol. 3, pp. 194-205, March 1992.

Digital Library

[18]

W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Trans. Computers, vol. C-36, no. 5, pp. 547-553, May 1987.

Digital Library

[19]

L. Ni and P. McKinley, "A survey of wormhole routing techniques in direct networks," IEEE Computer, pp. 62-76, February 1993.

Digital Library

[20]

K. Aoyama and A. Chien, "Cost of adaptivity and virtual lanes in a wormhole router," Journal of VLSI Design, vol. 2, no. 4, pp. 315-333, 1995.

[21]

F. A. Tobagi, "Fast packet switch architectures for broadband integrated services digital networks," Proceedings of the IEEE, vol. 78, pp. 133-167, January 1990.

[22]

Q. Zheng, K. G. Shin, and C. Chen, "Real-time communication in ATM," in Proc. Annual Conference on Local Computer Networks, pp. 156-164, October 1994.

[23]

D. Picker and It. D. Fellman, "Scaling and performance of a priority packet queue for real-time applications," in Proc. Real-Time Systems Symposium, pp. 56-62, December 1994.

[24]

H. J. Chao, "A novel architecture for queue management in the ATM network," IEEE Journal on Selected Areas in Communications, vol. 9, pp. 1110-1118, September 1991.

Digital Library

[25]

P. E. Boyer, F. M. Guillemin, M. J. Servel, and J.-P. Coudreuse, "Spacing cells protects and enhances utilization of ATM network links," IEEE Network Magazine, pp. 38-49, September 1992.

Digital Library

[26]

E. Wallmeier and T. Worster, "The Spacing Policer, an algorithm for efficient peak bit rate control in ATM networks," in Proc. International Switching Symposium, pp. 22-26, October 1992.

[27]

J. Liebeherr and D. Wrege, "Versatile packet multiplexer for quality-of-service networks," in Proc. IEEE International Symposium on High Performance Distributed Computing, pp. 148-155, August 1995.

Digital Library

[28]

J. Rexford, A. Greenberg, and F. Bonomi, "Haxdwareefficient fair queueing architectures for high-speed networks," in Proc. IEEE INFOCOM, March 1996.

Digital Library

[29]

P. Kermani and L. Kleinrock, "Virtual cut-through: A new computer communication switching technique," Computer Networks, vol. 3, pp. 267-286, September 1979.

[30]

J. Rexford, J. Dolter, W. Feng, and K. G. Shin, "PP- MESS-SIM: A simulator for evaluating multicomputer interconnection networks," in Proc. IEEE Annual Simulation Symposium, pp. 84-93, April 1995.

Digital Library

Cited By

Anderson JEl-Ghazawi TGiorgi RBecchi MPalumbo F(2017)Hardware Support for Secure Stream Processing in Cloud EnvironmentsProceedings of the Computing Frontiers Conference10.1145/3075564.3075592(283-286)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3075592
Yum KJin YKim EDas C(2010)Integration of admission, congestion, and peak power control in QoS-aware clustersJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.06.00170:11(1087-1099)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2010.06.001
Akesson BSteffens LStrooisma EGoossens K(2008)Real-Time Scheduling Using Credit-Controlled Static-Priority Arbitration2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2008.21(3-14)Online publication date: Aug-2008
https://doi.org/10.1109/RTCSA.2008.21
Show More Cited By

Index Terms

A router architecture for real-time point-to-point networks

Recommendations

A router architecture for real-time point-to-point networks
Special Issue: Proceedings of the 23rd annual international symposium on Computer architecture (ISCA '96)

Parallel machines have the potential to satisfy the large computational demands of emerging real-time applications. These applications require a predictable communication network, where time-constrained traffic requires bounds on latency or throughput ...
A Router Architecture for Real-Time Communication in Multicomputer Networks

Parallel machines have the potential to satisfy the large computational demands of real-time applications. These applications require a predictable communication network, where time-constrained traffic requires bounds on throughput and latency, while ...
Real-time task and message scheduling for multiprocessor systems connected by point-to-point networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '96: Proceedings of the 23rd annual international symposium on Computer architecture

May 1996

318 pages

ISBN:0897917863

DOI:10.1145/232973

Chairman:
Jean-Loup Baer
Univ. of Washington, Seattle

ACM SIGARCH Computer Architecture News Volume 24, Issue 2
Special Issue: Proceedings of the 23rd annual international symposium on Computer architecture (ISCA '96)
May 1996
303 pages
ISSN:0163-5964
DOI:10.1145/232974
Chairman:
Jean-Loup Baer
Univ. of Washington, Seattle
Issue’s Table of Contents

Copyright © 1996 Authors.

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 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISCA96

Sponsor:

SIGARCH
IEEE-CS\TCCA

ISCA96: International Conference on Computer Architecture

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

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

46
Total Citations
View Citations
778
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)20

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anderson JEl-Ghazawi TGiorgi RBecchi MPalumbo F(2017)Hardware Support for Secure Stream Processing in Cloud EnvironmentsProceedings of the Computing Frontiers Conference10.1145/3075564.3075592(283-286)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3075592
Yum KJin YKim EDas C(2010)Integration of admission, congestion, and peak power control in QoS-aware clustersJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.06.00170:11(1087-1099)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2010.06.001
Akesson BSteffens LStrooisma EGoossens K(2008)Real-Time Scheduling Using Credit-Controlled Static-Priority Arbitration2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2008.21(3-14)Online publication date: Aug-2008
https://doi.org/10.1109/RTCSA.2008.21
Kim EYum KDas C(2005)Performance analysis of a QoS capable cluster interconnectPerformance Evaluation10.1016/j.peva.2004.10.00860:1-4(275-302)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.peva.2004.10.008
Shin DKim JOrailoglu AChou PEles PJantsch A(2004)Power-aware communication optimization for networks-on-chips with voltage scalable linksProceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/1016720.1016763(170-175)Online publication date: 8-Sep-2004
https://dl.acm.org/doi/10.1145/1016720.1016763
Pedreiras PAlmeida L(2004)Message routing in multi-segment FTT networks: the isochronous approach18th International Parallel and Distributed Processing Symposium, 2004. Proceedings.10.1109/IPDPS.2004.1303082(122-129)Online publication date: 2004
https://doi.org/10.1109/IPDPS.2004.1303082
Hwan Yum KJung Kim EDas CVaidya A(2002)MediaWormIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2002.115826413:12(1261-1274)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1109/TPDS.2002.1158264
Jonsson JShin K(2002)Robust Adaptive Metrics for Deadline Assignment in Distributed Hard Real-Time SystemsReal-Time Systems10.1023/A:102027992941723:3(239-271)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1023/A%3A1020279929417
Yum KKim EDas C(2001)QoS provisioning in clustersACM SIGARCH Computer Architecture News10.1145/384285.37925729:2(120-129)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1145/384285.379257
Yum KKim EDas CStenström P(2001)QoS provisioning in clustersProceedings of the 28th annual international symposium on Computer architecture10.1145/379240.379257(120-129)Online publication date: 1-Jun-2001
https://dl.acm.org/doi/10.1145/379240.379257
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