More Web Proxy on the site http://driver.im/

research-article

Open access

TETRiS: a Multi-Application Run-Time System for Predictable Execution of Static Mappings

Authors:

Robert Khasanov,

Jeronimo Castrillon,

Marcus Hähnel,

Hermann HärtigAuthors Info & Claims

SCOPES '17: Proceedings of the 20th International Workshop on Software and Compilers for Embedded Systems

Pages 11 - 20

https://doi.org/10.1145/3078659.3078663

Published: 12 June 2017 Publication History

Abstract

For embedded system software, it is common to use static mappings of tasks to cores. This becomes considerably more challenging in multi-application scenarios. In this paper, we propose TETRiS, a multi-application run-time system for static mappings for heterogeneous system-on-chip architectures. It leverages compile-time information to map and migrate tasks in a fashion that preserves the predictable performance of using static mappings, allowing the system to accommodate multiple applications. TETRiS runs on off-the-shelf embedded systems and is Linux-compatible. We embed our approach in a state-of-the-art compiler for multicore systems and evaluate the proposed run-time system in a modern heterogeneous platform using realistic benchmarks. We present two experiments whose execution time and energy consumptions are comparable to those obtained by the highly-optimized Linux scheduler CFS, and where execution time variance is reduced by a factor of 510, and energy consumption variance by a factor of 83.

References

[1]

P. Axer, R. Ernst, H. Falk, A. Girault, D. Grund, N. Guan, B. Jonsson, P. Marwedel, J. Reineke, C. Rochange, et al. Building timing predictable embedded systems. ACM Transactions on Embedded Computing Systems (TECS), 13(4):82, 2014.

Digital Library

[2]

M. Bekooij, O. Moreira, P. Poplavko, B. Mesman, M. Pastrnak, and J. Van Meerbergen. Predictable embedded multiprocessor system design. In International Workshop on Software and Compilers for Embedded Systems, pages 77--91. Springer, 2004.

[3]

J. Castrillon, A. Tretter, R. Leupers, and G. Ascheid. Communication-Aware Mapping of KPN Applications onto Heterogeneous MPSoCs. In DAC '12: Proceedings of the 49th annual conference on Design automation, 2012.

Digital Library

[4]

J. Castrillon, R. Velasquez, A. Stulova, W. Sheng, J. Ceng, R. Leupers, G. Ascheid, and H. Meyr. Trace-based kpn composability analysis for mapping simultaneous applications to mpsoc platforms. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 753--758. European Design and Automation Association, 2010.

Digital Library

[5]

J. Ceng, J. Castrillon, W. Sheng, H. Scharwächter, R. Leupers, G. Ascheid, H. Meyr, T. Isshiki, and H. Kunieda. Maps: an integrated framework for mpsoc application parallelization. In Proceedings of the 45th annual Design Automation Conference, pages 754--759. ACM, 2008.

Digital Library

[6]

J. East, A. Egri-Nagy, J. Mitchell, and Y. Péresse. Computing finite semigroups. arXiv eprints.

[7]

S. A. Edwards and E. A. Lee. The case for the precision timed (pret) machine. In Proceedings of the 44th annual Design Automation Conference, pages 264--265. ACM, 2007.

Digital Library

[8]

J. Eker, J. W. Janneck, E. A. Lee, J. Liu, X. Liu, J. Ludvig, S. Neuendorffer, S. Sachs, and Y. Xiong. Taming heterogeneity-the ptolemy approach. Proceedings of the IEEE, 91(1):127--144, 2003.

[9]

A. Goens and J. Castrillon. Analysis of process traces for mapping dynamic kpn applications to mpsocs. In Proceedings of the IFIP International Embedded Systems Symposium (IESS), Foz do Iguaçu, Brazil, Nov. 2015.

[10]

A. Goens, S. Siccha, and J. Castrillon. Symmetry in software synthesis. arXiv e-prints, Apr. 2017.

[11]

P. Greenhalgh. Big. little processing with arm cortex-a l5 & cortex-a7. ARM White paper, pages 1--8, 2011.

[12]

A. Hansson, K. Goossens, M. Bekooij, and J. Huisken. Compsoc: A template for composable and predictable multi-processor system on chips. ACM Transactions on Design Automation of Electronic Systems (TODAES), 14(1):2, 2009.

Digital Library

[13]

G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information processing, pages 471--475, Stockholm, Sweden, Aug 1974. North Holland, Amsterdam.

[14]

S.-h. Kang, H. Yang, S. Kim, I. Bacivarov, S. Ha, and L. Thiele. Static mapping of mixed-critical applications for fault-tolerant mpsocs. In Proceedings of the 51st Annual Design Automation Conference, pages 1--6. ACM, 2014.

Digital Library

[15]

A. Kumar, B. Mesman, B. Theelen, H. Corporaal, and Y. Ha. Analyzing composability of applications on mpsoc platforms. Journal of Systems Architecture, 54(3):369--383, 2008.

Digital Library

[16]

E. A. Lee. Cyber physical systems: Design challenges. In 2008 11th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC), pages 363--369. IEEE, 2008.

Digital Library

[17]

B. D. McKay and A. Piperno. Practical graph isomorphism, {II}. Journal of Symbolic Computation, 60(0):94--112, 2014.

Digital Library

[18]

O. Moreira, J. J.-D. Mol, and M. Bekooij. Online resource management in a multiprocessor with a network-on-chip. In Proceedings of the 2007 ACM symposium on Applied computing, pages 1557--1564. ACM, 2007.

Digital Library

[19]

H. Nikolov, M. Thompson, T. Stefanov, A. Pimentel, S. Polstra, R. Bose, C. Zissulescu, and E. Deprettere. Daedalus: toward composable multimedia mp-soc design. In Proceedings of the 45th annual Design Automation Conference, pages 574--579. ACM, 2008.

Digital Library

[20]

A. Olofsson. Epiphany-v: A 1024 processor 64-bit risc system-on-chip. arXiv preprint arXiv: 1610.01832, 2016.

[21]

A. D. Pimentel, C. Erbas, and S. Polstra. A systematic approach to exploring embedded system architectures at multiple abstraction levels. IEEE Transactions on Computers, 55(2):99--112, 2006.

Digital Library

[22]

W. Quan and A. D. Pimentel. A hierarchical run-time adaptive resource allocation framework for large-scale mpsoc systems. Design Automation for Embedded Systems, pages 1--29, 2016.

Digital Library

[23]

Silexica. SLXMapper, 2016.

[24]

A. K. Singh, M. Shafique, A. Kumar, and J. Henkel. Mapping on multi/many-core systems: survey of current and emerging trends. In Proceedings of the 50th Annual Design Automation Conference, page 1. ACM, 2013.

Digital Library

[25]

L. Thiele, I. Bacivarov, W. Haid, and K. Huang. Mapping applications to tiled multiprocessor embedded systems. In Application of Concurrency to System Design, 2007. ACSD 2007. Seventh International Conference on, pages 29--40. IEEE, 2007.

Digital Library

[26]

A. Weichslgartner, D. Gangadharan, S. Wildermann, M. Glaß, and J. Teich. Daarm: Design-time application analysis and run-time mapping for predictable execution in many-core systems. In Hardware/Software Codesign and System Synthesis (CODES+ ISSS), 2014 International Conference on, pages 1--10. IEEE, 2014.

Digital Library

[27]

A. Weichslgartner, S. Wildermann, J. Götzfried, F. Freiling, M. Glaß, and J. Teich. Design-time/run-time mapping of security-critical applications in heterogeneous mpsocs. In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems, pages 153--162. ACM, 2016.

Digital Library

[28]

D. Zhu, L. Chen, S. Yue, T. Pinkston, and M. Pedram. Providing balanced mapping for multiple applications in many-core chip multiprocessors.

Cited By

Khasanov RDietrich MCastrillon J(2024)Flexible Spatio-Temporal Energy-Efficient Runtime Management2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC58780.2024.10473885(777-784)Online publication date: 22-Jan-2024
https://doi.org/10.1109/ASP-DAC58780.2024.10473885
Dallant JIacono J(2024)How fast can we play Tetris greedily with rectangular pieces?Theoretical Computer Science10.1016/j.tcs.2024.114405992:COnline publication date: 21-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114405
Chen XKrishnakumar AOgras UChakrabarti C(2024)PED: Probabilistic Energy-efficient Deadline-aware scheduler for heterogeneous SoCsJournal of Systems Architecture10.1016/j.sysarc.2023.103051147(103051)Online publication date: Feb-2024
https://doi.org/10.1016/j.sysarc.2023.103051
Show More Cited By

Recommendations

Symmetry in Software Synthesis

