A Survey on Static Cache Analysis for Real-Time Systems

Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, Wang Yi

Abstract


Real-time systems are reactive computer systems that must produce their reaction to a stimulus within given time bounds. A vital verification requirement is to estimate the Worst-Case Execution Time (WCET) of programs. These estimates are then used to predict the timing behavior of the overall system. The execution time of a program heavily depends on the underlying hardware, among which cache has the biggest influence. Analyzing cache behavior is very challenging due to the versatile cache features and complex execution environment. This article provides a survey on static cache analysis for real-time systems. We first present the challenges and static analysis techniques for independent programs with respect to different cache features. Then, the discussion is extended to cache analysis in complex execution environment, followed by a survey of existing tools based on static techniques for cache analysis. An outlook for future research is provided at last.


Keywords


Hard real-time; Cache analysis; Worst-case execution time

Full Text:

PDF

References


Martin Alt, Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. Cache behavior prediction by abstract interpretation. In Radhia Cousot and David A. Schmidt, editors, Static Analysis, Third International Symposium, SAS’96, Aachen, Germany, September 24-26, 1996, Proceedings, volume 1145 of Lecture Notes in Computer Science, pages 52–66. Springer, 1996. doi:10.1007/3-540-61739-6_33.

Sebastian Altmeyer and Claire Burguière. A new notion of useful cache block to improve the bounds of cache-related preemption delay. In 21st Euromicro Conference on Real-Time Systems, ECRTS 2009, Dublin, Ireland, July 1-3, 2009, pages 109– 118. IEEE Computer Society, 2009. doi:10.1109/ECRTS.2009.21.

Sebastian Altmeyer, Claire Burguiere, and Reinhard Wilhelm. Computing the maximum blocking time for scheduling with deferred preemption. In Future Dependable Distributed Systems, 2009 Software Technologies for, pages 200–204, March 2009. doi:10.1109/STFSSD.2009.12.

Sebastian Altmeyer, Robert I. Davis, and Claire Maiza. Improved cache related pre-emption delay aware response time analysis for fixed priority preemptive systems. Real-Time Systems, 48(5):499– 526, 2012. doi:10.1007/s11241-012-9152-2.

Sebastian Altmeyer, Claire Maiza, and Jan Reineke. Resilience analysis: tightening the CRPD bound for set-associative caches. In Jaejin Lee and Bruce R. Childers, editors, Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems, LCTES 2010, Stockholm, Sweden, April 13-15, 2010, pages 153–162. ACM, 2010. doi:10.1145/1755888.1755911.

Rajeev Alur and David L. Dill. A theory of timed automata. Theor. Comput. Sci., 126(2):183–235, 1994. doi:10.1016/0304-3975(94)90010-8.

Neil C. Audsley, Alan Burns, Mike M. Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284–292, 1993. URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=238595.

Philip Axer, Rolf Ernst, Heiko Falk, Alain Girault, Daniel Grund, Nan Guan, Bengt Jonsson, Peter Marwedel, Jan Reineke, Christine Rochange, Maurice Sebastian, Reinhard von Hanxleden, Reinhard Wilhelm, and Wang Yi. Building timing predictable embedded systems. ACM Trans. Embedded Comput. Syst., 13(4):82:1–82:37, 2014. doi:10.1145/2560033.

Gogul Balakrishnan and Thomas W. Reps. Analyzing memory accesses in x86 executables. In Evelyn Duesterwald, editor, Compiler Construction, 13th International Conference, CC 2004, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 – April 2, 2004, Proceedings, volume 2985 of Lecture Notes in Computer Science, pages 5–23. Springer, 2004. doi:10.1007/978-3-540-24723-4_2.

Clément Ballabriga and Hugues Cassé. Improving the first-miss computation in set-associative instruction caches. In 20th Euromicro Conference on Real-Time Systems, ECRTS 2008, 2-4 July 2008, Prague, Czech Republic, Proceedings, pages 341–350. IEEE Computer Society, 2008. doi:10.1109/ECRTS.2008.34.

Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. OTAWA: an open toolbox for adaptive WCET analysis. In Sang Lyul Min, Robert G. Pettit IV, Peter P. Puschner, and Theo Ungerer, editors, Software Technologies for Embedded and Ubiquitous Systems – 8th IFIP WG 10.2 International Workshop, SEUS 2010, Waidhofen/Ybbs, Austria, October 13-15, 2010. Proceedings, volume 6399 of Lecture Notes in Computer Science, pages 35–46. Springer, 2010. doi:10.1007/978-3-642-16256-5_6.

Abhijeet Banerjee, Sudipta Chattopadhyay, and Abhik Roychoudhury. Precise micro-architectural modeling for WCET analysis via AI+SAT. In 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013, pages 87–96. IEEE Computer Society, 2013. doi:10.1109/RTAS. 2013.6531082.

Sanjoy K. Baruah. The limited-preemption uniprocessor scheduling of sporadic task systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS 2005), 6-8 July 2005, Palma de Mal lorca, Spain, Proceedings, pages 137–144. IEEE Computer Society, 2005. doi:10.1109/ECRTS.2005.32.

