ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Cache-aware scheduling and analysis for multicores
Full text PdfPdf (605 KB)
Source
International Conference On Embedded Software archive
Proceedings of the seventh ACM international conference on Embedded software table of contents
Grenoble, France
SESSION: Time predictability and memory management table of contents
Pages: 245-254  
Year of Publication: 2009
ISBN:978-1-60558-627-4
Authors
Nan Guan  Uppsala University, Uppsala, Sweden
Martin Stigge  Uppsala University, Uppsala, Sweden
Wang Yi  Uppsala University, Uppsala, Sweden
Ge Yu  Northeastern University, China, Shenyang, China
Sponsors
ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 34,   Downloads (12 Months): 92,   Citation Count: 0
Additional Information:

abstract   references   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629335.1629369
What is a DOI?

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.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
 
2
 
3
 
4
 
5
T. P. Baker. A comparison of global and partitioned edf schedulability tests for multiprocessors. In Technical Report, Florida State University, 2005.
 
6
 
7
M. Berkelaar. lp solve: a mixed integer linear program solver. In Relatorio Tecnico, Eindhoven University of Technology, 1999.
8
 
9
 
10
 
11
J. Vicente Busquets-Mataix and A. Wellings. Hybrid instruction cache partitioning for preemptive real-time systems. In ECRTS, 1997.
 
12
 
13
 
14
D. Chiou, S. Devadas, L. Rudolph, and B. S. Ang. Dynamic cache partitioning via columnization. In Technical Report, MIT, 1999.
15
 
16
S. Dropsho and C. Weems. Comparing caching techniques for multitasking real-time systems. In Technical Report, University of Massachusetts-Amherst, 1997.
 
17
A. Fedorova, M. Seltzer, C. Small, and D. Nussbaum. Throughput-oriented scheduling on chip multithreading systems. Technical Report, Harvard University, 2005.
 
18
19
 
20
N. Guan, M. Stigge, W. Yi, and G. Yu. Cache-aware scheduling and analysis for multicores. In Technical Report, Uppsala University, (http://user.it.uu.se/~yi), 2009.
 
21
 
22
 
23
24
 
25
 
26
27
28
 
29
D. Tam, R. Azimi, and M. Stumm L. Soares. Managing shared l2 caches on multicore systems in software. In WIOSCA, 2007.
30
 
31
 
32

Collaborative Colleagues:
Nan Guan: colleagues
Martin Stigge: colleagues
Wang Yi: colleagues
Ge Yu: colleagues