More Web Proxy on the site http://driver.im/

research-article

RunPar: an allocation algorithm for automotive applications exploiting runnable parallelism in multicores

Authors:

Sebastian Kehr,

Eduardo Quiñones,

Bert Boddecker,

Francisco J. CazorlaAuthors Info & Claims

CODES '14: Proceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis

Article No.: 29, Pages 1 - 10

https://doi.org/10.1145/2656075.2656096

Published: 12 October 2014 Publication History

Abstract

Automotive applications increasingly rely on AUTOSAR for their design and execution. AUTOSAR applications comprise functions, called runnables, that are grouped into AUTOSAR tasks. Tasks are the unit of scheduling (UoS) of the AUTOSAR operating system as the legacy of the single-core platforms. However, on multi-core platforms using tasks as UoS considerably reduces the available parallelism due to communication dependencies, which in turn reduces the potential average and guaranteed performance obtainable with multi-cores. Furthermore, running tasks in parallel requires re-validating the functional correctness of the application, since current AUTOSAR applications are designed following a sequential execution model of tasks.

In this paper, we propose a new allocation algorithm, RunPar, that considers runnables and not tasks as the UoS and assigns runnables that form tasks to different cores. RunPar improves the application performance, while keeping the sequential execution of tasks, hence not requiring any extra validation effort when migrating AUTOSAR applications from single-core to the multi-core platforms. We evaluate RunPar with a real automotive application, an Engine Management System (EMS) for which we observe an average WCET reduction on EMS' tasks of 26% and 30% in a two-core and four-core ECU.

References

[1]

Guide to multi-core systems. http://www.autosar.org, 2014.

[2]

AUTOSAR GbR. AUTomotive Open System ARchitecture (AUTOSAR) Operating System. http://www.autosar.org, February 2013.

[3]

C. Ballabriga, H. Casse, C. Rochange, and P. Sainrat. Otawa: an open toolbox for adaptive wcet analysis. In Workshop on Software technologies for Embedded and Ubiquitous Systems (SEUS), 2011.

Digital Library

[4]

S. K. Dhall and C. L. Liu. On a real-time scheduling problem. In Operation Research, pages 127--140, 1978.

Digital Library

[5]

Hamid Reza Faragardi, Björn Lisper, and Thomas Nolte. Towards a communication-efficient mapping of AUTOSAR runnables on multi-cores. In Emerging Technologies and Factory Automation (ETFA)f, pages 1--5, 2013.

[6]

Freescale. P4080 QorIQ Integrated Processor Hardware Specifications, Rev. 0, 02/2011, Doc. Num. P4080EC, 2011.

[7]

Aeroflex Gaisler. Quad Core (LEON4 SPARC V8) Processor - (LEON4-NGMP-DRAFT) - Data Sheet and Users Manual, 2011.

[8]

Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1990.

Digital Library

[9]

Infineon. AURIX - TC27x B-Step, 32-bit Sigle-Chip Micro-controller, User's Manual, v14.1, 2014-02.

[10]

ISO. Road vehicles -- Functional safety -- Part 6: Product development at the software level, Ref. num. ISO 26262-6:2011(E), 2011.

[11]

Javier Jalle, Jaume Abella, Eduardo Quiñones, Luca Fossati, Marco Zulianello, and Francisco J. Cazorla. Deconstructing bus access control policies for real-time multicores. In International Symposium on Industrial Embedded Systems (SIES), pages 31--38, 2013.

[12]

Jörg Liebeherr, Almut Burchard, Yingfeng Oh, and Sang H. Son. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Transactions on Computers, 44(12):1429--1442, 1995.

Digital Library

[13]

Aurelien Monot, Nicolas Navet, Bernard Bavoux, and Françoise Simonot-Lion. Multisource software on multicore automotive ecus - combining runnable sequencing with task scheduling. IEEE Transactions on Industrial Electronics, 59(10):3934--3942, 2012.

[14]

Yingfeng Oh and Sang H. Son. Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Systems, 9(3):207--239, 1995.

Digital Library

[15]

OSEK/VDX Group. Offene Systeme und deren Schnittstellen fuer die Elektronik im Kraftfahrzeug (OSEK) Operating System Specification. http://www.osek-vdx.org, February 2005.

