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

摘要：

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

关键词：剪枝算法、Map/Reduce、任务调度、云计算

所属期刊栏目：12

分类号：TP319(计算技术、计算机技术)

资助基金：The Innovation Fund for Technology Base Firms of Harbin Science and Technology Bureau under Grant No.2014FFICJ036

在线出版日期：2018-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：72-81