research-article

Response time analysis of dataflow applications on a many-core processor with shared-memory and network-on-chip

Authors:

Amaury Graillat,

Pascal Raymond,

Benoît Dupont de DinechinAuthors Info & Claims

RTNS '19: Proceedings of the 27th International Conference on Real-Time Networks and Systems

Pages 61 - 69

https://doi.org/10.1145/3356401.3356416

Published: 06 November 2019 Publication History

Abstract

We consider hard real-time applications running on many-core processor containing several clusters of cores linked by a Network-on-Chip (NoC). Communications are done via shared memory within a cluster and through the NoC for inter-cluster communication. We adopt the time-triggered paradigm, which is well-suited for hard real-time applications, and we consider data-flow applications, where communications are explicit.

We extend the AER (Acquisition/Execution/Restitution) execution model to account for all delays and interferences linked to communications, including the interference between the NoC interface and the memory. Indeed, for NoC communications, data is first read from the initiator's local memory, then sent over the NoC, and finally written to the local memory of the target cluster. Read and write accesses to transfer data between local memories may interfere with shared-memory communication inside a cluster, and, as far as we know, previous work did not take these interferences into account.

Building on previous work on deterministic network calculus and shared memory interference analysis, our method computes a static, time-triggered schedule for an application mapped on several clusters. This schedule guarantees that deadlines are met, and therefore provides a safe upper bound to the global worst-case response time.

References

[1]

Sebastian Altmeyer, Robert I Davis, Leandro Indrusiak, Claire Maiza, Vincent Nelis, and Jan Reineke. 2015. A generic and compositional framework for multi-core response time analysis. In Proceedings of the 23rd International Conference on Real Time and Networks Systems. ACM, 129--138.

Digital Library

[2]

Hamdi Ayed, Jérôme Ermont, Jean-luc Scharbarg, and Christian Fraboul. 2016. Towards a unified approach for worst-case analysis of Tilera-like and Kalray-like NoC architectures. In Factory Communication Systems (WFCS), 2016 IEEE World Conference on. IEEE, 1--4.

[3]

Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. 2010. OTAWA: an open toolbox for adaptive WCET analysis. In IFIP International Workshop on Software Technolgies for Embedded and Ubiquitous Systems. Springer, 35--46.

[4]

Mathias Becker, Dakshina Dasari, Borislav Nicolic, Benny Åkesson, Vincent Nélis, and Thomas Nolte. 2016. Contention-Free Execution of Automotive Applications on a Clustered Many-Core Platform. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS). 14--24.

[5]

Gérard Berry. 2007. SCADE: Synchronous design and validation of embedded control software. In Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems. Springer, 19--33.

[6]

Marc Boyer, Benoît Dupont de Dinechin, Amaury Graillat, and Lionel Havet. 2018. Computing Routes and Delay Bounds for the Network-on-Chip of the Kalray MPPA2 Processor. In ERTS 2018-9th European Congress on Embedded Real Time Software and Systems.

[7]

Jean-Louis Colaço, Bruno Pagano, Cédric Pasteur, and Marc Pouzet. 2018. Scade 6: from a Kahn Semantics to a Kahn Implementation for Multicore. In Forum on specification & Design Languages (FDL). Munich, Germany. https://hal.archives-ouvertes.fr/hal-01960410.

[8]

Benoît Dupont de Dinechin and Amaury Graillat. 2017. Network-on-chip service guarantees on the kalray mppa-256 bostan processor. In Proceedings of the 2nd International Workshop on Advanced Interconnect Solutions and Technologies for Emerging Computing Systems. ACM, 35--40.

[9]

Benoît Dupont de Dinechin, Duco van Amstel, Marc Poulhiès, and Guillaume Lager. 2014. Time-critical Computing on a Single-chip Massively Parallel Processor. In Proceedings of the Conference on Design, Automation & Test in Europe (DATE '14). European Design and Automation Association, 3001 Leuven, Belgium, Belgium, Article 97, 6 pages. http://dl.acm.org/citation.cfm?id=2616606.2616725

Digital Library

[10]

Guy Durrieu, Madeleine Faugere, Sylvain Girbal, Daniel Gracia Pérez, Claire Pagetti, and Wolfgang Puffitsch. 2014. Predictable Flight Management System Implementation on a Multicore Processor. In ERTS 2014-7th European Congress on Embedded Real Time Software and Systems.

[11]

Thomas Ferrandiz, Fabrice Frances, and Christian Fraboul. 2012. A sensitivity analysis of two worst-case delay computation methods for spacewire networks. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on. IEEE, 47--56.

Digital Library

[12]

Fabien Geyer and Georg Carle. 2016. Network engineering for real-time networks: comparison of automotive and aeronautic industries approaches. IEEE Communications Magazine 54, 2 (2016), 106--112.

Digital Library

[13]

Georgia Giannopoulou, Nikolay Stoimenov, Pengcheng Huang, Lothar Thiele, and Benoît Dupont de Dinechin. 2016. Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources. Real-Time Systems 52, 4 (2016), 399--449.

Digital Library

[14]

Amaury Graillat, Matthieu Moy, Pascal Raymond, and Benoît Dupont de Dinechin. 2018. Parallel code generation of synchronous programs for a many-core architecture. In DATE. IEEE, 1139--1142.

[15]

Amaury Graillat, Matthieu Moy, Pascal Raymond, and Benoît Dupont De Dinechin. 2018. Parallel Code Generation of Synchronous Programs for a Many-core Architecture. In DATE 2018 - Design, Automation and Test in Europe. Dresden, Germany. https://hal.inria.fr/hal-01667594

[16]

Jérôme Grieu. 2004. Analyse et évaluation de techniques de commutation Ethernet pour l'interconnexion des systêmes avioniques. Ph.D. Dissertation. Institut National Polytechnique de Toulouse.

[17]

N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. 1991. The synchronous dataflow programming language Lustre. Proc. IEEE 79, 9 (Sept. 1991), 1305--1320.

[18]

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 (May 2017), 1500--1517.

Digital Library

[19]

A.E. Kiasari, A. Jantsch, and Z. Lu. 2013. Mathematical Formalisms for Performance Evaluation of Networks-on-chip. ACM Comput. Surv. 45, 3, Article 38 (July 2013), 41 pages.

Digital Library

[20]

The Mathworks. [n. d.]. Simulink: User's Guide.

[21]

Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio Buttazzo. 2015. Memory-Processor Co-Scheduling in Fixed Priority Systems. In Proceedings of the 23rd International Conference on Real Time and Networks Systems (RTNS). 87--96.

Digital Library

[22]

Bruno Pagano, Cédric Pasteur, Günther Siegel, and R Kníźek. 2018. A model based safety critical flow for the AURIX multi-core platform. Embedded Real-Time Software and Systems (ERTS'18) (2018).

[23]

Claire Pagetti, David Saussié, Romain Gratia, Eric Noulard, and Pierre Siron. 2014. The ROSACE case study: From simulink specification to multi/many-core execution. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2014 IEEE 20th. IEEE, 309--318.

[24]

Hamza Rihani. 2017. Many-Core timing Analysis of Real-Time Systems. Ph.D. Dissertation. Univ. Grenoble Alpes.

[25]

Hamza Rihani, Matthieu Moy, Claire Maiza, Robert I Davis, and Sebastian Altmeyer. 2016. Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor. In RTNS'16. ACM, 67--76.

Digital Library

[26]

Selma Saidi, Rolf Ernst, Sascha Uhrig, Henrik Theiling, and Benoît Dupont de Dinechin. 2015. The shift to multicores in real-time and safety-critical systems. In Proceedings of the 10th International Conference on Hardware/Software Codesign and System Synthesis. IEEE Press, 220--229.

[27]

Stefanos Skalistis and Alena Simalatsar. 2016. Worst-Case Execution Time Analysis for Many-Core Architectures with NoC. In Proceedings of the 14th International Conference on Formal Modelling and Analysis of Timed Systems, Springer (Ed.). 211--227.

[28]

Pranav Tendulkar, Peter Poplavko, Ioannis Galanommatis, and Oded Maler. 2014. Many-core scheduling of data parallel applications using SMT solvers. In Digital System Design (DSD), 2014 17th Euromicro Conference on. IEEE, 615--622.

Digital Library

Cited By

Khalil KEldash OKumar ABayoumi M(2021)Self-Healing Router Approach for High-Performance Network-on-ChipIEEE Open Journal of Circuits and Systems10.1109/OJCAS.2021.30950002(485-496)Online publication date: 2021
https://doi.org/10.1109/OJCAS.2021.3095000
Dupont de Dinechin B(2021)A Qualitative Approach to Many‐core ArchitectureMulti‐Processor System‐on‐Chip 110.1002/9781119818298.ch2(27-51)Online publication date: 26-Mar-2021
https://doi.org/10.1002/9781119818298.ch2
Schuh MMaiza CGoossens JRaymond Pde Dinechin B(2020)A study of predictable execution models implementation for industrial data-flow applications on a multi-core platform with shared banked memory2020 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS49844.2020.00034(283-295)Online publication date: Dec-2020
https://doi.org/10.1109/RTSS49844.2020.00034

Index Terms

Response time analysis of dataflow applications on a many-core processor with shared-memory and network-on-chip
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Embedded systems
    2. Robotics
2. Networks
  1. Network properties
    1. Network reliability

Recommendations

A multilayer nanophotonic interconnection network for on-chip many-core communications
DAC '10: Proceedings of the 47th Design Automation Conference

Multi-core chips or chip multiprocessors (CMPs) are becoming the de facto architecture for scaling up performance and taking advantage of the increasing transistor count on the chip within reasonable power consumption levels. The projected increase in ...
Time-predictable distributed shared on-chip memory
Abstract
Multi-core processors for real-time systems need to have a time-predictable way of communicating. The use of a single, external shared memory is the standard for multi-core processor communication. However, this solution is hardly time-...
Buffer Allocation Based On-Chip Memory Optimization for Many-Core Platforms
IPDPSW '15: Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop

The problem of finding an optimal allocation of logical data buffers to memory has emerged as a new research challenge due to the increased complexity of applications and new emerging Dynamic RAM (DRAM) interface technologies. This new opportunity of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '19: Proceedings of the 27th International Conference on Real-Time Networks and Systems

November 2019

221 pages

ISBN:9781450372237

DOI:10.1145/3356401

General Chair:
Jérôme Ermont
IRIT, ENSEEIHT, France
,
Program Chairs:
Ye-Qiong Song
LORIA - Université de Lorraine, France
,
Christopher Gill
Washington University in St. Louis

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

RTNS 2019

RTNS 2019: 27th International Conference on Real-Time Networks and Systems

November 6 - 8, 2019

Toulouse, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
83
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khalil KEldash OKumar ABayoumi M(2021)Self-Healing Router Approach for High-Performance Network-on-ChipIEEE Open Journal of Circuits and Systems10.1109/OJCAS.2021.30950002(485-496)Online publication date: 2021
https://doi.org/10.1109/OJCAS.2021.3095000
Dupont de Dinechin B(2021)A Qualitative Approach to Many‐core ArchitectureMulti‐Processor System‐on‐Chip 110.1002/9781119818298.ch2(27-51)Online publication date: 26-Mar-2021
https://doi.org/10.1002/9781119818298.ch2
Schuh MMaiza CGoossens JRaymond Pde Dinechin B(2020)A study of predictable execution models implementation for industrial data-flow applications on a multi-core platform with shared banked memory2020 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS49844.2020.00034(283-295)Online publication date: Dec-2020
https://doi.org/10.1109/RTSS49844.2020.00034

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.

Media

Figures

Other

Tables

View Table of Contents