[16]

Haluk Ozaktas, Christine Rochange, and Pascal Sainrat. Automatic wcet analysis of real-time parallel applications. In 13th International Workshop on Worst-Case Execution Time Analysis WCET, Satellite Workshop of ECRTS, 2013.

[17]

M. Paolieri, E. Quinones, and F. J. Cazorla. Timing effects of the memory system in real-time multicore integrated architectures: Problems and solutions. In Transactions on Embedded Computing Systems, 2012.

Digital Library

[18]

M. Paolieri, E. Quinones, F. J. Cazorla, G. Bernat, and M. Valero. Hardware support for WCET analysis of hard real-time multicore systems. In International Symposium on Computer Architecture (ISCA), 2009.

Digital Library

[19]

Padmanabhan Pillai and Kang G. Shin. Real-time dynamic voltage scaling for low-power embedded operating systems. In SOSP, pages 89--102, 2001.

Digital Library

[20]

A. Roca, C. Hernandez, J. Flich, F. Silla, and J. Duato. Enabling high-performance crossbars through a floorplan-aware design. In Intl. Conf.Parallel Processing (ICPP), pages 269--278, 2012.

Digital Library

[21]

Jorn Schneider, Michael Bohn, and Robert Robger. Migration of automotive real-time software to multicore systems: First steps towards an automated solution. In 22nd EUROMICRO Conference on Real-Time Systems, WIP Session, 2010.

[22]

O. Sinnen, L. A. Sousa, and F.-E. Sandnes. Toward a realistic task scheduling model. Parallel and Distributed Systems, IEEE Transactions on, 17(3):263--275, 2006.

Digital Library

[23]

Theo Ungerer, Francisco Cazorla, Pascal Sainrat, Guillem Bernat, Zlatko Petrov, Christine Rochange, Eduardo Quinones, Mike Gerdes, Marco Paolieri, Julian Wolf, Hugues Casse, Sascha Uhrig, Irakli Guliashvili, Michael Houston, Floria Kluge, Stefan Metzlaff, and Jorg Mische. Merasa: Multicore execution of hard real-time applications supporting analyzability. IEEE Micro, 30(5):66--75, 2010.

Digital Library

[24]

Reinhard Wilhelm, Daniel Grund, Jan Reineke, Marc Schlickling, Markus Pister, and Christian Ferdinand. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Transactions on CAD of Integrated Circuits and Systems, 28(7):966--978, 2009.

Digital Library

Cited By

Ali Ahmad MKrisper MBatista Ribeiro LBaunach MHong JPark J(2024)Avoiding Empty Instances and Offset Drifts of Basic Sequencer Tasks in Automotive Operating SystemProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635886(400-409)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3605098.3635886
Munera ARoyuela SPressler MMackamul HZiegenbein DQuiñones E(2024)Fine-grained adaptive parallelism for automotive systems through AMALTHEA and OpenMPJournal of Systems Architecture10.1016/j.sysarc.2023.103034146(103034)Online publication date: Jan-2024
https://doi.org/10.1016/j.sysarc.2023.103034
Xu SGhosh BHobbs CThiagarajan PJoshi PChakraborty S(2023)Safety-Aware Implementation of Control Tasks via Scheduling with Period Boosting and Compressing2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA58653.2023.00031(196-205)Online publication date: 30-Aug-2023
https://doi.org/10.1109/RTCSA58653.2023.00031
Show More Cited By

Index Terms

RunPar: an allocation algorithm for automotive applications exploiting runnable parallelism in multicores

Recommendations

Evaluation of Rodinia Codes on Intel Xeon Phi
ISMS '13: Proceedings of the 2013 4th International Conference on Intelligent Systems, Modelling and Simulation

High performance computing (HPC) is a niche area where various parallel benchmarks are constantly used to explore and evaluate the performance of Heterogeneous computing systems on the horizon. The Rodinia benchmark suite, a collection of parallel ...
On the Efficacy of a Fused CPU+GPU Processor (or APU) for Parallel Computing
SAAHPC '11: Proceedings of the 2011 Symposium on Application Accelerators in High-Performance Computing

