两台恒速机上的MapReduce排序算法研究

Online MapReduce scheduling on two uniform machines

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件,每个工件包含两类任务:Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析,得到其一般情形下的竞争比当s≥(1+51/2)/2时为1+1/s,否则为1+s/(s+1)。而当每个工件Jj都满足其Map任务总长大于等于Reduce任务总长时,其竞争比当s≥(1+31/2)/2时不超过1+1/(2s),否则为不超过1+s/(2s+1)。

In this paper,we investigate a class of online over-list scheduling problem in MapReduce system.We are given two uniform machines,and a list of jobs arrive one by one,each job consists of one Map task and one Reduce task.The map task can be arbitrarily split and processed on both machines simultaneously,while the reduce task has to be processed on a single machine.After ajob arrived,we should assign a(some)machine(s)to process its map and reduce task,which aims to minimize the makespan.We show that the classical LSc algorithm has competitive ratio 1+1/s when s≥(1+51/2)/2 and 1+s/(s+1),otherwise.If the length of Map task is greater than or equal to the length of Reduce task for each job,then the competitive ratio is at most 1+1/(2 s)when s≥(1+31/2)/2 and 1+s/(2 s+1)otherwise.