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

research-article

Time-predictable execution of multithreaded applications on multicore systems

Authors:

Ahmed Alhammad,

Rodolfo PellizzoniAuthors Info & Claims

DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

Article No.: 29, Pages 1 - 6

Published: 24 March 2014 Publication History

Abstract

In multicore systems, contention for access to main memory between application threads complicates timing analysis and may lead to pessimistic bounds on execution time. This is particularly problematic for real-time applications, which require provable bounds on worst-case performance. In this work, we employ a predictable execution model to schedule memory accesses performed by application threads without relying on unpredictable hardware arbiters. In addition, we statically schedule application's threads with the objective to minimize the application's makespan. Our experimental evaluation with NAS Parallel Benchmarks on 4-core system indicates that the proposed execution scheme yields an aggregated improvement of 21% over contention execution in which application's threads uncontrollably access main memory.

References

[1]

H.-M. Huang, T. Tidwell, C. Gill, C. Lu, X. Gao, and S. Dyke, "Cyber-physical systems for real-time hybrid structural testing: a case study," in Proc. Int. Conf. Cyber-Physical Systems. ACM, 2010, pp. 69--78.

Digital Library

[2]

A. Kurdila, M. Nechyba, R. Prazenica, W. Dahmen, P. Binev, R. DeVore, and R. Sharpley, "Vision-based control of micro-air-vehicles: Progress and problems in estimation," in Proc. Decision and Control, vol. 2. IEEE, 2004, pp. 1635--1642.

[3]

K. Lakshmanan, S. Kato, and R. R. Rajkumar, "Scheduling parallel real-time tasks on multi-core processors," in Proc. RTSS. IEEE, 2010, pp. 259--268.

Digital Library

[4]

A. Saifullah, K. Agrawal, C. Lu, and C. Gill, "Multi-core real-time scheduling for generalized parallel task models," in Proc. RTSS. IEEE, 2011, pp. 217--226.

Digital Library

[5]

R. Pellizzoni, A. Schranzhofery, J.-J. Cheny, M. Caccamo, and L. Thieley, "Worst case delay analysis for memory interference in multicore systems," in Proc. DATE. IEEE, 2010, pp. 741--746.

Digital Library

[6]

H. Jin, M. Frumkin, and J. Yan, "The openmp implementation of nas parallel benchmarks and its performance," Technical Report NAS-99-011, NASA Ames Research Center, Tech. Rep., 1999.

[7]

F. Boniol, H. Cassé, E. Noulard, and C. Pagetti, "Deterministic execution model on COTS hardware," Architecture of Computing, pp. 98--110, 2012.

Digital Library

[8]

R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, M. Caccamo, and R. Kegley, "A predictable execution model for cots-based embedded systems," in Proc. RTAS. IEEE, 2011, pp. 269--279.

Digital Library

[9]

G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo, "Memory-centric scheduling for multicore hard real-time systems," Real-Time Systems, vol. 48, no. 6, pp. 681--715, 2012.

Digital Library

[10]

D. Lea, "A java fork/join framework," in Proc. Conf. Java Grande. ACM, 2000, pp. 36--43.

Digital Library

[11]

IA-32 Architectures Software Developers Manual, Volume 3^a ed., Intel, 2011.

[12]

S. Udayakumaran, A. Dominguez, and R. Barua, "Dynamic allocation for scratch-pad memory using compile-time decisions," ACM Transactions on Embedded Computing Systems, vol. 5, no. 2, pp. 472--511, May 2006.

Digital Library

[13]

R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni, "Real-time cache management framework for multi-core architectures," in Proc. RTAS. IEEE, 2013, pp. 45--54.

Digital Library

[14]

A. Darte, Y. P. Robert, F. Vivien, and F. Vivien, Scheduling and automatic Parallelization. Springer, 2000.

Digital Library

[15]

P. Radojković, V. Čakarević, M. Moretó, J. Verdú, A. Pajuelo, F. Cazorla, M. Nemirovsky, and M. Valero, "Optimal task assignment in multithreaded processors: a statistical approach," in Proc. ASPLOS, 2012, pp. 235--248.

Digital Library

[16]

M. Bach, M. Charney, R. Cohn, E. Demikhovsky, T. Devor, K. Hazelwood, A. Jaleel, C.-K. Luk, G. Lyons, H. Patil et al., "Analyzing parallel programs with pin," Computer, vol. 43, no. 3, pp. 34--41, 2010.

Digital Library

Cited By

