Exploring locking & partitioning for predictable shared caches on multi-cores

ABSTRACT

Multi-core architectures consisting of multiple processing cores on a chip have become increasingly prevalent. Synthesizing hard real-time applications onto these platforms is quite challenging, as the contention among the cores for various shared resources leads to inherent timing unpredictability. This paper proposes the use of shared cache in a predictable manner through a combination of locking and partitioning mechanisms. We explore possible design choices and evaluate their effects on the worst-case application performance. Our study reveals certain design principles that strongly dictate the performance of a predictable memory hierarchy.

REFERENCES

• 1: 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]
• 2: J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms. In J. Y.-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman Hall/CRC Press, 2004.
• 3: Derek T. Chiou , Arvind , Larry Rudolph, Extending the reach of microprocessors: column and curious caching, Massachusetts Institute of Technology, 1999
• 4: D. Kirk. SMART (Strategic Memory Allocation for Real-Time) Cache Design. In RTSS, 1989.
• 5: Yau-Tsun Steven Li , Sharad Malik , Benjamin Ehrenberg, Performance Analysis of Real-Time Embeded Software, Kluwer Academic Publishers, Norwell, MA, 1998
• 6: J. López, M. García, J. Díaz, and D. García. Worst-Case Utilization Bound for EDF Scheduling on Real-Time Multiprocessor Systems. In ECRTS, 2000.
• 7: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 8: Isabelle Puaut, WCET-Centric Software-controlled Instruction Caches for Hard Real-Time Systems, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.217-226, July 05-07, 2006 [doi>10.1109/ECRTS.2006.32]
• 9: Isabelle Puaut , David Decotigny, Low-Complexity Algorithms for Static Cache Locking in Multitasking Hard Real-Time Systems, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.114, December 03-05, 2002
• 10: Rakesh Reddy , Peter Petrov, Eliminating inter-process cache interference through cache reconfigurability for real-time and low-power embedded multi-tasking systems, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289917]
• 11: J. E. Sasinowski , J. K. Strosnider, A Dynamic Programming Algorithm for Cache Memory Partitioning for Real-Time Systems, IEEE Transactions on Computers, v.42 n.8, p.997-1001, August 1993 [doi>10.1109/12.238493]
• 12: G. Suh, L. Rudolph, and S. Devadas. Dynamic Cache Partitioning for Simultaneous Multithreading Systems. In PDCS, 2001.
• 13: Henrik Theiling , Christian Ferdinand , Reinhard Wilhelm, Fast and Precise WCET Prediction by Separated Cache andPath Analyses, Real-Time Systems, v.18 n.2-3, p.157-179, May 2000 [doi>10.1023/A:1008141130870]
• 14: Xavier Vera , Björn Lisper , Jingling Xue, Data cache locking for higher program predictability, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Measurement, Performance

Keywords:
WCET, cache locking, cache partitioning, shared-cache multi-core