A Survey of Probabilistic Timing Analysis Techniques for Real-Time Systems

Robert I. Davis, Liliana Cucu-Grosjean

Abstract


This survey covers probabilistic timing analysis techniques for real-time systems. It reviews and critiques the key results in the field from its origins in 2000 to the latest research published up to the end of August 2018. The survey provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas: static probabilistic timing analysis, measurement-based probabilistic timing analysis, and hybrid methods. In addition, research on supporting mechanisms and techniques, case studies, and evaluations is also reviewed. The survey concludes by identifying open issues, key challenges and possible directions for future research.


Keywords


Probabilistic; real-time; timing analysis

Full Text:

PDF

References


J. Abella, F. J. Cazorla, E. Quinones, and T. Vardanega.Measurement-based probabilistic timing analysis and i.i.d property. White Paper Version 2. Technical report http://www.proartis-project.eu/publications/MBPTA-white-paper, BSC, July 2014.

J. Abella, D. Hardy, I. Puaut, E. Quiñones, and F. J. Cazorla.On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 266-275, July 2014. URL: http://dx.doi.org/10.1109/ECRTS.2014.16

J. Abella, M. Padilla, J. Del Castillo, and F. J. Cazorla.Measurement-Based Worst-Case Execution Time Estimation Using the Coefficient of Variation. ACM Trans. Des. Autom. Electron. Syst., 22(4):72:1-72:29, June 2017. URL: http://dx.doi.org/10.1145/3065924

J. Abella, E. Quiñones, F. Wartel, T. Vardanega, and F. J. Cazorla.Heart of Gold: Making the Improbable Happen to Increase Confidence in MBPTA. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 255-265, 2014. URL: http://dx.doi.org/10.1109/ECRTS.2014.33

I. Agirre, M. Azkarate-askasua, C. Hernandez, J. Abella, J. Perez, T. Vardanega, and F. J. Cazorla.IEC-61508 SIL 3 Compliant Pseudo-Random Number Generators for Probabilistic Timing Analysis. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 677-684, August 2015. URL: http://dx.doi.org/10.1109/DSD.2015.26

S. Altmeyer, L. Cucu-Grosjean, and R. I. Davis.Static probabilistic timing analysis for real-time systems using random replacement caches.Springer Real-Time Systems, 51(1):77-123, 2015. URL: http://dx.doi.org/10.1007/s11241-014-9218-4

S. Altmeyer and R. I. Davis.On the Correctness, Optimality and Precision of Static Probabilistic Timing Analysis. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 26:1-26:6, 2014. URL: http://dl.acm.org/citation.cfm?id=2616606.2616638.

S. Altmeyer, R. I. Davis, L. Indrusiak, C. Maiza, V. Nelis, and J. Reineke.A Generic and Compositional Framework for Multicore Response Time Analysis. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 129-138, 2015. URL: http://dx.doi.org/10.1145/2834848.2834862

H. Anwar, C. Chen, and G. Beltrame.A probabilistically analysable cache implementation on FPGA. In IEEE International New Circuits and Systems Conference (NEWCAS), pages 1-4, June 2015. URL: http://dx.doi.org/10.1109/NEWCAS.2015.7181984

I. Bate and U. Khan.WCET Analysis of Modern Processors Using Multi-criteria Optimisation. Empirical Softw. Engg., 16(1):5-28, February 2011.

P. Benedicte, C. Hernandez, J. Abella, and F. J. Cazorla.Design and integration of hierarchical-placement multi-level caches for real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 455-460, March 2018. URL: http://dx.doi.org/10.23919/DATE.2018.8342052

P. Benedicte, C. Hernandez, J. Abella, and F. J. Cazorla.RPR: A Random Replacement Policy with Limited Pathological Replacements. In Proceedings of ACM Symposium on Applied Computing (SAC), pages 593-600, 2018. URL: http://dx.doi.org/10.1145/3167132.3167197

P. Benedicte, L. Kosmidis, E. Quinones, J. Abella, and F. J. Cazorla.Modelling the confidence of timing analysis for time randomised caches. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-8, May 2016. URL: http://dx.doi.org/10.1109/SIES.2016.7509421

P. Benedicte, L. Kosmidis, E. Quiñones, J. Abella, and F. J. Cazorla.A confidence assessment of WCET estimates for software time randomized caches. In Proceedings of the IEEE International Conference on Industrial Informatics (INDIN), pages 90-97, July 2016. URL: http://dx.doi.org/10.1109/INDIN.2016.7819140

