Analysis of the extreme value theory on the estimation of probabilistic wcet

Abstract

Quando sistemas de tempo real são desenvolvidos para aplicações críticas, o tempo de execução é um requisito tão importante quanto o resultado computado. Por este motivo, o tempo máximo de execução de um sistema de tempo real deve obrigatoriamente ser determinado durante a fase de projeto. Estimar o tempo de execução de sistemas complexos impacta diretamente no tempo e nos custos da análise durante o desenvolvimento do sistema. Neste contexto, esta dissertação tem por objectivo avaliar a possibilidade do método MBPTA (do inglês: Measured-Based Probabilistic Timing Analysis) se basear na Teoria de Valores Extremos (EVT - Extreme Value Theory) para estimar o tempo de execução do pior caso probabilístico (pWCET - Probabilistic Worst-Case Execution Time) de uma aplicação em uma plataforma de hardware simulado. Para tanto, utilizou-se o processador MIPS rodando dois algoritmos como estudo-de-caso: Bubble Sort e Filtro FIR. Estes algoritmos têm o WCET estimado através do método de análise de tempo determinístico estático (Static Deterministic Timing Analysis – SDTA). Neste trabalho, o MBPTA é estimado através de duas técnicas distintas: Block Maxima (BM) e Peak Over Threshold (POT), as quais são combinadas com EVT para a estimação final do WCET. Os valores de WCET obtidos por MBPTA/BM e MBPTA/POT com EVT são comparados contra os valores de referência, obtidos através do método SDTA. Os resultados obtidos sugerem que a técnica BM fornece resultados confiáveis mais facilmente do que POT. Embora POT seja mais complexa, as análises sugerem que esta técnica possui mais precisão que BM, especialmente quando não são repetidos os valores de entrada da aplicação analisada.

Real Time systems developed for critical applications require a proper execution time as important as the correct computed outcome. Owing to this, the maximum execution time of a Real Time System shall be determined by design. Estimate the execution time of complex systems affects time and analysis cost directly during the system development. In this sense, this dissertation aims to assess the possibility of applying MBPTA (Measured-Based Probabilistic Timing Analysis) based on EVT (Extreme Value Theory) to estimate the pWCET (Probabilistic Worst-Case Execution Time) of a given application in a given hardware platform. With this purpose, this dissertation makes use of the MIPS processor executing two algorithms as case studies: Bubble Sort and FIR Filter. These algorithms have WCET estimated by SDTA (Static Deterministic Timing Analysis). This work applies MBPTA with two different approaches: Block Maxima (BM) and Peak Over Threshold (POT), which are combined with EVT to estimate the final WCET. Then it compares the obtained WCET values by MBPTA/BM and MBPTA/POT with EVT to reference values, obtained by the SDTA method. The obtained results suggest that the BM approach presents a reduced complexity implementation as compared to the POT approach. Nevertheless, besides the POT higher complexity, this approach is more accurate than the BM, especially when input data values are not repeated.