Christoph Berg. PLRU cache domino effects. In Frank Mueller and Frank Mueller, editors, 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, July 4, 2006, Dresden, Germany, volume 4 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2006. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/OASIcs.WCET.2006.672.

Marko Bertogna, Orges Xhani, Mauro Marinoni, Francesco Esposito, and Giorgio C. Buttazzo. Optimal selection of preemption points to minimize preemption overhead. In Karl-Erik Årzén, editor, 23rd Euromicro Conference on Real-Time Systems, ECRTS 2011, Porto, Portugal, 5-8 July, 2011, pages 217–227. IEEE Computer Society, 2011. doi:10.1109/ECRTS.2011.28.

Reinder J. Bril, Sebastian Altmeyer, Martijn M. H. P. van den Heuvel, Robert I. Davis, and Moris Behnam. Integrating cache-related pre-emption delays into analysis of fixed priority scheduling with pre-emption thresholds. In Proceedings of the IEEE 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, December 25, 2014, pages 161–172. IEEE Computer Society, 2014. doi:10.1109/RTSS.2014.25.

Claire Burguière, Jan Reineke, and Sebastian Altmeyer. Cache-related preemption delay computation for set-associative caches – pitfalls and solutions. In Niklas Holsti, editor, 9th Intl. Workshop on Worst-Case Execution Time Analysis, WCET 2009, Dublin, Ireland, July 1-3, 2009, volume 10 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2009. doi:10.4230/OASIcs.WCET.2009.2285.

Claire Burguière and Christine Rochange. A contribution to branch prediction modeling in WCET analysi. In 2005 Design, Automation and Test in Europe Conference and Exposition (DATE 2005), 7-11 March 2005, Munich, Germany, pages 612– 617. IEEE Computer Society, 2005. doi:10.1109/DATE.2005.7.

Alan Burns. Preemptive priority-based scheduling: An appropriate engineering approach. In Sang H. Son, editor, Advances in Real-time Systems, pages 225–248. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995. URL: http://dl.acm.org/citation.cfm?id=207721.207731.

José V. Busquets-Mataix, Juan José Serrano, Rafael Ors, Pedro J. Gil, and Andy J. Wellings. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In 2nd IEEE Real-Time Technology and Applications Symposium, RTAS’96, Boston, MA, USA, June 10-12, 1996, pages 204–212. IEEE Computer Society, 1996. doi:10.1109/RTTAS.1996.509537.

Giorgio C. Buttazzo. Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 2004.

Franck Cassez, René Rydhof Hansen, and Mads Chr. Olesen. What is a timing anomaly? In Tullio Vardanega, editor, 12th International Workshop on Worst-Case Execution Time Analysis, WCET 2012, July 10, 2012, Pisa, Italy, volume 23 of OpenAccess Series in Informatics (OASIcs), pages 1–12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2012. doi:10.4230/OASIcs.WCET.2012.1.

Siddhartha Chatterjee, Erin Parker, Philip J. Hanlon, and Alvin R. Lebeck. Exact analysis of the cache behavior of nested loops. In Michael Burke and Mary Lou Soffa, editors, Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Snowbird, Utah, USA, June 20-22, 2001, pages 286–297. ACM, 2001. doi:10.1145/378795. 378859.

Sudipta Chattopadhyay and Abhik Roychoudhury. Unified cache modeling for WCET analysis and layout optimizations. In Theodore P. Baker, editor, Proceedings of the 30th IEEE Real-Time Systems Symposium, RTSS 2009, Washington, DC, USA, 1-4 December 2009, pages 47–56. IEEE Computer Society, 2009. doi:10.1109/RTSS. 2009.20.

Sudipta Chattopadhyay and Abhik Roychoudhury. Scalable and precise refinement of cache timing analysis via model checking. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 – December 2, 2011, pages 193–203. IEEE Computer Society, 2011. doi:10.1109/RTSS.2011.25.

Edmund M. Clarke, Orna Grumberg, and Doron A. Peled. Model checking. MIT Press, 2001.

Philippe Clauss. Counting solutions to linear and nonlinear constraints through ehrhart polynomials: Applications to analyze and transform scientific programs. In Pen-Chung Yew, editor, Proceedings of the 10th international conference on Supercomputing, ICS 1996, Philadelphia, PA, USA, May 25-28, 1996, pages 278–285. ACM, 1996. doi:10.1145/237578.237617.

Antoine Colin and Isabelle Puaut. Worst case execution time analysis for a processor with branch prediction. Real-Time Systems, 18(2/3):249–274, 2000. doi:10.1023/A:1008149332687.

PREDATOR Consortium. The predator project page, 2011. URL: http://www.predator-project.eu/consortium.htm.

Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Robert M. Graham, Michael A. Harrison, and Ravi Sethi, editors, Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, pages 238– 252. ACM, 1977. doi:10.1145/512950.512973.

Christoph Cullmann. Cache persistence analysis: Theory and practice. ACM Trans. Embedded Comput. Syst., 12(1s):40, 2013. doi:10.1145/2435227.2435236.

Andreas Engelbredt Dalsgaard, Mads Chr. Olesen, Martin Toft, René Rydhof Hansen, and Kim Guldstrand Larsen. METAMOC: modular execution time analysis using model checking. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OpenAccess Series in Informatics (OASIcs), pages 113–123. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2010. doi: 10.4230/OASIcs.WCET.2010.113.

