Graph partition

This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( ) Reason: general intelligibility - V ¿ 22:37, August 6, 2013 (UTC)

Graph partitioning refers to the application of appropriate algorithms for computing graph partitions (see section (graph theory ) ) with desired properties.

Graph partitioning in parallel programming

Formulation of the problem

Graph partitioning is primarily used in parallel processing use: In order to fully exploit the advantages of a parallel system in a computationally intensive computer program, it must meet two criteria:

The optimization problem as a graph partitioning problem

This optimization problem can be formulated as a graph partitioning problem:

  • The individual calculation tasks in the program are modeled as nodes of a graph.
  • For each calculation, which is the result of a different calculation dependent on the respective nodes are connected with an edge.
  • After partitioning the calculated subsets of the graph reflect the processors on which the tasks are to be distributed.

Thus, the optimization problem now reads: Find a partition of the given graph such that:

Edges whose adjazente nodes are in different subsets are cut by the partition, and therefore referred to as cutting edges.

Weighted graphs

One can formulate the optimization problem for weighted graphs. Thus, different intensive computing tasks can be represented by different nodes weights. Also can be modeled by different amounts of data by weighted edges of the data exchange. Thus, the optimization problem is, generally:

The sum of the weights of the cut edges is ( engl. cutsize, edge-cut ) as a cut size indicates. The above special formulation of the optimization problem is with this equivalent if all the edges and nodes receive the weight 1.

Example

In the above figure, the ( unweighted ) graph was cut with six nodes and eight edges into two parts, each consisting of three nodes. A subset is assigned to processor 1, the other two processor. In this case, two edges are cut, resulting in a certain amount of communication means. There is no uniform distribution of the nodes that would result in no more than two cutting edges. Thus, this partition is optimal.

Algorithms

Computing the optimal partition for a graph is an NP -complete problem. Therefore, there are a number of proposed heuristics to find in a short time at least near optimal partitions.

These can be roughly broken down by the different approaches that they pursue:

Recursive bisection

This method can be applied in all those mentioned in the following algorithms. It pursues the common divide-and- conquer principle, and is that the graph is cut into only two subsets. The resulting subgraphs are then divided into two parts recursively again, until the desired number is reached by k subsets. This figure therefore must be a power of two, ie for a ( = depth of recursion ). That is, in practice, in fact, often the case, for example, in a parallel computer which comprises processors.

By using recursive bisection taking a suboptimal solution in purchase to obtain a large temporal gain.

Geometric Algorithms

Geometric algorithms make use of coordinate information of the node. A graph has as such no coordinates. In some applications, however, the graph is formed by a two - or three-dimensional network. This is for example the case when in a physical simulation of a real object is modeled by means of a network, to which then calculations will be carried out in each node. Mostly these are each dependent only on the results of the neighboring nodes so that the network can be used directly as a graph for partitioning. The coordinate information of such networks then reflect quite well the topology of the graph.

Examples of geometric algorithms:

  • Koordinatenbisektion: Choose the coordinate ( eg x ), in which the nodes farthest apart, and for this a threshold c such that for half of the node (x > c ) applies.
  • Inertialbisektion: Calculate the Inertialachse and choose this instead of a coordinate axis.

Spectral Bisection

The idea of ​​spectral bisection is to mathematically formulate the (discrete ) optimization problem in a continuous system of equations and derive the analytic solution. Then one tries to approximate the solution of the steady equations discrete.

Combinatorial algorithms

For graph partitioning without coordinate information there are a number of combinatorial algorithms, which are only mentioned by name here:

  • Graph growing
  • Greedy algorithms
  • Kernighan-Lin/Fidduccia-Mattheyses

Multilevel partitioning

The idea here is a large graph using so-called matching to shrink to a smaller, representing the global structure of the original. This shrinkage (English coarsening ) is repeated several times until only a few (eg less than 100) knots are available. After that, the smallest graph is partitioned. The partitioning is calculated back to the next larger graph, and there, for example by means of Kernighan -Lin optimized (English refinement ), then back projected to the next larger graph until you ended up with the original graph. With this scheme, takes into account the local and global topology of the graph, which leads to very good results.

Open source graph partitioning packages

  • KaHIP (Karlsruhe High Quality Partitioning). http://algo2.iti.kit.edu/documents/kahip/index.html
  • KMetis. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview
  • Scotch. http://www.labri.fr/perso/pelegrin/scotch/
Cut (graph theory) Kernighan–Lin algorithm
277422
de