research-article

CITTA: Cache Interference-aware Task Partitioning for Real-time Multi-core Systems

Authors:

Andy D. PimentelAuthors Info & Claims

LCTES '20: The 21st ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems

Pages 97 - 107

https://doi.org/10.1145/3372799.3394367

Published: 16 June 2020 Publication History

Abstract

Shared caches in multi-core processors introduce serious difficulties in providing guarantees on the real-time properties of embedded software due to the interaction and the resulting contention in the shared caches. Prior work has studied the schedulability analysis of global scheduling for real-time multi-core systems with shared caches. This paper considers another common scheduling paradigm: partitioned scheduling in the presence of shared cache interference. To achieve this, we propose CITTA, a cache-interference aware task partitioning algorithm. An integer programming formulation is constructed to calculate the upper bound on cache interference exhibited by a task, which is required by CITTA. We conduct schedulability analysis of CITTA and formally prove its correctness. A set of experiments is performed to evaluate the schedulability performance of CITTA against global EDF scheduling over randomly generated tasksets. Our empirical evaluations show that CITTA outperforms global EDF scheduling in terms of task sets deemed schedulable.

Supplementary Material

MP4 File (3372799.3394367.mp4)

Presentation Video

Download
27.36 MB

References

[1]

K. Albers and F. Slomka. 2004. An event stream driven approximation for the analysis of real-time systems. In Proceedings. 16th Euromicro Conference on Real-Time Systems, 2004. ECRTS 2004. 187--195.

[2]

Sanjoy Baruah. 2005. The limited-preemption uniprocessor scheduling of sporadic task systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS'05). 137--144.

Digital Library

[3]

Sanjoy Baruah. 2007. Techniques for Multiprocessor Global Schedulability Analysis. In RTSS'07 (RTSS '07). IEEE Computer Society, Washington, DC, USA, 119--128.

[4]

S. Baruah and N. Fisher. 2005. The partitioned multiprocessor scheduling of sporadic task systems. In 26th IEEE International Real-Time Systems Symposium (RTSS'05). 9 pp.--329.

[5]

Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. 1990. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor. In In Proceedings of the 11th Real-Time Systems Symposium. IEEE Computer Society Press, 182--190.

[6]

A. Bastoni, B. B. Brandenburg, and J. H. Anderson. 2010. An Empirical Comparison of Global, Partitioned, and Clustered Multiprocessor EDF Schedulers. In 2010 31st IEEE Real-Time Systems Symposium. 14--24. https://doi.org/10.1109/RTSS.2010.23

Digital Library

[7]

M. Bertogna, M. Cirinei, and G. Lipari. 2009. Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms. IEEE Transactions on Parallel and Distributed Systems, Vol. 20, 4 (April 2009), 553--566. https://doi.org/10.1109/TPDS.2008.129

Digital Library

[8]

B. B. Brandenburg and M. Gül. 2016. Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations. In 2016 IEEE Real-Time Systems Symposium (RTSS). 99--110.

[9]

Marco Caccamo, Marco Cesati, Rodolfo Pellizzoni, Emiliano Betti, Roman Dudko, and Renato Mancuso. 2013. Real-time Cache Management Framework for Multi-core Architectures. In RTAS' 13 (RTAS '13). IEEE Computer Society, Washington, DC, USA, 45--54.

[10]

Daniel Casini, Alessandro Biondi, and Giorgio Buttazzo. 2017. Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based on Analysis-Driven Load Balancing. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Marko Bertogna (Ed.), Vol. 76. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 13:1--13:23.

[11]

Kenneth L. Clarkson. 1995. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM, Vol. 42 (1995), 488--499.

Digital Library

[12]

Robert I. Davis and Alan Burns. 2011. A Survey of Hard Real-time Scheduling for Multiprocessor Systems. ACM Comput. Surv., Vol. 43, 4, Article 35 (Oct. 2011), bibinfonumpages44 pages. https://doi.org/10.1145/1978802.1978814

[13]

Nathan Fisher and Sanjoy Baruah. 2006. The partitioned multiprocessor scheduling of non-preemptive sporadic task systems. In 14th International conference on real-time and network systems.