K. Berezovskyi, F. Guet, L. Santinelli, K. Bletsas, and E. Tovar.Measurement-Based Probabilistic Timing Analysis for Graphics Processor Units. In Proceedings of the International Conference on the Architecture of Computing Systems (ARCS), pages 223-236, April 2016. URL: http://dx.doi.org/10.1007/978-3-319-30695-7_17

K. Berezovskyi, L. Santinelli, K. Bletsas, and E. Tovar.WCET Measurement-based and Extreme Value Theory Characterisation of CUDA Kernels. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 279-288, 2014. URL: http://dx.doi.org/10.1145/2659787.2659827

G. Bernat, A. Burns, and M. Newby.Probabilistic Timing Analysis: An Approach Using Copulas. J. Embedded Comput., 1(2):179-194, April 2005. URL: http://dl.acm.org/citation.cfm?id=1233760.1233763.

G. Bernat, A. Colin, and S. Petters.pwcet: A tool for probabilistic worst-case execution time analysis of real-time systems. Technical report, Department of Computer Science, University of York, 2003.

G. Bernat, A. Colin, and S. M. Petters.WCET analysis of probabilistic hard real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 279-288, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181582

B. Braams, S. Altmeyer, and A. D. Pimentel.EDiFy: An execution time distribution finder. In Proceedings of the Design Automation Conference (DAC), pages 1-6, June 2017. URL: http://dx.doi.org/10.1145/3061639.3062233

S. Bunte, M. Zolda, M. Tautschnig, and R. Kirner.Improving the Confidence in Measurement-Based Timing Analysis. In Proceedings of the IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing (ISORC), pages 144-151, March 2011. URL: http://dx.doi.org/10.1109/ISORC.2011.27

A. Burns and S. Edgar.Predicting computation time for advanced processor architectures. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 89-96, 2000. URL: http://dx.doi.org/10.1109/EMRTS.2000.853996

A. Burns and D. Griffin.Predictability as an emergent behaviour. In Proceedings of the Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS), pages 27-29, 2011.

S. Bünte, M. Zolda, and R. Kirner.Let's get less optimistic in measurement-based timing analysis. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 204-212, June 2011. URL: http://dx.doi.org/10.1109/SIES.2011.5953663

F. J. Cazorla, J. Abella, J. Andersson, T. Vardanega, F. Vatrinet, I. Bate, I. Broster, M. Azkarate-Askasua, F. Wartel, L. Cucu, F. Cros, G. Farrall, A. Gogonel, A. Gianarro, B. Triquet, C. Hernandez, C. Lo, C. Maxim, D. Morales, E. Quinones, E. Mezzetti, L. Kosmidis, I. Aguirre, M. Fernandez, M. Slijepcevic, P. Conmy, and W. Talaboulma.PROXIMA: Improving Measurement-Based Timing Analysis through Randomisation and Probabilistic Analysis. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 276-285, August 2016. URL: http://dx.doi.org/10.1109/DSD.2016.22

F. J. Cazorla, E. Quiñones, T. Vardanega, L. Cucu, B. Triquet, G. Bernat, E. Berger, J. Abella, F. Wartel, M. Houston, L. Santinelli, L. Kosmidis, C. Lo, and D. Maxim.PROARTIS: Probabilistically Analyzable Real-Time Systems.ACM Transactions on Embedded Computing Systems, 12(2s):94:1-94:26, May 2013. URL: http://dx.doi.org/10.1145/2465787.2465796

F. J. Cazorla, T. Vardanega, E. Quiñones, and J. Abella.Upper-bounding Program Execution Time with Extreme Value Theory. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 64-76, 2013. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2013.64

C. Chen and G. Beltrame.An Adaptive Markov Model for the Timing Analysis of Probabilistic Caches. ACM Trans. Des. Autom. Electron. Syst., 23(1):12:1-12:24, August 2017. URL: http://dx.doi.org/10.1145/3123877

C. Chen, J. Panerati, and G. Beltrame.Effects of online fault detection mechanisms on Probabilistic Timing Analysis. In Proceedings of IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT), pages 41-46, September 2016. URL: http://dx.doi.org/10.1109/DFT.2016.7684067

