A Survey on Cache Management Mechanisms for Real-Time Embedded Systems

Abstract

Multicore processors are being extensively used by real-time systems, mainly because of their demand for increased computing power. However, multicore processors have shared resources that affect the predictability of real-time systems, which is the key to correctly estimate the worst-case execution time of tasks. One of the main factors for unpredictability in a multicore processor is the cache memory hierarchy. Recently, many research works have proposed different techniques to deal with caches in multicore processors in the context of real-time systems. Nevertheless, a review and categorization of these techniques is still an open topic and would be very useful for the real-time community. In this article, we present a survey of cache management techniques for real-time embedded systems, from the first studies of the field in 1990 up to the latest research published in 2014. We categorize the main research works and provide a detailed comparison in terms of similarities and differences. We also identify key challenges and discuss future research directions.

References

1. Aeronautical Radio, Inc. 2013. Avionics Application Software Standard Interface: ARINC Specification 653 Part 0. Retrieved from https://www.arinc.com/cf/store/catalog_detail.cfm?item_id=2039.
2. Y. Afek, D. Dice, and A. Morrison. 2011. Cache index-aware memory allocation. In Proc. of the ISMM. ACM, 55--64.
3. Hussein Al-Zoubi, Aleksandar Milenkovic, and Milena Milenkovic. 2004. Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite. In Proc. of the 42nd ACM-SE. ACM, New York, NY, 267--272.
4. AMD. 2013. AMD64 Architecture Programmers Manual Volume 2: System Programming. Section 7.3: Memory Coherency and Protocol. Publication # 24593. Revision: 3.23.
5. L. C. Aparicio, J. Segarra, C. Rodríguez, and V. Viñals. 2011. Improving the WCET computation in the presence of a lockable instruction cache in multitasking real-time systems. Journal of Systems Architecture 57, 7 (2011), 695--706.
6. Alexis Arnaud and Isabelle Puaut. 2006. Dynamic instruction cache locking in hard real-time systems. In Proc. of the 14th RTNS.
7. Abu Asaduzzaman, Fadi N. Sibai, and Manira Rani. 2010. Improving cache locking performance of modern embedded systems via the addition of a miss table at the {L2} cache level. Journal of Systems Architecture 56, 4--6 (2010), 151--162.
8. Mathieu Avila and Isabelle Puaut. 2009. Heptane—A Tree-based WCET Analysis Tool. Retrieved from http://ralyx.inria.fr/2004/Raweb/aces/uid43.html.
9. Andrea Bastoni, Björn Brandenburg, and James Anderson. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proc. of OSPERT. 33--44.
10. Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. 2010. An analysis of Linux scalability to many cores. In Proc. of the 9th OSDI. USENIX Association, Berkeley, CA, 1--8.
11. Edouard Bugnion, Jennifer M. Anderson, Todd C. Mowry, Mendel Rosenblum, and Monica S. Lam. 1996. Compiler-directed page coloring for multiprocessors. In Proc. of the 7th ASPLOS. ACM, 244--255.
12. B. D. Bui, M. Caccamo, Lui Sha, and J. Martinez. 2008. Impact of cache partitioning on multi-tasking real time embedded systems. In Proc. of the 14th RTCSA. 101--110.
13. Marti Campoy, A. Perles Ivars, and J. V. Busquets Mataix. 2001. Static use of locking caches in multitask preemptive real-time systems. In Proc. of IEEE Real-Time Embedded Systems Workshop. London, UK.
14. Francisco J. Cazorla, Eduardo Quinones, Tullio Vardanega, Liliana Cucu, Benoit Triquet, Guillem Bernat, Emery Berger, Jaume Abella, Franck Wartel, Michael Houston, and others. 2013. Proartis: Probabilistically analyzable real-time systems. ACM Transactions on Embedded Computing Systems 12, 2s (2013), 94.
15. Certification Authorities Software Team (CAST). 2014. Position Paper on Multi-core Processors - CAST-32. Retrieved from https://www.faa.gov/aircraft/air_cert/design_approvals/air_software/cast/cast_papers/media/cast-32.pdf.
16. M. Cesati, R. Mancuso, E. Betti, and M. Caccamo. 2015. A memory access detection methodology for accurate workload characterization. In Proc. of the 21th IEEE RTCSA. IEEE.
17. Yu Chen, Wenlong Li, Changkyu Kim, and Zhizhong Tang. 2009. Efficient shared cache management through sharing-aware replacement and streaming-aware insertion policy. In Proc. of the 24th IEEE IPDPS’09. 1--11.
18. T. M. Chilimbi, M. D. Hill, and J. R. Larus. 2000. Making pointer-based data structures cache conscious. Computer 33, 12 (Dec. 2000), 67--74.
19. Derek Chiou, Prabhat Jain, Srinivas Devadas, and Larry Rudolph. 2000. Dynamic cache partitioning via columnization. In Proc. of DAC. ACM.
20. Ali Chousein and Rabi N. Mahapatra. 2005. Fully associative cache partitioning with don’t care bits for real-time applications. SIGBED Review 2, 2 (April 2005), 35--38.
21. P. Cousot. 2001. Abstract interpretation based formal methods and future challenges. In Informatics - 10 Years Back. 10 Years Ahead. Springer-Verlag, London, UK, 138--156.
22. Silviu S. Craciunas, Christoph M. Kirsch, Hannes Payer, Ana Sokolova, Horst Stadler, and Robert Staudinger. 2008. A compacting real-time memory management system. In Proc. of USENIX ATC. USENIX, 49--362.
23. C. Cullmann. 2013. Cache persistence analysis: Theory and practice. ACM Trans. Embed. Comput. Syst. 12, 1s, Article 40 (March 2013), 25 pages.
24. C. Cullmann, C. Ferdinand, G. Gebhard, D. Grund, C. Maiza, J. Reineke, B. Triquet, S. Wegener, and R. Wilhelm. 2010. Predictability considerations in the design of multi-core embedded systems. Ingénieurs de l’Automobile 807 (Sept. 2010), 36--42.
25. Robert I. Davis and Alan Burns. 2011. A survey of hard real-time scheduling for multiprocessor systems. Computing Surveys 43, 4, Article 35 (Oct. 2011), 44 pages.
26. R. I. Davis, L. Santinelli, S. Altmeyer, C. Maiza, and L. Cucu-Grosjean. 2013. Analysis of probabilistic cache related pre-emption delays. In Proc. of the 25th ECRTS. IEEE, 168--179.
27. J.-F. Deverge and I. Puaut. 2007. WCET-directed dynamic scratchpad memory allocation of data. In Proc. of the 19th Euromicro Conference on Real-Time Systems (ECRTS’07). 179--190.
28. Huping Ding, Yun Liang, and T. Mitra. 2012. WCET-Centric partial instruction cache locking. In Proc. of the 49th ACM/IEEE DAC. 412--420.
29. Huping Ding, Yun Liang, and T. Mitra. 2014. WCET-Centric dynamic instruction cache locking. In Proc. of DATE. 1--6.
30. Eiman Ebrahimi, Onur Mutlu, Chang Joo Lee, and Yale N. Patt. 2009. Coordinated control of multiple prefetchers in multi-core systems. In Proc. of the 42Nd MICRO. ACM, 316--326.
31. Heiko Falk, Sascha Plazar, and Henrik Theiling. 2007. Compile-time decided instruction cache locking using worst-case execution paths. In Proc. of the 5th IEEE/ACM CODES+ISSS. ACM, 143--148.
32. C. Ferdinand. 1997. Cache Behavior Prediction for Real-Time Systems. Ph.D. Dissertation. Saarland University.
33. G. Gracioli and A. A. Fröhlich. 2013. An experimental evaluation of the cache partitioning impact on multicore real-time schedulers. In Proc. of the 19th IEEE RTCAS. IEEE, 10.
34. Daniel Grund and Jan Reineke. 2010a. Precise and efficient FIFO-replacement analysis based on static phase detection. In Proc. of the 22nd ECRTS. 155--164.
35. Daniel Grund and Jan Reineke. 2010b. Toward precise PLRU cache analysis. In Proc. of 10th Workshop on WCET Analysis. 28--39.
36. Nan Guan, Martin Stigge, Wang Yi, and Ge Yu. 2009. Cache-aware scheduling and analysis for multicores. In Proc. of the EMSOFT’09. ACM, 245--254.
37. Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi. 2013. FIFO cache analysis for WCET estimation: A quantitative approach. In Proc. of DATE. 296--301.
38. Fei Guo, Yan Solihin, Li Zhao, and Ravishankar Iyer. 2007. A framework for providing quality of service in chip multi-processors. In Proc. of the 40th IEEE/ACM MICRO. IEEE, 343--355.
39. Damien Hardy, Thomas Piquet, and Isabelle Puaut. 2009. Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In Proc. of the 30th RTSS. IEEE, 68--77.
40. Damien Hardy and Isabelle Puaut. 2009. Estimation of cache related migration delays for multi-core processors with shared instruction caches. In Proc. of the 17th RTNS. 45--54.
41. John L. Hennessy and David A. Patterson. 2006. Computer Architecture: A Quantitative Approach (4th ed.). Morgan Kaufmann.
42. J. Herter, P. Backes, F. Haupenthal, and J. Reineke. 2011. CAMA: A predictable cache-aware memory allocator. In Proc. of the 2011 ECRTS. 23--32.
43. J. Herter and J. Reineke. 2009. Making dynamic memory allocation static to support WCET analyses. In Proc. of 9th International Workshop on WCET Analysis.
44. Intel. 2010. An Introduction to the Intel QuickPath Interconnect. Retrieved from http://www.intel.com/content/www/us/en/io/quickpath-technology/quick-path-interconnect-introduction-paper.html.
45. T. Ishikawa, T. Kato, S. Honda, and H. Takada. 2013. Investigation and improvement on the impact of TLB misses in real-time systems. In Proc. of OSPERT.
46. Ravi Iyer. 2004. CQoS: A framework for enabling QoS in shared caches of CMP platforms. In Proc. of the 18th ICS. ACM, 257--266.
47. Ravi Iyer, Li Zhao, Fei Guo, Ramesh Illikkal, Srihari Makineni, Don Newell, Yan Solihin, Lisa Hsu, and Steve Reinhardt. 2007. QoS policies and architecture for cache/memory in CMP platforms. In Proc. of the 2007 ACM SIGMETRICS. ACM, 25--36.
48. R. E. Kessler and Mark D. Hill. 1992. Page placement algorithms for large real-indexed caches. ACM Transaction on Computer Systems 10, 4 (Nov. 1992), 338--359.
49. Hyoseung Kim, Arvind Kandhalu, and Ragunathan Rajkumar. 2013. A coordinated approach for practical OS-level cache management in multi-core real-time systems. In Proc. of the 25th ECRTS. 80--89.
50. J. C. King. 1976. Symbolic execution and program testing. Communications of the ACM 19, 7 (July 1976), 385--394.
51. D. B. Kirk and J. K. Strosnider. 1990. SMART (strategic memory allocation for real-time) cache design using the MIPS R3000. In Proc. of the 11th RTSS. 322--330.
52. Donald E. Knuth. 1997. The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms. Addison Wesley Longman.
53. Leonidas Kosmidis, Jaume Abella, Eduardo Quinones, and Francisco J. Cazorla. 2013a. A cache design for probabilistically analysable real-time systems. In Proc. of the DATE. 513--518.
54. L. Kosmidis, J. Abella, R. Quinones, and F. J. Cazorla. 2013b. Multi-level unified caches for probabilistically time analysable real-time systems. In Proc. of the 34th RTSS. IEEE, 360--371.
55. Lea, D. 1996. A Memory Allocator. Unix/Mail, 6/96.
56. Jaekyu Lee, Hyesoon Kim, and Richard Vuduc. 2012. When prefetching works, when it doesn’t, and why. ACM Trans. Archit. Code Optim. 9, 1, Article 2 (March 2012), 29 pages.
57. Yun Liang, Huping Ding, Tulika Mitra, Abhik Roychoudhury, Yan Li, and Vivy Suhendra. 2012. Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Systems 48, 6 (2012), 638--680.
58. Yun Liang and T. Mitra. 2010. Instruction cache locking using temporal reuse profile. In Proc. of the 47th ACM/IEEE DAC. 344--349.
59. Jochen Liedtke, Hermann Haertig, and Michael Hohmuth. 1997. OS-controlled cache predictability for real-time systems. In Proc. of the 3rd IEEE RTAS. IEEE, 213--224.
60. Jiang Lin, Qingda Lu, Xiaoning Ding, Zhao Zhang, Xiaodong Zhang, and P. Sadayappan. 2008. Gaining insights into multicore cache partitioning: Bridging the gap between simulation and real systems. In Proc. of the HPCA. IEEE, 367--378.
61. Chun Liu, Anand Sivasubramaniam, and Mahmut Kandemir. 2004. Organizing the last line of defense before hitting the memory wall for CMPs. In Proc. of the 10th HPCA. IEEE, 176.
62. C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20, 1 (Jan. 1973), 46--61.
63. Tiantian Liu, Minming Li, and C. J. Xue. 2009a. Instruction cache locking for real-time embedded systems with multi-tasks. In Proc. of the 15th IEEE RTCSA. 494--499.
64. Tiantian Liu, Minming Li, and C. J. Xue. 2009b. Minimizing WCET for real-time embedded systems via static instruction cache locking. In Proc. of the 15th IEEE RTAS. 35--44.
65. Qingda Lu, Jiang Lin, Xiaoning Ding, Zhao Zhang, Xiaodong Zhang, and P. Sadayappan. 2009. Soft-OLP: Improving hardware cache performance through software-controlled object-level partitioning. In Proc. of the 18th PACT. 246--257.
66. R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni. 2013. Real-time cache management framework for multi-core architectures. In Proc. of the 19th IEEE RTAS. 45--54.
67. Renato Mancuso, Rodolfo Pellizzoni, Marco Caccamo, Lui Sha, and Heechul Yun. 2015. WCET(m) estimation in multi-core systems using single core equivalence. In Proc. of the 27th ECRTS.
68. Miguel Masmano, Ismael Ripoll, and Alfons Crespo. 2006. A comparison of memory allocators for real-time applications. In Proc. of the 4th JTRES. ACM, 68--76.
69. M. Masmano, I. Ripoll, A. Crespo, and J. Real. 2004. TLSF: A new dynamic memory allocator for real-time systems. In Proc. of the 16th ECRTS. 79--88.
70. S. Mohan, M. Caccamo, L. Sha, R. Pellizzoni, G. Arundale, R. Kegley, and D. de Niz. 2011. Using multicore architectures in cyber-physical systems. In Proc. of the Workshop on Developing Dependable and Secure Automotive Cyber-Physical Systems from Components.
71. Frank Mueller. 1995. Compiler support for software-based cache partitioning. In Proc. of the ACM SIGPLAN LCTES. ACM, 125--133.
72. S. P. Muralidhara, M. Kandemir, and P. Raghavan. 2010. Intra-application cache partitioning. In Proc. of the 25th IEEE IPDPS. 1--12.
73. T. Ogasawara. 1995. An algorithm with constant execution time for dynamic storage allocation. In Proc. of the 2Nd RTCSA. IEEE, 21.
74. S. Panchamukhi and F. Mueller. 2015. Providing task isolation via TLB coloring. In Proc. of the 21th RTAS.
75. Marco Paolieri, Eduardo Quiñones, Francisco J Cazorla, Guillem Bernat, and Mateo Valero. 2009. Hardware support for WCET analysis of hard real-time multicore systems. In ACM SIGARCH Computer Architecture News, Vol. 37. ACM, 57--68.
76. R. Pellizzoni. 2010. Predictable and Monitored Execution for COTS-based Real-Time Embedded Systems. Ph.D. Dissertation. University of Illinois at Urbana-Champaign.
77. I. Puaut. 2002. Real-time performance of dynamic memory allocation algorithms. In Proc. of the 14th ECRTS. 41--49.
78. I. Puaut and D. Decotigny. 2002. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In Proc. of the 23rd IEEE RTSS. 114--123.
79. I. Puaut and C. Pais. 2007. Scratchpad memories vs locked caches in hard real-time systems: A quantitative comparison. In Proc. of DATE. 1--6.
80. Moinuddin K. Qureshi and Yale N. Patt. 2006. Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches. In Proc. of MICRO 39. IEEE, 423--432.
81. Nauman Rafique, Won-Taek Lim, and Mithuna Thottethodi. 2006. Architectural support for operating system-driven CMP cache management. In Proc. of the 15th PACT. ACM, 2--12.
82. Parthasarathy Ranganathan, Sarita Adve, and Norman P. Jouppi. 2000. Reconfigurable caches and their application to media processing. In Proc. of the 27th ISCA. ACM, 214--224.
83. Jan Reineke, Daniel Grund, Christoph Berg, and Reinhard Wilhelm. 2007. Timing predictability of cache replacement policies. Real-Time Systems 37, 2 (Nov. 2007), 99--122.
84. Theodore Romer, Dennis Lee, Brian N. Bershad, and J. Bradley Chen. 1994. Dynamic page mapping policies for cache conflict resolution on standard hardware. In Proc. of the 1st OSDI. 255--266.
85. Abhik Sarkar, Frank Mueller, and Harini Ramaprasad. 2011. Predictable task migration for locked caches in multi-core systems. In Proc. of the LCTES’11. ACM, 131--140.
86. Abhik Sarkar, Frank Mueller, and Harini Ramaprasad. 2012. Static task partitioning for locked caches in multi-core real-time systems. In Proc. of the CASES’12. ACM, 161--170.
87. Timothy Sherwood, Brad Calder, and Joel Emer. 1999. Reducing cache misses using hardware and software page placement. In Proc. of the 13th ICS. ACM, 155--164.
88. Mladen Slijepcevic, Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. 2014. Time-analysable non-partitioned shared caches for real-time multicore systems. In Proc. of the 51st ACM/IEEE DAC. IEEE, 1--6.
89. S. Srikantaiah, M. Kandemir, and M. J. Irwin. 2008. Adaptive set pinning: Managing shared caches in chip multiprocessors. In Proc. of the 13th ASPLOS. ACM, 135--144.
90. G. E. Suh, L. Rudolph, and S. Devadas. 2004. Dynamic partitioning of shared cache memory. The Journal of Supercomputing 28, 1 (April. 2004), 7--26.
91. Vivy Suhendra and Tulika Mitra. 2008. Exploring locking & partitioning for predictable shared caches on multi-cores. In Proc. of the 45th DAC. ACM, 300--303.
92. Q. Sun and H. Tian. 2011. A flexible automatic source-level instrumentation framework for dynamic program analysis. In Proc. of the 2nd IEEE ICSESS. 401--404.
93. Xiao Hui Sun, JinLin Wang, and Xiao Chen. 2007. An improvement of TLSF algorithm. In Proc. of the 15th IEEE-NPSS. 1--5.
94. K. T. Sundararajan, T. M. Jones, and N. P. Topham. 2013. RECAP: Region-aware cache partitioning. In Proc. of the 31st IEEE ICCD. 294--301.
95. D. Tam, R. Azimi, L. Soares, and M. Stumm. 2007. Managing shared L2 caches on multicore systems in software. In Proc. of the WIOSCA.
96. George Taylor, Peter Davies, and Michael Farmwald. 1990. The TLB slice - a low-cost high-speed address translation mechanism. In Proc. of the 17th ISCA. ACM, New York, NY, 355--363.
97. S. Udayakumaran, A. Dominguez, and R. Barua. 2006. Dynamic allocation for scratch-pad memory using compile-time decisions. ACM Transactions on Embedded Computing Systems (TECS) 5, 2 (May 2006).
98. K. Varadarajan, S. K. Nandy, V. Sharda, A. Bharadwaj, R. Iyer, S. Makineni, and D. Newell. 2006. Molecular Caches: A caching structure for dynamic creation of application-specific Heterogeneous cache regions. In Proc. of the 39th MICRO. 433--442.
99. Xavier Vera, Björn Lisper, and Jingling Xue. 2003a. Data Cache locking for higher program predictability. In Proc. of ACM SIGMETRICS. ACM, New York, NY, 272--282.
100. Xavier Vera, Björn Lisper, and Jingling Xue. 2003b. Data Caches in multitasking hard real-time systems. In Proc. of the RTSS’03. IEEE, 154--.
101. B. C. Ward, J. L. Herman, C. J. Kenna, and J. H. Anderson. 2013. Making shared caches more predictable on multicore platforms. In Proc. of the 25th ECRTS. 157--167.
102. I. Wasly and I. Pellizzoni. 2014. Hiding memory latency using fixed priority scheduling. In Proc. of the 20th IEEE RTAS.
103. J. Whitham and N. Audsley. 2009. Implementing time-predictable load and store operations. In Proc. EMSOFT. 265--274.
104. Jack Whitham and Neil C. Audsley. 2012. Explicit reservation of local memory in a predictable, preemptive multitasking real-time system. In Proc. of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium. IEEE, 3--12.
105. 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, and Per Stenström. 2008. The worst-case execution-time problem -- overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems 7, 3, Article 36 (May 2008), 53 pages.
106. Andrew Wolfe. 1994. Software-based Cache partitioning for real-time applications. Journal of Computing Software Engineering 2, 3 (March 1994), 315--327.
107. G. Xiaofeng, M. Laurenzano, B. Simon, and A. Snavely. 2005. Reducing overheads for acquiring dynamic memory traces. In Proc. of the IEEE IISWC. 46--55.
108. Jun Yan and Wei Zhang. 2008. WCET analysis for multi-core processors with shared L2 instruction caches. In Proc. of the 14th IEEE RTAS. 80--89.
109. H. Yun, R. Mancuso, Z. P. Wu, and R. Pellizzoni. 2014. PALLOC: DRAM bank-aware memory allocator for performance isolation on multicore platforms. In Proc. of the 20th IEEE RTAS.
110. Wei Zhang and Yan Jun. 2012. Static timing analysis of shared caches for multicore processors. Journal of Computing Science and Engineering 6, 4 (2012), 267--278.
111. Xiao Zhang, Sandhya Dwarkadas, and Kai Shen. 2009. Towards practical page coloring-based multicore cache management. In Proc. of the 4th ACM EuroSys. ACM, 89--102.
112. Sergey Zhuravlev, Juan Carlos Saez, Sergey Blagodurov, Alexandra Fedorova, and Manuel Prieto. 2012. Survey of scheduling techniques for addressing shared resources in multicore processors. Computing Surveys 45, 1, Article 4 (Dec. 2012), 28 pages.

Index Terms

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

      • Microcomputers