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

作者：姜晓燕; 帅天平^*

来源：运筹学学报, 2020, 24(03): 57-66.

DOI：10.15960/j.cnki.issn.1007-6093.2020.03.004

• MapReduce
• 在线排序
• LSc算法
• 竞争比

研究源自于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)。

• 单位
  北京邮电大学