The graphics processing unit (GPU) has made significant strides as an accelerator in parallel computing. However, because the GPU has resided out on PCIe as a discrete device, the performance of GPU applications can be bottlenecked by data transfers ...
Mars: Accelerating MapReduce with Graphics Processors

We design and implement Mars, a MapReduce runtime system accelerated with graphics processing units (GPUs). MapReduce is a simple and flexible parallel programming paradigm originally proposed by Google, for the ease of large-scale data processing on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CODES '14: Proceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis

October 2014

331 pages

ISBN:9781450330510

DOI:10.1145/2656075

Program Chairs:
Radu Marculescu
Carnegie Mellon University
,
Gabriela Nicolescu
Polytechnique Montréal

Copyright © 2014 ACM.

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

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems
SIGDA: ACM Special Interest Group on Design Automation
IEEE CAS
IEEE Council on Electronic Design Automation (CEDA)
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Ministerio de Economía y Competitividad
Spanish Ministry of Education

Conference

ESWEEK'14

Sponsor:

ESWEEK'14: TENTH EMBEDDED SYSTEM WEEK

October 12 - 17, 2014

New Delhi, India

Acceptance Rates

Overall Acceptance Rate 280 of 864 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
272
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ali Ahmad MKrisper MBatista Ribeiro LBaunach MHong JPark J(2024)Avoiding Empty Instances and Offset Drifts of Basic Sequencer Tasks in Automotive Operating SystemProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635886(400-409)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3605098.3635886
Munera ARoyuela SPressler MMackamul HZiegenbein DQuiñones E(2024)Fine-grained adaptive parallelism for automotive systems through AMALTHEA and OpenMPJournal of Systems Architecture10.1016/j.sysarc.2023.103034146(103034)Online publication date: Jan-2024
https://doi.org/10.1016/j.sysarc.2023.103034
Xu SGhosh BHobbs CThiagarajan PJoshi PChakraborty S(2023)Safety-Aware Implementation of Control Tasks via Scheduling with Period Boosting and Compressing2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA58653.2023.00031(196-205)Online publication date: 30-Aug-2023
https://doi.org/10.1109/RTCSA58653.2023.00031
Han ZQu GLiu BZhang F(2022)Exploit the data level parallelism and schedule dependent tasks on the multi-core processorsInformation Sciences: an International Journal10.1016/j.ins.2021.10.072585:C(382-394)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.ins.2021.10.072
Bandur VSelim GPantelic VLawford M(2021)Making the Case for Centralized Automotive E/E ArchitecturesIEEE Transactions on Vehicular Technology10.1109/TVT.2021.305493470:2(1230-1245)Online publication date: Feb-2021
https://doi.org/10.1109/TVT.2021.3054934
Copic MLeupers RAscheid G(2021)Runnable Configuration in Mixed Classic/Adaptive AUTOSAR Systems by Leveraging Nondeterminism2021 24th Euromicro Conference on Digital System Design (DSD)10.1109/DSD53832.2021.00070(418-425)Online publication date: Sep-2021
https://doi.org/10.1109/DSD53832.2021.00070
Copic MLeupers RAscheid G(2020)Modelling Machine Learning Components for Mapping and Scheduling of AUTOSAR Runnables2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE5003.2020.00021(127-137)Online publication date: Oct-2020
https://doi.org/10.1109/ISSRE5003.2020.00021
Copic MLeupers RAscheid G(2020)Reducing idle time in event-triggered software execution via runnable migration and DPM-Aware schedulingIntegration, the VLSI Journal10.1016/j.vlsi.2019.09.00470:C(10-20)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1016/j.vlsi.2019.09.004
Zhao YZeng HSangiovanni-Vincentelli ASztipanovits JZhu Q(2019)Optimization techniques for time-critical cyber-physical systemsProceedings of the Workshop on Design Automation for CPS and IoT10.1145/3313151.3313168(41-50)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.1145/3313151.3313168
Copic MLeupers RAscheid GShibuya T(2019)Efficient sporadic task handling in parallel AUTOSAR applications using runnable migrationProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3287654(603-608)Online publication date: 21-Jan-2019
https://dl.acm.org/doi/10.1145/3287624.3287654
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents