Database Reference
In-Depth Information
pods, and each pod consists of two machines. Assuming that the intra-pod net-
work bandwidth is higher than the inter-pod one, and the intra-pod bandwidth is
the same across pods, the machine graph consists of four vertices and six edges.
The intra-pod connections are represented as thicker edges, indicating that they
have a higher interconnected bandwidth.
7.5.2 P
artition
s
ketCh
The
process
of a multilevel graph partitioning algorithm is modeled as a tree struc-
ture (namely
partition sketch
). Each node in the partition sketch represents the
graph acting as the input for the partition operation at a level of the entire graph
partitioning process: the root node representing the input graph; nonleaf nodes at
level (
i
+ 1) representing the partitions of the
i
ith iteration; the leaf nodes represent-
ing the graph partitions generated by the multilevel graph partitioning algorithm.
The partition sketch is a
k
-ary tree for
k
-section-based graph partitioning algo-
rithm. In practice, graph partitioning is often done using bisections iteratively, and
hence, the partition sketch is represented as a binary tree. If the number of graph
partitions is
P
, the number of levels of the partition sketch is (⌈log
2
P
⌉ + 1).
Example
Figure 7.3 illustrates the correspondence between partition sketch and the bisec-
tions in the entire graph partitioning process. In the figure, the graph is divided into
four partitions, and the partition sketch has three levels.
7.5.2.1 Design Principles of Ideal Partition Sketch
Among various partition sketches, an
ideal partition sketch
describes the partition-
ing process that strikes a balance between partitioning time and partition quality.
Graph partitioning
Partition sketch
G
G
G
G
1
G
2
G
1
G
2
Level 0
G
G
21
G
22
G
11
G
1
G
2
Level 1
G
12
G
11
G
21
G
12
G
22
Level 2
FIGURE 7.3
Correspondence between bisections and the partition sketch for the process of
partitioning the graph into four partitions.
Search WWH ::
Custom Search