Model-Based Automotive Partitioning and Mapping for Embedded Multicore Systems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:69030", author = "Robert H¨ottger and Lukas Krawczyk and Burkhard Igel", title = "Model-Based Automotive Partitioning and Mapping for Embedded Multicore Systems", 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.", volume = "9", number = "1", pages = "268-7", }
