ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

Sanjoy K. Baruah; Vincenzo Bonifaci; Renato Bruni; Alberto Marchetti-Spaccamela

doi:10.1007/s10951-018-0593-x

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

Sanjoy K. Baruah
, Vincenzo Bonifaci
, Renato Bruni
, Alberto Marchetti-Spaccamela

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

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.

Original language	English
Pages (from-to)	195-209
Number of pages	15
Journal	Journal of Scheduling
Volume	22
Issue number	2
DOIs	https://doi.org/10.1007/s10951-018-0593-x
State	Published - Apr 15 2019

Keywords

ILP rounding
Speedup bound
Sporadic tasks
Task partitioning
Unrelated machines

Access to Document

10.1007/s10951-018-0593-x

Cite this

@article{3c928abd871241e48733c1897395b819,

title = "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 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.",

keywords = "ILP rounding, Speedup bound, Sporadic tasks, Task partitioning, Unrelated machines",

author = "Baruah, \{Sanjoy K.\} and Vincenzo Bonifaci and Renato Bruni and Alberto Marchetti-Spaccamela",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = apr,

day = "15",

doi = "10.1007/s10951-018-0593-x",

language = "English",

volume = "22",

pages = "195--209",

journal = "Journal of Scheduling",

issn = "1094-6136",

number = "2",

}

TY - JOUR

T1 - ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

AU - Baruah, Sanjoy K.

AU - Bonifaci, Vincenzo

AU - Bruni, Renato

AU - Marchetti-Spaccamela, Alberto

PY - 2019/4/15

Y1 - 2019/4/15

N2 - 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.

AB - 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.

KW - ILP rounding

KW - Speedup bound

KW - Sporadic tasks

KW - Task partitioning

KW - Unrelated machines

UR - https://www.scopus.com/pages/publications/85058638695

U2 - 10.1007/s10951-018-0593-x

DO - 10.1007/s10951-018-0593-x

M3 - Article

AN - SCOPUS:85058638695

SN - 1094-6136

VL - 22

SP - 195

EP - 209

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 2

ER -

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this