Igarashi SIshigooka THoriguchi TKoike RAzumi TVoznak MCalafate CDe Rango F(2020)Heuristic contention-free scheduling algorithm for multi-core processor using LET modelProceedings of the IEEE/ACM 24th International Symposium on Distributed Simulation and Real Time Applications10.5555/3451906.3451914(49-58)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.5555/3451906.3451914
Maiza CRihani HRivas JGoossens JAltmeyer SDavis R(2019)A Survey of Timing Verification Techniques for Multi-Core Real-Time SystemsACM Computing Surveys10.1145/332321252:3(1-38)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323212
Forsberg BBenini LMarongiu A(2018)On the Cost of Freedom From Interference in Heterogeneous SoCsProceedings of the 21st International Workshop on Software and Compilers for Embedded Systems10.1145/3207719.3207735(31-34)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3207719.3207735
Show More Cited By

Index Terms

Time-predictable execution of multithreaded applications on multicore systems

Recommendations

Leveraging transactional memory for a predictable execution of applications composed of hard real-time and best-effort tasks
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and Systems

In this paper, we utilise transactional memory (TM) to limit interferences of concurrent hard real-time (HRT) and best-effort (BE) tasks in a shared memory multi-core. We first propose a way to calculate the worst-case execution time (WCET) bound of HRT ...
Scaling Multicore Databases via Constrained Parallel Execution
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Multicore in-memory databases often rely on traditional con- currency control schemes such as two-phase-locking (2PL) or optimistic concurrency control (OCC). Unfortunately, when the workload exhibits a non-trivial amount of contention, both 2PL and OCC ...
Analyzing lock contention in multithreaded applications
PPoPP '10

Many programs exploit shared-memory parallelism using multithreading. Threaded codes typically use locks to coordinate access to shared data. In many cases, contention for locks reduces parallel efficiency and hurts scalability. Being able to quantify ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

March 2014

1959 pages

ISBN:9783981537024

General Chairs:
Gerhard Fettweis
TU Dresden, DE
,
Wolfgang Nebel
OFFIS, DE

Sponsors

EDAA: European Design Automation Association
ECSI
EDAC: Electronic Design Automation Consortium
IEEE Council on Electronic Design Automation (CEDA)
The Russian Academy of Sciences: The Russian Academy of Sciences

In-Cooperation

SIGDA: ACM Special Interest Group on Design Automation

Publisher

European Design and Automation Association

Leuven, Belgium

Publication History

Published: 24 March 2014

Check for updates

Qualifiers

Research-article

Conference

DATE '14

Sponsor:

EDAA
EDAC
The Russian Academy of Sciences

DATE '14: Design, Automation and Test in Europe

March 24 - 28, 2014

Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
91
Total Downloads

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

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Igarashi SIshigooka THoriguchi TKoike RAzumi TVoznak MCalafate CDe Rango F(2020)Heuristic contention-free scheduling algorithm for multi-core processor using LET modelProceedings of the IEEE/ACM 24th International Symposium on Distributed Simulation and Real Time Applications10.5555/3451906.3451914(49-58)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.5555/3451906.3451914
Maiza CRihani HRivas JGoossens JAltmeyer SDavis R(2019)A Survey of Timing Verification Techniques for Multi-Core Real-Time SystemsACM Computing Surveys10.1145/332321252:3(1-38)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323212
Forsberg BBenini LMarongiu A(2018)On the Cost of Freedom From Interference in Heterogeneous SoCsProceedings of the 21st International Workshop on Software and Compilers for Embedded Systems10.1145/3207719.3207735(31-34)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3207719.3207735
Matějka JForsberg BSojka MHanzálek ZBenini LMarongiu A(2018)Combining PREM compilation and ILP scheduling for high-performance and predictable MPSoC executionProceedings of the 9th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3178442.3178444(11-20)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178442.3178444
Forsberg BMarongiu ABenini L(2017)GPUguardProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130453(318-321)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130453
Martinez SHardy DPuaut IBini EPagetti C(2017)Quantifying WCET reduction of parallel applications by introducing slack time to limit resource contentionProceedings of the 25th International Conference on Real-Time Networks and Systems10.1145/3139258.3139263(188-197)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3139258.3139263
Rouxel BDerrien SPuaut I(2017)Tightening Contention Delays While Scheduling Parallel Applications on Multi-core ArchitecturesACM Transactions on Embedded Computing Systems10.1145/312649616:5s(1-20)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3126496
Alhammad APellizzoni RMitra TReineke J(2014)Schedulability analysis of global memory-predictable schedulingProceedings of the 14th International Conference on Embedded Software10.1145/2656045.2656070(1-10)Online publication date: 12-Oct-2014
https://dl.acm.org/doi/10.1145/2656045.2656070

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