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.