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

发布时间：2018-12-28 06:44

【摘要】：作为数据中心大规模处理框架,MapReduce集群包含成百上千个节点,多采用推测执行的方法来有效解决并行计算中的掉队任务。针对集群中实时性需求较高并且任务量较小的目标作业,提出基于MapReduce模型的推测执行优化算法,其目的是在满足实时性需求的基础上尽量减少目标作业的完成时间。首先通过分析任务模型和时间模型,引入数学0-1规划模型,求得整体作业的完成时间最小;然后设计可以在多项式复杂度内完成的启发式算法,目的是在可用资源允许的范围内尽量逼近最优值;最后通过大量实验模拟验证算法的执行效果。
[Abstract]:As a data center large-scale processing framework, the MapReduce cluster consists of hundreds of nodes, most of which use the method of conjecture execution to effectively solve the drop off task in parallel computing. Aiming at the target jobs with high real-time requirement and low task quantity in cluster, an optimal algorithm based on MapReduce model is proposed, which aims to reduce the completion time of target jobs on the basis of satisfying the real-time requirements. Firstly, by analyzing the task model and the time model, the mathematical 0-1 programming model is introduced to get the minimum completion time of the whole job. Then a heuristic algorithm which can be completed in polynomial complexity is designed to approach the optimal value within the limits of available resources. Finally, a large number of experiments are carried out to verify the performance of the algorithm.
【作者单位】： 南京工业大学计算机科学与技术系;
【基金】：国家自然科学基金项目(61502230,61073197) 江苏省自然科学基金项目(BK20150960) 江苏省科技支撑计划(工业)项目(BE2011186) 江苏省未来网络前瞻性研究项目(BY2013095-4-09) 江苏省普通高校自然科学研究项目(15KJB520015) 江苏省六大高峰人才基金资助项目(第八批) 江苏省2015年度普通高校研究生科研创新计划(KYLX15_0804)资助
【分类号】：TP308;TP301.6

【相似文献】

相关期刊论文 前10条

1 孙广中;陈国良;徐云;郑启龙;吴俊敏;;并行计算系列课程教学团队建设[J];中国大学教学;2008年02期

2 孙广中;徐云;郑启龙;吴俊敏;陈国良;;并行计算系列课程教学团队建设[J];计算机教育;2008年15期

3 陆克中;孙宏元;;同构集群中并行计算熵研究[J];深圳大学学报(理工版);2009年01期

4 胡霞;;并行计算如何用于科学问题研究[J];科技资讯;2009年27期

5 颜宝勇;快速富里叶变换的并行计算[J];计算机工程与科学;1984年03期

6 吴靖;;一种用于基因序列比较的并行计算方法[J];国外医学.生物医学工程分册;1992年01期

7 李斌;并行计算用的计算机和模型[J];管理科学文摘;1996年04期

8 魏臻;;高性能计算,高兴能计算[J];中国教育网络;2010年06期

9 刘杰,迟利华,胡庆丰;优化并行计算的性能评价[J];计算机工程与设计;2000年06期

10 刘赫男,罗霄,高晓东;并行计算的现状与发展[J];煤;2001年01期

相关会议论文 前10条

1 黄宇光;;整体同步并行计算方法的现状与发展[A];信息科学与微电子技术:中国科协第三届青年学术年会论文集[C];1998年

2 罗文彩;陈小前;;并行计算的多方法优化协作[A];第二十四届中国控制会议论文集（上册）[C];2005年

3 左风丽;莫则尧;叶文华;;计算流体三维分裂格式的高效并行计算[A];中国工程物理研究院科技年报（2003）[C];2003年

4 王欣;李志山;张志远;;并行计算在弹塑性时程分析中的应用[A];信息化推动工程建设工业化——第四届工程建设计算机应用创新论坛论文集[C];2013年

5 张理涛;黄廷祝;谷同祥;左宪禹;;一种适合于分布式并行计算改进的平方共轭残差法[A];2008年全国开放式分布与并行计算机学术会议论文集(下册)[C];2008年

6 胡金初;;并行计算中的任务分配算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