C. Chen, J. Panerati, I. Hafnaoui, and G. Beltrame.Static probabilistic timing analysis with a permanent fault detection mechanism. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-10, June 2017. URL: http://dx.doi.org/10.1109/SIES.2017.7993373

C. Chen, L. Santinelli, J. Hugues, and G. Beltrame.Static probabilistic timing analysis in presence of faults. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-10, May 2016. URL: http://dx.doi.org/10.1109/SIES.2016.7509422

S. Coles.An Introduction to Statistical Modeling of Extreme Values. Springer, 2001. URL: http://dx.doi.org/10.1007/978-1-4471-3675-0

F. Cros, L. Kosmidis, F. Wartel, D. Morales, J. Abella, I. Broster, and F. J. Cazorla.Dynamic software randomisation: Lessons learned from an aerospace case study. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 103-108, March 2017. URL: http://dx.doi.org/10.23919/DATE.2017.7926966

L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzetti, E. Quiñones, and F. J. Cazorla.Measurement-Based Probabilistic Timing Analysis for Multi-path Programs. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 91-101, July 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.31

L. David and I. Puaut.Static determination of probabilistic execution times. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 223-230, June 2004. URL: http://dx.doi.org/10.1109/EMRTS.2004.1311024

R. A. Davis and T. Mikosch.The extremogram: A correlogram for extreme events. Bernoulli, 15(4):977-1009, November 2009. URL: http://dx.doi.org/10.3150/09-BEJ213

R. I. Davis, S. Altmeyer, L. S. Indrusiak, C. Maiza, V. Nelis, and J. Reineke.An extensible framework for multicore response time analysis.Springer Real-Time Systems, 54(3):607-661, July 2018. URL: http://dx.doi.org/10.1007/s11241-017-9285-4

R. I. Davis and L. Cucu-Grosjean.A Survey of Probabilistic Schedulability Analysis Techniques for Hard Real-Time Systems. Leibniz Transactions on Embedded Systems (LITES), 6(1):04:1-04:53, May 2019. URL: http://dx.doi.org/10.4230/LITES-v006-i001-a004

R. I. Davis, L. Santinelli, S. Altmeyer, C. Maiza, and L. Cucu-Grosjean.Analysis of Probabilistic Cache Related Pre-emption Delays. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 168-179, July 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.27

R. I. Davis, J. Whitham, and D. Maxim.Static Probabilistic Timing Analysis for Multicore Processors with Shared Cache. In Proceedings of the Real-Time Scheduling Open Problems Seminar (RTSOPS), pages 3-5, 2013.

R.I. Davis.Improvements to Static Probabilistic Timing Analysis for Systems with Random Cache Replacement Policies. In Proceedings of the Real-Time Scheduling Open Problems Seminar (RTSOPS), pages 22-24, July 2013.

J-F. Deverge and I. Puaut.Safe measurement-based WCET estimation. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), 2005.

E. Díaz, M. Fernández, L. Kosmidis, E. Mezzetti, C. Hernandez, J. Abella, and F. J. Cazorla.MC2: Multicore and Cache Analysis via Deterministic and Probabilistic Jitter Bounding, pages 102-118. Springer International Publishing, Cham, 2017. URL: http://dx.doi.org/10.1007/978-3-319-60588-3_7

J. L. Diaz, J. M. Lopez, M. Garcia, A. M. Campos, Kanghee Kim, and L. L. Bello.Pessimism in the stochastic analysis of real-time systems: concept and applications. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 197-207, December 2004. URL: http://dx.doi.org/10.1109/REAL.2004.41

S. Edgar and A. Burns.Statistical analysis of WCET for scheduling. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 215-224, December 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990614

P. Embrechts, C. Kluppelberg, and T. Mikosch.Modelling extremal events for insurance and Finance. Springer, 1997. URL: http://dx.doi.org/10.1007/978-3-642-33483-2

I. Fedotova, B. Krause, and E. Siemens.Applicability of Extreme Value Theory to the Execution Time Prediction of Programs on SoCs. In Proceedings of the International Conference on Applied Innovations in IT (ICAIIT), March 2017.

M. Fernandez, D. Morales, L. Kosmidis, A. Bardizbanyan, I. Broster, C. Hernandez, E. Quinones, J. Abella, F. Cazorla, P. Machado, and L. Fossati.Probabilistic timing analysis on time-randomized platforms for the space domain. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 738-739, March 2017. URL: http://dx.doi.org/10.23919/DATE.2017.7927087

S. Jimenez Gil, I. Bate, G. Lima, L. Santinelli, A. Gogonel, and L. Cucu-Grosjean.Open Challenges for Probabilistic Measurement-Based Worst-Case Execution Time. IEEE Embedded Systems Letters, PP(99):1-1, 2017. URL: http://dx.doi.org/10.1109/LES.2017.2712858

D. Griffin, I. Bate, B. Lesage, and F. Soboczenski.Evaluating Mixed Criticality Scheduling Algorithms with Realistic Workloads. In Proceedings of Workshop on Mixed Criticality (WMC), 2015.

D. Griffin and A. Burns.Realism in Statistical Analysis of Worst Case Execution Times. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 44-53, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.44

D. Griffin, B. Lesage, A. Burns, and R. I. Davis.Static Probabilistic Timing Analysis of Random Replacement Caches Using Lossy Compression. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 289-298, 2014. URL: http://dx.doi.org/10.1145/2659787.2659809

F. Guet, L. Santinelli, and J. Morio.On the Reliability of the Probabilistic Worst-Case Execution Time Estimates. In Proceedings of the European Congress on Embedded Real Time Software and Systems (ERTS), January 2016. URL: https://hal.archives-ouvertes.fr/hal-01289477.

F. Guet, L. Santinelli, and J. Morio.Probabilistic analysis of cache memories and cache memories impacts on multi-core embedded systems. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-10, May 2016. URL: http://dx.doi.org/10.1109/SIES.2016.7509420

F. Guet, L. Santinelli, and J. Morio.On the Representativity of Execution Time Measurements: Studying Dependence and Multi-Mode Tasks. In Jan Reineke, editor, Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), volume 57 of OASICS, pages 3:1-3:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2017.3

J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper.The MälardalenWCET Benchmarks - Past, Present and Future. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 137-147, July 2010.

J. Hansen, S. A. Hissam, and G. A. Moreno. Statistical-based WCET estimation and validation . In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), volume 252, 2009.

D. Hardy and I. Puaut.Static Probabilistic Worst Case Execution Time Estimation for Architectures with Faulty Instruction Caches. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 35-44, 2013. URL: http://dx.doi.org/10.1145/2516821.2516842

D. Hardy and I. Puaut.Static Probabilistic Worst Case Execution Time Estimation for Architectures with Faulty Instruction Caches.Springer Real-Time Systems, 51(2):128-152, March 2015. URL: http://dx.doi.org/10.1007/s11241-014-9212-x

C. Hernandez, J. Abella, F. J. Cazorla, J. Andersson, and A. Gianarro.Towards making a LEON3 multicore compatible with probabilistic timing analysis. In Proceedings of the Data Systems In Aerospace Conference (DASIA), May 2015.

C. Hernandez, J. Abella, A. Gianarro, J. Andersson, and F. J. Cazorla.Random Modulo: A New Processor Cache Design for Real-time Critical Systems. In Proceedings of the Design Automation Conference (DAC), pages 29:1-29:6, 2016. URL: http://dx.doi.org/10.1145/2897937.2898076

K. Höfig.Failure-Dependent Timing Analysis - A New Methodology for Probabilistic Worst-Case Execution Time Analysis, pages 61-75. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-28540-0_5

T. Hsing.On Tail Index Estimation Using Dependent Data. The Annals of Statistics, 19(3):1547-1569, 1991. URL: http://www.jstor.org/stable/2241962.

M. Ivers and R. Ernst.Probabilistic Network Loads with Dependencies and the Effect on Queue Sojourn Times, pages 280-296. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10625-5_18

J. Jalle, L. Kosmidis, J. Abella, E. Quiñones, and F. J. Cazorla.Bus Designs for Time-probabilistic Multicore Processors. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 50:1-50:6, 2014. URL: http://dl.acm.org/citation.cfm?id=2616606.2616668.

T. Kelter, H. Falk, P. Marwedel, S. Chattopadhyay, and A. Roychoudhury.Static Analysis of Multi-core TDMA Resource Arbitration Delays.Springer Real-Time Systems, 50(2):185-229, March 2014. URL: http://dx.doi.org/10.1007/s11241-013-9189-x

L. Kosmidis, J. Abella, E. Quinones, and F. J. Cazorla.Efficient Cache Designs for Probabilistically Analysable Real-Time Systems. IEEE Transactions on Computers, 63(12):2998-3011, December 2014. URL: http://dx.doi.org/10.1109/TC.2013.182

