Model-Based Automotive Partitioning and Mapping for Embedded Multicore Systems

Authors: Robert H¨ottger, Lukas Krawczyk, Burkhard Igel

Abstract:

This paper introduces novel approaches to partitioning and mapping in terms of model-based embedded multicore system engineering and further discusses benefits, industrial relevance and features in common with existing approaches. In order to assess and evaluate results, both approaches have been applied to a real industrial application as well as to various prototypical demonstrative applications, that have been developed and implemented for different purposes. Evaluations show, that such applications improve significantly according to performance, energy efficiency, meeting timing constraints and covering maintaining issues by using the AMALTHEA platform and the implemented approaches. Furthermore, the model-based design provides an open, expandable, platform independent and scalable exchange format between OEMs, suppliers and developers on different levels. Our proposed mechanisms provide meaningful multicore system utilization since load balancing by means of partitioning and mapping is effectively performed with regard to the modeled systems including hardware, software, operating system, scheduling, constraints, configuration and more data.

Keywords: Partitioning, mapping, distributed systems, scheduling, embedded multicore systems, model-based, system analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1099216

References:

[1] “Autosar - automotive open system architecture,” http://www.autosar.org, June 2014.
[2] “Amalthea project homepage,” http://www.amalthea-project.org/, April 2014.
[3] M. Weiser, B. Welch, A. Demers, and S. Shenker, “Scheduling for reduced cpu energy,” in Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, ser. OSDI ’94. Berkeley, CA, USA: USENIX Association, 1994. (Online). Available: http://dblp.uni-trier.de/db/conf/osdi/osdi94.html
[4] Amalthea platform: Help documentation, Itea 2 project 09013 Amalthea, www.amalthea-project.org, 2014.
[5] T. Kuhn, T. Forster, T. Braun, and R. Gotzhein, “Feral - framework for simulator coupling on requirements and architecture level.” in MEMOCODE. IEEE, 2013, pp. 11–22. (Online). Available: http://dblp.uni-trier.de/db/conf/memocode/memocode2013.html
[6] D. A. Cordes, “Automatic parallelization for embedded multi-core systems using high-level cost models,” Ph.D. dissertation, Technische Universit¨at Dortmund, 2013.
[7] T.-Y. Choe, “Task scheduling algorithm to reduce the number of processors using merge conditions,” International Journal on Computer Science and Engineering (IJCSE), February 2012.
[8] K. Kanoun, D. Atienza, N. Mastronarde, and M. van der Schaar, “A unified online directed acyclic graph flow manager for multicore schedulers,” in Design Automation Conference (ASP-DAC), 2014 19th Asia and South Pacific, 2014, pp. 714–719. (Online). Available: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6742974
[9] G. S. Hornby, L. Sekanina, and P. C. Haddow, “Evolvable systems: From biology to hardware,” in 8th International Conference, ICES 2008. Springer, 2008.
[10] G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities,” in Proceedings of the April 18-20, 1967, Spring Joint Computer Conference, ser. AFIPS ’67 (Spring), New York, NY, USA, 1967, pp. 483–485.
[11] R. Preis, “Analysis and design of efficient graph partitioning methods,” Ph.D. dissertation, University Paderborn, 2000.
[12] V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Publishing Company Redwood City, CA, 1994.
[13] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1990.
[14] C. Lucchesi, A Minimax Equality for Directed Graphs. Thesis (Ph.D.)–University of Waterloo, 1976. (Online). Available: http: //books.google.de/books?id=KA8nnQEACAAJ
[15] B. Schwikowski and E. Speckenmeyer, “On enumerating all minimal solutions of feedback problems,” Discrete Applied Mathematics, vol. 117, no. 1-3, pp. 253–265, Mar. 2002.
[16] R. Tarjan, “Depth first search and linear graph algorithms,” SIAM Journal on Computing, 1972.
[17] “Jgrapht - a free java graph library,” http://jgrapht.org/, November 2013.
[18] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009, vol. 3, ch. 21, 24 and 27.
[19] Y.-K. Kwok and I. Ahmad, “Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors,” Parallel and Distributed Systems, IEEE Transactions on, vol. 7, no. 5, pp. 506–521, 1996.
[20] T. Yang and A. Gerasoulis, “Dsc: Scheduling parallel tasks on an unbounded number of processors,” IEEE Transactions on Parallel and Distributed Systems, vol. 5, pp. 951–967, 1993.
[21] T. A. GmbH, “Personal meetings and technical discussions,” March 2014, unpublished.
[22] J. Hong, X. Tan, and D. Towsley, “A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system,” IEEE Transactions on Computers, vol. 38, no. 12, pp. 1736–1744, 1989. (Online). Available: http://ieeexplore.ieee.org/stamp/stamp.jsp? arnumber=40851
[23] M. Drozdowski, Scheduling for Parallel Processing, ser. Computer Communications and Networks. Springer, 2009.
[24] Y. Zhang, X. S. Hu, and D. Z. Chen, “Task scheduling and voltage selection for energy minimization,” in Proceedings of the 39th annual Design Automation Conference. ACM, 2002, pp. 183–188.