Cache-aware scheduling and analysis for multicores

Nan Guan, Martin Stigge, Wang Yi, Ge Yu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

86 Citations (Scopus)

Abstract

The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time. As technical contributions, we have developed a sufficient schedulability test for non-preemptive fixed-priority scheduling for multicores with shared L2 cache, encoded as a linear programming problem. To improve the scalability of the test, we then present our second schedulability test of quadratic complexity, which is an over approximation of the first test. To evaluate the performance and scalability of our techniques, we use randomly generated task sets. Our experiments show that the first test which employs an LP solver can easily handle task sets with thousands of tasks in minutes using a desktop computer. It is also shown that the second test is comparable with the first one in terms of precision, but scales much better due to its low complexity, and is therefore a good candidate for efficient schedulability tests in the design loop for embedded systems or as an on-line test for admission control.
Original languageEnglish
Title of host publicationEmbedded Systems Week 2009 - Proceedings of the 7th ACM International Conference on Embedded Software, EMSOFT '09
Pages245-254
Number of pages10
DOIs
Publication statusPublished - 24 Dec 2009
Externally publishedYes
EventEmbedded Systems Week 2009, ESWEEK 2009 - 7th ACM International Conference on Embedded Software, EMSOFT '09 - Grenoble, France
Duration: 11 Oct 200916 Oct 2009

Conference

ConferenceEmbedded Systems Week 2009, ESWEEK 2009 - 7th ACM International Conference on Embedded Software, EMSOFT '09
Country/TerritoryFrance
CityGrenoble
Period11/10/0916/10/09

Keywords

  • Cache partitioning
  • Multicores
  • Real-time systems
  • Schedulability analysis

ASJC Scopus subject areas

  • Software

Cite this