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

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.