7 宋庭新;李慧;;面向服务的有限元并行计算网格系统设计[A];湖北省机械工程学会设计与传动学会、武汉机械设计与传动学会2008年学术年会论文集（2）[C];2008年

8 裘懿勇;徐斌;刘晓明;;并行计算作业调度系统的架构及应用[A];第十四届中国科协年会第5分会场：绿色船舶与海洋装备创新发展及产业化论坛论文集[C];2012年

9 裘懿勇;徐斌;刘晓明;;并行计算作业调度系统的架构及应用[A];2012年MIS/S&A学术交流会议论文集[C];2012年

10 肖保国;杨顺华;邢建文;赵慧勇;;当地自适应建表方法在煤油超燃发动机并行计算中的应用[A];第十四届全国激波与激波管学术会议论文集（下册）[C];2010年

相关重要报纸文章 前10条

1 轶嘉;英特尔全球首个并行计算中心落户无锡[N];人民邮电;2009年

2 曙光信息产业有限公司研发中心 温鑫;并行计算任重道远[N];中国计算机报;2007年

3 英特尔并行计算实验室研究员 TimothyMattson;并行计算:减少串行软件[N];中国计算机报;2007年

4 曙光信息产业有限公司研发中心 温鑫;并行计算软件开发概述[N];中国计算机报;2007年

5 刘霞;计算能力的提升需要一场革命[N];科技日报;2010年

6 安世亚太 雷先华;ANSYS高性能并行计算[N];中国航空报;2005年

7 张云泉;并行计算：迎接多核时代的挑战[N];计算机世界;2006年

8 本报记者 马文方;英特尔为何要牵头并行计算[N];中国计算机报;2009年

9 英特尔 赵军(Jun Zhao);PC机并行计算革命尚未成功[N];中国计算机报;2009年

10 ;Linux下的网络并行计算[N];计算机世界;2000年

相关博士学位论文 前10条

1 张雨新;改进的MPS方法及其三维并行计算研究[D];上海交通大学;2014年

2 李维山;面向领域应用的空间域和频域分解模式并行计算[D];吉林大学;2016年

3 孙安香;数值气象预报变分同化的伴随模式并行计算[D];中国人民解放军国防科学技术大学;2002年

4 张理论;面向气象预报数值模式的高效并行计算研究[D];中国人民解放军国防科学技术大学;2002年

5 龙柏;并行计算平台上的数据索引技术研究[D];中国科学技术大学;2011年

6 管建和;电磁场有限元法解释分布式并行计算的研究[D];中国地质大学（北京）;2006年

7 刘耀儒;三维有限元并行计算及其在水利工程中的应用[D];清华大学;2003年

8 金晶;并行计算普适编程模型及系统架构研究[D];北京邮电大学;2012年

9 盛艳秀;多核异构环境下通用并行计算框架关键技术研究[D];中国海洋大学;2013年

10 张帆;过程系统优化的分布式并行计算[D];浙江大学;2002年

相关硕士学位论文 前10条

1 张康宇;基于ASAR近海风场反演方法研究[D];浙江大学;2015年

2 胡荣华;并行计算在临近天气预报系统中的应用研究[D];华南理工大学;2015年

3 严善楷;异构系统中并行计算的动态负载均衡技术研究[D];华南理工大学;2015年

4 陈磊;基于监控信号的多信息提取识别的并行计算方法[D];南京理工大学;2015年

5 焦弘杰;CPU-GPU异构并行计算体系的设计与实现[D];江苏科技大学;2015年

6 陈从江;基于面向云服务的Python并行计算的研究[D];电子科技大学;2014年

7 唐吉卓;基于GPU平台的SVD并行计算研究与实现[D];电子科技大学;2014年

8 吴颀;GPU并行计算及其在飞行器设计中的应用[D];北京理工大学;2015年

9 李保安;基于液态食品冷冻浓缩冰晶生长机制并行计算[D];电子科技大学;2013年

10 钟承群;基于CPU/GPU异构并行计算的OTN仿真验证系统的研究与实现[D];电子科技大学;2015年

，

本文编号：2393614