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 trade-offs 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.

Baruah, S.K., Bonifaci, V., Bruni, R., Marchetti-Spaccamela, A. (2019). ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. JOURNAL OF SCHEDULING, 22(2), 195-209 [10.1007/s10951-018-0593-x].

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

Bonifaci V.;
2019-01-01

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 trade-offs 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.
Baruah, S.K., Bonifaci, V., Bruni, R., Marchetti-Spaccamela, A. (2019). ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. JOURNAL OF SCHEDULING, 22(2), 195-209 [10.1007/s10951-018-0593-x].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/381914
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact