On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs
Tóm tắt
Probabilistic hard real-time systems, based on hardware architectures that use a random replacement cache, provide a potential means of reducing the hardware over-provision required to accommodate pathological scenarios and the associated extremely rare, but excessively long, worst-case execution times that can occur in deterministic systems. Timing analysis for probabilistic hard real-time systems requires the provision of probabilistic worst-case execution time (pWCET) estimates. The pWCET distribution can be described as an exceedance function which gives an upper bound on the probability that the execution time of a task will exceed any given execution time budget on any particular run. This paper introduces a more effective static probabilistic timing analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the pWCET distribution of multi-path programs. The analysis uses a conservative join function that provides a proper over-approximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache. For some benchmarks the performance of LRU is better, while for others, the new analysis techniques show that random replacement has provably better performance.
Tài liệu tham khảo
Al-Zoubi H, Milenkovic A, Milenkovic M (2004) Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite. In: Proceedings of the 42nd annual Southeast regional conference. ACM, New York, pp 267–272
Alt M, Ferdinand C, Martin F, Wilhelm R (1996) Cache behavior prediction by abstract interpretation. In: Science of computer programming. Springer, Heidelberg, pp 52–66
Altmeyer S, Davis RI (2014) On the correctness, optimality and precision of static probabilistic timing analysis. In: 17th Conference on Design, Automation and Test in Europe (DATE)
Altmeyer S, Cucu-Grosjean L, Davis RI (2015) Static probabilistic timing analysis for real-time systems using random replacement caches. Real Time Syst 51:77–123
Atanassov P, Puschner P (2001) Impact of DRAM refresh on the execution time of real-time tasks. In: Proceedings of IEEE international workshop on application of reliable computing and communication, pp 29–34
Ballabriga C, Cassé H (2008) Improving the WCET computation time by IPET using control flow graph partitioning. In: 8th International workshop on worst-case execution time analysis (WCET)
Bernat G, Burns A, Newby M (2005) Probabilistic timing analysis: an approach using copulas. J Embed Comput 1(2):179–184
Bernat G, Colin A, Petters S (2002) WCET analysis of probabilistic hard real-time systems. In: 23rd IEEE real-time systems symposium (RTSS), pp 279–288
Bernat G, Colin A, Petters S (2003) pWCET: a tool for probabilistic worst-case execution time analysis of real-time systems. Tech. Report YCS-353-2003, Department of Computer Science, The University of York
Bhat B, Mueller F (2011) Making DRAM refresh predictable. Real Time Syst 47:430–453
Bourgade R, Ballabriga C, Cassé H, Rochange C, Sainrat P (2008) Accurate analysis of memory latencies for WCET estimation. In: 16th Conference on real-time and network systems (RTNS)
Burns A, Edgar S (2000) Predicting computation time for advanced processor architectures. In: Proceedings of the 12th Euromicro conference on real-time systems (Euromicro-RTS’00)
Cazorla F, Quiñones E, Vardanega T, Cucu L, Triquet B, Bernat G, Berger E, Abella J, Wartel F, Houston M, Santinelli L, Kosmidis L, Lo C, Maxim D (2013) Proartis: probabilistically analysable real-time systems. ACM Trans Embed Comput Syst 1(2s):1–26
Chiou D, Chiouy D, Rudolph L, Rudolphy L, Devadas S, Devadasy S, Ang BS, Angz BS (2000) Dynamic cache partitioning via columnization. In: Proceedings of design automation conference
Colin A, Puaut I (2001) A modular and retargetable framework for tree-based WCET analysis. In: 13th Euromicro conference on real-time systems (ECRTS), pp 37–44
Cortex-R4 and Cortex-R4F Technical Reference Manual (2010) http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.set.cortexr/index.html
Cucu-Grosjean L (2013) Independence—a misunderstood property of and for probabilistic real-time systems. In: Alan Burns 60th anniversary, York
Cucu-Grosjean L, Santinelli L, Houston M, Lo C, Vardanega T, Kosmidis L, Abella J, Mezzetti E, Quiones E, Cazorla FJ (2012) Measurement-based probabilistic timing analysis for multi-path programs. In: 24th Euromicro conference on real-time systems (ECRTS), pp 91–101
David L, Puaut I (2004) Static determination of probabilistic execution times. In: 16th Euromicro conference on real-time systems (ECRTS), pp 223–230, June 2004
Davis RI, Santinelli L, Altmeyer S, Maiza C, Cucu-Grosjean L (2013) Analysis of probabilistic cache related pre-emption delays. In: 25th Euromicro conference on real-time systems (ECRTS)
de Dinechin BD, van Amstel D, Poulhiès M, Lager G (2014) Time-critical computing on a single-chip massively parallel processor. In: Conference on Design, Automation & Test in Europe (DATE)
Edgar S, Burns A (2001) Statistical analysis of WCET for scheduling. In: 22nd IEEE real-time systems symposium (RTSS ’01)
Griffin D, Burns A (2010) Realism in statistical analysis of worst case execution times. In: 10th International workshop on worst-case execution time analysis (WCET’10), July 2010
Griffin D, Lesage B, Burns A, Davis R (2014a) Lossy compression for static probabilistic timing analysis of random replacement caches. In: 22st International conference on real-time networks and systems (RTNS ’14)
Griffin D, Lesage B, Burns A, Davis RI (2014b) Lossy compression for worst-case execution time analysis of PLRU caches. In: Proceedings of the 22nd international conference on real-time networks and systems (RTNS ’14)
Grund D, Reineke J (2010) Precise and efficient FIFO-replacement analysis based on static phase detection. In: the 22nd Euromicro conference on real-time systems (ECRTS ’10), July 2010
Grund D, Reineke J (2010) Toward precise PLRU cache analysis. In: 10th International workshop on worst-case execution time analysis (WCET’10), pp 28–39, July 2010
Gustafsson J, Betts A, Ermedahl A, Lisper B (2010) The Mälardalen WCET benchmarks—past, present and future. In: Proceedings of the 10th international workshop on worst-case execution time analysis (WCET), pp 137–147
Hahn S, Grund D (2012) Relational cache analysis for static timing analysis. In: 2012 24th Euromicro conference on real-time systems, pp 102–111
Hahn S, Reineke J, Wilhelm R (2015) Towards compositionality in execution time analysis: definition and challenges. In: SIGBED Review, vol 12. ACM, New York, pp 28–36
Hennessy JL, Patterson DA (2011) Computer architecture: A quantitative approach, 5th edn. Morgan Kaufmann, Burlington
Holsti N, Lngbacka T, Saarinen S (2000) Using a worst-case execution time tool for real-time verification of the DEBIE software. In: Proceedings of the DASIA 2000 (data systems in aerospace) conference
Huynh BK, Ju L, Roychoudhury A (2011) Scope-aware data cache analysis for WCET estimation. In: 17th Real-time and embedded technology and applications symposium (RTAS)
Kosmidis L, Abella J, Quiñones E, Cazorla FJ (2013) A cache design for probabilistically analysable real-time systems. In: 16th conference on Design, Automation and Test in Europe (DATE), pp 513–518
Kosmidis L, Abella J, Wartel F, Quinones E, Colin A, Cazorla F (2014) PUB: path upper-bounding for measurement-based probabilistic timing analysis. In: 26th Euromicro conference on real-time systems (ECRTS)
Lesage B, Griffin D, Davis R, Altmeyer S (2013) On the application of static probabilistic timing analysis to memory hierarchies. In: Real-time scheduling open problems seminar (RTSOPS)
Lesage B, Griffin D, Altmeyer S, Davis R (2015a) Static probabilistic timing analysis for multi-path programs. In: Real-time systems symposium (RTSS)
Lesage B, Griffin D, Soboczenski F, Bate I, Davis RI (2015b) A framework for the evaluation of measurement-based timing analyses. In: 23rd International conference on real time and networks systems (RTNS)
Li YT, Malik S (1997) Performance analysis of embedded software using implicit path enumeration. Trans Comput Aided Des Integr Circuit Syst 16:1477–1487
Liang Y, Mitra T (2008) Cache modeling in probabilistic execution time analysis. In: Proceedings of the 45th annual design automation conference (DAC), pp 319–324
López J, Díaz J, Entrialgo J, García D (2008) Stochastic analysis of real-time systems underpreemptive priority-driven scheduling. Real Time Syst 40:180–207
Maxim D, Houston M, Santinelli L, Bernat G, Davis RI, Cucu-Grosjean L (2012) Re-sampling for statistical timing analysis of real-time systems. In: 20th International conference on real-time and network systems (RTNS), pp 111–120
MPC8641D Integrated Host Processor Family Reference Manual (2008) http://www.nxp.com/products/microcontrollers-and-processors/power-architecture-processors/integrated-host-processors/high-performance-dual-core-processor:MPC8641D?fpsp=1&tab=Documentation_Tab
Muchnick SS (1997) Advanced compiler design and implementation. Morgan Kaufmann, San Francisco
Nemer F, Cassé H, Sainrat P, Bahsoun J.P, Michiel M D (2006) PapaBench: a free real-time benchmark. In: 6th International workshop on worst-case execution time analysis (WCET’06), vol 4 of OpenAccess Series in Informatics (OASIcs)
Pasdeloup B (2014) Static probabilistic timing analysis of worst-case execution time for random replacement caches. Tech. Report, INRIA, Rennes
Peleska J, Löding H (2008) Static analysis by abstract interpretation. University of Bremen, Centre of Information Technology, Bremen
Puschner P, Koza C (1989) Calculating the maximum, execution time of real-time programs. Real Time Syst 1(2):159–176
Quinones E, Berger ED, Bernat G, Cazorla FJ (2009) Using randomized caches in probabilistic real-time systems. In: 21st Euromicro conference on real-time systems (ECRTS), pp 129–138
Reineke J (2014) Randomized caches considered harmful in hard real-time systems. LITES 1(1):03:1–03:13
Reineke J, Wachter B, Thesing S, Wilhelm R, Polian I, Eisinger J, Becker B (2006) A definition and classification of timing anomalies. In: 6th International workshop on worst-case execution time (WCET) analysis
Spreitzer R, Plos T (2013) Cache-access pattern attack on disaligned AES T-tables. In: Proceedings of the 4th international conference on constructive side-channel analysis and secure design (COSADE’13), pp 200–214
Theiling H, Ferdinand C, Wilhelm R (1999) Fast and precise WCET prediction by separated cache and path analyses. Real Time Syst 18:157–179
Wang Z, Lee RB (2007) New cache designs for thwarting software cache-based side channel attacks. In: Proceedings of the 34th annual international symposium on computer architecture (ISCA ’07). ACM, New York, pp 494–505
Wang Z, Lee RB (2008) A novel cache architecture with enhanced performance and security. In: Proceedings of the 41st annual IEEE/ACM international symposium on microarchitecture (MICRO 41), pp 83–93
Wegener S (2012) Computing same block relations for relational cache analysis. In: 12th International workshop on worst-case execution time analysis, pp 25–37
Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckmann R, Mitra T, Mueller F, Puaut I, Puschner P, Staschulat J, Stenström P (2008) The worst-case execution-time problem: overview of methods and survey of tools. ACM Trans Embed Comput Syst 7(3):1–53