Research On Task Allocation Problem In Parallel Computing System

As the advance of the computer science and technology, there comes various types of parallel computing systems, distributed systems, multi-core processor-based computing systems, etc. The task allocation also expand its coverage. Task allocation problem is a typical combinatorial optimization problem, also it is a classic problem in computer research area. The purpse of task allocation is to design reasonable and effective scheme and assign the tasks to each node within the system so as to improve the performance of certain aspects of the system. Therefor, research on task allocation problem is very valuable in both theory and application. As the task allocation problem is a recognized NP-hard problem, constructing effective approximation algorithms ro heuristic algorithms is a research focus.In parallel computing area, using graph model to describle the data dependence in calculation is widespread. Once the graph model of the calculation forms, graph partition can be used to determine the tasks and data decomposition, and this decomposition produces a highly efficient parallel computing. So graph partition theory and motheds play an important role in the field of parallel computing.In this thesis, we study and analyze the task allocation problem and algorithms in parallel computing systems as well as graph partition problem and algorithms. We find out the similarity of the two issues, design graph partition based algorithm to solve the task allocation problem in parallel computing systems. In processor and network homogeneous parallel computing systems, graph partition based algorithm has lower time complexity than task-clustering based algorithm, while still enabling the processor load balancing. In processor heterogeneous and network homogeneous parallel computing systems, we give the method to modify the task interaction graph, prove that the edge cut of the modified task interaction graph is equal to the sum of the computing cost and communication cost. On this basis, we give the task allocation algorithm based on multilevel graph partition algorithm. It has lower time complexity than traditional graph theory based task allocation algorithms, and can solve task allocation problem in parallel computing systems with any number of processors.For task allocation problem in multi-core processor based parallel computing system, we give a hypergraph model. Using hypergraph model to represent multi-process and multi-thread in multi-core processor based parallel computing systems. Then a hypergraph partition based algorithm is gived to assign processes and threads. This algoritm try to minimize the communication cost between processor nodes and cores as well as maintain load balance. At last, we use randomly generated task interaction graph to test the validity of the model and algorithm.