Abstract

Introduction

The problem of graph partition appeares in many scientific and technical problems which decision it is possible partially or completely come to the decision on graph structures. To a class of such problems traditionally referred problems of mathematical physics on not structured grids, a loadbalancing problem of the distributed computing systems, a devirtualization problem of task decisions on the real parallel computers and others. As a rule, the purpose of partition is to get independent vertex subsets of initial graph with a minimum quantity of communications between these subsets. Formally it can be written in the following way:

We have graph G = (V, E), where V is a set of graph vertex, and Е - set of its edges. The quantity of vertex |V| equals n. It is necessary to get such graph partition in p parts V1,V2,...,Vp, that for all pairs i,j = 1,2, …,p and i <> j following conditions were satisfied:

• crossing Vi c Vj = 0
• union of all subsets Vi = V
• vertex quantity in each part |Vi|=n/p, if it is given by task description
• the edges quantity of set |with first vertex va from Vi and second vertex vb from Vj| minimized among all possible partitions V.

To simplify the understanding, the partition problem is presented on animation below:

graph partition the column on 4 parts

By partition algorithms development the basic problem, which is occurred to developer, is the balance between quantity of search variants and work content of algorithm. In many problems is insufficiently simply to divide graph, and it is necessary to make this for the shortest time as partition is only the intermediate stage of the task decision. Therefore full search of variants of partitioning for great graphs in practice is inapplicable in connection with NP-completeness and in consequence with unsatisfactory time of implementation. Instead of this methods are used methods with partial search and application of various schemes for consecutive improvement of partition quality. Quality of partitioning is determined by such important parameters as quantity of communications between parts of divided graph, size of weight of each part and others, depending on a solved problem.

Existing decisions of the given problem

Today there are very many consecutive and parallel algorithms (geometrical, spectral, multilevel) of graph partition which have been realized in concrete software products. The most widespread software from this series are METIS[1] and ParMETIS[2] which have been developed at Minnesota university in 1998-2003. In these software packages is realized the class of so-called multilevel algorithms which have shown sufficiently good results in speed of work and in quality of created partitions. We shall consider in detail an essence of a multilevel decision technique of the given problem.

The multilevel partition algorithm consists of three phases ([3], [4], [5]):

Multilevel partition algorithm

Coarsening phase During the coarsening phase consistently is received from graph Gi = (Vi-1, Ei-1) smaller derivative graph Gi = (Vi, Ei), |Vi| <| Vi-1|, where i – a level of coarsening, and |Vi| and |Vi-1| - set of graph vertexes on one of level. The principle of the graph coarsening consists in the following: the set of incidental tops is united in one at a following level of coarsening. And the weight of the jointed vertex is equaled to the sum of weights of vertexes which were jointed. Connectivity of the obtained vertex is equaled to the sum of connectivities of initial vertexes too. Graph coarsening comes to the end, when the quantity of tops |Vi| in derivative graph reaches value, which is less 100.

Initial partitioning phase For partitioning of the coarsest graph developers evaluated four different algorithms for partitioning: spectral bisection, Kernighan-Lin bisection, breadth-first region growing and greedy region growing.

Uncoarsening phase During the given phase consecutive vertex expansion in parts till the initial graph size is performed. At the same time at each level of uncoarsening one of algorithms of local improvement, which are based on Kernighan-Lin Refinement algorithm, is used. Vertex pairs, which have more external communications with opposite part, than internal (inside the part), are changed places. On it improvement at i-th level comes to an end, and transition on following i-1 level is performed, and etc.

Current results

At present I continue to work by the given theme, the work will come to the end in January 2007. My current results are confined by three programs developed by me:

• for generation oriented cyclic graphs which meet the requirements of electronic schemes
• for transformation of the received graph description in a format of library METIS
• for the graph and parts, which are created by library METIS, visualization, based on utilities of application GraphViz.

Results of teamwork of my applications with library METIS and GraphViz are presented in below-mentioned pictures:

generated graph G(10, 20)

transformed graph in a format of library METIS

received graph, as a result of partition into three parts by library METIS

Conclusion

The problem of graph partition is actual by the decision of many scientific tasks. In our time there are many classes of partition algorithms and each class of algorithms has many versions. In the given abstract the basic attention is given to consideration of a so-called multilevel method of graph partition on which software products METIS and ParMETIS (consecutive and parallel realization of the given method accordingly) are based.

Bibliography

[1] George Karypis and Vipin Kumar,  METIS - A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices

[2] George Karypis, Kirk Schloegel and Vipin Kumar, ParMETIS - Parallel Graph Partitioning and Sparse Matrix Ordering Library

[3] George Karypis and Vipin Kumar - Analysis of Multilevel Graph Partitioning

[4] George Karypis, Kirk Schloegel and Vipin Kumar - Graph Partitioning for High Performance Scientific Simulations

[5] George Karypis and Vipin Kumar - A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

Upward