Andreas Engelbredt Dalsgaard, Mads Chr. Olesen, Martin Toft, René Rydhof Hansen, and Kim Guldstrand Larsen. METAMOC: modular execution time analysis using model checking. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OpenAccess Series in Informatics (OASIcs), pages 113–123. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2010. doi:10.4230/OASIcs.WCET.2010.113.

Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. doi:10.1145/1978802.1978814.

Goran Doychev, Dominik Feld, Boris Köpf, Laurent Mauborgne, and Jan Reineke. Cacheaudit: A tool for the static analysis of cache side channels. In Samuel T. King, editor, Proceedings of the 22th USENIX Security Symposium, Washington, DC, USA, August 14-16, 2013, pages 431–446. USENIX Association, 2013. URL: https://www.usenix.org/conference/usenixsecurity13/technical-sessions/paper/doychev.

Heiko Falk and Helena Kotthaus. Wcet-driven cache-aware code positioning. In Rajesh K. Gupta and Vincent John Mooney, editors, Proceedings of the 14th International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES 2011, part of the Seventh Embedded Systems Week, ESWeek 2011, Taipei, Taiwan, October 9-14, 2011, pages 145–154. ACM, 2011. doi:10.1145/2038698.2038722.

Christian Ferdinand. Cache Behavior Prediction for Real-Time Systems. PhD thesis, Saarland University, Saarbruecken, Germany, 1997. ISBN:3-9307140-31-0.

Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. Real-Time Systems, 17(2-3):131–181, 1999. doi:10.1023/A:1008186323068.

Somnath Ghosh, Margaret Martonosi, and Sharad Malik. Cache miss equations: a compiler framework for analyzing and tuning memory behavior. ACM Trans. Program. Lang. Syst., 21(4):703–746, 1999. doi:10.1145/325478.325479.

Daniel Grund. Static Cache Analysis for Real-Time Systems – LRU, FIFO, PLRU. PhD thesis, Saarland University, Saarbruecken, Germany, 2011. ISBN: 978-3-8442-1699-8.

Daniel Grund and Jan Reineke. Abstract interpretation of FIFO replacement. In Jens Palsberg and Zhendong Su, editors, Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings, volume 5673 of Lecture Notes in Computer Science, pages 120–136. Springer, 2009. doi:10.1007/978-3-642-03237-0_10.

Daniel Grund and Jan Reineke. Precise and efficient fifo-replacement analysis based on static phase detection. In 22nd Euromicro Conference on Real-Time Systems, ECRTS 2010, Brussels, Belgium, July 6-9, 2010, pages 155–164. IEEE Computer Society, 2010. doi:10.1109/ECRTS.2010.8.

Daniel Grund and Jan Reineke. Toward precise PLRU cache analysis. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OpenAccess Series in Informatics (OASIcs), pages 23– 35. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2010. doi:10.4230/OASIcs. WCET.2010.23.

Daniel Grund, Jan Reineke, and Gernot Gebhard. Branch target buffers: WCET analysis framework and timing predictability. Journal of Systems Architecture – Embedded Systems Design, 57(6):625– 637, 2011. doi:10.1016/j.sysarc.2010.05.013.

Nan Guan, Mingsong Lv, Wang Yi, and Ge Yu. WCET analysis with MRU caches: Challenging LRU for predictability. In Marco Di Natale, editor, 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium, Beijing, China, April 16-19, 2012, pages 55–64. IEEE Computer Society, 2012. doi:10.1109/RTAS.2012.31.

Nan Guan, Martin Stigge, Wang Yi, and Ge Yu. Cache-aware scheduling and analysis for multicores. In Samarjit Chakraborty and Nicolas Halbwachs, editors, Proceedings of the 9th ACM & IEEE International conference on Embedded software, EMSOFT 2009, Grenoble, France, October 12-16, 2009, pages 245–254. ACM, 2009. doi:10.1145/1629335.1629369.

Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi. FIFO cache analysis for WCET estimation: a quantitative approach. In Enrico Macii, editor, Design, Automation and Test in Europe, DATE 13, Grenoble, France, March 18-22, 2013, pages 296–301. EDA Consortium San Jose, CA, USA / ACM DL, 2013. doi:10.7873/DATE.2013.073.

Jan Gustafsson. WCET challenge 2006 – technical report. Technical Report ISSN 1404-3041 ISRN MDH-MRTC-206/2007-1-SE, Mälardalen University Sweden, January 2007. URL: http://www.es.mdh.se/publications/1020-.

Jan Gustafsson, Andreas Ermedahl, Christer Sandberg, and Björn Lisper. Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS 2006), 5-8 December 2006, Rio de Janeiro, Brazil, pages 57–66. IEEE Computer Society, 2006. doi:10.1109/RTSS.2006.12.

Andreas Gustavsson, Andreas Ermedahl, Björn Lisper, and Paul Pettersson. Towards WCET analysis of multicore architectures using UPPAAL. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OpenAccess Series in Informatics (OA- SIcs), pages 101–112. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2010. doi:10.4230/OASIcs.WCET.2010.101.

