... | ... | @@ -24,15 +24,15 @@ In a distributed-memory setting, where data are scattered across |
|
|
processors, two factors are important: equal division of work across
|
|
|
processors and reduction of the communication overhead.
|
|
|
A typical approach, is to formulate the problem as a
|
|
|
graph-partitioning problem: the physical domain is divided into sub-domains (_Domain decomposition_)
|
|
|
graph-partitioning problem: the physical domain is divided into sub-sub-domains (_Domain decomposition_)
|
|
|
(vertices of the graph), each of them carrying a weight modelling the computational cost.
|
|
|
The communication pattern between sub-domains is represented as links
|
|
|
between the sub-domains (edges of the graph) with weights formalizing
|
|
|
between the sub-sub-domains (edges of the graph) with weights formalizing
|
|
|
the communication cost (_Generate graph model_). The requirement of balanced computation with
|
|
|
minimal communication then translates to the optimization problem of
|
|
|
finding a graph partitioning where each group contains the same sum of
|
|
|
weights, and the sum of the cut edges is minimal (_Find optimal decomposition_). As final step
|
|
|
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.
|
|
|
the decomposition can be post-process further more to be for optimal, based on factors not considered by the optimization process, like merging vertex, or merging sub-sub-domain, 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](http://ppmcore.mpi-cbg.de/doxygen/openfpm_pdata/classCartDecomposition.html)
|
... | ... | |