Heuristic Algorithm Based On Bipartite Graph Matching Multiprocessor Task Scheduling

ABSTRACT The parallel and distributed computer system is a new trend of computer technology, and more and more researchers are absorbed in this field. For a long time, low efficiency of computing is one of the main obstacles that prevent parallel and distributed systems from being applied practically and widely. However, researchers have found that the multiprocessor scheduling is one of the critical steps to improve the efficiency. Therefore, the multiprocessor scheduling problem is significant in distributed and parallel computing. To schedule and map a task graph with the goal of minimizing the program executing time is known to be an NP-complete problem, as a result, seeking heuristic algorithms of the problem has a very practical meaning. In this paper, we present a new heuristic strategy about scheduling a task graph onto a fully connected multiprocessor system with high communication latency. Instead of focusing on critical path in other heuristic strategies, our strategy is based on the map between scheduling and bigraph matching of the task graph. We also give a new algorithm based on the new strategy. The example and experiment are given to show the ability of our algorithm compared with other algorithms, and it is obviously that our algorithm is fast and efficient, and can easily be developed to a hybrid algorithm. The main work in this paper is as follows. 1. The fundamental concepts, model and definitions, related works are described. 2. A new concept 搑easonable amount of processors 搃s presented and proved. 3. The map between scheduling and bigraph matching of the task graph is built. 4. A new heuristic algorithm based on new strategy is given. 5. The analysis and exper駈ent compared with other algorithms are presented.