Scheduling MapReduce jobs under multi-round precedences

DOI10.1007/978-3-319-43659-3_16MaRDI QIDQ1693215zbMATH OpenOpenAlexFDO

Authors Ioannis Milis, Dimitris Fotakis, Orestis Papadigenopoulos, Vasilis Vassalos, Georgios Zois

Publication date 11 January 2018

Full work available at URL https://arxiv.org/abs/1602.05263

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14)

Abstract: We consider non-preemptive scheduling of MapReduce jobs with multiple tasks in the practical scenario where each job requires several map-reduce rounds. We seek to minimize the average weighted completion time and consider scheduling on identical and unrelated parallel processors. For identical processors, we present LP-based O(1)-approximation algorithms. For unrelated processors, the approximation ratio naturally depends on the maximum number of rounds of any job. Since the number of rounds per job in typical MapReduce algorithms is a small constant, our scheduling algorithms achieve a small approximation ratio in practice. For the single-round case, we substantially improve on previously best known approximation guarantees for both identical and unrelated processors. Moreover, we conduct an experimental analysis and compare the performance of our algorithms against a fast heuristic and a lower bound on the optimal solution, thus demonstrating their promising practical performance.

Recommendations

• Scheduling MapReduce jobs on identical and unrelated processors
• Malleable scheduling for flows of jobs and applications to MapReduce
• Parallel machine scheduling with splitting jobs in MapReduce system
• Heuristics for periodical batch job scheduling in a MapReduce computing framework
• Scheduling preemptive jobs with precedence constraints on parallel machines

Cited in

(5)

• Scheduling MapReduce jobs on identical and unrelated processors
• Malleable scheduling for flows of jobs and applications to MapReduce
• Experimental evaluation of multi-round matrix multiplication on MapReduce
• Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms
• Scheduling distributed clusters of parallel machines: primal-dual and LP-based approximation algorithms

This page was built for publication: Scheduling MapReduce jobs under multi-round precedences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693215)