research-article

A method for calculating hard QoS guarantees for Networks-on-Chip

Authors:

Srinivasan Murali,

Federico Angiolini,

Giovanni De Micheli,

Hamid Sarbazi-AzadAuthors Info & Claims

ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

Pages 579 - 586

https://doi.org/10.1145/1687399.1687507

Published: 02 November 2009 Publication History

Abstract

Many Networks-on-Chip (NoC) applications exhibit one or more critical traffic flows that require hard Quality of Service (QoS). Guaranteeing bandwidth and latency for such real time flows is crucial. In this paper, we present novel methods to efficiently calculate worst-case bandwidth and latency bounds and thereby provide hard QoS guarantees. Importantly, the proposed methods apply even to best-effort NoC architectures, with no extra hardware dedicated to QoS support. By applying our methods to several realistic NoC designs, we show substantial improvements (on average, more than 30% in bandwidth and 50% in latency) in bound tightness with respect to existing approaches.

References

[1]

W. J. Dally and B. Towles, "Route packets, not wires: On-chip interconnection networks, "Proceedings of the 38th Design Automation Conference, 2001.

Digital Library

[2]

L. Benini and G. D. Micheli, "Networks on Chips: A New SoC Paradigm," Computer, 35(1):70--78, 2002.

Digital Library

[3]

