Efficient Algorithms For Scheduling Of Parallel Tasks Based On The DAG Model

In the network and parallel computing environment, task scheduling has become a nontrivial problem in the parallel processing and high performance computing area. An improper scheduling method will counteract the benefits from the parallelism of the tasks. So this paper focuses on the parallel task scheduling problem which is represented by the node-labeled and edge-labeled Directed Acyclic Graphs(DAGs). The DAG scheduling problem has shown to be NP complete in general.The DAG scheduling problem has drawn many researchers' attention in the past two decades. Many outstanding achievements have been made in this area. But with the rapid development of the network hardware technology and the processor technology, there still exist lots of unsolved problems in the DAG scheduling area. This paper mainly aims to solve the three problems. Firstly, in the nonlinearly clustering method, the paper proposes an efficient independent task scheduling algorithm named MPD which overcomes the shortcomings of the current peer algorithms. The MPD algorithm means it is based on the maximized parallelism degree among the independent tasks; Secondly, because some current DAG scheduling algorithms posses a good performance while with a high complexity, and some algorithms posses a low complexity while with an incomparable performance, the paper then presents a new efficient algorithm called EZDCP. This algorithm has a comparable performance while with a low complexity thus makes it very attractive in practice; Thirdly, A systematic granularity theory of the DAG scheduling is given in this paper. Based on the fork and join graphs, it has been proved that the nonlinearly clustering is better than linearly clustering for the fine grain DAGs which is defined by the paper. The granularity theory can be very effective in choosing the appropriate scheduling algorithms and in performance evaluation. The two proposed algorithms have been shown superiority over the previous algorithms with the same assumption through the peer set graphs which have been introduced as useful benchmark graphs.