|
# Decomposition
|
|
# Decomposition
|
|
|
|
|
|
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, considering that in our context multiple distributed structures can interact with each other and dynamically change, our particular focus is in mapping structures into common domain and decomposition and distribution strategies over this domain. Once this domain is defined two main approach are considered inside OpenFPM.
|
|
|
|
|
|
* Model decomposition:
|
|
* Model decomposition:
|
|
* Domain decomposition
|
|
* Domain decomposition
|
... | @@ -20,14 +20,17 @@ The Fixed decomposition just divide the domain as the user specified and assign |
... | @@ -20,14 +20,17 @@ The Fixed decomposition just divide the domain as the user specified and assign |
|
|
|
|
|
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.
|
|
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
|
|
### Domain definition
|
|
|
|
|
|
|
|
In general the concept of common domain is not defined in general, can go from different way to re-index the information so from multi-index concept to mapping the information into common spaces discrete or continuos, In the following we will consider structures that map over N-dimensional spaces because at the moment is our main but not only interest
|
|
|
|
|
|
|
|
### Model decomposition
|
|
|
|
|
|
In a distributed-memory setting, where data are scattered across
|
|
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-sub-domains (_Domain decomposition_)
|
|
graph-partitioning problem: the 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-sub-domains (edges of the graph) with weights formalizing
|
|
between the sub-sub-domains (edges of the graph) with weights formalizing
|
... | | ... | |