Sebastian Hahn and Daniel Grund. Relational cache analysis for static timing analysis. In Robert Davis, editor, 24th Euromicro Conference on Real-Time Systems, ECRTS 2012, Pisa, Italy, July 11-13, 2012, pages 102–111. IEEE Computer Society, 2012. doi:10.1109/ECRTS.2012.14.

Sebastian Hahn, Jan Reineke, and Reinhard Wilhelm. Towards compositionality in execution time analysis: definition and challenges. SIGBED Review, 12(1):28–36, 2015. doi:10.1145/2752801.2752805.

Reinhard von Hanxleden, Niklas Holsti, Björn Lisper, Erhard Ploedereder, Armelle Bonenfant, Hugues Cassé, Sven Bünte, Wolfgang Fellger, Sebastian Gepperth, Jan Gustafsson, Benedikt Huber, Nazrul Mohammad Islam, Daniel Kästner, Raimund Kirner, Laura Kovacs, Felix Krause, Marianne de Michiel, Mads Christian Olesen, Adrian Prantl, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Simon Wegener, Michael Zolda, and Jakob Zwirchmayr. WCET tool challenge 2011: Report. In the 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011), July 2011.

Damien Hardy, Thomas Piquet, and Isabelle Puaut. Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In Theodore P. Baker, editor, Proceedings of the 30th IEEE Real-Time Systems Symposium, RTSS 2009, Washington, DC, USA, 1-4 December 2009, pages 68–77. IEEE Computer Society, 2009. doi:10.1109/RTSS.2009.34.

Damien Hardy and Isabelle Puaut. WCET analysis of multi-level non-inclusive set-associative instruction caches. In Proceedings of the 29th IEEE Real-Time Systems Symposium, RTSS 2008, Barcelona, Spain, 30 November – 3 December 2008, pages 456–466. IEEE Computer Society, 2008. doi:10.1109/RTSS.2008.10.

Damien Hardy and Isabelle Puaut. WCET analysis of instruction cache hierarchies. Journal of Systems Architecture – Embedded Systems Design, 57(7):677–694, 2011. doi:10.1016/j.sysarc.2010.08.007.

Reinhold Heckmann and Christian Ferdinand. Worst-case execution time prediction by static program analysis. The whitepaper of aiT, 2014. URL: https://www.absint.com/aiT_WCET.pdf.

Reinhold Heckmann, Marc Langenbach, Stephan Thesing, and Reinhard Wilhelm. The influence of processor architecture on the design and the results of WCET tools. Proceedings of the IEEE, 91(7):1038–1054, 2003. doi:10.1109/JPROC.2003.814618.

John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5th edition, 2011.

Heptane. The Heptane tool page, 2013. URL:http://www.irisa.fr/alf/index.php?option=com_content&view=article&id=29&Itemid=0〈=en.

Niklas Holsti, Jan Gustafsson, Guillem Bernat, Clément Ballabriga, Armelle Bonenfant, Roman Bourgade, Hugues Cassé, Daniel Cordes, Albrecht Kadlec, Raimund Kirner, Jens Knoop, Paul Lokuciejewski, Nicholas Merriam, Marianne De Michiel, Adrian Prantl, Bernhard Rieder, Christine Rochange, Pascal Sainrat, and Markus Schordan. WCET 2008 – report from the tool challenge 2008 – 8th intl. workshop on worst-case execution time (WCET) analysis. In Raimund Kirner, editor, 8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, Prague, Czech Republic, July 1, 2008, volume 8 of OpenAccess Series in Informatics (OASIcs). Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2008. URL: http://drops.dagstuhl.de/opus/volltexte/2008/1663, doi:10.4230/OASIcs.WCET.2008.1663.

Bach Khoa Huynh, Lei Ju, and Abhik Roychoudhury. Scope-aware data cache analysis for WCET estimation. In 17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011, Chicago, Illinois, USA, 11-14 April 2011, pages 203–212. IEEE Computer Society, 2011. doi:10.1109/RTAS.2011.27.

Lei Ju, Samarjit Chakraborty, and Abhik Roychoudhury. Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In Design, Automation Test in Europe Conference Exhibition, 2007, pages 1–6, April 2007. doi:10.1109/DATE.2007.364534.

Gary A. Kildall. A unified approach to global program optimization. In Patrick C. Fischer and Jeffrey D. Ullman, editors, Conference Record of the ACM Symposium on Principles of Programming Languages, Boston, Massachusetts, USA, October 1973, pages 194–206. ACM Press, 1973. doi:10.1145/512927.512945.

Sung-Kwan Kim, Sang Lyul Min, and Rhan Ha. Efficient worst case timing analysis of data caching. In 2nd IEEE Real-Time Technology and Applications Symposium, RTAS’96, Boston, MA, USA, June 10-12, 1996, pages 230–240. IEEE Computer Society, 1996. doi:10.1109/RTTAS. 1996.509540.

