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.
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. East, A. Egri-Nagy, J. Mitchell, and Y. Péresse. Computing finite semigroups. arXiv eprints.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- A. Goens, S. Siccha, and J. Castrillon. Symmetry in software synthesis. arXiv e-prints, Apr. 2017.Google Scholar
- P. Greenhalgh. Big. little processing with arm cortex-a l5 & cortex-a7. ARM White paper, pages 1--8, 2011.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- B. D. McKay and A. Piperno. Practical graph isomorphism, {II}. Journal of Symbolic Computation, 60(0):94--112, 2014. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Olofsson. Epiphany-v: A 1024 processor 64-bit risc system-on-chip. arXiv preprint arXiv: 1610.01832, 2016.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Silexica. SLXMapper, 2016.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Zhu, L. Chen, S. Yue, T. Pinkston, and M. Pedram. Providing balanced mapping for multiple applications in many-core chip multiprocessors.Google Scholar
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 PlatformsModern 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 systemsThe 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