.png){kind=icon}
返回
Makespan minimization for MapReduce systems with different servers
.png){kind=icon}
PRE
AI
DOI：10.1016/j.future.2016.07.012.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we study MapReduce scheduling on n parallel machines (servers) with different speeds v(1) >= v(2) >= ... >= v(n). Each job contains two kinds of tasks: map tasks and reduce tasks. The job's reduce tasks can only be processed after finishing all its map tasks. We assume that the map tasks are parallelized, i.e., it can be arbitrarily split and parts of the same task can be processed on different machines in parallel, while the reduce tasks are non-parallelizable. We consider both the offline and online scheduling problems. On offline version, if the reduce tasks are non-preemptive, we design an approximation algorithm whose worst case ratio is at most max{1 + Delta/2 - 1/n, Delta}, where Delta = v(1)/v(n) is the ratio of the fastest speed to the slowest speed. If the reduce tasks are preemptive, we provide an approximation algorithm with worst case ratio of 2. On online version where jobs arriving over time, we design two heuristics for non-preemptive and preemptive reduce tasks respectively. In experiment, we verify the advantage of our algorithms comparing with the state-of-the-art. (C) 2016 Elsevier B.V. All rights reserved.
Keyword:
MapReduce
Scheduling algorithm
Worst-case ratio
Big data
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
F
IF:
6.1
论文数:
6.8K
被引数:
2.3W
机构
查看更多机构
引用论文
.png){kind=icon}
没有更多内容