Abstract: Under the cloud environment, the whole efficiency of traditional task allocation and scheduling algorithms for the complex tasks is low. In order to improve the whole efficiency of the Map/Reduce for complex tasks assignment, this paper proposes a pruning algorithm based on processing time. In this algorithm, the complex tasks are sorted in an optimal topology manner according to the size of the task dependencies, so that the tasks can be executed in sequence to improve the scheduling accuracy. Then, use the predictive time that node processes tasks and the node processing capacity as a subtask for quantitative modeling in each node time, and build the task and the metric matrix of processing time. According to the pruning methods, reduce the scale of task allocation gradually. For the allocation problem of N tasks with N nodes, (N-1) times operation can obtain the optimal solution of the task assignment. This paper uses Hadoop platform to evaluate the effectiveness of algorithms. The experiment evaluates the pruning algorithm, fair scheduling algorithm, genetic algorithm and GRAPHENE algorithm in the task scheduling and resource utilization efficiency angles. The experimental results show that the pruning algorithm can significantly improve the whole efficiency of task scheduling, and make full use of the computing power of nodes to enhance the efficiency of Map/Reduce scheduling.

Key words: pruning optimization, Map/Reduce, task scheduling, cloud computing

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

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