Randomized Caches Considered Harmful in Hard Real-Time Systems

Jan Reineke

Abstract


We investigate the suitability of caches with randomized placement and replacement in the context of hard real-time systems. Such caches have been claimed to drastically reduce the amount of information required by static worst-case execution time (WCET) analysis, and to be an enabler for measurement-based probabilistic timing analysis. We refute these claims and conclude that with prevailing static and measurement-based analysis techniques caches with deterministic placement and least-recently-used replacement are preferable over randomized ones.

Keywords


Real-time systems; Caches; Randomization; WCET analysis

Full Text:

PDF

References


Bryan D. Ackland, Alex Anesko, Douglas M. Brinthaupt, Steven J. Daubert, Asawaree Kalavade, Joseph Knobloch, E. Micca, Mallik Moturi, Chris J. Nicol, Jay H. O’Neill, Joseph H. Othmer, Eduard Säckinger, Kanwar J. Singh, J. Sweet, Christopher J. Terman, and Joseph Williams. A single-chip, 1.6 billion, 16-b mac/s multiprocessor DSP. IEEE Journal of Solid-State Circuits, 35(3):412–423, March 2000. doi:10.1109/4.826824.

Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78–101, 1966. doi:10.1147/sj.52.0078.

Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, New York, NY, USA, 1998.

Francisco J. Cazorla, Eduardo Quiñones, Tullio Vardanega, Liliana Cucu, Benoit Triquet, Guillem Bernat, Emery Berger, Jaume Abella, Franck Wartel, Michael Houston, Luca Santinelli, Leonidas Kosmidis, Code Lo, and Dorin Maxim. PROARTIS: Probabilistically analyzable real-time systems. ACM Transactions on Embedded Computing Systems, 12(2s):94:1–94:26, May 2013. doi:10.1145/2465787.2465796.

Liliana Cucu-Grosjean, Luca Santinelli, Michael Houston, Code Lo, Tullio Vardanega, Leonidas Kosmidis, Jaume Abella, Enrico Mezzetti, Eduardo Quiñones, and Francisco J. Cazorla. Measurement-based probabilistic timing analysis for multi-path programs. In 24th Euromicro Conference on Real-Time Systems, ECRTS’12, Pisa, Italy, pages 91–101, Washington, DC, USA, July 2012. IEEE Computer Society. doi:10.1109/ECRTS.2012.31.

Robert I. Davis. Improvements to static probabilistic timing analysis for systems with random cache replacement policies. In 2013 4th Real-Time Scheduling Open Problems Seminar, RTSOPS’13, July 2013.

Robert I. Davis, Luca Santinelli, Sebastian Altmeyer, Claire Maiza, and Liliana Cucu-Grosjean. Analysis of probabilistic cache related pre-emption delays. In 25th Euromicro Conference on Real-Time Systems, ECRTS’13, Paris, France, pages 168–179, July 2013. doi:10.1109/ECRTS.2013.27.

Benoît Dupont de Dinechin, Duco van Amstel, Marc Poulhiès, and Guillaume Lager. Time-critical computing on a single-chip massively parallel processor. In Design, Automation & Test in Europe Conference & Exhibition, DATE’14, Dresden, Germany, pages 513–518, March 2014. doi:10.7873/DATE2014.110.

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

Daniel Grund. Static Cache Analysis for Real-Time Systems – LRU, FIFO, PLRU. PhD thesis, Saarland University, 2012. URL:https://www.epubli.de/shop/buch/Static-Cache-Analysis-for-Real-Time-Systems-Daniel-Grund-9783844216998/13092

Daniel Grund and Jan Reineke. Abstract interpretation of FIFO replacement. In Static Analysis, 16th International Symposium, SAS’09, Los Angeles, CA, USA, pages 120–136. Springer, August 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’10, Brussels, Belgium, pages 155–164. IEEE Computer Society, July 2010. doi:10.1109/ECRTS.2010.8.

