Every structure should divide the information that they store across processors, in order to do this two main approach are considered inside OpenFPM.
Every structure should divide the information that they store across processors, in order to do this two main approach are considered inside OpenFPM.
* Model decomposition: (Steps)
* Model decomposition:
* Domain decomposition
* Domain decomposition
* Generate graph model
* Generate graph model
* Find optimal decomposition
* Find optimal decomposition
*Optimizing the decomposition
*Post process the decomposition
* Fixed decomposition
* Fixed decomposition
* Domain decomposition
* Domain decomposition
...
@@ -25,15 +25,16 @@ In a distributed-memory setting, where data are scattered across
...
@@ -25,15 +25,16 @@ In a distributed-memory setting, where data are scattered across
processors, two factors are important: equal division of work across
processors, two factors are important: equal division of work across
processors and reduction of the communication overhead.
processors and reduction of the communication overhead.
A typical approach, is to formulate the problem as a
A typical approach, is to formulate the problem as a
graph-partitioning problem: the physical domain is divided into sub-domains
graph-partitioning problem: the physical domain is divided into sub-domains (_Domain decomposition_)
(vertices of the graph), each of them carrying a weight modeling the computational cost.
(vertices of the graph), each of them carrying a weight modelling the computational cost.
The communication pattern between sub-domains is represented as links
The communication pattern between sub-domains is represented as links
between the sub-domains (edges of the graph) with weights formalizing
between the sub-domains (edges of the graph) with weights formalizing
the communication cost. The requirement of balanced computation with
the communication cost (_Generate graph model_). The requirement of balanced computation with
minimal communication then translates to the optimization problem of
minimal communication then translates to the optimization problem of
finding a graph partitioning where each group contains the same sum of
finding a graph partitioning where each group contains the same sum of
weights, and the sum of the cut edges is minimal. Even if a model decomposition
weights, and the sum of the cut edges is minimal (_Find optimal decomposition_). As final step
it is not bind to a graph model it is true that until now is the main approach
the decomposition can be post-process further more to be for optimal, based on factors not considered by the optimization process, like merging vertex to create bigger sub-domains.
Even if a model decomposition it is not bind to a graph model it is true that until now is the main approach
