In this paper we present a parallel exact algorithm to compute an upper bound to tardiness of preemptive Global EDF (G-EDF) schedulers, named harmonic bound, which has been proved to be up to 30% tighter than previously proposed bounds. Tightness is a crucial property of tardiness bounds: a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Unfortunately, no polynomial-time algorithm is known to date to compute the harmonic bound. Although there is no proof of hardness of any sort either, the complex formula of the bound apparently provides no hints to devise algorithms with sub-exponential worst-case cost. In this paper we address this issue by proposing a parallel, exact, branch-andbound algorithm to compute the harmonic bound, called harm-BB, which proves to be extremely fast in a large number of experiments. More specifically, we compare its execution times with those of existing polynomial-time algorithms for other known tardiness bounds on 630000 random task sets. harm-BB outperforms, or is comparable to, the competitor algorithms in all scenarios but the ones with the highest number of processors (7 and 8) and tasks (50). In the latter scenarios harm-BB is indeed slower than the other algorithms; yet, it was still feasible, as it takes only about 2:8 s to compute the bound on a commodity Dual-Core CPU. Even better, we show that harm-BB has a high parallel efficiency, thus its execution time may be largely cut down on highly-parallel platforms.

A Parallel Branch-and-Bound Algorithm to Compute a Tighter Tardiness Bound for Preemptive Global EDF / Leoncini, Mauro; Montangero, Manuela; Valente, Paolo. - In: REAL-TIME SYSTEMS. - ISSN 0922-6443. - 55:2(2019), pp. 349-386. [10.1007/s11241-018-9319-6]

A Parallel Branch-and-Bound Algorithm to Compute a Tighter Tardiness Bound for Preemptive Global EDF

Mauro Leoncini;Manuela Montangero;Paolo Valente
2019

Abstract

In this paper we present a parallel exact algorithm to compute an upper bound to tardiness of preemptive Global EDF (G-EDF) schedulers, named harmonic bound, which has been proved to be up to 30% tighter than previously proposed bounds. Tightness is a crucial property of tardiness bounds: a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Unfortunately, no polynomial-time algorithm is known to date to compute the harmonic bound. Although there is no proof of hardness of any sort either, the complex formula of the bound apparently provides no hints to devise algorithms with sub-exponential worst-case cost. In this paper we address this issue by proposing a parallel, exact, branch-andbound algorithm to compute the harmonic bound, called harm-BB, which proves to be extremely fast in a large number of experiments. More specifically, we compare its execution times with those of existing polynomial-time algorithms for other known tardiness bounds on 630000 random task sets. harm-BB outperforms, or is comparable to, the competitor algorithms in all scenarios but the ones with the highest number of processors (7 and 8) and tasks (50). In the latter scenarios harm-BB is indeed slower than the other algorithms; yet, it was still feasible, as it takes only about 2:8 s to compute the bound on a commodity Dual-Core CPU. Even better, we show that harm-BB has a high parallel efficiency, thus its execution time may be largely cut down on highly-parallel platforms.
26-ott-2018
55
2
349
386
A Parallel Branch-and-Bound Algorithm to Compute a Tighter Tardiness Bound for Preemptive Global EDF / Leoncini, Mauro; Montangero, Manuela; Valente, Paolo. - In: REAL-TIME SYSTEMS. - ISSN 0922-6443. - 55:2(2019), pp. 349-386. [10.1007/s11241-018-9319-6]
Leoncini, Mauro; Montangero, Manuela; Valente, Paolo
File in questo prodotto:
File Dimensione Formato  
HB_main.pdf

accesso aperto

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 301.83 kB
Formato Adobe PDF
301.83 kB Adobe PDF Visualizza/Apri
s11241-018-9319-6.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 1.6 MB
Formato Adobe PDF
1.6 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/1169169
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact