Real-Time Guarantees in Routerless Networks-on-Chip
Article No.: 88, Pages 1 - 27
Abstract
This article considers the use of routerless networks-on-chip as an alternative on-chip interconnect for multi-processor systems requiring hard real-time guarantees for inter-processor communication. It presents a novel analytical framework that can provide latency upper bounds to real-time packet flows sent over routerless networks-on-chip, and it uses that framework to evaluate the ability of such networks to provide real-time guarantees. Extensive comparative analysis is provided, considering different architectures for routerless networks and a state-of-the-art wormhole network based on priority-preemptive routers as a baseline.
References
[1]
F. Alazemi, A. AziziMazreah, B. Bose, and L. Chen. 2018. Routerless network-on-chip. In Proceedings of the 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA’18). 492–503.
[2]
R. Ausavarungnirun, C. Fallin, X. Yu, K. K. Chang, G. Nazario, R. Das, G. H. Loh, and O. Mutlu. 2014. Design and evaluation of hierarchical rings with deflection routing. In Proceedings of the IEEE 26th International Symposium on Computer Architecture and High Performance Computing. 230–237.
[3]
E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny. 2004. QNoC: QoS architecture and design process for network on chip. Journal of Systems Architecture 50, 2-3 (2004), 105–128.
[4]
S. Bourduas and Z. Zilic. 2007. A hybrid ring/mesh interconnect for network-on-chip using hierarchical rings for global routing. In Proceedings of the International Symposium on Networks-on-Chip (NOCS’07). 195–204.
[5]
A. Burns, L. S. Indrusiak, N. Smirnov, and J. Harrison. 2020. A novel flow control mechanism to avoid multi-point progressive blocking in hard real-time priority-preemptive NoCs. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’20). 137–147.
[6]
L. Chen, F. M. Alazemi, and B. Bose. 2020. Routerless networks-on-chip. (May 2020). Patent No. US10657216B2.
[7]
W. J. Dally and B. Towles. 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann, San Francisco, CA.
[8]
F. Giroudot and A. Mifdaoui. 2019. Tightness and computation assessment of worst-case delay bounds in wormhole networks-on-chip. In Proceedings of the 27th International Conference on Real-Time Networks and Systems (RTNS’19). 19–29.
[9]
K. Goossens, J. Dielissen, and A. Radulescu. 2005. AEthereal network on chip: Concepts, architectures, and implementations. IEEE Design & Test of Computers 22, 5 (2005), 414–421.
[10]
C. Gómez, M. E. Gómez, P. López, and J. Duato. 2008. Reducing packet dropping in a bufferless NoC. In Proceedings of the 14th International Conference on Parallel Processing (Euro-Par’08). 899–909.
[11]
S. L. Hary and F. Ozguner. 1997. Feasibility test for real-time communication using wormhole routing. IET Proceedings–Computers and Digital Techniques 144, 5 (1997), 273–278.
[12]
S. Hesham, J. Rettkowski, D. Goehringer, and M. A. Abd El Ghany. 2017. Survey on real-time networks-on-chip. IEEE Transactions on Parallel and Distributed Systems 28, 5 (2017), 1500–1517.
[13]
L. S. Indrusiak, A. Burns, and B. Nikolic. 2018. Buffer-aware bounds to multi-point progressive blocking in priority-preemptive NoCs. In Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’18). 219–224.
[14]
H. Kashif and H. Patel. 2016. Buffer space allocation for real-time priority-aware networks. In Proceedings of the 2016 Real-Time and Embedded Technology and Applications Symposium (RTAS’16). 1–12.
[15]
S. Khan, S. Anjum, U. A. Gulzari, M. K. Afzal, T. Umer, and F. Ishmanov. 2018. An efficient algorithm for mapping real time embedded applications on NoC architecture. IEEE Access 6 (2018), 16324–16335.
[16]
B. Kim, J. Kim, S. Hong, and S. Lee. 1998. A real-time communication method for wormhole switching networks. In Proceedings of the International Conference on Parallel Processing. 527–534.
[17]
T. Lin, D. Penney, M. Pedram, and L. Chen. 2020. A deep reinforcement learning framework for architectural exploration: A routerless NoC case study. In Proceedings of the IEEE International Symposium on High Performance Computer Architecture (HPCA ’20). 99–110.
[18]
S. Liu, T. Chen, L. Li, X. Feng, Z. Xu, H. Chen, F. Chong, and Y. Chen. 2016. IMR: High-performance low-cost multi-ring NoCs. IEEE Transactions on Parallel and Distributed Systems 27, 6 (June2016), 1700–1712.
[19]
Y. Ma, M. N. S. M. Sayuti, and L.S. Indrusiak. 2014. Inexact end-to-end response time analysis as fitness function in search-based task allocation heuristics for hard real-time network-on-chips. In Proceedings of the International Symposium on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC’14). IEEE, Los Alamitos, CA. DOI:
[20]
G. Michelogiannakis, D. Sanchez, W. J. Dally, and C. Kozyrakis. 2010. Evaluating bufferless flow control for on-chip networks. In Proceedings of the ACM/IEEE International Symposium on Networks-on-Chip. 9–16.
[21]
T. Moscibroda and O. Mutlu. 2009. A case for bufferless routing in on-chip networks. ACM SIGARCH Computer Architecture News 37, 3 (June2009), 196–207.
[22]
M. W. Mutka. 1994. Using rate monotonic scheduling technology for real-time communications in a wormhole network. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. 194–199.
[23]
B. Nikolic, R. Hofmann, and R. Ernst. 2019. Slot-based transmission protocol for real-time NoCs—SBT-NoC. In Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS’19). Article 26, 22 pages.
[24]
B. Nikolic, S. Tobuschat, L. S. Indrusiak, R. Ernst, and A. Burns. 2019. Real-time analysis of priority-preemptive NoCs with arbitrary buffer sizes and router delays. Real-Time Systems 55, 1 (2019), 63–105.
[25]
W. Penny, D. Palomino, M. S. Porto, B. Zatt, and L. S. Indrusiak. 2019. Design space exploration of HEVC RCL mapped onto NoC-based embedded platforms. In Proceedings of the International Symposium on Reconfigurable Communication-Centric Systems-on-Chip (ReCoSoC’19). IEEE, Los Alamitos, CA. DOI:
[26]
D. C. Pham, T. Aipperspach, D. Boerstler, M. Bolliger, R. Chaudhry, D. Cox, P. Harvey, P. M. Harvey, H. P. Hofstee, C. Johns, J. Kahle, A. Kameyama, J. Keaty, Y. Masubuchi, M. Pham, J. Pille, S. Posluszny, M. Riley, D. L. Stasiak, M. Suzuoki, O. Takahashi, J. Warnock, S. Weitzel, D. Wendel, and K. Yazawa. 2006. Overview of the architecture, circuit design, and physical implementation of a first-generation cell processor. IEEE Journal of Solid-State Circuits 41, 1 (2006), 179–196.
[27]
Yilian Ribot González and Geoffrey Nelissen. 2020. HopliteRT*: Real-time NoC for FPGA. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39, 11 (2020), 3650–3661. DOI:
[28]
E. Rotem, A. Naveh, A. Ananthakrishnan, E. Weissmann, and D. Rajwan. 2012. Power-management architecture of the Intel microarchitecture code-named Sandy Bridge. IEEE Micro 32, 2 (2012), 20–27.
[29]
M. N. S. M. Sayuti and L. S. Indrusiak. 2013. Real-time low-power task mapping in networks-on-chip. In Proceedings of the 2013 IEEE Computer Society Annual Symposium on VLSI (ISVLSI’13). 14–19.
[30]
Z. Shi and A. Burns. 2008. Real-time communication analysis for on-chip networks with wormhole switching. In Proceedings of the 2nd ACM/IEEE International Symposium on Networks-on-Chip (NOCS’08). 161–170.
[31]
D. Siguenza-Tortosa and J. Nurmi. 2002. Proteo: A new approach to network-on-chip. In Proceedings of the IASTED International Conference on Communication Systems and Networks (CSN’02).
[32]
K. W. Tindell, A. Burns, and A. J Wellings. 1994. An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Systems 6, 2 (1994), 133–151.
[33]
N. Ueter, G. von der Brueggen, J. J. Chen, T. Mitra, and V. Venkataramani. 2019. Simultaneous progressing switching protocols for timing predictable real-time network-on-chips. arXiv:1909.09457v1 [cs.DC] (2019).
[34]
J. Xiao and K. L. Yeung. 2019. Onion: An efficient heuristic for designing routerless network-on-chip. In Proceedings of the 2019 IEEE 44th LCN Symposium on Emerging Topics in Networking (LCN Symposium’19). 125–132. DOI:
[35]
Q. Xiong, Z. Lu, F. Wu, and C. Xie. 2016. Real-time analysis for wormhole NoC: Revisited and revised. In Proceedings of the 2016 International Great Lakes Symposium on VLSI (GLSVLSI’16). 75–80.
[36]
Q. Xiong, F. Wu, Z. Lu, and C. Xie. 2017. Extending real-time analysis for wormhole NoCs. IEEE Transactions on Computers 66, 9 (2017), 1532–1546.
Index Terms
- Real-Time Guarantees in Routerless Networks-on-Chip
Recommendations
Using non-preemptive regions and path modification to improve schedulability of real-time traffic over priority-based NoCs
Network-on-Chip (NoC) is a preferred communication medium for massively parallel platforms. Fixed-priority based scheduling using virtual-channels is one of the promising solutions to support real-time traffic in on-chip networks. Most of the existing ...
Flattened Butterfly Topology for On-Chip Networks
With the trend towards increasing number of cores in a multicore processors, the on-chip network that connects the cores needs to scale efficiently. In this work, we propose the use of high-radix networks in on-chip networks and describe how the ...
Survey on Real-Time Networks-on-Chip
Multi-Processor Systems-on-Chip (MPSoCs) have emerged as an evolution trend to meet the growing complexity of embedded applications with increasing computation parallelism. Particularly, real-time applications make out a significant portion of the ...
Comments
Information & Contributors
Information
Published In
September 2023
217 pages
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 the author(s) 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].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 26 September 2023
Online AM: 23 August 2023
Accepted: 07 August 2023
Revised: 03 July 2023
Received: 21 September 2022
Published in TECS Volume 22, Issue 5
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 147Total Downloads
- Downloads (Last 12 months)75
- Downloads (Last 6 weeks)6
Reflects downloads up to 29 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in