L. Kosmidis, J. Abella, E. Quiñones, and F. J. Cazorla.A cache design for probabilistically analysable real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 513-518, March 2013. URL: http://dx.doi.org/10.7873/DATE.2013.116

L. Kosmidis, J. Abella, E. Quiñones, and F. J. Cazorla.Multi-level Unified Caches for Probabilistically Time Analysable Real-Time Systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 360-371, December 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.43

L. Kosmidis, J. Abella, F. Wartel, E. Quiñones, A. Colin, and F. J. Cazorla.PUB: Path Upper-Bounding for Measurement-Based Probabilistic Timing Analysis. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 276-287, July 2014. URL: http://dx.doi.org/10.1109/ECRTS.2014.34

L. Kosmidis, D. Compagnin, D. Morales, E. Mezzetti, E. Quiñones, J. Abella, T. Vardanega, and F. J. Cazorla.Measurement-Based Timing Analysis of the AURIX Caches. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), 2016.

L. Kosmidis, C. Curtsinger, E. Quiñones, J. Abella, E. Berger, and F. J. Cazorla.Probabilistic timing analysis on conventional cache designs. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 603-606, March 2013. URL: http://dx.doi.org/10.7873/DATE.2013.132

L. Kosmidis, E. Quiñones, J. Abella, G. Farrall, F. Wartel, and F. J. Cazorla.Containing Timing-Related Certification Cost in Automotive Systems Deploying Complex Hardware. In Proceedings of the Design Automation Conference (DAC), pages 22:1-22:6, 2014. URL: http://dx.doi.org/10.1145/2593069.2593112

L. Kosmidis, E. Quiñones, J. Abella, T. Vardanega, I. Broster, and F. J. Cazorla.Measurement-Based Probabilistic Timing Analysis and Its Impact on Processor Architecture. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 401-410, August 2014. URL: http://dx.doi.org/10.1109/DSD.2014.50

L. Kosmidis, E. Quiñones, J. Abella, T. Vardanega, and F. J. Cazorla.Achieving timing composability with measurement-based probabilistic timing analysis. In Proceedings of the IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing (ISORC), pages 1-8, June 2013. URL: http://dx.doi.org/10.1109/ISORC.2013.6913193

L. Kosmidis, E. Quiñones, J. Abella, T. Vardanega, C. Hernandez, A. Gianarro, I. Broster, and F. J. Cazorla.Fitting processor architectures for measurement-based probabilistic timing analysis. Microprocessors and Microsystems, 2016. URL: http://dx.doi.org/10.1016/j.micpro.2016.07.014

L. Kosmidis, T. Vardanega, J. Abella, E. Quiñones, and F. J. Cazorla.Applying Measurement-Based Probabilistic Timing Analysis to Buffer Resources. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 97-108, 2013. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2013.97

L. Kosmidis, R. Vargas, D. Morales, E. Quiñones, J. Abella, and F. J. Cazorla.TASA: Toolchain-Agnostic Static Software randomisation for critical real-time systems. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1-8, November 2016. URL: http://dx.doi.org/10.1145/2966986.2967078

K. Lahiri, A. Raghunathan, and G. Lakshminarayana.LOTTERYBUS: a new high-performance communication architecture for system-on-chip designs. In DAC, pages 15-20, 2001. URL: http://dx.doi.org/10.1109/DAC.2001.156100

S. Law and I. Bate.Achieving Appropriate Test Coverage for Reliable Measurement-Based Timing Analysis. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 189-199, July 2016. URL: http://dx.doi.org/10.1109/ECRTS.2016.21

M. R. Leadbetter, G. Lindgren, and H. Rootzen.Conditions for the convergence in distribution of maxima of stationary normal processes. Stochastic Processes and their Applications, 8(2), 1978.

B. Lesage, D. Griffin, S. Altmeyer, L. Cucu-Grosjean, and R. I. Davis.On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs. Real-Time Systems, December 2017. URL: http://dx.doi.org/10.1007/s11241-017-9295-2

B. Lesage, D. Griffin, S. Altmeyer, and R. I. Davis.Static Probabilistic Timing Analysis for Multi-path Programs. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 361-372, December 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.41

