Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: James H. Anderson , John M. Calandrino, Parallel Real-Time Task Scheduling on Multicore Platforms, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.89-100, December 05-08, 2006 [doi>10.1109/RTSS.2006.32]
• 2: James H. Anderson , John M. Calandrino , UmaMaheswari C. Devi, Real-Time Scheduling on Multicore Platforms, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.179-190, April 04-07, 2006 [doi>10.1109/RTAS.2006.35]
• 3: Bjorn Andersson , Sanjoy Baruah , Jan Jonsson, Static-Priority Scheduling on Multiprocessors, Proceedings of the 22nd IEEE Real-Time Systems Symposium, p.93, December 03-06, 2001
• 4: Theodore P. Baker, Multiprocessor EDF and Deadline Monotonic Schedulability Analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.120, December 03-05, 2003
• 5: T. P. Baker. A comparison of global and partitioned edf schedulability tests for multiprocessors. In Technical Report, Florida State University, 2005.
• 6: Sanjoy Baruah, Techniques for Multiprocessor Global Schedulability Analysis, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.119-128, December 03-06, 2007 [doi>10.1109/RTSS.2007.48]
• 7: M. Berkelaar. lp solve: a mixed integer linear program solver. In Relatorio Tecnico, Eindhoven University of Technology, 1999.
• 8: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• 9: Marko Bertogna , Michele Cirinei , Giuseppe Lipari, Improved Schedulability Analysis of EDF on Multiprocessor Platforms, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.209-218, July 06-08, 2005 [doi>10.1109/ECRTS.2005.18]
• 10: Bach D. Bui , Marco Caccamo , Lui Sha , Joseph Martinez, Impact of Cache Partitioning on Multi-tasking Real Time Embedded Systems, Proceedings of the 2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.101-110, August 25-27, 2008 [doi>10.1109/RTCSA.2008.42]
• 11: J. Vicente Busquets-Mataix and A. Wellings. Hybrid instruction cache partitioning for preemptive real-time systems. In ECRTS, 1997.
• 12: John M. Calandrino , James H. Anderson, Cache-Aware Real-Time Scheduling on Multicore Platforms: Heuristics and a Case Study, Proceedings of the 2008 Euromicro Conference on Real-Time Systems, p.299-308, July 02-04, 2008 [doi>10.1109/ECRTS.2008.10]
• 13: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 14: D. Chiou, S. Devadas, L. Rudolph, and B. S. Ang. Dynamic cache partitioning via columnization. In Technical Report, MIT, 1999.
• 15: Klaus Danne , Marco Platzner, An EDF schedulability test for periodic tasks on reconfigurable hardware devices, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
• 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: Nathan Fisher , James H. Anderson , Sanjoy Baruah, Task Partitioning upon Memory-Constrained Multiprocessors, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.416-421, August 17-19, 2005 [doi>10.1109/RTCSA.2005.97]
• 19: Nan Guan , Qingxu Deng , Zonghua Gu , Wenyao Xu , Ge Yu, Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-43, September 2008 [doi>10.1145/1391962.1391964]
• 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: Nan Guan , Wang Yi , Zonghua Gu , Qingxu Deng , Ge Yu, New Schedulability Test Conditions for Non-preemptive Scheduling on Multiprocessor Platforms, Proceedings of the 2008 Real-Time Systems Symposium, p.137-146, November 30-December 03, 2008 [doi>10.1109/RTSS.2008.17]
• 22: Nan Guan , Wang Yi , Zonghua Gu , Qingxu Deng , Ge Yu, New Schedulability Test Conditions for Non-preemptive Scheduling on Multiprocessor Platforms, Proceedings of the 2008 Real-Time Systems Symposium, p.137-146, November 30-December 03, 2008 [doi>10.1109/RTSS.2008.17]
• 23: Jochen Liedtke , Hermann Haertig , Michael Hohmuth, OS-Controlled Cache Predictability for Real-Time Systems, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.213, June 09-11, 1997
• 24: Marco Paolieri , Eduardo Quiñones , Francisco J. Cazorla , Guillem Bernat , Mateo Valero, Hardware support for WCET analysis of hard real-time multicore systems, Proceedings of the 36th annual international symposium on Computer architecture, June 20-24, 2009, Austin, TX, USA
• 25: Jakob Rosen , Alexandru Andrei , Petru Eles , Zebo Peng, Bus Access Optimization for Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.49-60, December 03-06, 2007 [doi>10.1109/RTSS.2007.13]
• 26: Hassan Salamy , J. Ramanujam, A Framework for Task Scheduling and Memory Partitioning for Multi-Processor System-on-Chip, Proceedings of the 4th International Conference on High Performance Embedded Architectures and Compilers, January 25-28, 2009, Paphos, Cyprus [doi>10.1007/978-3-540-92990-1_20]
• 27: Vivy Suhendra , Tulika Mitra, Exploring locking & partitioning for predictable shared caches on multi-cores, Proceedings of the 45th annual Design Automation Conference, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391545]
• 28: Vivy Suhendra , Chandrashekar Raghavan , Tulika Mitra, Integrated scratchpad memory optimization and task scheduling for MPSoC architectures, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176809]
• 29: D. Tam, R. Azimi, and M. Stumm L. Soares. Managing shared l2 caches on multicore systems in software. In WIOSCA, 2007.
• 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 , Per Stenström, The worst-case execution-time problem—overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-53, April 2008 [doi>10.1145/1347375.1347389]
• 31: Andrew Wolfe, Software-based cache partitioning for real-time applications, Journal of Computer and Software Engineering, v.2 n.3, p.315-327, 1994
• 32: Jun Yan , Wei Zhang, WCET Analysis for Multi-Core Processors with Shared L2 Instruction Caches, Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, p.80-89, April 22-24, 2008 [doi>10.1109/RTAS.2008.6]

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