Worst-case execution time

Il tempo di esecuzione nel caso peggiore, molto più comunemente chiamato con il termine inglese Worst-Case Execution Time (WCET), è il tempo che un programma informatico necessita per completare la sua esecuzione su una data piattaforma hardware. Il suo valore è fondamentale nelle analisi dei sistemi real-time, specialmente per i sistemi critici.

Definizione

Il Worst-Case Execution Time di un dato programma informatico è un valore costante e calcolato a in fase di progettazione, che dipende dal programma stesso e dalla configurazione hardware del sistema. Questo lo differenzia dalla complessità computazionale, che invece non dipende dallo specifico hardware né dalla particolare implementazione dell'algoritmo. Esso è definito come il tempo massimo che intercorre tra l'inizio dell'esecuzione del task e la sua fine, senza conteggiare eventuali preemption, considerando tutti i possibili input ammessi dal programma^[1]. In questo tempo devono, invece, essere considerati anche tutte le interference causate da altri processi attivi nel sistema, ad esempio collissioni nell'accesso della cache. La conoscenza dell'esatto WCET o di almeno una sua approssimazione pessimistica è fondamentale per dimostrare la correttezza temporale di un sistema real-time.

Il WCET può essere espresso come unità di misura continua (come il secondo o un suo sotto-multiplo) oppure discreta (come numero di cicli di clock).

Altri tempi di esecuzione correlati

Altri sigle comunemente utilizzate nella letteratura scientifica per identificare tempi di esecuzioni particolari sono^[2]^[3]:

BCET - Best-Case Execution Time: il tempo di esecuzione nel caso migliore
ACET - Average-Case Execution Time: il tempo di esecuzione nel caso medio

Modalità di stima

È possibile classificare le modalità di stima del WCET in quattro categorie^[4]^[5]:

SDTA: Deterministico, statico
MBDTA: Deterministico, basato su misure
SPTA: Probabilistico, statico
MBPTA: Probabilistico, basato su misure

Dei quattro, solo le prime due categorie sono effettivamente utilizzate in sistemi critici e certificabili, mentre le seconde due sono attualmente utilizzate solo in mondo accademico. L'MBDTA è utilizzabile ai fini pratici solo su architetture hardware molto semplici e software poco complessi.

SDTA

L'analisi temporale statica deterministica (Static Deterministic Timing Analysis, SPTA) si basa sulla dettagliata conoscenza di software e hardware, in particolare delle loro caratteristiche temporali. Il control-flow graph del programma di cui si vuole calcolare il WCET viene analizzato al fine di trovare il path peggiore i termini di tempo.

La complessità computazionale degli algoritmi utilizzati per questa analisi è il maggiore limite nell'uso di approcci statici su architetture di processori complesse. Per ovviare al problema, si introducono nell'analisi alcune semplificazioni hardware. Per esempio, se è presenta una memoria cache, si assume sempre miss. Queste semplificazioni riducono il tempo necessario all'analisi ma peggiora la stima del WCET che diventa in questo modo pessimistica.

MBDTA

La tecnica Measurement-Based Deterministic Timing Analysis (MBDTA) consiste nel misurare direttamente il tempo di esecuzione del sistema stesso e utilizzare il massimo osservato come WCET. Questo approccio non richiede complesse analisi dell'hardware e software, perché il tempo odi esecuzione viene misurato direttamente.

Tuttavia, per fare in modo che questa tecnica sia sicura e che non sottostimi il WCET, è necessario assicurarsi di aver visitato tutti gli stati dell'hardware e aver visitato tutti i path (o quantomeno i peggiori) del control-flow graph. Ottenere questa certezza è il maggior problema della tecnica MBDTA e le tecniche attuali richiedono un effort parti alle analisi di SDTA.

SPTA

MBPTA

Note

^ Björn Franke, Lecture 11: Worst-Case Execution Time (PDF), su inf.ed.ac.uk, University of Edinburgh. URL consultato il 5 gennaio 2020.
^ (EN) Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, Per Stenstrom, The Worst-Case Execution Time Problem — Overview of Methods and Survey of Tools, in Transactions on Embedded Computing Systems, vol. 7, n. 3, ACM, maggio 2008, p. 53, DOI:10.1145/1347375.1347389.
^ X. Guo, M. Boubekeur, J. McEnery, and D. Hickey, ACET Based Scheduling of Soft Real-Time Systems: An Approach to Optimise Resource Budgeting, in International Journal of Computers and Communications, vol. 1, n. 3, 2007.
^ J. Abella, D. Hardy, I. Puaut, E. Quiñones, F. J. Cazorla, On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques, in 26th Euromicro Conference on Real-Time Systems, IEEE, 2014, DOI:10.1109/ECRTS.2014.16.
^ Augusto Vega, Pradip Bose, Alper Buyuktosunoglu, Rugged Embedded Systems: Computing in Harsh Environments, Morgan Kaufmann, 2016, ISBN 9780128026328.

Voci correlate

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] Björn Franke, Lecture 11: Worst-Case Execution Time (PDF), su inf.ed.ac.uk, University of Edinburgh. URL consultato il 5 gennaio 2020.

[wcet-overview-2] (EN) Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, Per Stenstrom, The Worst-Case Execution Time Problem — Overview of Methods and Survey of Tools, in Transactions on Embedded Computing Systems, vol. 7, n. 3, ACM, maggio 2008, p. 53, DOI:10.1145/1347375.1347389.

[3] X. Guo, M. Boubekeur, J. McEnery, and D. Hickey, ACET Based Scheduling of Soft Real-Time Systems: An Approach to Optimise Resource Budgeting, in International Journal of Computers and Communications, vol. 1, n. 3, 2007.

[4] J. Abella, D. Hardy, I. Puaut, E. Quiñones, F. J. Cazorla, On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques, in 26th Euromicro Conference on Real-Time Systems, IEEE, 2014, DOI:10.1109/ECRTS.2014.16.

[5] Augusto Vega, Pradip Bose, Alper Buyuktosunoglu, Rugged Embedded Systems: Computing in Harsh Environments, Morgan Kaufmann, 2016, ISBN 9780128026328.

[1]

[2]

[3]

[4]

[5]