Tightness is a crucial property of tardiness bounds; in fact, a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Recently, a new tardiness bound for preemptive global EDF (G-EDF), named harmonic bound, has been proposed and proved to be up to 30% tighter than previous bounds. 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 an exact branch-and-bound algorithm, called harm-BB, which proved to be extremely fast in a large number of experiments. More specifically, we compared its execution times with those of existing polynomial-time algorithms for other known similar bounds on 630000 random task sets. harm-BB outperformed the competitor algorithms in all scenarios but the ones with the highest number of processors and tasks (8 and ∼50, respectively). However, even in the latter cases, harm-BB was at most 1.5 slower than the other algorithms, and, in absolute terms, took only about 4.4 ms to compute the bound on commodity hardware.

A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global EDF scheduler / Leoncini, Mauro; Montangero, Manuela; Valente, Paolo. - 131837:(2017), pp. 128-137. ((Intervento presentato al convegno 25th International Conference on Real-Time Networks and Systems, RTNS 2017 tenutosi a fra nel 2017 [10.1145/3139258.3139277].

A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global EDF scheduler

Leoncini, Mauro;Montangero, Manuela;Valente, Paolo
2017

Abstract

Tightness is a crucial property of tardiness bounds; in fact, a too loose bound may cause a feasible soft real-time application to be mistakenly deemed unfeasible. Recently, a new tardiness bound for preemptive global EDF (G-EDF), named harmonic bound, has been proposed and proved to be up to 30% tighter than previous bounds. 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 an exact branch-and-bound algorithm, called harm-BB, which proved to be extremely fast in a large number of experiments. More specifically, we compared its execution times with those of existing polynomial-time algorithms for other known similar bounds on 630000 random task sets. harm-BB outperformed the competitor algorithms in all scenarios but the ones with the highest number of processors and tasks (8 and ∼50, respectively). However, even in the latter cases, harm-BB was at most 1.5 slower than the other algorithms, and, in absolute terms, took only about 4.4 ms to compute the bound on commodity hardware.
25th International Conference on Real-Time Networks and Systems, RTNS 2017
fra
2017
131837
128
137
Leoncini, Mauro; Montangero, Manuela; Valente, Paolo
A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global EDF scheduler / Leoncini, Mauro; Montangero, Manuela; Valente, Paolo. - 131837:(2017), pp. 128-137. ((Intervento presentato al convegno 25th International Conference on Real-Time Networks and Systems, RTNS 2017 tenutosi a fra nel 2017 [10.1145/3139258.3139277].
File in questo prodotto:
File Dimensione Formato  
HB_main.pdf

non disponibili

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 247.73 kB
Formato Adobe PDF
247.73 kB 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: https://hdl.handle.net/11380/1151329
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact