[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3078659.3078663acmotherconferencesArticle/Chapter ViewAbstractPublication PagesscopesConference Proceedingsconference-collections
research-article
Open access

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

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[17]
B. D. McKay and A. Piperno. Practical graph isomorphism, {II}. Journal of Symbolic Computation, 60(0):94--112, 2014.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Recommendations

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
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2017

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Heterogeneous
  2. MPSoC
  3. adaptivity
  4. multi-application
  5. run-time
  6. symmetry

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

  • DFG

Conference

SCOPES '17

Acceptance Rates

SCOPES '17 Paper Acceptance Rate 6 of 9 submissions, 67%;
Overall Acceptance Rate 38 of 79 submissions, 48%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)126
  • Downloads (Last 6 weeks)31
Reflects downloads up to 25 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (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
  • (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
  • (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
  • (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
  • (2024)Methodologies for Design Space ExplorationHandbook of Computer Architecture10.1007/978-981-97-9314-3_23(915-945)Online publication date: 21-Dec-2024
  • (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
  • (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
  • (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
  • (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
  • (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
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media