P. Guerrier and A. Greiner, "A generic architecture for on-chip packet-switched interconnections," in Proceedings of Design, Automation and Test in Europe Conference ands Exhibition(DATE '00), pp. 250--256, Paris, France, March 2000.

Digital Library

[4]

Z. Guz, I. Walter, E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, "Network Delays and Link Capacities in application-Specific Wormhole NoCs," VLSI Design, Volume 2007, Article ID 90941

[5]

J. Henkel, W. Wolf, and S. Chakradhar, "On-chip networks: a scalable, communication-centric embedded system design paradigm," in Proceedings of the 17th International Conference on VLSI Design (VLSID '04), vol. 17, pp. 845--851, Mumbai, India, January 2004.

Digital Library

[6]

S. Furber and J. Bainbridge. "Future trends in SoC interconnect", In VLSI Design, Automation and Test, pages 183--186, 2005.

[7]

Z. Shi and A. Burns, "Real-Time Communication Analysis for On-Chip Networks with Wormhole Switching, "Second ACM/IEEE International Symposium on Networks-on-Chip, 2008

Digital Library

[8]

C. Paukovits, H. Kopetz, "Concepts of Switching in the Time-Triggered Network-on-Chip," Proceedings of the 2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems, pp. 120--12.

Digital Library

[9]

K. Goossens, J. Dielissen, and A. Radulescu, "The Æthereal network on chip: Concepts, architectures, and implementations," IEEE Design and Test of Computers, 22(5):414--421, 2005.

Digital Library

[10]

S. Lee, "Real-time wormhole channels," J. Parallel Distrib. Comput. 63 (2003) 299--311

Digital Library

[11]

D. Kandlur, K. Shin, D. Ferrari, "Real-Time Communication in Multihop Networks," IEEE Trans. on Para. and Distributed Systems, vol. 5, no. 10, Oct. 1994.

Digital Library

[12]

M. Zhang, J. Shi, T. Zhang, Y. Hu, "Hard Real-time Communication over Multi-hop Switched Ethernet, "Int. Conf. on Networking, Architecture, and Storage, 2008

Digital Library

[13]

S. Gopalakrishnan, S. Lui, and M. Caccamo, "Hard Real-Time Communication in Bus-Based Networks," In Proc. 25th IEEE Int. Real-Time Systems Symp., 2004.

Digital Library

[14]

A. Yiming, and T. Eisaka, "A Switched Ethernet Protocol for Hard Real-Time Embedded System Applications," In 19th Conf. on Advanced Information Networking & Applications, March 2005, pp. 41--44.

Digital Library

[15]

K. Watson and J. Jasperneite, "Determining end-to-end delays using network calculus," In Proc. 5th IFAC Int. Conf. on Fieldbus Systems and Their Applications (IFAC-FET2003), July 7--8, 2003, pp. 255--260.

[16]

J. Chen, Z. Wang, and Y. Sun, "Real-time capability analysis for switch industrial Ethernet traffic priority-based," In Proc. of Int. Conf. on Control Applications, Glasgow, UK, Sep. 2002, pp. 525--529.

[17]

J. Jaspernite, P. Neumann, M. Theis, and K. Watson, "Deterministic Real-Time Communication with Switched Ethernet," In Proc. of WFCS'02, Vasteras, Sweden.

[18]

S. Lee; K. C. Lee, and H. H. Kim, "Maximum communication delay of a realtime industrial switched Ethernet with multiple switching hubs," In 30th Conf. of IEEE Industrial Electronics Society, 2004.

[19]

J. Loeser and H. Haertig, "Low-latency hard real-time communication over switched Ethernet," In Proc. of ECRTS 2004.

Digital Library

[20]

J. Kiszka, B. Wagner, Y. Zhang, J. Broenink," RTnet -- A Flexible Hard RealTime Networking Framework," In: 10th IEEE International Conference on Emerging Technologies and Factory Automation, 2005.

[21]

H. Kopetz, A. Damm, C. Koza, et al., "Distributed fault-tolerant real-time systems: the Mars approach," IEEE Micro, 1989, 9(1): 25--40.

Digital Library

[22]

E. Bolotin et al., "QNoC: QoS architecture and design process for network on chip," Journal of Systems Architecture, vol. 50, no. 2--3, pp. 105--128, Feb. 2004.

Digital Library

[23]

T. Bjerregaardand, J. Sparsoe, "Arouter architecturefor connection-oriented service guarantees in the MANGO clockless network-on-chip," in DATE, vol. 2, Mar. 2005, pp. 1226--1231.

Digital Library

[24]

A. Bouhraoua and M. E. Elrabaa, "A high-throughput network-on-chip architecture for systems-on-chip interconnect," in Intl. Symposium on Soc, Nov. 2006.

[25]

F. Felicijan and S. Furber, "An asynchronous on-chip network router with quality-of-service (QoS) support," in SOCC, Sep. 2004, pp. 274--277.

[26]

N. Kavaldjiev et al., "A virtual channel network-on-chip for GT and BE traffic," in ISVLSI, vol. 00, Mar. 2006.

Digital Library

[27]

A. Leroy et al., "Spatial division multiplexing: a novel approach for guaranteed throughput on NoCs," in CODES+ISSS, 2005, pp. 81--86.

Digital Library

[28]

A. Mello, L. Tedesco, N. Calazans, and F. Moraes, "Evaluation of current QoS mechanisms in network on chip," in Intl. Symposium on Soc, 2006, pp. 115--118.

[29]

M. Millberg, R. T. E. Nilsson, and A. Jantsch, "Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip," in DATE, 2004, pp. 890--895.

Digital Library

[30]

F. Mondinelli, M. Borgatti, and Z. Vajna, "A 0.13 um 1Gb/s/channel store-and-forward network on-chip," in SOCC, Sep. 2004, pp. 141--142.

[31]

R. Mullins, A. West, and S. Moore, "The design and implementation of a low-latency on-chip network," in ASP-DAC, 2006.

Digital Library

[32]

A. Radulescu et al., "An efficient on-chip NI offering guaranteed services, shared-memory abstraction, and flexible network configuration," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 1, pp. 4--17, Jan. 2005.

Digital Library

[33]

E. Rijpkema et al., "Trade offs in the design of a router with both guaranteed and best-effort services for network on chip," IEE Proc. Computers and Digital Techniques, vol. 150, no. 5, pp. 294--302, 2003.

[34]

E. Salminen, A. Kulmala, T. Hamalainen, "Survey of Network-on-Chip Proposals," www.ocpip.org, March 2008.

Cited By

Kashi SPatooghy ARahmati DFazeli MKinsy M(2018)Application Specific Networks-on-Chip Synthesis: An Energy Efficient Approach2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2018.00020(52-57)Online publication date: Jul-2018
https://doi.org/10.1109/ISVLSI.2018.00020
Tobuschat SErnst R(2017)Real-time communication analysis for networks-on-chip with backpressureProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130513(590-595)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130513
Tobuschat SErnst R(2017)Real-time communication analysis for Networks-on-Chip with backpressureDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927055(590-595)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927055
Show More Cited By

Index Terms

A method for calculating hard QoS guarantees for Networks-on-Chip
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Interconnection architectures
2. Hardware
  1. Integrated circuits
    1. Interconnect

Recommendations

Computing Accurate Performance Bounds for Best Effort Networks-on-Chip

Real-time (RT) communication support is a critical requirement for many complex embedded applications which are currently targeted to Network-on-chip (NoC) platforms. In this paper, we present novel methods to efficiently calculate worst case bandwidth ...
Enabling dynamic and programmable QoS in SoCs
NoCArc '10: Proceedings of the Third International Workshop on Network on Chip Architectures

While System-on-Chip (SoC) complexity grows, the problem of designing interconnects offering a suitable Quality-of-Service (QoS) becomes drastically complex and forces designers to spend significant effort and time. Moreover, the current trend to employ ...
Introducing the SuperGT network-on-chip: SuperGT QoS: more than just GT
DAC '07: Proceedings of the 44th annual Design Automation Conference

Predictability of multi-processor systems-on-chip communication is critical and needs to be addressed by providing the right mix of soft and hard real-time guarantees. To this end, state-of-the-art packet-switched networks-on-chip (NoC) provide ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design

November 2009

803 pages

ISBN:9781605588001

DOI:10.1145/1687399

General Chair:
Jaijeet Roychowdhury
Univ. of California, Berkeley, Berkeley, California

Copyright © 2009 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

SIGDA: ACM Special Interest Group on Design Automation
IEEE CAS
IEEE Council on Electronic Design Automation (CEDA)

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICCAD '09

Sponsor:

SIGDA

ICCAD '09: The International Conference on Computer-Aided Design

November 2 - 5, 2009

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kashi SPatooghy ARahmati DFazeli MKinsy M(2018)Application Specific Networks-on-Chip Synthesis: An Energy Efficient Approach2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2018.00020(52-57)Online publication date: Jul-2018
https://doi.org/10.1109/ISVLSI.2018.00020
Tobuschat SErnst R(2017)Real-time communication analysis for networks-on-chip with backpressureProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130513(590-595)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130513
Tobuschat SErnst R(2017)Real-time communication analysis for Networks-on-Chip with backpressureDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927055(590-595)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927055
Qian ZBogdan PTsui CMarculescu R(2016)Performance Evaluation of NoC-Based Multicore SystemsACM Transactions on Design Automation of Electronic Systems10.1145/287063321:3(1-38)Online publication date: 11-May-2016
https://dl.acm.org/doi/10.1145/2870633
Khawaja SMushtaq MKhan SAkram MJamal H(2015)Designing Area Optimized Application-Specific Network-On-Chip Architectures while Providing Hard QoS GuaranteesPLOS ONE10.1371/journal.pone.012523010:4(e0125230)Online publication date: 21-Apr-2015
https://doi.org/10.1371/journal.pone.0125230
Jafari FLu ZJantsch A(2015)Least Upper Delay Bound for VBR Flows in Networks-on-Chip with Virtual ChannelsACM Transactions on Design Automation of Electronic Systems10.1145/273337420:3(1-33)Online publication date: 24-Jun-2015
https://dl.acm.org/doi/10.1145/2733374
Dasari DNikoli'c BN'elis VPetters S(2014)NoC contention analysis using a branch-and-prune algorithmACM Transactions on Embedded Computing Systems10.1145/256793713:3s(1-26)Online publication date: 28-Mar-2014
https://dl.acm.org/doi/10.1145/2567937
Ding YZhang W(2014)Hop-Based Priority Scheduling to Improve Worst-Case Inter-core Communication LatencyProceedings of the 2014 12th IEEE International Conference on Embedded and Ubiquitous Computing10.1109/EUC.2014.17(52-57)Online publication date: 26-Aug-2014
https://dl.acm.org/doi/10.1109/EUC.2014.17
Qian ZBogdan PTsui CMarculescu RHenkel J(2013)Performance evaluation of multicore systemsProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561845(82-84)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561845
Seiculescu CRahmati DMurali SSarbazi-Azad HBenini LMicheli G(2013)Designing best effort networks-on-chip to meet hard latency constraintsACM Transactions on Embedded Computing Systems10.1145/2485984.248599612:4(1-23)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2485984.2485996
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents