Limits...
Vertex Separators for Partitioning a Graph

View Article: PubMed Central - PubMed

ABSTRACT

Finite Element Method (FEM) is a well known technique extensively studied for spatial and temporal modeling of environmental processes, weather prediction computations, and intelligent signal processing for wireless sensors. The need for huge computational power arising in such applications to simulate physical phenomenon correctly mandates the use of massively parallel computers to distribute the workload evenly. In this study, a novel heuristic algorithm called Line Graph Bisection which partitions a graph via vertex separators so as to balance the workload amongst the processors and to minimize the communication overhead is proposed. The proposed algorithm is proved to be computationally feasible and makes cost-effective parallel implementations possible to speed up the solution process.

No MeSH data available.


Original graph G.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3927507&req=5

f5-sensors-08-00635: Original graph G.

Mentions: An example graph G for which a small size vertex separator is sought and its corresponding line graph L(G) are depicted in Figures 5 and 6, respectively. The numbers shown next to each edge in Figure 5 are used to uniquely identify them. All the nodes are assumed to be associated with a weight of one for the example graph G given in Figure 5. The dotted line in red seen in Figure 6 represents the bisection of L(G) computed by the LGB algorithm. There are a total of four edges in the cut in Figure 6. These edges have been all labeled the same (i.e., 3 corresponding to node 3 in Figure 5). It can easily be seen from Figure 6 that nodes 1, 2, 4 and 7 shaded in grey together with edges 1, 2, 3, 6, and 9 of L(G) to the left of the dotted line in red are all pinned in a separate partition. These grey-shaded nodes 1, 2, 4, and 7 in Figure 6 are actually the edges labeled as 1, 2, 4, and 7 again, respectively in Figure 5. The edge separator and the partitioning scheme in Figure 6 obtained by the LGB algorithm, thus, induce the nodal partitioning specified by the configuration of Figure 5 in which only node 3 ends up in the separator. While nodes in grey (1, 2, 6, 9) are assigned to a partition, nodes in yellow (4, 5, 7, 8) are placed in another which turns out, in this case, to be an optimal vertex partition with respect to both the separator size minimization (just node 3) and the load balance (each have 4 nodes) constraints. It should, however, be noted at that point that the cut size has been treated as one in Figure 6 by counting only the number of distinct labels of weight one as specified by the example at the cut. As it is quite clear from the discussion of the example, LGB is a modified KLB applied to the line graph. The only modifications needed, apparently, are those which stem from the fact that a number of edges having the same label in the line graph have to be treated as a single edge and the fact that the partition weights implicitly used to control the quality of load balance are, now, a function of the edge weights rather than the node weights. The existence of multiple edges having the same labels in the line graph as seen in Figure 6 has a direct effect on the way the gain of a node is calculated and updated in the line graph. The efficiency of the proposed LGB algorithm heavily depends on preserving the locality of updates in LGB as is the case in KLB.


Vertex Separators for Partitioning a Graph
Original graph G.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3927507&req=5

f5-sensors-08-00635: Original graph G.
Mentions: An example graph G for which a small size vertex separator is sought and its corresponding line graph L(G) are depicted in Figures 5 and 6, respectively. The numbers shown next to each edge in Figure 5 are used to uniquely identify them. All the nodes are assumed to be associated with a weight of one for the example graph G given in Figure 5. The dotted line in red seen in Figure 6 represents the bisection of L(G) computed by the LGB algorithm. There are a total of four edges in the cut in Figure 6. These edges have been all labeled the same (i.e., 3 corresponding to node 3 in Figure 5). It can easily be seen from Figure 6 that nodes 1, 2, 4 and 7 shaded in grey together with edges 1, 2, 3, 6, and 9 of L(G) to the left of the dotted line in red are all pinned in a separate partition. These grey-shaded nodes 1, 2, 4, and 7 in Figure 6 are actually the edges labeled as 1, 2, 4, and 7 again, respectively in Figure 5. The edge separator and the partitioning scheme in Figure 6 obtained by the LGB algorithm, thus, induce the nodal partitioning specified by the configuration of Figure 5 in which only node 3 ends up in the separator. While nodes in grey (1, 2, 6, 9) are assigned to a partition, nodes in yellow (4, 5, 7, 8) are placed in another which turns out, in this case, to be an optimal vertex partition with respect to both the separator size minimization (just node 3) and the load balance (each have 4 nodes) constraints. It should, however, be noted at that point that the cut size has been treated as one in Figure 6 by counting only the number of distinct labels of weight one as specified by the example at the cut. As it is quite clear from the discussion of the example, LGB is a modified KLB applied to the line graph. The only modifications needed, apparently, are those which stem from the fact that a number of edges having the same label in the line graph have to be treated as a single edge and the fact that the partition weights implicitly used to control the quality of load balance are, now, a function of the edge weights rather than the node weights. The existence of multiple edges having the same labels in the line graph as seen in Figure 6 has a direct effect on the way the gain of a node is calculated and updated in the line graph. The efficiency of the proposed LGB algorithm heavily depends on preserving the locality of updates in LGB as is the case in KLB.

View Article: PubMed Central - PubMed

ABSTRACT

Finite Element Method (FEM) is a well known technique extensively studied for spatial and temporal modeling of environmental processes, weather prediction computations, and intelligent signal processing for wireless sensors. The need for huge computational power arising in such applications to simulate physical phenomenon correctly mandates the use of massively parallel computers to distribute the workload evenly. In this study, a novel heuristic algorithm called Line Graph Bisection which partitions a graph via vertex separators so as to balance the workload amongst the processors and to minimize the communication overhead is proposed. The proposed algorithm is proved to be computationally feasible and makes cost-effective parallel implementations possible to speed up the solution process.

No MeSH data available.