[14]

Laurent George, Paul Muhlethaler, and Nicolas Rivierre. 1995. Optimality and non-preemptive real-time scheduling revisited. Research Report RR-2516. INRIA. Projet REFLECS.

[15]

G. Gracioli and A. A. Fröhlich. 2013. An experimental evaluation of the cache partitioning impact on multicore real-time schedulers. In RTCSA' 03. 72--81.

[16]

Nan Guan, Martin Stigge, Wang Yi, and Ge Yu. 2009. Cache-aware scheduling and analysis for multicores. In 7th ACM international conference on Embedded software. ACM, 245--254.

Digital Library

[17]

D. Hardy, T. Piquet, and I. Puaut. 2009. Using Bypass to Tighten WCET Estimates for Multi-Core Processors with Shared Instruction Caches. In RTSS '09. 68--77.

[18]

D. Hardy and I. Puaut. 2008. WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction Caches. In RTSS'08. 456--466.

[19]

K. Jeffay, D. F. Stanat, and C. U. Martel. 1991. On non-preemptive scheduling of period and sporadic tasks. In Proceedings Twelfth Real-Time Systems Symposium. 129--139.

[20]

S. Kato and N. Yamasaki. 2009. Semi-partitioned Fixed-Priority Scheduling on Multiprocessors. In 2009 15th IEEE Real-Time and Embedded Technology and Applications Symposium. 23--32.

[21]

H. Kim, A. Kandhalu, and R. Rajkumar. 2013. A Coordinated Approach for Practical OS-Level Cache Management in Multi-core Real-Time Systems. In ECRTS' 13. 80--89.

[22]

J. Lee, K. G. Shin, I. Shin, and A. Easwaran. 2015. Composition of Schedulability Analyses for Real-Time Multiprocessor Systems. IEEE Trans. Comput., Vol. 64, 4 (April 2015), 941--954. https://doi.org/10.1109/TC.2014.2308183

Digital Library

[23]

Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. 2009. Timing Analysis of Concurrent Programs Running on Shared Cache Multi-Cores. In 2009 30th IEEE Real-Time Systems Symposium. 57--67. https://doi.org/10.1109/RTSS.2009.32

[24]

J. Liedtke, H. Hartig, and M. Hohmuth. 1997. OS-controlled cache predictability for real-time systems. In RTAS' 97. 213--224.

[25]

José Mar'ia López, José Luis Díaz, and Daniel F García. 2004. Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Systems, Vol. 28, 1 (2004), 39--68.

Digital Library

[26]

Mayank Shekhar, Abhik Sarkar, Harini Ramaprasad, and Frank Mueller. 2012. Semi-Partitioned Hard-Real-Time Scheduling Under Locked Cache Migration in Multicore Systems. In ECRTS' 12. IEEE Computer Society, Washington, DC, USA, 331--340.

[27]

Roger Stafford. 2006. Random vectors with fixed sum. http://www.mathworks.com/matlabcentral/fileexchange/9700

[28]

