Bishwaranjan Bhattacharjee, Scott Boag, et al.
IBM J. Res. Dev
MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. There are a variety of scheduling challenges within the MapReduce architecture, and this paper studies the challenges that result from the overlapping of the "map" and "shuffle" phases. We propose a new, general model for this scheduling problem, and validate this model using cluster experiments. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate (i.e., in the resource augmentation framework). Finally, we validate the algorithms using a workload trace from a Google cluster and show that the algorithms are near optimal in practical settings. © 2013 Elsevier B.V. All rights reserved.
Bishwaranjan Bhattacharjee, Scott Boag, et al.
IBM J. Res. Dev
José E. Moreira, Maged M. Michael, et al.
ICS 2007
Bernardetta Addis, Danilo Ardagna, et al.
IEEE TDSC
Luna Xu, Min Li, et al.
IPDPS 2016