Map/Reduce下快速剪枝算法在复杂任务调度中的应用

• 作者: 孔德凯 宋冬梅 裴树军
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 剪枝算法 Map/Reduce 任务调度 云计算
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 高性能计算
• 页码范围: 72-81
• 页数: 10页
• 分类号: TP319
• 字数: 7356字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1611057

摘要

云环境下传统任务分配与调度算法对于复杂任务调度的整体效率较低,为了提高Map/Reduce对复杂任务分配调度的整体效率,提出了一种基于任务处理时间的快速剪枝算法.该算法首先将复杂任务按照任务依赖关系大小进行最佳拓扑排序,使任务按顺序执行,从而提高调度准确率.然后使用节点处理任务的预测时间与节点处理能力的比值作为子任务在每个节点的处理时间进行量化建模,建立任务和处理时间的度量矩阵,通过采用按阶剪枝方法逐渐缩小任务分配规模,对N个节点处理N个任务的分配问题,进行N-1次操作可获得任务分配的最优解.运用Hadoop平台进行实验验证,从任务调度效率与资源使用率角度将剪枝算法与公平调度算法、遗传算法和GRAPHENE算法进行对比验证.实验结果表明剪枝算法能明显提高任务调度的整体效率,充分利用各节点的计算能力提高Map/Reduce调度效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	裴树军	哈尔滨理工大学计算机科学与技术学院	20	99	5.0	9.0
2	宋冬梅	哈尔滨理工大学计算机科学与技术学院	1	1	1.0	1.0
3	孔德凯	哈尔滨理工大学计算机科学与技术学院	2	2	1.0	1.0