Chang-Gun Lee, Joosun Hahn, Yang-Min Seo, Sang Lyul Min, Rhan Ha, Seongsoo Hong, Chang Yun Park, Minsuk Lee, and Chong-Sang Kim. Analysis of cache-related preemption delay in fixed-priority preemtive scheduling. IEEE Trans. Computers, 47(6):700–713, 1998. doi:10.1109/12.689649.

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. WCET analysis of multi-level setassociative data caches. In Niklas Holsti, editor, 9th Intl. Workshop on Worst-Case Execution Time Analysis, WCET 2009, Dublin, Ireland, July 1-3, 2009, volume 10 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2009. doi:10.4230/OASIcs.WCET.2009.2283.

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. Shared data cache conflicts reduction for wcet computation in multi-core architectures. In Proc. of the 18th Real-Time and Network Systems, Toulouse, France, 2010.

Xianfeng Li, Abhik Roychoudhury, and Tulika Mitra. Modeling out-of-order processors for WCET analysis. Real-Time Systems, 34(3):195–227, 2006. doi:10.1007/s11241-006-9205-5.

Xianfeng Li, Liang Yun, Tulika Mitra, and Abhik Roychoudhury. Chronos: A timing analyzer for embedded software. Sci. Comput. Program., 69(1-3):56–67, 2007. doi:10.1016/j.scico.2007. 01.014.

Yau-Tsun Steven Li and Sharad Malik. Performance analysis of embedded software using implicit path enumeration. In DAC, pages 456–461, 1995. doi:10.1145/217474.217570.

Yau-Tsun Steven Li, Sharad Malik, and Andrew Wolfe. Cache modeling for real-time software: beyond direct mapped instruction caches. In Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS’96), December 4-6, 1996, Washington, DC, USA, pages 254–263. IEEE Computer Society, 1996. doi:10.1109/REAL.1996.563722.

Yun Liang, Huping Ding, Tulika Mitra, Abhik Roychoudhury, Yan Li, and Vivy Suhendra. Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Systems, 48(6):638–680, 2012. doi:10.1007/s11241-012-9160-2.

Fang Liu and Yan Solihin. Understanding the behavior and implications of context switch misses. TACO, 7(4):21, 2010. doi:10.1145/1880043.1880048.

Tiantian Liu, Yingchao Zhao, Minming Li, and Chun Jason Xue. Task assignment with cache partitioning and locking for WCET minimization on mpsoc. In 39th International Conference on Parallel Processing, ICPP 2010, San Diego, California, USA, 13-16 September 2010, pages 573–582. IEEE Computer Society, 2010. doi:10.1109/ICPP.2010.65.

Thomas Lundqvist and Per Stenström. A method to improve the estimated worst-case performance of data caching. In 6th International Workshop on Real-Time Computing and Applications Symposium (RTCSA’99), 13-16 December 1999, Hong Kong, China, pages 255–262. IEEE Computer Society, 1999. doi:10.1109/RTCSA.1999.811244.

Thomas Lundqvist and Per Stenström. A method to improve the estimated worst-case performance of data caching. In 6th International Workshop on Real-Time Computing and Applications Symposium (RTCSA’99), 13-16 December 1999, Hong Kong, China, pages 255–262. IEEE Computer Society, 1999. doi:10.1109/RTCSA.1999.811244.

Will Lunniss, Sebastian Altmeyer, and Robert I. Davis. A comparison between fixed priority and EDF scheduling accounting for cache related preemption delays. LITES, 1(1):01:1–01:24, 2014. doi:10.4230/LITES-v001-i001-a001.

Will Lunniss, Sebastian Altmeyer, Claire Maiza, and Robert I. Davis. Integrating cache related pre-emption delay analysis into EDF scheduling. In 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013, pages 75–84. IEEE Computer Society, 2013. doi:10. 1109/RTAS.2013.6531081.

Mingsong Lv, Nan Guan, Qingxu Deng, Ge Yu, and Wang Yi. Mcait – A timing analyzer for multicore real-time software. In Tevfik Bultan and Pao-Ann Hsiung, editors, Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011. Proceedings, volume 6996 of Lecture Notes in Computer Science, pages 414–417. Springer, 2011. doi:10.1007/978-3-642-24372-1_29.

Mohamed Abdel Maksoud and Jan Reineke. A compiler optimization to increase the efficiency of WCET analysis. In Mathieu Jan, Belgacem Ben Hedia, Joël Goossens, and Claire Maiza, editors, 22nd International Conference on Real-Time Networks and Systems, RTNS’14, Versaille, France, October 8-10, 2014, page 87. ACM, 2014. doi:10.1145/2659787.2659825.

Renato Mancuso, Roman Dudko, Emiliano Betti, Marco Cesati, Marco Caccamo, and Rodolfo Pellizzoni. Real-time cache management framework for multi-core architectures. In 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013, pages 45–54. IEEE Computer Society, 2013. doi:10.1109/RTAS.2013.6531078.

José Marinho, Vincent Nélis, Stefan M. Petters, and Isabelle Puaut. An improved preemption delay upper bound for floating non-preemptive region. In 7th IEEE International Symposium on Industrial Embedded Systems, SIES 2012, Karlsruhe, Germany, June 20-22, 2012, pages 57–66. IEEE, 2012. doi:10.1109/SIES.2012.6356570.

José Marinho, Vincent Nélis, Stefan M. Petters, and Isabelle Puaut. Preemption delay analysis for floating non-preemptive region scheduling. In Wolfgang Rosenstiel and Lothar Thiele, editors, 2012 Design, Automation & Test in Europe Conference & Exhibition, DATE 2012, Dresden, Germany, March 12-16, 2012, pages 497–502. IEEE, 2012. doi:10.1109/DATE.2012.6176520.

Florian Martin, Martin Alt, Reinhard Wilhelm, and Christian Ferdinand. Analysis of loops. In Kai Koskimies, editor, Compiler Construction, 7th International Conference, CC’98, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS’98, Lisbon, Portugal, March 28 – April 4, 1998, Proceedings, volume 1383 of Lecture Notes in Computer Science, pages 80–94. Springer, 1998. doi:10.1007/BFb0026424.

Richard L. Mattson, Jan Gecsei, Donald R. Slutz, and Irving L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78–117, 1970. doi:10.1147/sj.92.0078.

Frank Mueller. Timing predictions for multi-level caches. In In ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages 29–36, 1997.

Frank Mueller and David B. Whalley. Fast instruction cache analysis via static cache simulation. In Proceedings 28st Annual Simulation Symposium (SS’95), April 25-28, 1995, Santa Barbara, California, USA, pages 105–114. IEEE Computer Society, 1995. doi:10.1109/SIMSYM.1995.393589.

Frank Müller. Generalizing timing predictions to set-associative caches. In Proceedings of the Ninth Euromicro Workshop on Real-Time Systems, RTS 1997, 11-13 June, 1997, Toledo, Spain, pages 64–71. IEEE Computer Society, 1997. doi:10.1109/EMWRTS.1997.613765.

Frank Müller. Timing analysis for instruction caches. Real-Time Systems, 18(2/3):217–247, 2000. doi:10.1023/A:1008145215849.

Hemendra Singh Negi, Tulika Mitra, and Abhik Roychoudhury. Accurate estimation of cache-related preemption delay. In Rajesh Gupta, Yukihiro Nakamura, Alex Orailoglu, and Pai H. Chou, editors, Proceedings of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, CODES+ISSS 2003, Newport Beach, CA, USA, October 1-3, 2003, pages 201–206. ACM, 2003. doi:10.1145/944645.944698.

Marco Paolieri, Eduardo Quiñones, Francisco J. Cazorla, Guillem Bernat, and Mateo Valero. Hardware support for WCET analysis of hard real-time multicore systems. In Stephen W. Keckler and Luiz André Barroso, editors, 36th International Symposium on Computer Architecture(ISCA 2009), June 20-24, 2009, Austin, TX, USA, pages 57–68. ACM, 2009. doi:10.1145/1555754.1555764.

Kaustubh Patil, Kiran Seth, and Frank Mueller. Compositional static instruction cache simulation. In David B. Whalley and Ron Cytron, editors, Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’04), Washington, DC, USA, June 11-13, 2004, pages 136–145. ACM, 2004. doi:10.1145/997163.997183.

Rodolfo Pellizzoni, Emiliano Betti, Stanley Bak, Gang Yao, John Criswell, Marco Caccamo, and Russell Kegley. A predictable execution model for cots-based embedded systems. In 17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011, Chicago, Illinois, USA, 11-14 April 2011, pages 269–279. IEEE Computer Society, 2011. doi:10.1109/RTAS.2011.33.

Guillaume Phavorin and Pascal Richard. Cacherelated preemption delays and real-time scheduling: A survey for uniprocessor systems. Technical report, Laboratoire d’Informatique et d’Automatique pour les Systèmes, 2015. URL:http://www.lias-lab.fr/publications/19296/survey.pdf.

Guillaume Phavorin, Pascal Richard, Joël Goossens, Thomas Chapeaux, and Claire Maiza. Scheduling with preemption delays: anomalies and issues. In Julien Forget, editor, Proceedings of the 23rd International Conference on Real Time Networks and Systems, RTNS 2015, Lille, France, November 4-6, 2015, pages 109–118. ACM, 2015. doi:10.1145/2834848.2834853.

Harini Ramaprasad and Frank Mueller. Bounding worst-case data cache behavior by analytically deriving cache reference patterns. In 11th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2005), 7-10 March 2005, San Francisco, CA, USA, pages 148–157. IEEE Computer Society, 2005. doi:10.1109/RTAS. 2005.12.

Harini Ramaprasad and Frank Mueller. Bounding preemption delay within data cache reference patterns for real-time tasks. In 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2006), 4-7 April 2006, San Jose, California, USA, pages 71–80. IEEE Computer Society, 2006. doi:10.1109/RTAS.2006.14.

Harini Ramaprasad and Frank Mueller. Bounding worst-case response time for tasks with non-preemptive regions. In Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2008, April 22-24, 2008, St. Louis, Missouri, USA, pages 58–67. IEEE Computer Society, 2008. doi:10.1109/RTAS.2008.18.

Harini Ramaprasad and Frank Mueller. Tightening the bounds on feasible preemptions. ACM Trans. Embedded Comput. Syst., 10(2):27, 2010. doi:10.1145/1880050.1880063.

Jan Reineke. Caches in WCET Analysis: Predictability – Competitiveness – Sensitivity. PhD thesis, Saarland University, 2009. URL: http://www.epubli.de/shop/buch/Caches-in-WCET-Analysis-Jan-Reineke-9783941071698/12835.

