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

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