B. Lesage, D. Griffin, R. I. Davis, and S. Altmeyer.On the application of Static Probabilistic Timing Analysis to Memory Hierarchies. In Proceedings of the Real-Time Scheduling Open Problems Seminar (RTSOPS), 2014.

B. Lesage, D. Griffin, F. Soboczenski, I. Bate, and R. I. Davis.A Framework for the Evaluation of Measurement-based Timing Analyses. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 35-44, 2015. URL: http://dx.doi.org/10.1145/2834848.2834858

Y. Liang and T. Mitra.Cache modeling in probabilistic execution time analysis. In Proceedings of the Design Automation Conference (DAC), pages 319-324, June 2008.

G. Lima and I. Bate.Valid Application of EVT in Timing Analysis by Randomising Execution Time Measurements. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017.

G. Lima, D. Dias, and E. Barros.Extreme Value Theory for Estimating Task Execution Time Bounds: A Careful Look. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), July 2016.

Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean.A New Way About Using Statistical Analysis of Worst-case Execution Times. SIGBED Rev., 8(3):11-14, September 2011. URL: http://dx.doi.org/10.1145/2038617.2038619

Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean.A trace-based statistical worst-case execution time analysis of component-based real-time embedded systems. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-4, September 2011. URL: http://dx.doi.org/10.1109/ETFA.2011.6059190

R. Mancuso, R. Pellizzoni, M. Caccamo, L. Sha, and H. Yun.WCET(m) Estimation in Multi-core Systems Using Single Core Equivalence. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 174-183, July 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.23

C. Maxim, A. Gogonel, I. Asavoae, M. Asavoae, and L. Cucu-Grosjean.Reproducibility and representativity: mandatory properties for the compositionality of measurement-based WCET estimation approaches.SIGBED Review, 14(3):24-31, 2017. URL: http://dx.doi.org/10.1145/3166227.3166230

A. Melani, E. Noulard, and L. Santinelli.Learning from probabilities: Dependences within real-time systems. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-8, September 2013. URL: http://dx.doi.org/10.1109/ETFA.2013.6648013

E. Mezzetti, M. Fernandez, A. Bardizbanyan, I Agirre, , J. Abella, T. Vardanega, and F. J. Cazorla.EPC Enacted: Integration in an Industrial Toolbox and Use Against a Rialway Application. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017.

E. Mezzetti, N. Holsti, A. Colin, G. Bernat, and T. Vardanega.Attacking the sources of unpredictability in the instruction cache behavior. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), 2008.

E. Mezzetti, M. Ziccardi, T. Vardanega, J. Abella, E. Quiñones, and F. J. Cazorla.Randomized Caches Can Be Pretty Useful to Hard Real-Time Systems. Leibniz Transactions on Embedded Systems, 2(1):01-1-01:10, 2015. URL: http://dx.doi.org/10.4230/LITES-v002-i001-a001

a. Milutinovic, j. Abella, i. Agirre, M. Azkarate-Askasua, E. Mezzetti, T. Vardanega, and F. J. Cazorla.Software Time Reliability in the Presence of Cache Memories, pages 233-249. Springer International Publishing, Cham, 2017. URL: http://dx.doi.org/10.1007/978-3-319-60588-3_15

S. Milutinovic, J. Abella, and F. J. Cazorla.Modelling Probabilistic Cache Representativeness in the Presence of Arbitrary Access Patterns. In Proceedings of the IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing (ISORC), pages 142-149, May 2016. URL: http://dx.doi.org/10.1109/ISORC.2016.28

S. Milutinovic, J. Abella, and F. J. Cazorla.On the assessment of probabilistic WCET estimates reliability for arbitrary programs. EURASIP Journal on Embedded Systems, 2017(1):28, April 2017. URL: http://dx.doi.org/10.1186/s13639-017-0076-8

S. Milutinovic, J. Abella, E. Mezzetti, and F. J. Cazorla.Measurement-based Cache Representativeness on Multipath Programs. In Proceedings of the Design Automation Conference (DAC), pages 123:1-123:6, 2018. URL: http://dx.doi.org/10.1145/3195970.3196075

S. Milutinovic, E. Mezzetti, J. Abella, T. Vardanega, and F. J. Cazorla.On uses of extreme value theory fit for industrial-quality WCET analysis. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-6, June 2017. URL: http://dx.doi.org/10.1109/SIES.2017.7993402

