KIT | KIT-Bibliothek | Impressum | Datenschutz

Decentralized Online Scheduling of Malleable NP-hard Jobs

Sanders, Peter ORCID iD icon 1; Schreiber, Dominik ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


In this work, we address an online job scheduling problem in a large distributed computing environment. Each job has a priority and a demand of resources, takes an unknown amount of time, and is malleable, i.e., the number of allotted workers can fluctuate during its execution. We subdivide the problem into (a) determining a fair amount of resources for each job and (b) assigning each job to an according number of processing elements. Our approach is fully decentralized, uses lightweight communication, and arranges each job as a binary tree of workers which can grow and shrink as necessary. Using the NP-complete problem of propositional satisfiability (SAT) as a case study, we experimentally show on up to 128 machines (6144 cores) that our approach leads to near-optimal utilization, imposes minimal computational overhead, and performs fair scheduling of incoming jobs within a few milliseconds.

Verlagsausgabe §
DOI: 10.5445/IR/1000149349
Veröffentlicht am 05.08.2022
DOI: 10.1007/978-3-031-12597-3_8
Zitationen: 3
Zitationen: 5
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2022
Sprache Englisch
Identifikator ISBN: 978-3-031-12596-6
ISSN: 0302-9743
KITopen-ID: 1000149349
Erschienen in Euro-Par 2022 : Parallel Processing. Hrsg.: J. Cano
Veranstaltung 28th International European Conference on Parallel and Distributed Computing (Euro-Par 2022), Glasgow, Vereinigtes Königreich, 22.08.2022 – 26.08.2022
Auflage 1.
Verlag Springer International Publishing
Seiten 119–135
Serie Lecture Notes in Computer Science
Vorab online veröffentlicht am 01.08.2022
Schlagwörter Malleable job scheduling, Load balancing, SAT
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page