Distributed Tree Management

The fundamental unit of the AMR mesh is a node or rectangular patch. First we define N as the set of all nodes and P as the set of all processors. We also define the functions L(n), M(n), and G(n) to identify the level of a node, the mpi_id of the processor containing the node's data, and the generation of the node. Using these definitions we can construct the set of all nodes on level l and generation g as

begin{equation} N^l_g := \left \{ n \in N : L(n)=l \wedge G(n)=g \right \} \end{equation}

For the AMR calculation to proceed, every node must be aware of any nodes with which they might need to exchange data. This is generally based on some distance between the nodes boundaries. We can define an internode distance between nodes m and n as

begin{equation} \setcounter{equation}{2} R(m,n)=\max_i\left[\max \left( m(i,1)-n(i,2), n(i,1)-m(i,2) \right) \right] \end{equation}

Note if grids are adjacent than R_mn = 1, and if grids overlap then R_mn ⇐ 0

Different stages of the algorithm require different number of ghost zones. The hyperbolic advance for instance - will typically require between 2 and 4 ghost zones (mbc_H). After a hydro advance the size of the grid with valid data will be reduced by mbc_H. If we need to take 2 hydro steps on this level and finish with an updated region the size of the node, we must start out with data that is 2 * mbc_H. We therefore would need to begin by collecting the data from all previous nodes with an inter-node distance ⇐ 2*mbc_H. Since this data will come from previous overlapping nodes we'll call this \mbox{mbc}_O^l.

The collection of nodes that we need to receive previous data from is called the previous overlap node group

begin{equation} \setcounter{equation}{3} \mbox{PONG}(n \in N^l_s) := \left \{ m \in N^l_{s-1} : R(n,m) <= \mbox{mbc}_{O}^l \right \} \end{equation}

After completing one hydro step, we now need to synchronize fluxes with adjacent neighboring nodes. These Neighbor Node Groups (NNG) are defined as nodes with inter-node distances of \mbox{mbc}_N^l=1 or more formerly

begin{equation} \setcounter{equation}{4} \mbox{NNG}(n \in N^l_s) := \left \{m \in N^l_{s} : R(n,m) = \mbox{mbc}_N^l \right \} \end{equation}

After synchronizing fluxes and internal data from child grids, we should update our external data with refined data from surrounding grids… Of course now we have completed one step - and if we need to take a second step we only need to fill in ghost data from current grids that are within mbc_H or more generally within a distance \mbox{mbc}_G^l. We will call these the Current Overlap Node Group (CONG) or more formerly:

begin{equation} \setcounter{equation}{5} \mbox{CONG}(n \in N^l_s) : \left \{ m \in N^l_{s} : R(n,m) <= \mbox{mbc}_{G}^l \right \} \end{equation}

Of course we should resynchronize our fluxes with our neighbors - but these will be the same neighbors as before.

Finally we need to exchange our data with the new set of grids - or our Future Overlap Node Groups

begin{equation} \setcounter{equation}{6} \mbox{FONG}(n \in N^l_s) := \left \{ m \in N^l_{s+1} : R(n,m) <= \mbox{mbc}_{O}^l \right \} \end{equation}

It is likely that our Current Overlaps and Neighbors will contain many of the same nodes - in fact \mbox{NNG}(n) \subseteq \mbox{CONG}(n) \forall n \in N^l_s provided that \mbox{mbc}_N^l <= \mbox{mbc}_G^l so we can use our current overlaps in place of our neighbors, however this may occasionally lead to sync-flux sub-messages being sent to processors containing non-adjacent grids…

Each node group also defines a processor group made up of the collection of processors on which the node groups of a processor's nodes resides… For example - the Previous Overlap Processor Group for processor l can be defined as

begin{equation} \setcounter{equation}{7} \mbox{POPG}^l_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{PONG}(n \in N^l_s) : M(n) = p \right \} \right \} \end{equation}

Similarly the Neighbor Processor Group (NPG), the Current Overlap Processor Group (COPG), and the Future Overlap Processor Group (FOPG) can be similarly defined:

begin{equation} \setcounter{equation}{8} \mbox{NPG}^l_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{NNG}(n \in N^l_s) : M(n) = p \right \} \right \} \end{equation} \begin{equation} \mbox{COPG}^l_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{CONG}(n \in N^l_s) : M(n) = p \right \} \right \} \end{equation} \begin{equation} \mbox{FOPG}^l_s(p \in P) := \bigcup \left \{ M(m) : m \in \bigcup \left \{ \mbox{FONG}(n \in N^l_s) : M(n) = p \right \} \right \} \end{equation}

Since there is no coordinating processor managing the transfers, the sending and receiving of data needs to be a cooperative endeavor. So if processor 'p' is in the 'POPG' of processor 'q', then processor 'q' should be in the FOPG of processor 'p'. Fortunately as long as the inclusion criteria for node groups is symmetric, the processor groups will be symmetric. Of course before a remote node can be put in a node group - the processor must know about the remote node. Since we implement a nested grid sturcture - any node in a node group should be the child of a node's parent's node group. So if parent node's exchange their children, they can determine whether or not the children of the nodes in their node groups belong in the node groups of their children. Of course this requires parents exchange their children with members of their node groups (or at least the children that might belong to that member's children's nodegroups).