Malleable scheduling for flows of jobs and applications to MapReduce

Viswanath Nagarajan (), Joel Wolf (), Andrey Balmin () and Kirsten Hildrum ()
Additional contact information
Viswanath Nagarajan: University of Michigan
Joel Wolf: IBM T.J. Watson Research Center
Andrey Balmin: Platfora Inc.
Kirsten Hildrum: IBM T.J. Watson Research Center

Journal of Scheduling, 2019, vol. 22, issue 4, No 2, 393-411

Abstract: Abstract This paper provides a unified family of algorithms with performance guarantees for malleable scheduling problems on flows. A flow represents a set of jobs with precedence constraints. Each job has a speedup function that governs the rate at which work is done on the job as a function of the number of processors allocated to it. In our setting, each speedup function is linear up to some job-specific processor maximum. A key aspect of malleable scheduling is that the number of processors allocated to any job is allowed to vary with time. The overall objective is to minimize either the total cost (minisum) or the maximum cost (minimax) of the flows. Our approach handles a very general class of cost functions, and in particular provides the first constant-factor approximation algorithms for total and maximum weighted completion time. Our motivation for this work was scheduling in MapReduce, and we also provide experimental evaluations that show good practical performance.

Keywords: Parallel scheduling; Precedence constraints; Approximation algorithms; MapReduce (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0576-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:22:y:2019:i:4:d:10.1007_s10951-018-0576-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0576-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().