research-article

Guaranteed Service Independent of the Task Placement in NoCs with Torus Topology

Authors:

Theo UngererAuthors Info & Claims

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

Pages 151 - 160

https://doi.org/10.1145/2659787.2659804

Published: 08 October 2014 Publication History

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

Guaranteed Service Independent of the Task Placement in NoCs with Torus Topology

Pages 151 - 160

Abstract
References

Abstract

Hard real-time systems based on many cores connected by a Network-on-Chip (NoC) need Guaranteed Service (GS) for bounded communication latencies and bandwidths. Typically, GS is implemented by a Custom Schedule, a static periodic communication schedule that minimises network conflicts. It offers minimal latencies and maximum utilisation of the network, but requires the definition of all node-to-node connections at design time of the software. Therefore it is specific to a certain traffic pattern and placement of tasks to nodes.

If the unused connections are not known or the schedule shall be independent of the task placement, all connections must be considered as equally possible, resulting in an All-To-All Schedule. The flexibility in communication and placement of the latter comes at the cost of rather long network latencies.

This paper presents two alternatives that lie between these two extremes: In a One-To-One Schedule the latencies are longer than in a Custom Schedule, but the task mapping has no influence and a real-time system can be composed by independent multi-node software components whose timings were analysed individually. The One-To-All Schedule is an alternative to the All-To-All Schedule. It provides shorter latencies under most circumstances, especially from a timing analysis perspective.

Furthermore, the paper describes how all four schedules can be implemented efficiently using decoupled semi-bufferless x-y-routing in a unidirectional torus.

References

[1]

N. Alon. A simple algorithm for edge-coloring bipartite multigraphs. Information Processing Letters, 85(6):301--302, 2003.

Digital Library

[2]

T. Bjerregaard and J. Sparso. A scheduling discipline for latency and bandwidth guarantees in asynchronous network-on-chip. In Int. Symp. on Asynchronous Circuits and Systems (ASYNC), pages 34--43, 2005.

Digital Library

[3]

F. Brandner and M. Schoeberl. Static routing in symmetric real-time network-on-chips. In Real-Time and Network Systems (RTNS), pages 61--70, 2012.

Digital Library

[4]

R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in o (e log d) time. Combinatorica, 21(1):5--12, 2001.

[5]

C. Cullmann et al. Predictability considerations in the design of multi-core embedded systems. In Embedded Real Time Software and Systems (ERTSS), pages 36--42, 2010.

[6]

K. Goossens and A. Hansson. The aethereal network on chip after ten years: Goals, evolution, lessons, and future. In Design Automation Conference (DAC), pages 306--311, 2010.

Digital Library

[7]

A. Hansson, K. Goossens, and A. Rădulescu. A unified approach to mapping and routing on a network-on-chip for both best-effort and guaranteed service traffic. VLSI design, 2007, 2007.

[8]

A. Hansson, M. Subburaman, and K. Goossens. aelite: a flit-synchronous network on chip with composable and predictable services. In Design, Automation and Test in Europe (DATE), pages 250--255, 2009.

Digital Library

[9]

M. Millberg, E. Nilsson, R. Thid, and A. Jantsch. Guaranteed bandwidth using looped containers in temporally disjoint networks within the nostrum network on chip. In Design, Automation and Test in Europe (DATE), volume 2, pages 890--895, 2004.

Digital Library

[10]

I. Miro-Panades, F. Clermidy, P. Vivet, and A. Greiner. Physical implementation of the dspin network-on-chip in the faust architecture. In Int. Symp. on Networks-on-Chip (NoCS), pages 139--148, 2008.

Digital Library

[11]

J. Mische and T. Ungerer. Low power flitwise routing in an unidirectional torus with minimal buffering. In International Workshop on Network on Chip Architectures (NoCArc), pages 63--68, 2012.

Digital Library

[12]

S.-W. Moon, J. Rexford, and K. G. Shin. Scalable hardware priority queue architectures for high-speed packet switches. IEEE Transactions on Computers, 49(11):1215--1227, 2000.

Digital Library

[13]

B. Nikolić, H. I. Ali, S. M. Petters, and L. M. Pinho. Are virtual channels the bottleneck of priority-aware wormhole-switched noc-based many-cores? In Real-Time Networks and Systems (RTNS), pages 13--22. ACM, 2013.

Digital Library

[14]

C. Paukovits and H. Kopetz. Concepts of switching in the time-triggered network-on-chip. In Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 120--129, 2008.

Digital Library

[15]

E. Rijpkema et al. Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip. IEE Proceedings-Computers and Digital Techniques, 150(5):294--302, 2003.

[16]

C. Rochange. An overview of approaches towards the timing analysability of parallel architecture. In Workshop on Predictability and Performance in Embedded Systems (PPES), pages 32--41, 2011.

[17]

M. Schoeberl. A time-triggered network-on-chip. In Field Programmable Logic and Applications (FPL), pages 377--382, 2007.

[18]

M. Schoeberl, F. Brandner, J. Sparsø, and E. Kasapaki. A statically scheduled time-division-multiplexed network-on-chip for real-time systems. In Int. Symp.on Networks on Chip (NoCS), pages 152--160, 2012.

Digital Library

[19]

