|
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
|
|
|
|
|
|
* CartDecomposition
|
|
* CartDecomposition
|
|
|
|
|
... | | ... | |