Jan Reineke, Sebastian Altmeyer, Daniel Grund, Sebastian Hahn, and Claire Maiza. Selfish-lru: Preemption-aware caching for predictability and performance. In 20th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2014, Berlin, Germany, April 15-17, 2014, pages 135–144. IEEE Computer Society, 2014. doi:10.1109/RTAS.2014.6925997.

Jan Reineke and Daniel Grund. Relative competitive analysis of cache replacement policies. In Krisztián Flautner and John Regehr, editors, Proceedings of the 2008 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’08), Tucson, AZ, USA, June 12-13, 2008, pages 51–60. ACM, 2008. doi:10.1145/1375657.1375665.

Jan Reineke and Daniel Grund. Sensitivity of cache replacement policies. ACM Trans. Embedded Comput. Syst., 12(1s):42, 2013. doi:10.1145/2435227.2435238.

Jan Reineke, Daniel Grund, Christoph Berg, and Reinhard Wilhelm. Timing predictability of cache replacement policies. Real-Time Systems, 37(2):99–122, 2007. doi:10.1007/s11241-007-9032-3.

Jan Reineke, Björn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anomalies. In Frank Mueller, editor, 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, July 4, 2006, Dresden, Germany, volume 4 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2006. doi:10.4230/OASIcs.WCET. 2006.671.

Jörn Schneider. Cache and pipeline sensitive fixed priority scheduling for preemptive real-time systems. In Proceedings of the 21st IEEE Real- Time Systems Symposium (RTSS 2000), Orlando, Florida, USA, 27-30 November 2000, pages 195– 204. IEEE Computer Society, 2000. doi:10.1109/REAL.2000.896009.

Martin Schoeberl. A java processor architecture for embedded real-time systems. Journal of Systems Architecture – Embedded Systems Design, 54(1-2):265–286, 2008. doi:10.1016/j.sysarc.2007.06.001.

Martin Schoeberl, Wolfgang Puffitsch, Rasmus Ulslev Pedersen, and Benedikt Huber. Worst-case execution time analysis for a java processor. Softw., Pract. Exper., 40(6):507–542, 2010. doi:10.1002/spe.968.

Rathijit Sen and Y. N. Srikant. WCET estimation for executables in the presence of data caches. In Christoph M. Kirsch and Reinhard Wilhelm, editors, Proceedings of the 7th ACM & IEEE International conference on Embedded software, EMSOFT 2007, September 30 – October 3, 2007, Salzburg, Austria, pages 203–212. ACM, 2007. doi:10.1145/1289927.1289960.

Tyler Sondag and Hridesh Rajan. A more precise abstract domain for multi-level caches for tighter WCET analysis. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, November 30 – December 3, 2010, pages 395–404. IEEE Computer Society, 2010. doi:10.1109/RTSS.2010.8.

Jan Staschulat and Rolf Ernst. Worst case timing analysis of input dependent data cache behavior. In 18th Euromicro Conference on Real-Time Systems, ECRTS’06, 5-7 July 2006, Dresden, Germany, Proceedings, pages 227–236. IEEE Computer Society, 2006. doi:10.1109/ECRTS.2006.33.

Jan Staschulat and Rolf Ernst. Scalable precision cache analysis for real-time software. ACM Trans. Embedded Comput. Syst., 6(4), 2007. doi:10.1145/1274858.1274863.

Jan Staschulat, Simon Schliecker, and Rolf Ernst. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In 17th Euromicro Conference on Real-Time Systems (ECRTS 2005), 6-8 July 2005, Palma de Mal lorca, Spain, Proceedings, pages 41–48. IEEE Computer Society, 2005. doi:10.1109/ECRTS.2005.26.

Martin Stigge and Wang Yi. Graph-based models for real-time workload: a survey. Real-Time Systems, 51(5):602–636, 2015. doi:10.1007/s11241-015-9234-z.

Vivy Suhendra and Tulika Mitra. Exploring locking & partitioning for predictable shared caches on multi-cores. In Limor Fix, editor, Proceedings of the 45th Design Automation Conference, DAC 2008, Anaheim, CA, USA, June 8-13, 2008, pages 300–303. ACM, 2008. doi:10.1145/1391469.1391545.

SWEET. The SWEET tool page, 2012. URL: http://www.mrtc.mdh.se/projects/wcet/sweet/online/content/index.php.

Yudong Tan and Vincent John Mooney III. Timing analysis for preemptive multitasking real-time systems with caches. ACM Trans. Embedded Comput. Syst., 6(1), 2007. doi:10.1145/1210268.1210275.

Yudong Tan and Vincent John Mooney. Integrated intra- and inter-task cache analysis for preemptive multi-tasking real-time systems. In Henk Schepers, editor, Software and Compilers for Embedded Systems, 8th International Workshop, SCOPES 2004, Amsterdam, The Netherlands, September 2-3, 2004, Proceedings, volume 3199 of Lecture Notes in Computer Science, pages 182–199. Springer, 2004. doi:10.1007/978-3-540-30113-4_14.

Henrik Theiling, Christian Ferdinand, and Reinhard Wilhelm. Fast and precise WCET prediction by separated cache and path analyses. Real-Time Systems, 18(2/3):157–179, 2000. doi:10.1023/A:1008141130870.

