计算机科学 ›› 2017, Vol. 44 ›› Issue (4): 193-196.doi: 10.11896/j.issn.1002-137X.2017.04.042

• 高性能计算 • 上一篇    下一篇

基于MapReduce模型的推测执行优化算法

黄中平,白光伟,沈航,承骁,华志翔   

  1. 南京工业大学计算机科学与技术系 南京210009,南京工业大学计算机科学与技术系 南京210009,南京工业大学计算机科学与技术系 南京210009,南京工业大学计算机科学与技术系 南京210009,南京工业大学计算机科学与技术系 南京210009
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金项目(61502230,7),江苏省自然科学基金项目(BK20150960),江苏省科技支撑计划(工业)项目(BE2011186),江苏省未来网络前瞻性研究项目(BY2013095-4-09),江苏省普通高校自然科学研究项目(15KJB520015),江苏省六大高峰人才基金资助

Speculative Execution Optimization Algorithm with MapReduce

HUANG Zhong-ping, BAI Guang-wei, SHEN Hang, CHENG Xiao and HUA Zhi-xiang   

  • Online:2018-11-13 Published:2018-11-13

摘要: 作为数据中心大规模处理框架,MapReduce集群包含成百上千个节点,多采用推测执行的方法来有效解决并行计算中的掉队任务。针对集群中实时性需求较高并且任务量较小的目标作业,提出基于MapReduce模型的推测执行优化算法,其目的是在满足实时性需求的基础上尽量减少目标作业的完成时间。首先通过分析任务模型和时间模型,引入数学0-1规划模型,求得整体作业的完成时间最小;然后设计可以在多项式复杂度内完成的启发式算法,目的是在可用资源允许的范围内尽量逼近最优值;最后通过大量实验模拟验证算法的执行效果。

关键词: MapReduce,并行计算,推测执行,实时性

Abstract: In the framework of data center for large-scale data processing,MapReduce contains thousands of nodes.Speculative execution is a way to improve the efficiency of parallel computing,which can deal with the straggling task in parallel computing effectively.In this paper,we proposed a speculative execution optimization algorithm with MapReduce,focusing on the target jobs with higher demand of real time and less amount of calculation.The purpose is to minimize execution time while meeting real time demand.To this end,we established a task model and a time model.By the analysis of the task model and time model,we employed a 0-1 integer linear program to minimize the total finishing time.In addition,a heuristic algorithm was put forword to meet the optimal value,which can be done with the polynomial complexity.Finally,the simulation experiment results show that the proposed algorithm can gain remarkable effect.

Key words: MapReduce,Parallel computing,Speculative execution,Real time

[1] DEAN J,GHEMAWAT S.MapReduce:simplified data proces-sing on large clusters[C]∥Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM Press,2004:137-150.
[2] ANANTHANARANAN G,GHODSI A,Shenker S,et al.Effective straggler mitigation:Attack of the clones[C]∥Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13).2013:185-198.
[3] SUN X,HE C,LU Y.Esamr:An enhanced self-adaptive mapreduce scheduling algorithm[C]∥Proceedings of the 18th International Conference on Parallel and Distributed Systems (ICPADS).2012:148-155.
[4] ANANTHANARANAN G,KANDULA S,GREENBERG A,etal.Reining in the outliers in mapreduce clusters using mantri[C]∥Usenix Symposium on Operating Systems Design and Implementation(OSDI 2010).Canada,2010:265-278.
[5] CHEN Q,LIU C,XIAO Z.Improving mapreduce performanceusing smart speculative execution strategy[J].IEEE Transactions on Computers,2014,63(4):954-967.
[6] ISARD M,BUDIU M,YU Y,et al.Dryad:distributed data-pa-rallel programs from sequential building blocks[C]∥Procee-dings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems.2007:59-72.
[7] LIU C.Improving Speculative Execution and Skew Data Handing in MapReduce[D].Beijing:Peking University,2012.(in Chinese) 刘成.MapReduce推测执行策略及倾斜数据处理优化[D].北京:北京大学,2012.
[8] BORTHAKUR D.The hadoop distributed file system:Architecture and design[J].Hadoop Project Website,2007,11(11):1-10.
[9] RAO B T,REDDY L S S.Survey on improved scheduling in Hadoop MapReduce in cloud environments[J].International Journal of Computer Applications,2012,34(9):29-33
[10] WANG X Q.Optimization of High-performance MapReduce System[D].Hefei:University of Science and Technology of China,USTC.2010.(in Chinese) 王向前.高性能MapReduce系统的优化[D].合肥:中国科学技术大学,2010.
[11] XU H,LAU W C.Optimization for Speculative Execution ofMultiple Jobs in a MapReduce-like Cluster[C]∥ IEEE INFOCOM 2015-IEEE Conference on Computer Communications.IEEE,2015:1017-1079.
[12] ZAHARIA M,KONWINSKI A,JOSEPH A D,et al.Improving MapReduce Performance in Heterogeneous Environments[C]∥Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation(OSDI).San Diego,California,2008:29-42
[13] XU H,LAU W C.Speculative Execution for a Single Job in a MapReduce-Like System[C]∥ Proceedings of 7th IEEE International Conference on Cloud Computing (CLOUD).2014:586-593.
[14] KWON Y C,BALAZINSKA M,HOWE B,et al.Skewtune:mi-tigating skew in mapreduce applications[C]∥Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012:25-36.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!