Doctoral Thesis ETH No. 15927
Approximating the Worst-Case Execution Time of
Soft Real-Time Applications
A dissertation submitted to the
S WISS F EDERAL I NSTITUTE OF T ECHNOLOGY Z URICH
(ETH Z ÜRICH )
for the degree of
Doctor of Technical Sciences
presented by
Matteo Corti
Dipl. Informatik-Ing. ETH
born September 12, 1974
citizen of Aranno, TI
accepted on the recommendation of
Prof. Dr. Thomas Gross, examiner
Prof. Dr. Peter Puschner, co-examiner
2005
Abstract
The soundness of real-time systems not only depends on the exactness of the results but also on
their delivery according to given timing constraints. Real-time schedulers need an estimation of
the worst-case execution time (i.e., the longest possible run time) of each process to guarantee
that all the deadlines will be met. In addition to be necessary to guarantee the correctness of
soft- and hard-real-time systems, the worst-case execution time is also useful in multimedia
systems where it can be used to better distribute the computing resources among the processes
by adapting the quality of service to the current system load.
This dissertation presents a set of static compile-time analyses to estimate the worst-case
execution time of Java processes focusing on the approximation of the WCET of fairly large
soft-real-time applications on modern hardware systems.
In a first phase the program is analyzed to extract semantic information and to determine the
maximal (and minimal) number of iterations for each basic block, by possibly bounding every
cyclic structure in the program. As a first step, the semantic analyzer, embedded in an ahead-oftime bytecode-to-native Java compiler, performs an abstract interpretation pass of linear code
segments delimiting the set of possible values of local variables at a given program point and
discovering a subset of the program’s infeasible paths. This step is followed by a loop-bounding
algorithm based on local induction variable analysis that, combined with structural analysis,
is able to deliver fine-grained per-block bounds on the minimum and maximum number of
iterations. To resolve the target of method calls the compiler performs a variable type based
analysis reducing the call-graph size.
In a second phase the duration of the different program’s instructions or basic blocks is
computed with respect to the used hardware platform and the computational context where the
instructions are executed. Modern systems with preemption and modern architectures with nonconstant instruction duration (due to pipelining, branch prediction and different level of caches)
hinder a fast and precise computation of a program’s WCET. Instead of simulating the CPU
behavior on all the possible paths we apply the principle of locality, limiting the effects of a
given instruction to a restricted period in time and allowing us to analyze large applications in
asymptotically linear time.
We describe the effectiveness in approximating the worst-case execution time for a number
of programs from small kernels and soft-real-time applications.
v
Riassunto
La correttezza dei sistemi in tempo reale non dipende unicamente dall’esattezza dei risultati
ma anche dalla consegna dei risultati entro dei limiti temporali prestabiliti. Per garantire che
tutte le scadenze siano rispettate, gli scheduler in tempo reale necessitano della stima del tempo
massimo di esecuzione (worst-case execution time) di ogni processo. Il tempo massimo di esecuzione, oltre a essere necessario per garantire la correttezza dei sistemi in tempo reale (softe hard real-time), è anche utile in sistemi multimediali, dove può essere usato per meglio distribuire le risorse tra i processi, adattando la qualità del servizio offerto, al carico momentaneo
del sistema.
Questa dissertazione presenta una serie di analisi statiche eseguite durante la compilazione
per stimare la durata massima di esecuzione di processi Java concentrandosi sulla approsimazione del tempo di esecuzione di applicazioni in tempo reale sufficientemente grandi su
piattaforme hardware moderne.
In una prima fase, la semantica del programma è analizzata in modo da determinare il numero massimo (e minimo) di iterazioni per ogni blocco trovando il limite del numero di iterazioni delle strutture cicliche. Questa analisi, implementata come modulo di un compilatore
Java ahead-of-time (da bytecode a codice nativo), esegue un’interpretazione astratta di segmenti lineari di codice delimitando i possibili valori che le variabili locali possono assumere in un
determinato punto nel programma, e scoprendo un sottoinsieme dei cammini impossibili nel
grafo del controllo di flusso. In seguito, usando un algoritmo per la delimitazione del numero
di iterazioni dei cicli, basato sull’analisi delle variabili induttive combinato con un’analisi strutturale del programma, ricaviamo dei limiti accurati sul numero di iterazioni a livello dei singoli
blocchi. Per definire le possibili destinazioni delle chiamate dei metodi il compilatore esegue un
analisi basata sui tipi delle variabili, in grado di ridurre la dimensione del grafo delle chiamate.
In una seconda fase, viene calcolata la durata delle singole istruzioni (o dei singoli blocchi)
in relazione alla piattaforma hardware usata e al contesto computazionale nel quale le istruzioni
sono eseguite. La presenza di diritto di prelazione e la durata non costante delle varie istruzioni
sulle architetture moderne (dovuta alla presenza di pipeline, predizione delle diramazioni e diversi livelli di cache) impedisce un calcolo veloce e preciso del tempo massimo di esecuzione
di un programma. Invece di simulare il comportamento del processore su tutti i possibili cammini applichiamo il principio di località, limitando gli effetti di una data istruzione a un periodo
definito di tempo, permettendoci di analizzare grosse applicazioni in un tempo asintoticamente
lineare.
Descriviamo infine l’efficacia dell’approssimazione del tempo massimo di esecuzione per
una serie di programmi: da piccoli benchmark ad applicazioni soft-real-time.
vii