Vivy Suhendra and Tulika Mitra. 2008. Exploring Locking & Partitioning for Predictable Shared Caches on Multi-cores. In Proceedings of the 45th Annual Design Automation Conference (DAC '08). ACM, New York, NY, USA, 300--303. https://doi.org/10.1145/1391469.1391545

Digital Library

[29]

B. C. Ward, J. L. Herman, C. J. Kenna, and J. H. Anderson. 2013. Making Shared Caches More Predictable on Multicore Platforms. In ECRTS' 13. 157--167.

[30]

Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström. 2008. The Worst-case Execution-time Problem--Overview of Methods and Survey of Tools. ACM Trans. Embed. Comput. Syst., Vol. 7, 3, Article 36 (May 2008), bibinfonumpages53 pages.

Digital Library

[31]

J. Xiao, S. Altmeyer, and A. Pimentel. 2017. Schedulability Analysis of Non-preemptive Real-Time Scheduling for Multicore Processors with Shared Caches. In 2017 IEEE Real-Time Systems Symposium (RTSS). 199--208. https://doi.org/10.1109/RTSS.2017.00026

[32]

J. Xiao, S. Altmeyer, and A. D. Pimentel. 2020. Schedulability Analysis of Global Scheduling for Multicore Systems with Shared Caches. IEEE Trans. Comput. (2020), 1--1. https://doi.org/10.1109/TC.2020.2974224

[33]

M. Xu, L. T. X. Pha, H. Choi, Y. Lin, H. Li, C. Lu, and I. Lee. [n. d.]. Holistic Resource Allocation for Multicore Real-Time Systems. In RTAS'19. https://doi.org/10.1109/RTAS.2019.00036

[34]

M. Xu, L. T. X. Phan, H. Y. Choi, and I. Lee. 2016. Analysis and Implementation of Global Preemptive Fixed-Priority Scheduling with Dynamic Cache Allocation. In RTAS. 1--12.

[35]

Maolin Yang, Wen-Hung Huang, and Jian-Jia Chen. 2018. Resource-Oriented Partitioning for Multiprocessor Systems with Shared Resources. IEEE Trans. Comput., Vol. PP (12 2018), 1--1. https://doi.org/10.1109/TC.2018.2889985

[36]

W. Zhang and J. Yan. 2009. Accurately Estimating Worst-Case Execution Time for Multi-core Processors with Shared Direct-Mapped Instruction Caches. In RTCSA '09. 455--463.

Cited By

Xiao JShen YPimentel A(2022)Cache Interference-aware Task Partitioning for Non-preemptive Real-time Multi-core SystemsACM Transactions on Embedded Computing Systems10.1145/348758121:3(1-28)Online publication date: 28-May-2022
https://dl.acm.org/doi/10.1145/3487581
Lugo TLozano SFernandez JCarretero J(2022)A Survey of Techniques for Reducing Interference in Real-Time Applications on Multicore PlatformsIEEE Access10.1109/ACCESS.2022.315189110(21853-21882)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3151891
Casini DBiondi ACicero GButtazzo G(2021)Latency Analysis of I/O Virtualization Techniques in Hypervisor-Based Real-Time Systems2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00032(306-319)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00032

Index Terms

CITTA: Cache Interference-aware Task Partitioning for Real-time Multi-core Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software

Recommendations

Cache Interference-aware Task Partitioning for Non-preemptive Real-time Multi-core Systems
Shared caches in multi-core processors introduce serious difficulties in providing guarantees on the real-time properties of embedded software due to the interaction and the resulting contention in the shared caches. Prior work has studied the ...
TCPS: a task and cache-aware partitioned scheduler for hard real-time multi-core systems
LCTES 2022: Proceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

Shared caches in multi-core processors seriously complicate the timing verification of real-time software tasks due to the task interference occurring in the shared caches. Explicitly calculating the amount of cache interference among tasks and cache ...
Global EDF-based scheduling with laxity-driven priority promotion

This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '20: The 21st ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems

June 2020

163 pages

ISBN:9781450370943

DOI:10.1145/3372799

General Chair:
Jingling Xue
UNSW Sydney, Australia
,
Program Chair:
Changhee Jung
Purdue University, USA

Copyright © 2020 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '20

Sponsor:

LCTES '20: 21st ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems

June 16, 2020

London, United Kingdom

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
147
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xiao JShen YPimentel A(2022)Cache Interference-aware Task Partitioning for Non-preemptive Real-time Multi-core SystemsACM Transactions on Embedded Computing Systems10.1145/348758121:3(1-28)Online publication date: 28-May-2022
https://dl.acm.org/doi/10.1145/3487581
Lugo TLozano SFernandez JCarretero J(2022)A Survey of Techniques for Reducing Interference in Real-Time Applications on Multicore PlatformsIEEE Access10.1109/ACCESS.2022.315189110(21853-21882)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3151891
Casini DBiondi ACicero GButtazzo G(2021)Latency Analysis of I/O Virtualization Techniques in Hypervisor-Based Real-Time Systems2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00032(306-319)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00032

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