# OGSM: A Parallel Implicit Assembly Algorithm and Library for Overlapping Grids
## 3 Parallel Implicit Assembly Method
### Parallel Hole-Cutting Based on Two-Step Nodes Classification Scheme
#### 3.3.2 Verification Step: Parallel Treatment of Query Nodes  
The query nodes \(N_{q}^{i}\) on grid \(G^{i}\) can be defined as  
\[N_{q}^{i}:=\{p\mid(dt(p)<ds(p))\wedge(p\in\bigcup_{s=0}^{L-1}B_{X}^{j_{s}})\} \tag{15}\]  
where \(j_{s}\) is the index of certain target grid of \(G^{i}\). Equation (15) only requires that the query node are covered by the minimal external box of the target grid, which is a necessary and insufficient condition for the coverage relation in Equation (2). Despite this, the treatment can exclude a large number of elements from the query nodes since the minimal external box can approximate the external boundary of the grid.  
The ultimate goal of treating the query nodes is to identify the _inactive_ nodes (Equation (2)). The parallel query algorithm and the relevant data stream are depicted in Figure 9. Assume the source grid \(G^{i}\) is distributed in \(S\) processes with continuous indexes. In each process, an alternating digital tree (ADT) [26] is generated for the local grid, which provides fast-query services for any spatial node. Note that the query nodes belong to \(T\) index-continuous processes (different from the \(S\) processes hosting \(G^{i}\)), and each process contains a subset \(N_{q}^{j_{s}}\). Under the non-blocking communication pattern, the root process collects all the \(L\) subsets \(N_{q}^{j_{s}}\) of query nodes and then broadcasts them to the \(S\) processors hosting the source grid \(G^{i}\). The parallel treatment of the query nodes is performed as follows:  
1. Parallel query of donor cells and calculation of interpolation information. Each process hosting \(G^{i}\) owns the whole query nodes \(N_{q}^{i}\). On the help of the local ADT, we obtain the information whether an arbitrary query node \(p\in N_{q}^{i}\) is covered by any _internal_ cell \(\varepsilon\in C_{in}^{i}\), i.e., \(p\in\hat{\varepsilon}\). If \(p\in\hat{\varepsilon}\) holds, the information to be recorded includes the index of process containing \(\varepsilon\), the local index of \(\varepsilon\), the relative coordinates of \(p\) in \(\varepsilon\), and \(d(p,N_{w}^{i})\). Otherwise, all the information relevant to \(p\) is erased from the current process.
2. Screening of query nodes. In each process relevant to \(G^{i}\), the information of query nodes is gathered by the collectors shown in Figure 9 and broadcasted to the \(T\) targeting processes. For an arbitrary node \(p\in N_{q}^{i}\), if the stored process index is equal to that of current process \(P\), then \(dt(p)\) is updated in the process \(P\). Furthermore, if \(dt(p)<ds(p)\) holds, then \(p\) is an _inactive_ node and excluded from \(N_{q}^{i}\).  
Figure 9: Node query algorithm and interpolation information.  
Classification of query nodes. After the above two steps, \(N_{q}^{i}\) may still contain inactive node. If \(p\) is covered by the minimal internal box of \(G^{i}\) but no donor cells for \(p\) can be found on \(G^{i}\), then we treat \(p\) as an _inactive_ node and remove it from \(N_{q}^{j}\). Now all the remaining nodes in \(N_{q}^{i}\) are _active_.  
Thus far, we have completed the parallelization of hole-cutting with the proposed two-step classification scheme. We utilize the distance parameters (\(ds\) and \(dt\)) and minimal external boxes to screen the query nodes, which can dramatically decrease the amount of nodes to be queried and thereby relieves the communication load of parallel computation.