Daniel Grund and Jan Reineke. Toward precise PLRU cache analysis. In 10th International Workshop on Worst-Case Execution Time Analysis, WCET’10, Brussels, Belgium, pages 23–35. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, July 2010. doi:10.4230/OASIcs.WCET.2010.23.

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

Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi. FIFO cache analysis for WCET estimation: a quantitative approach. In Design, Automation and Test in Europe, DATE’13, Grenoble, France, pages 296–301. EDA Consortium San Jose, CA, USA / ACM DL, March 2013. URL: http://dl.acm.org/citation.cfm?id=2485362.

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

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.

Freescale Semiconductor Inc. MPC7450 RISC microprocessor family reference manual, rev. 5, 2005.

Dennis Komm, Rastislav Kràlovic, Richard Kràlovic, and Tobias Mömke. Randomized online algorithms with high probability guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science, STACS’14, Lyon, France, pages 470–481. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, March 2014. doi:10.4230/LIPIcs.STACS.2014.470.

Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. A cache design for probabilistically analysable real-time systems. In Design, Automation and Test in Europe, DATE’13, Grenoble, France, pages 513–518. EDA Consortium San Jose, CA, USA / ACM DL, March 2013. URL: http://dl.acm.org/citation.cfm?id=2485416.

Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. Efficient cache designs for probabilistically analysable realtime systems. IEEE Transactions on Computers, 99(PrePrints):1, 2013. doi:10.1109/TC.2013.182.

Leonidas Kosmidis, Charlie Curtsinger, Eduardo Quiñones, Jaume Abella, Emery D. Berger, and Francisco J. Cazorla. Probabilistic timing analysis on conventional cache designs. In Design, Automation and Test in Europe, DATE’13, Grenoble, France, pages 603–606. EDA Consortium San Jose, CA, USA / ACM DL, March 2013. URL:http://dl.acm.org/citation.cfm?id=2485435.

Leonidas Kosmidis, Eduardo Quiñones, Jaume Abella, Tullio Vardanega, and Francisco J. Cazorla. Achieving timing composability with measurement-based probabilistic timing analysis. In 2013 16th IEEE Symposium on Object/Component/Service-oriented Real-time Distributed Computing, ISORC’13, 2013.

Thomas Lundqvist and Per Stenström. Timing anomalies in dynamically scheduled microprocessors. In 20th IEEE Real-Time Systems Symposium, Phoenix, AZ, USA, pages 12–21. IEEE Computer Society, December 1999. doi:10.1109/REAL.1999.818824.

Eduardo Quiñones, Emery D. Berger, Guillem Bernat, and Francisco J. Cazorla. Using randomized caches in probabilistic real-time systems. In 21st Euromicro Conference on Real-Time Systems, ECRTS 2009, Dublin, Ireland, pages 129–138. IEEE Computer Society, July 2009. doi:10.1109/ECRTS.2009.30.

Jan Reineke. Caches in WCET Analysis. PhD thesis, Universität des Saarlandes, 2008. URL: http://rw4.cs.uni-saarland.de/~reineke/publications/DissertationCachesInWCETAnalysis.pdf.

Jan Reineke and Daniel Grund. Sensitivity of cache replacement policies. ACM Transactions on Embedded Computing Systems, 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 6th International Workshop on Worst-Case Execution Time Analysis, WCET’06, Dresden, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, March 2006. doi:10.4230/OASIcs.WCET.2006.671.

Rathijit Sen and David A. Wood. Reuse-based online models for caches. In ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS’ 13, Pittsburgh, PA, USA, pages 279–292. ACM, June 2013. doi:10.1145/2465529.2465756.

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 Transactions on Embedded Computing Systems, 7(3), 2008. doi:10.1145/1347375.1347389.

Shuchang Zhou. An efficient simulation algorithm for cache of random replacement policy. In Network and Parallel Computing, IFIP International Conference, NPC’10, Zhengzhou, China, pages 144–154. Springer, 2010. doi:10.1007/978-3-642-15672-4_13.




DOI: http://dx.doi.org/10.4230/LITES-v001-i001-a003

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v001-i001-a003-pdf4



Copyright (c) 2014 Jan Reineke

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.