With the surge of multi- and many-core systems, much research has focused on algorithms for mapping and scheduling on these complex platforms. Large classes of these algorithms face scalability problems. This is why diverse methods are commonly used for ...
Implicit Data-Parallelism in Kahn Process Networks: Bridging the MacQueen Gap
PARMA-DITAM '18: Proceedings of the 9th Workshop and 7th Workshop on Parallel Programming and RunTime Management Techniques for Manycore Architectures and Design Tools and Architectures for Multicore Embedded Computing Platforms

Modern embedded systems are rapidly increasing their complexity, both in terms of numbers of cores, as well as heterogeneity. To generate efficient code for these systems, it is common to leverage formal models of computation. Among these, the dataflow ...
From sequential programming to flexible parallel execution
CASES '12: Proceedings of the 2012 international conference on Compilers, architectures and synthesis for embedded systems

The embedded computing landscape is being transformed by three trends: growing demand for greater functionality and enriched user experience, increasing diversity and parallelism in the processing substrate, and an accelerating push for ever-greater ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SCOPES '17: Proceedings of the 20th International Workshop on Software and Compilers for Embedded Systems

June 2017

100 pages

ISBN:9781450350396

DOI:10.1145/3078659

Editor:
Sander Stuijk
Eindhoven University of Technology, The Netherlands

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

EDAA: European Design Automation Association
SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

DFG

Conference

SCOPES '17

SCOPES '17: 20th International Workshop on Software and Compilers for Embedded Systems

June 12 - 13, 2017

Sankt Goar, Germany

Acceptance Rates

SCOPES '17 Paper Acceptance Rate 6 of 9 submissions, 67%;

Overall Acceptance Rate 38 of 79 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
580
Total Downloads

Downloads (Last 12 months)126
Downloads (Last 6 weeks)31

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khasanov RDietrich MCastrillon J(2024)Flexible Spatio-Temporal Energy-Efficient Runtime Management2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC58780.2024.10473885(777-784)Online publication date: 22-Jan-2024
https://doi.org/10.1109/ASP-DAC58780.2024.10473885
Dallant JIacono J(2024)How fast can we play Tetris greedily with rectangular pieces?Theoretical Computer Science10.1016/j.tcs.2024.114405992:COnline publication date: 21-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114405
Chen XKrishnakumar AOgras UChakrabarti C(2024)PED: Probabilistic Energy-efficient Deadline-aware scheduler for heterogeneous SoCsJournal of Systems Architecture10.1016/j.sysarc.2023.103051147(103051)Online publication date: Feb-2024
https://doi.org/10.1016/j.sysarc.2023.103051
Castrillon JDesnos KGoens AMenard C(2024)Dataflow Models of Computation for Programming Heterogeneous MulticoresHandbook of Computer Architecture10.1007/978-981-97-9314-3_45(1107-1146)Online publication date: 21-Dec-2024
https://doi.org/10.1007/978-981-97-9314-3_45
Pimentel A(2024)Methodologies for Design Space ExplorationHandbook of Computer Architecture10.1007/978-981-97-9314-3_23(915-945)Online publication date: 21-Dec-2024
https://doi.org/10.1007/978-981-97-9314-3_23
Niknafs MEles PPeng Z(2023)Runtime Resource Management with Multiple-Step-Ahead Workload PredictionACM Transactions on Embedded Computing Systems10.1145/360521322:4(1-34)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3605213
Bloch ACasale-Brunet SMattavelli M(2023)Design Space Exploration for Partitioning Dataflow Program on CPU-GPU Heterogeneous SystemJournal of Signal Processing Systems10.1007/s11265-023-01884-695:10(1219-1229)Online publication date: 31-Jul-2023
https://doi.org/10.1007/s11265-023-01884-6
Castrillon JDesnos KGoens AMenard C(2023)Dataflow Models of Computation for Programming Heterogeneous MulticoresHandbook of Computer Architecture10.1007/978-981-15-6401-7_45-2(1-40)Online publication date: 28-Sep-2023
https://doi.org/10.1007/978-981-15-6401-7_45-2
Bloch ACasale-Brunet SMattavelli M(2022)Dynamic SIMD Parallel Execution on GPU from High-Level Dataflow SynthesisJournal of Low Power Electronics and Applications10.3390/jlpea1203004012:3(40)Online publication date: 17-Jul-2022
https://doi.org/10.3390/jlpea12030040
Bloch ACasale-Brunet SMattavelli M(2022)Performance Estimation of High-Level Dataflow Program on Heterogeneous Platforms by Dynamic Network ExecutionJournal of Low Power Electronics and Applications10.3390/jlpea1203003612:3(36)Online publication date: 23-Jun-2022
https://doi.org/10.3390/jlpea12030036
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten