کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
463073 696951 2013 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Joint optimization of overlapping phases in MapReduce
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
Joint optimization of overlapping phases in MapReduce
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Performance Evaluation - Volume 70, Issue 10, October 2013, Pages 720–735
نویسندگان
, , , ,