M. Panic, J. Abella, C. Hernandez, E. Quiñones, T. Ungerer, and F. J. Cazorla.Enabling TDMA Arbitration in the Context of MBPTA. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 462-469, August 2015. URL: http://dx.doi.org/10.1109/DSD.2015.68

M. Panić, J. Abella, E. Quiñones, C. Hernandez, T. Ungerer, and F. J. Cazorla.Adapting TDMA arbitration for measurement-based probabilistic timing analysis. Microprocessors and Microsystems, 52:188-201, 2017. URL: http://dx.doi.org/10.1016/j.micpro.2017.06.006

B. Pasdeloup.Static probabilistic timing analysis of worst-case execution time for random replacement caches. Technical report, Inria, 2014.

J. Pickands.Statistical Inference Using Extreme Order Statistics. Ann. Statist., 3(1):119-131, January 1975. URL: http://dx.doi.org/10.1214/aos/1176343003

E. Quinones, E. D. Berger, G. Bernat, and F. J. Cazorla.Using Randomized Caches in Probabilistic Real-Time Systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 129-138, July 2009. URL: http://dx.doi.org/10.1109/ECRTS.2009.30

F. Reghenzani, G. Massari, and Fornaciari W.chronovise: Measurement-Based Probabilistic Timing Analysis framework. Journal of Open Source Software, 3(28), June 2018. URL: http://dx.doi.org/10.21105/joss.00711

J. Reineke.Randomized Caches Considered Harmful in Hard Real-Time Systems. Leibniz Transactions on Embedded Systems, 1(1):03-1-03:13, 2014. URL: http://dx.doi.org/10.4230/LITES-v001-i001-a003

A. Rukhin, J. Soto, J. Nechvatal, E. Barker, S. Leigh, M. Levenson, D. Banks, A. Heckert, J. Dray, S. Vo, A. Rukhin, J. Soto, M. Smid, S. Leigh, M. Vangel, A. Heckert, J. Dray, and L. E. Bassham.Statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST special publication, 2010.

L. Santinelli, F. Guet, and J. Morio.Revising Measurement-Based Probabilistic Timing Analysis. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017.

L. Santinelli and Z. Guo.On the Criticality of Probabilistic Worst-Case Execution Time Models, pages 59-74. Springer International Publishing, Cham, 2017. URL: http://dx.doi.org/10.1007/978-3-319-69483-2_4

L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart.On the Sustainability of the Extreme Value Theory for WCET Estimation. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 21-30, 2014. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2014.21

M. Santos, B. Lisper, G. Lima, and V. Lima.Sequential Composition of Execution Time Distributions by Convolution. In Proceedings of the Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS), pages 30-37, November 2011. URL: http://www.es.mdh.se/publications/2215-.

C. Scarrott and A. MacDonald.A review of extreme value threshold estimation and uncertainty quantification. REVSTAT-Statistical Journal, 10(1):33-60, 2012.

M. Schlansker, R. Shaw, and S. Sivaramakrishnan.Randomization and associativity in the design of placement-insensitive caches. Hewlett Packard Laboratories, 1993.

K. P. Silva and R. Silva de Oliveira L. F. Arcaro.On Using GEV or Gumbel Models when Applying EVT for Probabilistic WCET Estimation. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), 2017.

M. Slijepcevic, M. Fernandez, C. Hernandez, J. Abella, E. Quinones, and F. J. Cazorla.pTNoC: Probabilistic Time-Analyzable Tree-Based NoC for Mixed Criticality Systems. In Proceedings of the Euromicro Conference on Digital System Design (DSD), 2016.

M. Slijepcevic, C. Hernandez, J. Abella, and F. J. Cazorla.Boosting Guaranteed Performance in Wormhole NoCs with Probabilistic Timing Analysis. In Proceedings of the Euromicro Conference on Digital System Design (DSD), pages 440-444, August 2017. URL: http://dx.doi.org/10.1109/DSD.2017.71

M. Slijepcevic, L. Kosmidis, J. Abella, E. Quiñones, and F. J. Cazorla.DTM: Degraded Test Mode for Fault-Aware Probabilistic Timing Analysis. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 237-248, July 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.33

M. Slijepcevic, L. Kosmidis, J. Abella, E. Quiñones, and F. J. Cazorla.Time-analysable non-partitioned shared caches for real-time multicore systems. In Proceedings of the Design Automation Conference (DAC), pages 1-6, June 2014. URL: http://dx.doi.org/10.1145/2593069.2593235

