Research On Mathematical Programming Based Graph Partitioning Model

With the complexity of every research area becomes, requirements for large scale of scientific computing are increasing more and more. As a result parallel processing technology and system are developing in a rapid speed. From the first cluster Cray-1 to the under researching BlueGene/P of IBM and the recently born of Tianhe NO. 1, computer hardware make a great improvement on performance. However, hardware always go ahead of software, people have to face to the problems that how to manage and make full use of the excellent hardware while their born. How to partition and assign the tasks and improve the output and performance of the system, become a key problem to be solved in scientific computing.Graph partitioning theory and methods have provided a impactive way to solve this problem. However, the problems arising in parallel computing are becoming so difficult that the existing graph partitioning models and methods couldn't meet the requirements of new applications.This thesis makes further research on the shortcomings of graph partitioning models and methods in parallel computing, and the major work includes the follows:First, analysis the history and development of graph partitioning theory and methods, then give a introduction and summary to the classic graph partitioning models and methods, including geometric techniques (such as coordinate nested dissection, recursive inertial bisection, space-fill curve techniques), combinatorial techniques (such as levelized nested dissection, KL/FM), spectral methods, multilevel schemes (such as multilevel recursive bisection partitioning scheme, multilevel direct k-way partitioning scheme).Second, analysis the shortcomings and limitations of traditional models, including communication metric and representation.Last, base on the research work in original graph partitioning problem with mathematical programming and graph partitioning applications in parallel computing fields, directed graph is used to present the data dependencies, and mathematical programming based graph partitioning models are established to solve TAP in parallel computing. This class of graph partitioning models have the following advantages:(1) Support with both unsymmetrical and rectangular data dependencies while traditional ones could not.(2) Express more metric on communication cost which could give a better reflection on real parallel computing. (3) Better partitions are obtained to minimize communication cost besides keeping loading balance on every partition.(4) This class of models are flexible and extensible, could be modified to meet the requirements of applications easily.Proved by comparison experiment, this class of models gain a smaller partitioning bound compared with state-of-the-art model. So they could be used in parallel computing and other applications better.