ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

Abstract : The problem of partitioning systems of independent constrained-deadline sporadic tasks upon heterogeneous multiprocessor platforms is considered. Several different integer linear program (ILP) formulations of this problem, offering different tradeoffs between effectiveness (as quantified by speedup bound) and running time efficiency, are presented. One of the formulations is leveraged to improve the best speedup guarantee known for a polynomial-time partitioning algorithm , from 12.9 to 7.83. Extensive computational results on synthetically generated instances are also provided to establish the effectiveness of the ILP formulations .
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-02339161
Contributor : Marie-France Sagot <>
Submitted on : Wednesday, October 30, 2019 - 11:57:39 AM
Last modification on : Thursday, October 31, 2019 - 1:26:45 AM

File

unrelated-jos.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Sanjoy Baruah, Vincenzo Bonifaci, Renato Bruni, Alberto Marchetti-Spaccamela. ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. Journal of Scheduling, Springer Verlag, 2019, 22 (2), pp.195-209. ⟨10.1007/s10951-018-0593-x⟩. ⟨hal-02339161⟩

Share

Metrics

Record views

46

Files downloads

138