... | @@ -14,9 +14,11 @@ Every structure should divide the information that they store across processors, |
... | @@ -14,9 +14,11 @@ Every structure should divide the information that they store across processors, |
|
* Data driven decomposition
|
|
* Data driven decomposition
|
|
* Divide the total information in equal chunks
|
|
* Divide the total information in equal chunks
|
|
|
|
|
|
The first approach try to create a model for computation and comunication and try to find a decomposition that minimize it.
|
|
The Model decomposition approach try to model the computation and comunication across processor given a certain decomposition and try to find the decomposition that minimize the communication balancing the computation.
|
|
|
|
|
|
The second just divide the domain as the user specified and assign 1 sub-domain to each processor
|
|
The Fixed decomposition just divide the domain as the user specified and assign 1 sub-domain to each processor
|
|
|
|
|
|
|
|
The data driven decomposition instead consider the volume of the information the structure store and divide the volume equally them equally regardless of the communication.
|
|
|
|
|
|
### Model decomposition
|
|
### Model decomposition
|
|
|
|
|
... | @@ -29,11 +31,11 @@ graph-partitioning problem: the physical domain is divided into sub-sub-domains |
... | @@ -29,11 +31,11 @@ graph-partitioning problem: the physical domain is divided into sub-sub-domains |
|
The communication pattern between sub-domains is represented as links
|
|
The communication pattern between sub-domains is represented as links
|
|
between the sub-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 an 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, or merging sub-sub-domain, to create bigger sub-domains.
|
|
the decomposition can be post-process further more to be more optimal and 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 it is the main approach
|
|
Even if a model decomposition it is not bind to a graph model it is true that until now it is the best approach in scientific computation
|
|
|
|
|
|
* CartDecomposition [(doc)](CartDecomposition)[(API reference)](http://ppmcore.mpi-cbg.de/doxygen/openfpm_pdata/classCartDecomposition.html)
|
|
* CartDecomposition [(doc)](CartDecomposition)[(API reference)](http://ppmcore.mpi-cbg.de/doxygen/openfpm_pdata/classCartDecomposition.html)
|
|
|
|
|
... | | ... | |