Updated Decomposition (markdown) authored by Anonymous's avatar Anonymous
...@@ -24,15 +24,15 @@ In a distributed-memory setting, where data are scattered across ...@@ -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, 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 (_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. (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-sub-domains (edges of the graph) with weights formalizing
the communication cost (_Generate graph model_). 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 (_Find optimal decomposition_). As final step 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 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) * [CartDecomposition](http://ppmcore.mpi-cbg.de/doxygen/openfpm_pdata/classCartDecomposition.html)
... ...
......