Hiroyuki Tomiyama and Nikil D. Dutt. Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In Frank Vahid and Jan Madsen, editors, Proceedings of the Eighth International Workshop on Hardware/Software Codesign, CODES 2000, San Diego, California, USA, 2000, pages 67–71. ACM, 2000. doi:10.1145/334012.334025.

Theo Ungerer, Francisco J. Cazorla, Pascal Sainrat, Guillem Bernat, Zlatko Petrov, Christine Rochange, Eduardo Quiñones, Mike Gerdes, Marco Paolieri, Julian Wolf, Hugues Cassé, Sascha Uhrig, Irakli Guliashvili, Michael Houston, Florian Kluge, Stefan Metzlaff, and Jörg Mische. Merasa: Multicore execution of hard real-time applications supporting analyzability. IEEE Micro, 30(5):66–75, 2010. doi:10.1109/MM.2010.78.

Xavier Vera, Björn Lisper, and Jingling Xue. Data caches in multitasking hard real-time systems. In Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS 2003), 3-5 December 2003, Cancun, Mexico, pages 154–165. IEEE Computer Society, 2003. doi:10.1109/REAL.2003.1253263.

Xavier Vera and Jingling Xue. Let’s study whole-program cache behaviour analytically. In Proceedings of the Eighth International Symposium on High-Performance Computer Architecture (HPCA’02), Boston, Massachusettes, USA, February 2-6, 2002, pages 175–186. IEEE Computer Society, 2002. doi:10.1109/HPCA.2002.995708.

Yun Wang and Manas Saksena. Scheduling fixed-priority tasks with preemption threshold. In 6th International Workshop on Real-Time Computing and Applications Symposium (RTCSA’99), 13-16 December 1999, Hong Kong, China, page 328. IEEE Computer Society, 1999. doi:10.1109/RTCSA.1999.811269.

Bryan C. Ward, Jonathan L. Herman, Christopher J. Kenna, and James H. Anderson. Outstanding paper award: Making shared caches more predictable on multicore platforms. In 25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013, pages 157– 167. IEEE Computer Society, 2013. doi:10.1109/ECRTS.2013.26.

Ingomar Wenzel, Raimund Kirner, Bernhard Rieder, and Peter P. Puschner. Measurement-based timing analysis. In Tiziana Margaria and Bernhard Steffen, editors, Leveraging Applications of Formal Methods, Verification and Validation, Third International Symposium, ISoLA 2008, Porto Sani, Greece, October 13-15, 2008. Proceedings, volume 17 of Communications in Computer and Information Science, pages 430– 444. Springer, 2008. doi:10.1007/978-3-540-88479-8_30.

Randall T. White, Christopher A. Healy, David B. Whalley, Frank Mueller, and Marion G. Harmon. Timing analysis for data caches and set-associative caches. In 3rd IEEE Real-Time Technology and Applications Symposium, RTAS’97, Montreal, Canada, June 9-11, 1997, pages 192– 202. IEEE Computer Society, 1997. doi:10.1109/RTTAS.1997.601358.

Randall T. White, Frank Mueller, Christopher A. Healy, David B. Whalley, and Marion G. Harmon. Timing analysis for data and wrap-around fill caches. Real-Time Systems, 17(2-3):209–233, 1999. doi:10.1023/A:1008190423977.

Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem – overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst., 7(3), 2008. doi:10.1145/1347375.1347389.

Reinhard Wilhelm, Daniel Grund, Jan Reineke, Marc Schlickling, Markus Pister, and Christian Ferdinand. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Trans. on CAD of Integrated Circuits and Systems, 28(7):966–978, 2009. doi:10.1109/TCAD.2009.2013287.

Lan Wu and Wei Zhang. A model checking based approach to bounding worst-case execution time for multicore processors. ACM Trans. Embedded Comput. Syst., 11(S2):56, 2012. doi:10.1145/2331147.2331166.

Jun Yan and Wei Zhang. WCET analysis for multi-core processors with shared L2 instruction caches. In Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2008, April 22-24, 2008, St. Louis, Missouri, USA, pages 80–89. IEEE Computer Society, 2008. doi:10.1109/RTAS.2008.6.

Patrick Meumeu Yomsi and Yves Sorel. Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems. In 19th Euromicro Conference on Real-Time Systems, ECRTS’07, 4-6 July 2007, Pisa, Italy, Proceedings, pages 280–290. IEEE Computer Society, 2007. doi:10.1109/ECRTS.2007.15.

Wei Zhang and Jun Yan. Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches. In 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009, Beijing, China, 24-26 August 2009, pages 455–463. IEEE Computer Society, 2009. doi:10.1109/RTCSA.2009.55.

Xiao Zhang, Sandhya Dwarkadas, and Kai Shen. Towards practical page coloring-based multicore cache management. In Wolfgang Schröder-Preikschat, John Wilkes, and Rebecca Isaacs, editors, Proceedings of the 2009 EuroSys Conference, Nuremberg, Germany, April 1-3, 2009, pages 89–102. ACM, 2009. doi:10.1145/1519065.1519076.




DOI: http://dx.doi.org/10.4230/LITES-v003-i001-a005

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v003-i001-a005-pdf2



Copyright (c) 2016 Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing.