计算机科学 ›› 2017, Vol. 44 ›› Issue (4): 193-196.doi: 10.11896/j.issn.1002-137X.2017.04.042
黄中平,白光伟,沈航,承骁,华志翔
HUANG Zhong-ping, BAI Guang-wei, SHEN Hang, CHENG Xiao and HUA Zhi-xiang
摘要: 作为数据中心大规模处理框架,MapReduce集群包含成百上千个节点,多采用推测执行的方法来有效解决并行计算中的掉队任务。针对集群中实时性需求较高并且任务量较小的目标作业,提出基于MapReduce模型的推测执行优化算法,其目的是在满足实时性需求的基础上尽量减少目标作业的完成时间。首先通过分析任务模型和时间模型,引入数学0-1规划模型,求得整体作业的完成时间最小;然后设计可以在多项式复杂度内完成的启发式算法,目的是在可用资源允许的范围内尽量逼近最优值;最后通过大量实验模拟验证算法的执行效果。
[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! |
|