J. E. Smith and J. R. Goodman.A Study of Instruction Cache Organizations and Replacement Policies. In Proceedings of the 10th Annual International Symposium on Computer Architecture, ISCA '83, pages 132-137, New York, NY, USA, 1983. ACM. URL: http://dx.doi.org/10.1145/800046.801648

J. E. Smith and J. R. Goodman.Instruction Cache Replacement Policies and Organizations. IEEE Transactions on Computers, C-34(3):234-241, March 1985. URL: http://dx.doi.org/10.1109/TC.1985.1676566

Z. Stephenson, J. Abella, and T. Vardanega.Supporting industrial use of probabilistic timing analysis with explicit argumentation. In Proceedings of the IEEE International Conference on Industrial Informatics (INDIN), pages 734-740, July 2013. URL: http://dx.doi.org/10.1109/INDIN.2013.6622975

N. Topham and A. Gonzalez.Randomized cache placement for eliminating conflicts. IEEE Transactions on Computers, 48(2):185-192, February 1999. URL: http://dx.doi.org/10.1109/12.752660

N. Tracey, J. Clark, K. Mander, and J. McDermid.An automated framework for structural test-data generation. In Proceedings 13th IEEE International Conference on Automated Software Engineering, pages 285-288, October 1998. URL: http://dx.doi.org/10.1109/ASE.1998.732680

N. Tracey, J. A. Clark, and K. Mander.The way forward for unifying dynamic test-case generation: The optimisation-based approach. Proceedings of the IFIP International Workshop on Dependable Computing and Its Applications (DCIA)., 1998.

D. Trilla, C. Hernandez, J. Abella, and F. J. Cazorla.Resilient random modulo cache memories for probabilistically-analyzable real-time systems. In IEEE International Symposium on On-Line Testing and Robust System Design (IOLTS), pages 27-32, July 2016. URL: http://dx.doi.org/10.1109/IOLTS.2016.7604666

F. Wartel, L. Kosmidis, A. Gogonel, A. Baldovino, Z. Stephenson, B. Triquet, E. Quiñones, C. Lo, E. Mezzetta, I. Broster, J. Abella, L. Cucu-Grosjean, T. Vardanega, and F. J. Cazorla.Timing analysis of an avionics case study on complex hardware/software platforms. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 397-402, March 2015.

F. Wartel, L. Kosmidis, C. Lo, B. Triquet, E. Quiñones, J. Abella, A. Gogonel, A. Baldovin, E. Mezzetti, L. Cucu, T. Vardanega, and F. J. Cazorla.Measurement-based probabilistic timing analysis: Lessons from an integrated-modular avionics case study. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 241-248, June 2013. URL: http://dx.doi.org/10.1109/SIES.2013.6601497

J. Wegener and F. Mueller.A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints. Real-Time Systems, 21(3):241-268, November 2001.

J. Wegener, H. Sthamer, B. F. Jones, and D. E. Eyres.Testing real-time systems using genetic algorithms. Software Quality Journal, 6(2):127-135, June 1997. URL: http://dx.doi.org/10.1023/A:1018551716639

I. Wenzel, R. Kirner, B. Rieder, and P. Puschner.Measurement-Based Timing Analysis. In Leveraging Applications of Formal Methods, Verification and Validation, pages 430-444, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenström.The Worst-case Execution-time Problem Overview of Methods and Survey of Tools.ACM Transactions on Embedded Computing Systems, 7(3):36:1-36:53, May 2008. URL: http://dx.doi.org/10.1145/1347375.1347389

N. Williams.WCET measurement using modified path testing. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), volume 1 of OpenAccess Series in Informatics (OASIcs), 2005. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2005.809

N. Williams and M. Roger.Test generation strategies to measure worst-case execution time. In ICSE Workshop on Automation of Software Test, pages 88-96, May 2009. URL: http://dx.doi.org/10.1109/IWAST.2009.5069045

M. Ziccardi, E. Mezzetti, T. Vardanega, J. Abella, and F. J. Cazorla.EPC: Extended Path Coverage for Measurement-Based Probabilistic Timing Analysis. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 338-349, December 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.39




DOI: https://doi.org/10.4230/LITES-v006-i001-a003

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

Copyright (c) 2019 Robert I. Davis and Liliana Cucu-Grosjean

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
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




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. | Imprint | Data Privacy Policy