Cache-aware scheduling and analysis for multicores

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

• 1: J. Anderson and J. Calandrino. Parallel real-time task scheduling on multicore platforms. RTSS, 2006.
• 2: J. Anderson, J. Calandrino, and U. Devi. Real-time scheduling on multicore platforms. RTAS, 2006.
• 3: B. Andersson, S. Baruah, and J. Jonsson. Static-priority scheduling on multiprocessors. In RTSS, 2001.
• 4: T. P. Baker. Multiprocessor EDF and deadline monotonic schedulability analysis. In RTSS, 2003.
• 5: T. P. Baker. A comparison of global and partitioned edf schedulability tests for multiprocessors. In Technical Report, Florida State University, 2005.
• 6: S. Baruah. Techniques for multiprocessor global schedulability analysis. In RTSS, 2007.
• 7: M. Berkelaar. lp solve: a mixed integer linear program solver. In Relatorio Tecnico, Eindhoven University of Technology, 1999.
• 8: B. K. Bershad, B. J. Chen, D. Lee, and T. H. Romer. Avoiding conflict misses dynamically in large direct mapped caches. In ASPLOS, 1994.
• 9: Marko Bertogna, Michele Cirinei, and Giuseppe Lipari. Improved schedulability analysis of edf on multiprocessor platforms. In ECRTS, 2005.
• 10: B.D. Bui, M. Caccamo, L. Sha, and J. Martinez. Impact of cache partitioning on multi-tasking real time embedded systems. In RTCSA, 2008.
• 11: J. Vicente Busquets-Mataix and A. Wellings. Hybrid instruction cache partitioning for preemptive real-time systems. In ECRTS, 1997.
• 12: J. Calandrino and J. Anderson. Cache-aware real-time scheduling on multicore platforms: Heuristics and a case study. In ECRTS, 2008.
• 13: D. Chandra, F. Guo, S. Kim, and Y. Solihin. Predicting inter-thread cache contention on a multi-processor architecture. In HPCA, 2005.
• 14: D. Chiou, S. Devadas, L. Rudolph, and B. S. Ang. Dynamic cache partitioning via columnization. In Technical Report, MIT, 1999.
• 15: K. Danne and M. Platzner. An edf schedulability test for periodic tasks on reconfigurable hardware devices. In LCTES, 2006.
• 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: N. Fisher, J. Anderson, and S. Baruah. Task partitioning upon memory-constrained multiprocessors. In RTCSA, 2005.
• 19: N. Guan, Q. Deng, Z. Gu, W. Xu, and G. Yu. Schedulability analysis of preemptive and non-preemptive edf on partial runtime-reconfigurable fpgas. In ACM Transaction on Design Automation of Electronic Systems, volume 13, 2008.
• 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: N. Guan, W. Yi, Z. Gu, Q. Deng, and G. Yu. New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms. In RTSS, 2008.
• 22: N. Guan, W. Yi, Z. Gu, Q. Deng, and G. Yu. New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms. In RTSS, 2008.
• 23: J. Liedtke, H. Hartig, and M. Hohmuth. Os-controlled cache predictability for real-time systems. In RTAS, 1997.
• 24: M. Paolieri, E. Quinones, F. Cazorla, G. Bernat, and M. Valero. Hardware support for wcet analysis of hard real-time multicore systems. In ISCA, 2009.
• 25: J. Rosen, A. Andrei, P. Eles, and Z. Peng. Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip. In RTSS, 2007.
• 26: H. Salamy and J. Ramanujam. A framework for task scheduling and memory partitioning for multi-processor system-on-chip. In HiPEAC, 2009.
• 27: V. Suhendra and T. Mitra. Exploring locking and partitioning for predictable shared caches on multi-cores. In DAC, 2008.
• 28: V. Suhendra, C. Raghavan, and T. Mitra. Integrated scratchpad memory optimization and task scheduling for mpsoc architectures. In CASES, 2006.
• 29: D. Tam, R. Azimi, and M. Stumm L. Soares. Managing shared l2 caches on multicore systems in software. In WIOSCA, 2007.
• 30: R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenstrom. The worst-case execution-time problem|overview of methods and survey of tools. In ACM Transaction on Embedded Computing Systems, 2008.
• 31: A. Wolfe. Software-based cache partitioning for real-time applications. In Journal of Computer Software Engineering, 1994.
• 32: J. Yan and W. Zhang. Wcet analysis for multi-core processors with shared l2 instruction caches. In RTAS, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Performance

Keywords:
cache partitioning, multicores, real-time systems, schedulability analysis