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.


Mapping partitions to processors.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3927507&req=5

f20-sensors-08-00635: Mapping partitions to processors.

Mentions: The algorithm, Recursive LGB, shown in Figure 19 is called with the depth parameter equal to zero initially. While the global depth parameter dmax controls the number of recursions, the global variable separator is for numbering the separators found sequentially. Given this simple framework to apply LGB recursively, a possible algorithm to map the partitions to processors is presented in Figure 20. In Algorithm 6.2, the subgraphs are all assigned initially to processor number 0. Then, at the ith iteration each subgraph is assigned to its current processor number with its ith bit set or reset depending on whether it is in partition two or one, respectively.


Vertex Separators for Partitioning a Graph
Mapping partitions to processors.
© Copyright Policy
Related In: Results  -  Collection

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

f20-sensors-08-00635: Mapping partitions to processors.
Mentions: The algorithm, Recursive LGB, shown in Figure 19 is called with the depth parameter equal to zero initially. While the global depth parameter dmax controls the number of recursions, the global variable separator is for numbering the separators found sequentially. Given this simple framework to apply LGB recursively, a possible algorithm to map the partitions to processors is presented in Figure 20. In Algorithm 6.2, the subgraphs are all assigned initially to processor number 0. Then, at the ith iteration each subgraph is assigned to its current processor number with its ith bit set or reset depending on whether it is in partition two or one, respectively.

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.