Methods for Comparing Execution Times of Different Input Data when Real-Time Tasks Run on Complex Computer Architectures
Resumo
Real-time tasks executed on complex computer architectures suffer large interference from other activities executing on the same system, hence generating noise in the observed execution times. In this context, it is difficult or impossible to determine the worst scenario for tasks' measurement-based temporal analysis, i.e., the hardware state and execution path that generates the longest execution time. Both the hardware effects and the execution paths depend directly or indirectly on the input data used. In this work, we (1) performed an empirical assessment of different measurement methods, with the objective of identifying which ones enable comparing different input data with respect to the generation of longer execution times, (2) implemented a genetic algorithm in which the fitness function is based on execution time measurements selected using both traditional and novel methods, showing the relevance of the measurement method for input data analysis. The focus of the work is hence not on finding tasks' worst input data, but on measurement methods that allow reliably comparing tasks' execution times produced using different input data by suppressing complex computer architectures' noise from measurements
Referências
F. J. Cazorla et al. "PROXIMA: Improving Measurement-Based Timing Analysis through Randomisation and Probabilistic Analysis" Euromicro Conference on Digital System Design 2016 (DSD'16) pp. 276-285 2016.
L. C. Briand Y. Labiche and M. Shousha "Stress testing real-time systems with genetic algorithms" Proceedings of the 7th annual conference on Genetic and evolutionary computation 2005.
D. Griffin and A. Burns "Realism in Statistical Analysis of Worst Case Execution Times" International Workshop on Worst-Case Execution Time Analysis 2010 (WCET'10) vol. 15 pp. 44-53 2010.
L. Kosmidis J. Abella E. Quiñones and F. J. Cazorla "A Cache Design for Probabilistically Analysable Real-time Systems" Design Automation and Test in Europe Conference and Exhibition 2013.
G. Marsaglia and W. W. Tsang "Some Difficult-to-pass Tests of Randomness" Journal of Statistical Software vol. 7 pp. 1-9 2002.
J. Abella et al. "Heart of Gold: Making the Improbable Happen to Increase Confidence in MBPTA" Euromicro Conference on Real-Time Systems 2014 (ECRTS'14) pp. 255-265 2014.
L. Kosmidis et al. "Fitting Processor Architectures for Measurement-Based Probabilistic Timing Analysis" Microprocessors and Microsystems (MICPRO) vol. 47B pp. 287-302 2016.
S. Law and I. Bate "Achieving Appropriate Test Coverage for Reliable Measurement-Based Timing Analysis" Euromicro Conference on Real-Time Systems 2016 (ECRTS'16) pp. 189-199 2016.
I. Wenzel R. Kirner B. Rieder and P. Puschner "Measurement-Based Timing Analysis" International Symposium on Leveraging Applications of Formal Methods Verification and Validation 2008 (ISoLA'08) pp. 430-444 2008.
J. Wegener and F. Mueller "A comparison of static analysis and evolutionary testing for the verification of timing constraints" Real- Time Systems vol. 21 no. 3 pp. 241-268 2001.
L. Cucu-Grosjean et al. "Measurement-Based Probabilistic Timing Analysis for Multi-path Programs" Euromicro Conference on Real-Time Systems 2012 (ECRTS'12) pp. 91-101 2012.
W. Bao et al. "Static and dynamic frequency scaling on multicore cpus" ACM Transactions on Architecture and Code Optimization (TACO) vol. 13 no. 4 pp. 51 2016.
D. B. Oliveira and R. S. Oliveira "Comparative Analysis of Trace Tools for Real-Time Linux" IEEE Latin America Transactions vol. 12 no. 6 pp. 1134-1140 Sept 2014.
