计算机科学与探索

作者：裴树军，宋冬梅，孔德凯

单位：哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

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

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

来源：2018年第1期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2018年第1期