Computer Science ›› 2017, Vol. 44 ›› Issue (4): 193-196.doi: 10.11896/j.issn.1002-137X.2017.04.042

Previous Articles     Next Articles

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

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!