A Reliability Evaluation Method for Probabilistic WCET Estimates based on the Comparison of Empirical Exceedance Densities
Resumo
Increasingly larger challenges on the determination of bounds for the Worst-Case Execution Times (WCETs) of software tasks that compose Real-Time Systems (RTSs) arise from computer architectures' performance-centric improvements. The Measurement-Based Probabilistic Timing Analysis (MBPTA) technique proposes determining probabilistic bounds for WCETs (i.e. pWCETs) by applying Extreme Value Theory (EVT) on tasks' execution time measurements, and is hence a promising approach for handling hardware complexity issues within RTSs' design. Such probabilistic WCET bounds can be associated to arbitrarily low exceedance probabilities, which are expected to be reliably respected during the system's long-term execution. In this work we propose a novel method for evaluating pWCETs' reliability, based on the comparison of empirical exceedance densities against their expected values considering target exceedance probabilities.
Palavras-chave:
MBPTA, EVT, pWCET, Reliability
Referências
J. W.-S. Liu, Real-Time systems, 1st ed. Prentice Hall, 2000.
R. Wilhelm, T. Mitra, F. Mueller, I. Puaut, P. Puschner et al., “The Worst-Case Execution-Time Problem - Overview of Methods and Survey of Tools,” ACM Transactions on Embedded Computing Systems (TECS), vol. 7, pp. 36:1–36:53, 2008.
F. J. Cazorla, J. Abella, J. Andersson, T. Vardanega, F. Vatrinet et al., “PROXIMA: Improving Measurement-Based Timing Analysis through Randomisation and Probabilistic Analysis,” in Euromicro Conference on Digital System Design 2016 (DSD’16). IEEE, 2016, pp. 276–285.
L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzetti, E. Qui˜nones, and F. J. Cazorla, “Measurement-Based Probabilistic Timing Analysis for Multipath Programs,” in Euromicro Conference on Real-Time Systems 2012 (ECRTS’12). IEEE, 2012, pp. 91–101.
S. G. Coles, An Introduction to Statistical Modeling of Extreme Values, 1st ed., ser. Springer Series in Statistics. Springer, 2001.
L. Kosmidis, E. Qui˜nones, 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 (MICPRO), vol. 47B, pp. 287–302, 2016.
K. P. Silva, L. F. Arcaro, and R. S. de Oliveira, “On Using GEV or Gumbel Models when Applying EVT for Probabilistic WCET Estimation,” in Real-Time Systems Symposium 2017 (RTSS’17). IEEE, 2017, pp. 220–230.
L. F. Arcaro, K. P. Silva, and R. S. de Oliveira, “On the Reliability and Tightness of GP and Exponential Models for Probabilistic WCET Estimation,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 23, pp. 39:1–39:27, 2018.
J. Beirlant, Y. Goegebeur, J. Segers, and J. Teugels, Statistics of Extremes: Theory and Applications, ser. Wiley Series in Probability and Statistics. Wiley, 2004.
L. de Haan and A. Ferreira, Extreme Value Theory - An Introduction, ser. Springer Series in Operations Research and Financial Engineering. Springer, 2006.
D. Griffin and A. Burns, “Realism in Statistical Analysis of Worst Case Execution Times,” in International Workshop on Worst-Case Execution Time Analysis 2010 (WCET’10), vol. 15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 44–53.
J. Abella, D. Hardy, I. Puaut, E. Qui˜nones, and F. J. Cazorla, “On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques,” in Euromicro Conference on Real-Time Systems 2014 (ECRTS’14). IEEE, 2014, pp. 266–275.
L. Kosmidis, E. Quiñones, J. Abella, T. Vardanega, and F. J. Cazorla, “Achieving timing composability with measurement-based probabilistic timing analysis,” in International Symposium on Object / Component / Service-Oriented Real-Time Distributed Computing 2013 (ISORC’13). IEEE, 2013, pp. 1–8.
G. Lima, D. Dias, and E. Barros, “Extreme Value Theory for Estimating Task Execution Time Bounds: A Careful Look,” in Euromicro Conference on Real-Time Systems 2016 (ECRTS’16). IEEE, 2016, pp. 200–211.
A. Burns and S. Edgar, “Predicting computation time for advanced processor architectures,” in Euromicro Conference on Real-Time Systems 2000 (ECRTS’00). IEEE, 2000, pp. 89–96.
S. Edgar and A. Burns, “Statistical analysis of WCET for scheduling,” in Real-Time Systems Symposium 2001 (RTSS’01). IEEE, 2001, pp. 215–224.
J. Hansen, S. Hissam, and G. A. Moreno, “Statistical-Based WCET Estimation and Validation,” in International Workshop on Worst-Case Execution Time Analysis 2009 (WCET’09), vol. 10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009, pp. 1–11.
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 International Conference on Emerging Technologies and Factory Automation 2011 (ETFA’11). IEEE, 2011, pp. 1–4.
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 Euromicro Conference on Real-Time Systems 2014 (ECRTS’14). IEEE, 2014, pp. 255–265.
M. Liu, M. Behnam, and T. Nolte, “Applying the peak over thresholds method on worst-case response time analysis of complex real-time systems,” in International Conference on Embedded and Real-Time Computing Systems and Applications 2013 (RTCSA’13). IEEE, 2013, pp. 22–31.
L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart, “On the Sustainability of the Extreme Value Theory for WCET Estimation,” in International Workshop on Worst-Case Execution Time Analysis 2014
(WCET’14), vol. 39. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 21–30.
F. Guet, L. Santinelli, and J. Morio, “On the Reliability of the Probabilistic Worst-Case Execution Time Estimates,” in European Congress on Embedded Real Time Software and Systems 2016 ERTS’16), 2016, p. 10.
L. Santinelli, F. Guet, and J. Morio, “Revising Measurement-Based Probabilistic Timing Analysis,” in Real-Time and Embedded Technology and Applications Symposium 2017 (RTAS’17). IEEE, 2017, pp. 199–208.
J. Abella, M. Padilla, J. del Castillo, and F. J. Cazorla, “Measurement-Based Worst-Case Execution Time Estimation Using the Coefficient of Variation,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 22, pp. 72:1–72:29, 2017.
J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper, “The Mälardalen WCET Benchmarks: Past, Present And Future,” in International Workshop on Worst-Case Execution Time Analysis 2010 (WCET’10), vol. 15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 136–146.
J. R. M. Hosking, “L-Moments: Analysis and Estimation of Distributions Using Linear Combinations of Order Statistics,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 52, pp. 105–124, 1990.
C. J. Willmott and K. Matsuura, “Advantages of the mean absolute error (MAE) over the root mean square error (RMSE) in assessing average model performance,” Climate Research, vol. 30, pp. 79–82, 2005.
R. Wilhelm, T. Mitra, F. Mueller, I. Puaut, P. Puschner et al., “The Worst-Case Execution-Time Problem - Overview of Methods and Survey of Tools,” ACM Transactions on Embedded Computing Systems (TECS), vol. 7, pp. 36:1–36:53, 2008.
F. J. Cazorla, J. Abella, J. Andersson, T. Vardanega, F. Vatrinet et al., “PROXIMA: Improving Measurement-Based Timing Analysis through Randomisation and Probabilistic Analysis,” in Euromicro Conference on Digital System Design 2016 (DSD’16). IEEE, 2016, pp. 276–285.
L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzetti, E. Qui˜nones, and F. J. Cazorla, “Measurement-Based Probabilistic Timing Analysis for Multipath Programs,” in Euromicro Conference on Real-Time Systems 2012 (ECRTS’12). IEEE, 2012, pp. 91–101.
S. G. Coles, An Introduction to Statistical Modeling of Extreme Values, 1st ed., ser. Springer Series in Statistics. Springer, 2001.
L. Kosmidis, E. Qui˜nones, 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 (MICPRO), vol. 47B, pp. 287–302, 2016.
K. P. Silva, L. F. Arcaro, and R. S. de Oliveira, “On Using GEV or Gumbel Models when Applying EVT for Probabilistic WCET Estimation,” in Real-Time Systems Symposium 2017 (RTSS’17). IEEE, 2017, pp. 220–230.
L. F. Arcaro, K. P. Silva, and R. S. de Oliveira, “On the Reliability and Tightness of GP and Exponential Models for Probabilistic WCET Estimation,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 23, pp. 39:1–39:27, 2018.
J. Beirlant, Y. Goegebeur, J. Segers, and J. Teugels, Statistics of Extremes: Theory and Applications, ser. Wiley Series in Probability and Statistics. Wiley, 2004.
L. de Haan and A. Ferreira, Extreme Value Theory - An Introduction, ser. Springer Series in Operations Research and Financial Engineering. Springer, 2006.
D. Griffin and A. Burns, “Realism in Statistical Analysis of Worst Case Execution Times,” in International Workshop on Worst-Case Execution Time Analysis 2010 (WCET’10), vol. 15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 44–53.
J. Abella, D. Hardy, I. Puaut, E. Qui˜nones, and F. J. Cazorla, “On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques,” in Euromicro Conference on Real-Time Systems 2014 (ECRTS’14). IEEE, 2014, pp. 266–275.
L. Kosmidis, E. Quiñones, J. Abella, T. Vardanega, and F. J. Cazorla, “Achieving timing composability with measurement-based probabilistic timing analysis,” in International Symposium on Object / Component / Service-Oriented Real-Time Distributed Computing 2013 (ISORC’13). IEEE, 2013, pp. 1–8.
G. Lima, D. Dias, and E. Barros, “Extreme Value Theory for Estimating Task Execution Time Bounds: A Careful Look,” in Euromicro Conference on Real-Time Systems 2016 (ECRTS’16). IEEE, 2016, pp. 200–211.
A. Burns and S. Edgar, “Predicting computation time for advanced processor architectures,” in Euromicro Conference on Real-Time Systems 2000 (ECRTS’00). IEEE, 2000, pp. 89–96.
S. Edgar and A. Burns, “Statistical analysis of WCET for scheduling,” in Real-Time Systems Symposium 2001 (RTSS’01). IEEE, 2001, pp. 215–224.
J. Hansen, S. Hissam, and G. A. Moreno, “Statistical-Based WCET Estimation and Validation,” in International Workshop on Worst-Case Execution Time Analysis 2009 (WCET’09), vol. 10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009, pp. 1–11.
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 International Conference on Emerging Technologies and Factory Automation 2011 (ETFA’11). IEEE, 2011, pp. 1–4.
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 Euromicro Conference on Real-Time Systems 2014 (ECRTS’14). IEEE, 2014, pp. 255–265.
M. Liu, M. Behnam, and T. Nolte, “Applying the peak over thresholds method on worst-case response time analysis of complex real-time systems,” in International Conference on Embedded and Real-Time Computing Systems and Applications 2013 (RTCSA’13). IEEE, 2013, pp. 22–31.
L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart, “On the Sustainability of the Extreme Value Theory for WCET Estimation,” in International Workshop on Worst-Case Execution Time Analysis 2014
(WCET’14), vol. 39. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 21–30.
F. Guet, L. Santinelli, and J. Morio, “On the Reliability of the Probabilistic Worst-Case Execution Time Estimates,” in European Congress on Embedded Real Time Software and Systems 2016 ERTS’16), 2016, p. 10.
L. Santinelli, F. Guet, and J. Morio, “Revising Measurement-Based Probabilistic Timing Analysis,” in Real-Time and Embedded Technology and Applications Symposium 2017 (RTAS’17). IEEE, 2017, pp. 199–208.
J. Abella, M. Padilla, J. del Castillo, and F. J. Cazorla, “Measurement-Based Worst-Case Execution Time Estimation Using the Coefficient of Variation,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 22, pp. 72:1–72:29, 2017.
J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper, “The Mälardalen WCET Benchmarks: Past, Present And Future,” in International Workshop on Worst-Case Execution Time Analysis 2010 (WCET’10), vol. 15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 136–146.
J. R. M. Hosking, “L-Moments: Analysis and Estimation of Distributions Using Linear Combinations of Order Statistics,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 52, pp. 105–124, 1990.
C. J. Willmott and K. Matsuura, “Advantages of the mean absolute error (MAE) over the root mean square error (RMSE) in assessing average model performance,” Climate Research, vol. 30, pp. 79–82, 2005.
Publicado
06/11/2018
Como Citar
ARCARO, Luıs Fernando; SILVA, Karila Palma; DE OLIVEIRA, Romulo Silva.
A Reliability Evaluation Method for Probabilistic WCET Estimates based on the Comparison of Empirical Exceedance Densities. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 8. , 2018, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 129-133.
ISSN 2237-5430.