Z. Shi and A. Burns. Real-time communication analysis for on-chip networks with wormhole switching. In Int. Symp. on Networks-on-Chip (NoCS, pages 161--170. IEEE Computer Society, 2008.

Digital Library

[20]

R. Stefan, A. Molnos, A. Ambrose, and K. Goossens. dAElite: A TDM NoC Supporting QoS, Multicast, and Fast Connection Set-up. IEEE Transactions on Computers, 2012.

Digital Library

[21]

R. Stefan, A. B. Nejad, and K. Goossens. Online allocation for contention-free-routing nocs. In Interconnection Network Architecture: On-Chip, Multi-Chip Workshop (INA-OCMC), pages 13--16, 2012.

Digital Library

[22]

V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz, 3(7):25--30, 1964.

Cited By

Garg TWasly SPellizzoni RKapre NBazargan KNeuendorffer S(2019)HopliteBufProceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3289602.3293917(222-231)Online publication date: 20-Feb-2019
https://dl.acm.org/doi/10.1145/3289602.3293917
Stegmeier AFrieb MMische JUngerer TOuhammou YRidouard FGrolleau EJan MBehnam M(2018)Analysing Real-Time Behaviour of Collective Communication Patterns in MPIProceedings of the 26th International Conference on Real-Time Networks and Systems10.1145/3273905.3273906(137-147)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3273905.3273906
Banerjee ANaumann DNikouei M(2018)A Logical Analysis of Framing for Specifications with Pure Method CallsACM Transactions on Programming Languages and Systems10.1145/317480140:2(1-90)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3174801
Show More Cited By

Index Terms

Guaranteed Service Independent of the Task Placement in NoCs with Torus Topology

Recommendations

Executing Algorithms with Hypercube Topology on Torus Multicomputers

Many parallel algorithms use hypercubes as the communication topology among their processes. When such algorithms are executed on hypercube multicomputers the communication cost is kept minimum since processes can be allocated to processors in such a ...
Design of a Concentrated Torus Topology with Channel Buffers and Efficient Crossbars in NoCs
IPDPSW '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum

Excess power dissipation along with increased leakage currents in router buffers and crossbars are becoming a major constraint that is affecting the performance of Network-on-Chips (NoCs) architectures. In this paper, we design channel buffers and ...
N-Dimensional Twin Torus Topology
Torus topology is one of the preferred topologies for the interconnection network in high-performance clusters and supercomputers. Cost and scalability are some of the properties that make torus suitable for systems with a large number of nodes. The 3D ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

October 2014

335 pages

ISBN:9781450327275

DOI:10.1145/2659787

General Chairs:
Mathieu Jan
CEA LIST, Gif-sur-Yvette, France
,
Belgacem Ben Hedia
CEA LIST, Gif-sur-Yvette, France
,
Program Chairs:
Joël Goossens
Université Libre de Bruxelles, Belgium
,
Claire Maiza
Grenoble INP / Verimag, France

Copyright © 2014 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 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].

In-Cooperation

CEA: Commissariat à l'énergie atomique et aux énergies alternatives
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

RTNS '14

RTNS '14: 22nd International Conference on Real-Time Networks and Systems

October 8 - 10, 2014

Versaille, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
121
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Garg TWasly SPellizzoni RKapre NBazargan KNeuendorffer S(2019)HopliteBufProceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/3289602.3293917(222-231)Online publication date: 20-Feb-2019
https://dl.acm.org/doi/10.1145/3289602.3293917
Stegmeier AFrieb MMische JUngerer TOuhammou YRidouard FGrolleau EJan MBehnam M(2018)Analysing Real-Time Behaviour of Collective Communication Patterns in MPIProceedings of the 26th International Conference on Real-Time Networks and Systems10.1145/3273905.3273906(137-147)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3273905.3273906
Banerjee ANaumann DNikouei M(2018)A Logical Analysis of Framing for Specifications with Pure Method CallsACM Transactions on Programming Languages and Systems10.1145/317480140:2(1-90)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3174801
Frieb MStegmeier AMische JUngerer T(2018)Lightweight Hardware Synchronization for Avoiding Buffer Overflows in Network-on-ChipsArchitecture of Computing Systems – ARCS 201810.1007/978-3-319-77610-1_9(112-126)Online publication date: 8-Mar-2018
https://doi.org/10.1007/978-3-319-77610-1_9
Wasly SPellizzoni RKapre N(2017)HopliteRT: An efficient FPGA NoC for real-time applications2017 International Conference on Field Programmable Technology (ICFPT)10.1109/FPT.2017.8280122(64-71)Online publication date: Dec-2017
https://doi.org/10.1109/FPT.2017.8280122
Mische JFrieb MStegmeier AUngerer T(2017)Reduced Complexity Many-Core: Timing Predictability Due to Message-PassingArchitecture of Computing Systems - ARCS 201710.1007/978-3-319-54999-6_11(139-151)Online publication date: 4-Mar-2017
https://doi.org/10.1007/978-3-319-54999-6_11
Panić MHernandez CAbella JRoca AQuiñones ECazorla FFanucci LTeich J(2016)Improving performance guarantees in wormhole mesh NoC designsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972154(1485-1488)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972154
Stegmeier AMische JFrieb MUngerer T(2016)WCTT bounds for MPI primitives in the PaterNoster NoCACM SIGBED Review10.1145/3015037.301504113:4(25-30)Online publication date: 3-Nov-2016
https://dl.acm.org/doi/10.1145/3015037.3015041
Ungerer TBradatsch CFrieb MKluge FMische JStegmeier AJahr RGerdes MZaykov PMatusova LLi ZPetrov ZBöddeker BKehr SRegler HHugl ARochange COzaktas HCassé HBonenfant ASainrat PLay NGeorge DBroster IQuiñones EPanic MAbella JHernandez CCazorla FUhrig SRohde MPyka A(2016)Parallelizing Industrial Hard Real-Time Applications for the parMERASA MulticoreACM Transactions on Embedded Computing Systems10.1145/291058915:3(1-27)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2910589
Kim DChon YJung WKim YCha H(2016)Accurate Prediction of Available Battery Time for Mobile ApplicationsACM Transactions on Embedded Computing Systems10.1145/287542315:3(1-17)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2875423
Show More Cited By

View Options

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.

Figures

Tables

Media

View Table of Conten