Multi-objective Partitioning Algorithm For Parallel Computations On Directed Graph

For grid based scientific numerical simulations, data dependencies of computations on grids is directed and it can be represented by a directed graph. Then these parallel scientific numerical simulations can be represented by parallel directed graph computing. Partitioning this directed graph into some subgraphs and mapping corresponding tasks onto processors are critical for parallel directed graph computing. Directed graph partitioning is constitutive of partitioning directed graph, priority algorithm of directed graph nodes and parallel sweep algorithm. Partitioning algorithms must synthesize the consideration for connectivity, degree of parallelism, load balancing, and communication cost. Based on traditional directed graph partitioning algorithms, this paper presents a multi-objective directed graph partitioning algorithm that can control the tradeoffs among above four objectives. If applied to 2-dimensional cylinder symmetrical neutron transport computations on unstructured grid, the parallel efficiency of parallel flux sweeping algorithm using our multi-objective partitioning algorithm is much larger than that of using undirected graph partitioining algorithms. Eleven chapters are included in this thesis.Chapter 1 simply surveyed the use of directed graph partitioning in grid based scientific numerical simulations, pointed out that it was indispensable to design multi-objective partitioning algorithm for parallel computations of directed graph, summarized the drawbacks of graph partitioning algorithms existed before. At last, the main research results in this thesis were given.Chapter 2 gived a presentation of some concepts related to graph partitioning, listed our judgement of efficiency that comparing all kinds of algorithms, introduced parallel sweep algorithm with scalable performance for directed graph.Chapter 3 introduced priority algorithm of directed graph nodes. After giving priority to every node, it is clear about selecting one from some computable nodes.Chapter 4 introduced multi-objective partitioning algorithm. Based on the data dependence of nodes, this algorithm achieves high efficiency of parallelism by partitioning a directed graph to P sub-graphs and mapping these to P processors. Then we modified multi-objective partitioning algorithm by using neighbor nodes and three new concepts. It is better than multi-objective partitioning algorithm in some ways.Chapter 5 compared the partitioning given by Iterative Kernigham-Lin (IKL)algorithm and multi-objective partitioning algorithm. The result of the performance indicates that multi-objective partitioning algorithm has achieved expectation, multi-objective partitioning algorithm is better than IKL algorithm in some ways, modified multi-objective partitioning algorithm is better than multi-objective partitioning algorithm in some ways.Chapter 6 summarized this thesis, surveyed the research fields in future...