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

摘要

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-and-bound 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 630,000 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 (similar to 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.