article

Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources

Authors:

Georgia Giannopoulou,

Nikolay Stoimenov,

Pengcheng Huang,

Lothar Thiele,

Benoît Dupont DinechinAuthors Info & Claims

Real-Time Systems, Volume 52, Issue 4

Pages 399 - 449

https://doi.org/10.1007/s11241-015-9227-y

Published: 01 July 2016 Publication History

Abstract

The embedded system industry is facing an increasing pressure for migrating from single-core to multi- and many-core platforms for size, performance and cost purposes. Real-time embedded system design follows this trend by integrating multiple applications with different safety criticality levels into a common platform. Scheduling mixed-criticality applications on today's multi/many-core platforms and providing safe worst-case response time bounds for the real-time applications is challenging given the shared platform resources. For instance, sharing of memory buses introduces delays due to contention, which are non-negligible. Bounding these delays is not trivial, as one needs to model all possible interference scenarios. In this work, we introduce a combined analysis of computing, memory and communication scheduling in a mixed-criticality setting. In particular, we propose: (1) a mixed-criticality scheduling policy for cluster-based many-core systems with two shared resource classes, i.e., a shared multi-bank memory within each cluster, and a network-on-chip for inter-cluster communication and access to external memories; (2) a response time analysis for the proposed scheduling policy, which takes into account the interferences from the two classes of shared resources; and (3) a design exploration framework and algorithms for optimizing the resource utilizations under mixed-criticality timing constraints. The considered cluster-based architecture model describes closely state-of-the-art many-core platforms, such as the Kalray MPPA®-256. The applicability of the approach is demonstrated with a real-world avionics application. Also, the scheduling policy is compared against state-of-the-art scheduling policies based on extensive simulations with synthetic task sets.

References

[1]

Alur R, Dill DL (1994) A theory of timed automata. Theor Comput Sci 126(2):183-235.

Digital Library

Google Scholar

[2]

Anderson J, Baruah S, Brandenburg B (2009) Multicore operating-system support for mixed criticality. In: Workshop on mixed criticality: roadmap to evolving UAV certification.

Google Scholar

[3]

ARINC (2003) ARINC 653-1 avionics application software standard interface. Technical report.

Google Scholar

[4]

Baruah S, Bonifaci V, D'Angelo G, Li H, Marchetti-Spaccamela A, Van der Ster S, Stougie L (2012) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In: ECRTS, pp. 145-154.

Crossref

Google Scholar

[5]

Baruah S, Chattopadhyay B, Li H, Shin I (2014) Mixed-criticality scheduling on multiprocessors. Real-Time Syst 50(1):142-177.

Digital Library

Google Scholar

[6]

Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In: RTSS, pp. 3-12.

Crossref

Google Scholar

[7]

Baruah S, Li H, Stougie L (2010) Towards the design of certifiable mixed-criticality systems. In: RTAS, pp. 13-22.

Crossref

Google Scholar

[8]

Burns A, Davis R (2013) Mixed criticality systems: a review. http://www-users.cs.york.ac.uk/burns/review.pdf

Google Scholar

[9]

Certainty. D8.3--validation results. Technical report (2014).

Google Scholar

[10]

Chang C-S (2000) Performance guarantees in communication networks. Springer, New York.

Crossref

Google Scholar

[11]

Cruz RL (1991) A calculus for network delay. I. Network elements in isolation. IEEE Trans Inf Theory 37(1):114-131.

Digital Library

Google Scholar

[12]

de Dinechin B, Ayrignac R, Beaucamps P-E, Couvert P, Ganne B, de Massas P, Jacquet F, Jones S, Chaisemartin N, Riss F, Strudel T (2013) A clustered manycore processor architecture for embedded and accelerated applications. In: HPEC, pp. 1-6.

Google Scholar

[13]

de Dinechin B, van Amstel D, Poulhies M, Lager G (2014) Time-critical computing on a single-chip massively parallel processor. In: DATE, pp. 1-6.

Crossref

Google Scholar

[14]

Diemer J, Ernst R (2010) Back suction: service guarantees for latency-sensitive on-chip networks. In: NOCS, pp. 155-162.

Crossref

Google Scholar

[15]

European commission's 7th framework programme: Certification of real-time applications designed for mixed criticality (certainty). www.certainty-project.eu

Google Scholar

[16]

Flodin J, Lampka K, Yi W (2014) Dynamic budgeting for settling dram contention of co-running hard and soft real-time tasks. In: SIES, pp. 151-159.

Google Scholar

[17]

Giannopoulou G, Lampka K, Stoimenov N, Thiele L (2012) Timed model checking with abstractions: towards worst-case response time analysis in resource-sharing manycore systems. In: EMSOFT, pp. 63-72.

Crossref

Google Scholar

[18]

Giannopoulou G, Stoimenov N, Huang P, Thiele L (2013) Scheduling of mixed-criticality applications on resource-sharing multicore systems. In: EMSOFT, pp. 17:1-17:15.

Crossref

Google Scholar

[19]

Giannopoulou G, Stoimenov N, Huang P, Thiele L (2014) Mapping mixed-criticality applications on multicore architectures. In: DATE, pp. 1-6.

Crossref

Google Scholar

[20]

Goossens S, Akesson B, Goossens K (2013) Conservative open-page policy for mixed time-criticality memory controllers. In: DATE, pp. 525-530.

Crossref

Google Scholar

[21]

Hahn S, Reineke J, Wilhelm R (2013) Towards compositionality in execution time analysis-definition and challenges. In: Workshop on compositional theory and technology for real-time embedded systems.

Google Scholar

[22]

Kim H, de Niz D, Andersson B, Klein M, Mutlu O, Rajkumar RR (2014) Bounding memory interference delay in cots-based multi-core systems. In: RTAS, pp. 145-154.

Google Scholar

[23]

Kim Y, Lee J, Shrivastava A, Paek Y (2010) Operation and data mapping for cgras with multi-bank memory. In: LCTES, pp. 17-26.

Crossref

Google Scholar

[24]

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671-680.

Crossref

Google Scholar

[25]

Le Boudec J-Y, Thiran P (2001) Network calculus: a theory of deterministic queuing systems for the internet, vol 2050. Springer, New York.

Crossref

Google Scholar

[26]

Li H, Baruah S (2012) Global mixed-criticality scheduling on multiprocessors. In: ECRTS, pp. 166-175.

Crossref

Google Scholar

[27]

Liu L, Cui Z, Xing M, Bao Y, Chen M, Wu C (2012) A software memory partition approach for eliminating bank-level interference in multicore systems. In: PACT, pp. 367-376.

Crossref

Google Scholar

[28]

Lu Z, Millberg M, Jantsch A, Bruce A, van der Wolf P, Henriksson T (2009) Flow regulation for on-chip communication. In: DATE, pp. 578-581.

Crossref

Google Scholar

[29]

Melpignano D, Benini L, Flamand E, Jego B, Lepley T, Haugou G, Clermidy F, Dutoit D (2012) Platform 2012, a many-core computing accelerator for embedded socs: performance evaluation of visual analytics applications. In: DAC, pp. 1137-1142.

Crossref

Google Scholar

[30]

Mi W, Feng X, Xue J, Jia Y (2010) Software-hardware cooperative dram bank partitioning for chip multiprocessors. In: Network and parallel computing, vol 6289. Lecture note on computer science, pp. 329-343.

Crossref

Google Scholar

[31]

Mollison M, Erickson J, Anderson J, Baruah S, Scoredos J, et al (2010) Mixed-criticality real-time scheduling for multicore systems. In: ICCIT, pp. 1864-1871.

Crossref

Google Scholar

[32]

Paolieri M, Qui nones E, Cazorla FJ, Bernat G, Valero M (2009) Hardware support for wcet analysis of hard real-time multicore systems. In: ISCA, pp. 57-68.

Crossref

Google Scholar

[33]

Pathan R (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: ECRTS, pp. 309-320.

Crossref

Google Scholar

[34]

Pellizzoni R, Bui BD, Caccamo M, Sha L (2008) Coscheduling of cpu and i/o transactions in cots-based embedded systems. In: RTSS, pp. 221-231.

Crossref

Google Scholar

[35]

Qian Y, Lu Z, Dou W (2009) Analysis of communication delay bounds for network on chips. In: NOCS.

Google Scholar

[36]

Qian Y, Lu Z, Dou W (2010) Analysis of worst-case delay bounds for on-chip packet-switching networks. IEEE Trans Comput Aided Design Integr Circ Syst 29(5):802-815.

Digital Library

Google Scholar

[37]

Reineke J, Liu I, Patel HD, Kim S, Lee EA (2011) Pret dram controller: bank privatization for predictability and temporal isolation. In: CODES+ISSS, pp. 99-108.

Crossref

Google Scholar

[38]

RTCA/DO-178B (1992) Software considerations in airborne systems and equipment certification Tamas-Selicean D, Pop P (2011) Design optimization of mixed-criticality real-time applications on cost-constrained partitioned architectures. In: RTSS, pp. 24-33.

Crossref

Google Scholar

[39]

Thiele L, Chakraborty S, Naedele M (2000) Real-time calculus for scheduling hard real-time systems. In: ISCAS, pp. 101-104.

Google Scholar

[40]

The dol-critical framework for mixed-criticality applications on multicores. https://www.tik.ee.ethz.ch/certainty/download.html

Google Scholar

[41]

Thiele L, Stoimenov N (2009) Modular performance analysis of cyclic dataflow graphs. In: EMSOFT, pp. 127-136.

Crossref

Google Scholar

[42]

Tobuschat S, Axer P, Ernst R, Diemer J (2013) Idamc: a noc for mixed criticality systems. In: RTCSA, pp. 149-156.

Google Scholar

[43]

Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: RTSS, pp. 239-243.

Crossref

Google Scholar

[44]

Wandeler E, Maxiaguine A, Thiele L (2006) Performance analysis of greedy shapers in real-time systems. In: DATE, pp. 444-449, Munich, Germany.

Crossref

Google Scholar

[45]

Wandeler E, Thiele L, Verhoef M, Lieverse P (2006) System architecture evaluation using modular performance analysis--a case study. Int J Softw Tools Technol Transf 8(6):649-667.

Digital Library

Google Scholar

[46]

Wilhelm R, Grund D, Reineke J, Schlickling M, Pister M, Ferdinand C (2009) Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Trans Comput Aided Design Integr Circ Syst 28(7):966-978.

Digital Library

Google Scholar

[47]

Wu ZP, Krish Y, Pellizzoni R (2013) Worst case analysis of dram latency in multi-requestor systems. In: RTSS, pp. 372-383.

Crossref

Google Scholar

[48]

Yun H, Mancuso R, Wu Z-P, Pellizzoni R (2014) Palloc: dram bank-aware memory allocator for performance isolation on multicore platforms. In: RTAS, pp. 155-166.

Google Scholar

[49]

Yun H, Yao G, Pellizzoni R, Caccamo M, Sha L (2012) Memory access control in multiprocessor for real-time systems with mixed criticality. In: ECRTS, pp. 299-308.

Crossref

Google Scholar

[50]

Zhan J, Stoimenov N, Ouyang J, Thiele L, Narayanan V, Xie Y (2013) Designing energy-efficient noc for real-time embedded systems through slack optimization. In: DAC, pp. 1-6.

Crossref

Google Scholar

Cited By

View all

Afshari FAbdi A(2024)Qsmix: Q-learning-based task scheduling approach for mixed-critical applications on heterogeneous multi-coresThe Journal of Supercomputing10.1007/s11227-024-06096-880:12(17895-17922)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11227-024-06096-8
Gomatheeshwari BGopi KMathias A(2023)Low-complex resource mapping heuristics for mobile and iot workloads on NoC-HMPSoC architectureMicroprocessors & Microsystems10.1016/j.micpro.2023.10480298:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104802
Teich JPourmohseni BKeszocze OSpieck JWildermann SCheng KYang H(2020)Run-Time Enforcement of Non-Functional Application Requirements in Heterogeneous Many-Core SystemsProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045536(629-636)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045536
Show More Cited By

Index Terms

Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Hardware
  1. Robustness

Recommendations

Cluster-based multicore real-time mixed-criticality scheduling

A cluster-based scheduling approach is proposed, to schedule the mixed-criticality task sets on multicore processors.This approach uses smaller cluster sizes (sub-cluster) in low criticality mode, and relatively larger cluster sizes in high criticality ...
A New RTA Based Scheduling Algorithm for Mixed-Criticality Systems
CSE '13: Proceedings of the 2013 IEEE 16th International Conference on Computational Science and Engineering

An increasing trend in many safety-critical embedded system is to integrate multiple functional components into a shared hardware platform for better cost and power efficiency. This mixed criticality system offers challenges both for static ...
Communication-aware task assignment algorithm for MPSoC using shared memory

In a Multi-Processor System-on-a-Chip (MPSoC) based on Network-on-Chip (NoC), which processes massive data in a distributed fashion, communication is concentrated on shared memory. This paper proposes an assignment algorithm that can minimize the total ...

Reviews

Reviewer: Cristiana Bolchini

Giannopoulou and colleagues describe their approach for the scheduling of mixed-criticality applications on many-core systems. The paper initially provides an overview of solutions for the scheduling and mapping of this kind of application onto platforms with resource contention issues, to allow the reader to understand what issues still need to be addressed and why existing strategies do not suffice. Then, notions on the adopted models for the system, the architecture (resources and communication), and the applications are introduced. The authors present all the aspects of the proposed solution, starting with flexible time-triggered scheduling (FTTS) proposed by them in a previous publication, on top of which they build the new proposal. Section 5 specifically introduces the strategy to compute function barriers for an FTTS schedule, and then to bound the delay on the shared-memory path, also taking into account data transfers over the communication network. Once these elements are computed and the scheduling constraints are identified, it is possible to map the mixed-criticality application tasks on the available computing resources, such that constraints are satisfied and workload is balanced among the cores. This is the key optimization proposal discussed in the paper and is compared against existing solutions in the subsequent sections. The evaluation is performed with respect to a case study of a flight management system application. (The reference in the paper pointing to the source code, is erroneous; the correct one is http://www.tik.ee.ethz.ch/~certainty/download.html.) An in-depth analysis of the achieved results is reported on the effects of the identified solutions, taking into account different platforms (for example, different number of memory banks, variable access times, and so on). Finally, a comparison against two solutions by another research team is performed, showing how the innovative approach outperforms the previous ones. In 2014, a few new solutions were proposed, and more recent ones are also available. A new publication with broader comparisons could provide a more interesting perspective on this work. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Real-Time Systems Volume 52, Issue 4

July 2016

165 pages

ISSN:0922-6443

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 July 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Afshari FAbdi A(2024)Qsmix: Q-learning-based task scheduling approach for mixed-critical applications on heterogeneous multi-coresThe Journal of Supercomputing10.1007/s11227-024-06096-880:12(17895-17922)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11227-024-06096-8
Gomatheeshwari BGopi KMathias A(2023)Low-complex resource mapping heuristics for mobile and iot workloads on NoC-HMPSoC architectureMicroprocessors & Microsystems10.1016/j.micpro.2023.10480298:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104802
Teich JPourmohseni BKeszocze OSpieck JWildermann SCheng KYang H(2020)Run-Time Enforcement of Non-Functional Application Requirements in Heterogeneous Many-Core SystemsProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045536(629-636)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045536
Nair AColaco LPatil GRaveendran BPunnekkatt SDe Rango FCalafate CVoznak M(2019)MEDIATORProceedings of the 23rd IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications10.5555/3395101.3395128(146-153)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.5555/3395101.3395128
Graillat AMaiza CMoy MRaymond Pde Dinechin BErmont JSong YGill C(2019)Response time analysis of dataflow applications on a many-core processor with shared-memory and network-on-chipProceedings of the 27th International Conference on Real-Time Networks and Systems10.1145/3356401.3356416(61-69)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3356401.3356416
Maiza CRihani HRivas JGoossens JAltmeyer SDavis R(2019)A Survey of Timing Verification Techniques for Multi-Core Real-Time SystemsACM Computing Surveys10.1145/332321252:3(1-38)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323212
Avramenko SViolante M(2019)RTOS Solution for NoC-Based COTS MPSoC Usage in Mixed-Criticality SystemsJournal of Electronic Testing: Theory and Applications10.1007/s10836-019-05779-y35:1(29-44)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10836-019-05779-y
Becker MMubeen SDasari DBehnam MNolte TShin Y(2018)Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraintsProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201738(560-567)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201738
Becker MMubeen SDasari DBehnam MNolte T(2018)Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2018.8297382(560-567)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.1109/ASPDAC.2018.8297382
Giannopoulou GPoplavko PSocci DHuang PStoimenov NBourgos PThiele LBozga MBensalem SGirbal SFaugere MSoulat RDinechin B(2018)DOL-BIP-CriticalDesign Automation for Embedded Systems10.1007/s10617-018-9206-322:1-2(141-181)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10617-018-9206-3
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Cluster-based multicore real-time mixed-criticality scheduling

A New RTA Based Scheduling Algorithm for Mixed-Criticality Systems

Communication-aware task assignment algorithm for MPSoC using shared memory

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations