Abstract
The application workloads in modern MPSoC-based embedded systems are becoming increasingly dynamic. Different applications concurrently execute and contend for resources in such systems, which could cause serious changes in the intensity and nature of the workload demands over time. To cope with the dynamism of application workloads at runtime and improve the efficiency of the underlying system architecture, this article presents a hybrid task mapping algorithm that combines a static mapping exploration and a dynamic mapping optimization to achieve an overall improvement of system efficiency. We evaluate our algorithm using a heterogeneous MPSoC system with three real applications. Experimental results reveal the effectiveness of our proposed algorithm by comparing derived solutions to the ones obtained from several other runtime mapping algorithms. In test cases with three simultaneously active applications, the mapping solutions derived by our approach have average performance improvements ranging from 45.9% to 105.9% and average energy savings ranging from 14.6% to 23.5%.
- Mohammad Abdullah Al Faruque, Rudolf Krist, and Jörg Henkel. 2008. ADAM: Run-time agent-based distributed application mapping for on-chip communication. In Proceedings of the 45th Annual Design Automation Conference (DAC’08). ACM, New York, NY, 760--765. DOI: http://dx.doi.org/10.1145/1391469. 1391664 Google ScholarDigital Library
- Eduardo Wenzel Brião, Daniel Barcelos, and Flávio Rech Wagner. 2008. Dynamic task allocation strategies in MPSoC for soft real-time applications. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’08). ACM, New York, NY, 1386--1389. DOI: http://dx.doi.org/10.1145/1403375.1403709 Google ScholarDigital Library
- Emanuele Cannella, Onur Derin, Paolo Meloni, Giuseppe Tuveri, and Todor Stefanov. 2012. Adaptivity support for MPSoCs based on process migration in polyhedral process networks. VLSI Des. 2012, Article 2 (Jan. 2012), 1 page. DOI: http://dx.doi.org/10.1155/2012/987209 Google ScholarDigital Library
- Jeronimo Castrillon, Rainer Leupers, and Gerd Ascheid. 2011. MAPS: Mapping concurrent dataflow applications to heterogeneous MPSoCs. IEEE Trans. Indust. Inf. PP, 99 (2011), 1. DOI: http://dx.doi.org/10.1109/TII.2011.2173941Google Scholar
- Chen-Ling Chou and R. Marculescu. 2008. User-aware dynamic task allocation in networks-on-chip. In Proceedings of the Design, Automation and Test in Europe (DATE’08). 1232--1237. DOI: http://dx.doi.org/10.1109/DATE.2008.4484847 Google ScholarDigital Library
- Cagkan Erbas, Selin Cerav-Erbas, and Andy D. Pimentel. 2006. Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design. IEEE Trans. Evolut. Comput. 10, 3 (2006), 358--374. Google ScholarDigital Library
- Stefan Valentin Gheorghita, Martin Palkovic, Juan Hamers, Arnout Vandecappelle, Stelios Mamagkakis, Twan Basten, Lieven Eeckhout, Henk Corporaal, Francky Catthoor, Frederik Vandeputte, and Koen De Bosschere. 2009. System-scenario-based design of dynamic embedded systems. ACM Trans. Des. Autom. Electron. Syst. 14, 1, Article 3 (Jan. 2009), 45 pages. DOI: http://dx.doi.org/10.1145/1455229.1455232 Google ScholarDigital Library
- Philip K. F. Hölzenspies, Johann L. Hurink, Jan Kuper, and Gerard J. M. Smit. 2008. Run-time spatial mapping of streaming applications to a heterogeneous multi-processor system-on-chip (MPSoC). In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’08). ACM, New York, NY, 212--217. DOI: http://dx.doi.org/10.1145/1403375.1403427 Google ScholarDigital Library
- Jia Huang, A. Raabe, C. Buckl, and A. Knoll. 2011. A workflow for runtime adaptive task allocation on heterogeneous MPSoCs. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’11). 1--6. DOI: http://dx.doi.org/10.1109/DATE.2011.5763189Google Scholar
- Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In Information Processing. North Holland, Amsterdam, 471--475.Google Scholar
- Rakesh Kumar, Dean M. Tullsen, Parthasarathy Ranganathan, Norman P. Jouppi, and Keith I. Farkas. 2004. Single-ISA heterogeneous multi-core architectures for multithreaded workload performance. In Proceedings of the 31st Annual International Symposium on Computer Architecture (ISCA’04). IEEE Computer Society, Washington, DC, 64. Google ScholarDigital Library
- G. Mariani, P. Avasare, G. Vanmeerbeeck, C. Ykman-Couvreur, G. Palermo, C. Silvano, and V. Zaccaria. 2010. An industrial design space exploration framework for supporting run-time resource management on multi-core systems. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’10). 196--201. DOI: http://dx.doi.org/10.1109/DATE.2010.5457211 Google ScholarDigital Library
- JoAnn M. Paul, Donald E. Thomas, and Alex Bobrek. 2006. Scenario-oriented design for single-chip heterogeneous multiprocessors. IEEE Trans. VLSI Syst. 14, 8 (2006), 868--880. DOI: http://dx.doi.org/10.1109/TVLSI.2006.878474 Google ScholarDigital Library
- Andy D. Pimentel, Cagkan Erbas, and Simon Polstra. 2006. A systematic approach to exploring embedded system architectures at multiple abstraction levels. IEEE Trans. Comput. 55, 2 (2006), 99--112. Google ScholarDigital Library
- Wei Quan and A. D. Pimentel. 2013a. An iterative multi-application mapping algorithm for heterogeneous MPSoCs. In Proceedings of the 2013 IEEE 11th Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia’13). 115--124. DOI: http://dx.doi.org/10.1109/ESTIMedia.2013.6704510Google Scholar
- Wei Quan and Andy D. Pimentel. 2013b. A scenario-based run-time task mapping algorithm for MPSoCs. In Proceedings of the 50th Annual Design Automation Conference (DAC’13). ACM, New York, NY, Article 131, 6 pages. DOI: http://dx.doi.org/10.1145/2463209.2488895 Google ScholarDigital Library
- Lars Schor, Iuliana Bacivarov, Devendra Rai, Hoeseok Yang, Shin-Haeng Kang, and Lothar Thiele. 2012. Scenario-based design flow for mapping streaming applications onto on-chip many-core systems. In Proceedings of the 2012 International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES’12). ACM, New York, NY, 71--80. DOI: http://dx.doi.org/10.1145/2380403.2380422 Google ScholarDigital Library
- Andreas Schranzhofer, Jian-Jian Chen, and Lothar Thiele. 2010. Dynamic power-aware mapping of applications onto heterogeneous MPSoC platforms. IEEE Transactions on Industrial Informatics 6, 4 (2010), 692--707. DOI: http://dx.doi.org/10.1109/TII.2010.2062192Google ScholarCross Ref
- Amit Kumar Singh, Akash Kumar, and Thambipillai Srikanthan. 2013a. Accelerating throughput-aware runtime mapping for heterogeneous MPSoCs. ACM Trans. Des. Autom. Electron. Syst. 18, 1 (Jan. 2013), Article 9, 29 pages. DOI: http://dx.doi.org/10.1145/2390191.2390200 Google ScholarDigital Library
- Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and Jörg Henkel. 2013b. Mapping on multi/many-core systems: Survey of current and emerging trends. In Proceedings of the 50th Annual Design Automation Conference (DAC’13). ACM, New York, NY, Article 1, 10 pages. DOI: http://dx.doi.org/10.1145/2463209.2488734 Google ScholarDigital Library
- Wei Sun and Tomoyoshi Sugawara. 2011. Heuristics and evaluations of energy-aware task mapping on heterogeneous multiprocessors. In Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW’11). 599--607. DOI: http://dx.doi.org/10.1109/IPDPS.2011.209 Google ScholarDigital Library
- P. van Stralen and A. Pimentel. 2010a. Scenario-based design space exploration of MPSoCs. In Proceedings of the 2010 IEEE International Conference on Computer Design (ICCD’10). 305--312. DOI: http://dx.doi.org/10.1109/ICCD.2010.5647727Google ScholarCross Ref
- P. van Stralen and A. D. Pimentel. 2010b. A trace-based scenario database for high-level simulation of multimedia MP-SoCs. In Embedded Computer Systems (SAMOS), 2010 International Conference on. 11--19. DOI: http://dx.doi.org/10.1109/ICSAMOS.2010.5642097Google Scholar
- C. Ykman-Couvreur, P. Avasare, G. Mariani, G. Palermo, C. Silvano, and V. Zaccaria. 2011. Linking run-time resource management of embedded multi-core platforms with automated design-time exploration. Computers Digital Techniques, IET 5, 2 (2011), 123--135. DOI: http://dx.doi.org/10.1049/iet-cdt.2010.0030Google ScholarCross Ref
Index Terms
- A Hybrid Task Mapping Algorithm for Heterogeneous MPSoCs
Recommendations
A scenario-based run-time task mapping algorithm for MPSoCs
DAC '13: Proceedings of the 50th Annual Design Automation ConferenceThe application workloads in modern MPSoC-based embedded systems are becoming increasingly dynamic. Different applications concurrently execute and contend for resources in such systems which could cause serious changes in the intensity and nature of ...
A hierarchical run-time adaptive resource allocation framework for large-scale MPSoC systems
In the embedded computer system domain, MPSoC systems have become increasingly popular due to the ever-increasing performance demands of modern embedded applications. The number of processing elements in these MPSoCs also steadily increases. Whereas ...
Task Mapping in Heterogeneous MPSoCs for System Level Design
ICECCS '08: Proceedings of the 13th IEEE International Conference on on Engineering of Complex Computer SystemsThis paper investigates automatic mapping of application-to-architecture in heterogeneous Multi Processor System on a Chip (MPSoC), a key problem in system level design of embedded systems. An algorithm is proposed to optimally solve this application-to-...
Comments