p4est 2020 HCM Summer School: Ghost

We are organizing a p4est summer school sponsored by the Hausdorff Center for Mathematics at the University of Bonn, Germany. Please see also the school's home page and application forms.

The ghost layer aka. halo

This tutorial is about collecting so-called ghost or halo elements and what you can do with them. The ghost layer is defined as a set of remote elements adjacent to the process-local ones. This data structure is ideally suited to establish the communication pattern between mesh-adjacent parallel processes. The ghost layer contains all information required to determine all sender-receiver pairs without additional MPI communication. The pattern is necessarily symmetric: Each sender of a pair is also a receiver and vice versa.

p4est provides dedicated functions p4est_ghost_new (2D), p8est_ghost_new (3D) and further methods to find individual elements in the ghost layer and to communicate associated data with remote processes.

Dependencies
Build; roughly understanding example/simple/
Required skills
Some idea about parallel computing
Skills acquired
Assembling the ghost aka. halo layer of an adaptive mesh.
Next steps
Extend your hello-world program by adding a call to ghost creation and destruction. In between, you may use the provided binary search functions to find individual elements in it. You may also call the ghost exchange functions with some per-element data that you define freely and verify that it is communicatied correctly. Furthermore, the ghost layer is one input to the p4est_iterate algorithm, which traverses all interface entities relevant to the local process.

Constructing the ghost layer

The ghost layer can be constructed from any valid p4est object. This forest does not need to be 2:1 balanced. The ghost layer is a read-only immutable object and must be destroyed when no longer needed. 

ghost = p4est_ghost_new (p4est, btype);

The p4est object is used as input to this algorithm. The result can be queried and searched without accessing the original input. The btype parameter determines if the ghost layer should collect face adjacency, face and edge adjacency in 3D, or full adjacency including corner neighbors. Please see the 2D and 3D declarations.

As with any p4est object, call p4est_ghost_destroy when the structure is no longer needed.

Accessing and searching the ghost layer

The ghost layer is a public struct with documented entries, most of them arrays. The 2D and 3D declarations are structurally identical: Linear tree storage is dimension independent, and ghost elements are ordered ascending just as mesh elements. We may index into the element storage by window start and offset indices. We may also use binary search in the linear order to find ghost elements.

A closer look at the data structure reveals that the ghost array is windowed once by tree and once by process offsets. Naturally, some trees or processes may have zero ghost elements for a given process, in which case the window has length zero.

A second set of arrays is called mirrors. These are local elements that are ghosts to remote processes, sometimes called the (inside) parallel boundary elements. Ghosts would be the outside parallel boundary elements. One mirror may be ghost to more than one remote process. Thus, the indexing structure is slightly less direct than for ghosts: We have an array mirror_proc_mirrors that contains one set of indices into the mirrors for each remote process. The array mirror_proc_offsets indexes into these sets, which vary in length by remote process.

Exercise G1: Write a routine to save the ghost layer to disk in the VTK format suitable for visualization. Proceed along the lines of p4est_vtk_write_file. See our graphics tutorial for details.

Exercise G2: Read the source code of p4est_ghost_bsearch. Write an example program where you construct a uniform mesh in parallel, then construct some random quadrants on the chosen refinement level using p4est_quadrant_set_morton and look for them in the ghost layer with this binary search function. Print hits and misses.

Calling parallel ghost data exchange

Only rarely will a programmer use the binary search function mentioned above. For example, to exchange face-neighbor data in a finite volume method, we would rather recommend using p4est_iterate as done in the step3 example program.

Alternatively, the provided p4est ghost exchange functions may be of interest. They encapsulate all MPI messaging and are framed as begin and end pairs that internally use non-blocking point-to-point communication, thus allowing for overlapping computation and communication. The sequence of usage is the following:

  1. Choose to either communicate the convenient per-quadrant user data allocated by p4est or a block of data allocated by you for the mirror elements.
  2. Call the p4est ghost exchange begin functions appropriate for your data choice.
  3. Do something else if you like, but do not touch the data in the mirror or ghost buffers.
  4. Call the matching ghost exchange end function. This will internally wait for all pending MPI messages. When it returns, the mirror storage may be freed and the ghost storage is ready to be read.
  5. Repeat as needed (usually once per time step). As long as the mesh is not refined, coarsened, 2:1 balanced or repartitioned, the ghost layer structure and the data buffers can be kept around.

Exercise G3: Expand on exercise G1. Collectively produce some data for the mirror elements, communicate it with p4est_ghost_exchange_custom and visualize it after receiving as an extra data field in the ghost VTK output.