Distributed Control

While each processor in scrambler executes the same code and is therefore somewhat autonomous - the AMR nested grid algorithm does create a hierarchy of nodes that is reflected in a hierarchy of processors. Fundamentally there is only need for one real root node. That node creates children and those children then create more children and so on… If nodes are not artificially split, (and single nodes are not shared across processors) then only one processor can determine which regions of the root grid to refine and in turn the nodes for the next higher level (level 1) Since this processor creates the children - it then has to distribute the children to other processors. These processors then create their own children and distribute those children to other processors and so on. In this way the tree is distributed across the entire collection of processors. However, the dependencies present in the nested grid algorithm create a dependency between level 0 processors and level 1 processors and so on.

This dependency requires a certain serialization of the algorithm from level to level - and unfortunately the only way to achieve perfect scalability is to balance these parts of the algorithm across each level. However in general the time spent during these serial portions of the AMR algorithm should be significantly less than the time spent during the parallel portion of the algorithm (ie the advance stage) and it should be possible to achieve good parallelization even with many levels of AMR without artificially fragmenting grids.

Child Groups

Before discussing distributed control it is helpful to first discuss child node groups \mbox{CNG}^t(n) and child processor groups \mbox{CPG}^t(n) where the t denotes whether it is the 0th or 1st generation of children. Using the same definitions in DistributedTree we can construct

begin{equation} \setcounter{equation}{1} \mbox{CNG}^t(n \in N^l_s) := \left \{ m \in N^{l+1}_{2s+t} : R(n,m) <= 0 \right \} \end{equation}

and

begin{equation} \setcounter{equation}{2} \mbox{CPG}^{l,t}_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{CNG}^t(n \in N^l_s) : M(n) = p \right \} \right \} \end{equation}

Additionally since each node contains a list of processor resources \mbox{R}(n) we can construct a Resource Processor Group:

begin{equation} \setcounter{equation}{3} \mbox{RPG}^l_s(p \in P) := \bigcup \left \{ \mbox{R}(n \in N^l_s) : M(n)=p \right \} \end{equation}

Since during the distribution of resources to children:

begin{equation} \setcounter{equation}{4} \bigcup \left \{ \mbox{M}(m) : m \in \mbox{CNG}^t(n)) \right \} \subseteq \mbox{R}(n) \end{equation}

we have

begin{equation} \setcounter{equation}{5} \mbox{CPG}^{l,t}_s \subseteq \mbox{RPG}^l_s \end{equation}

Additionally we can define a descendant processor group

begin{equation} \setcounter{equation}{6} \mbox{DPG}^{l,t}_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{R}(c) : c \in \bigcup \left \{ \mbox{CNG}^t(n \in N^l_s) : M(n) = p \right \} \right \} \right \} \end{equation}

Since during the distribution of resouces to children

begin{equation} \setcounter{equation}{7} \bigcup \left \{ \mbox{R}(m) : m \in \mbox{CNG}^t(n)) \right \} \subseteq \mbox{R}(n) \end{equation}

we also have

begin{equation} \setcounter{equation}{8} \mbox{DPG}^{l,t}_s \subseteq \mbox{RPG}^l_s \end{equation}

Processors in the \mbox{CPG}^l will receive child grids (level l+1) directly, while processors in the \mbox{DPG}^l may receive descendant grids (level > l+1) from the processors in the \mbox{CPG}^l in which case they need to receive the list of processors in the \mbox{CPG}^l which contain nodes with resource lists that contain that processor…