Concurrency

Distributed Memory

The strategy for achieving distributed-memory concurrency is to partition the nodes and distribute them across processors. Each processor has an orthtree that holds a subset of the nodes. The domain of each orthtree is the same. The nodes stored in a particular orthtree cover a portion of its domain.

There are many ways to partition the nodes across processors. The simplest method is to use the z-ordering and give each processor a contiguous block of nodes. The number of nodes in each processor is approximately equal.

Shared Memory

The strategy for achieving shared-memory concurrency is to partition a processor's nodes across threads. Let there be N threads available in concurrent sections. When applying an operation to all nodes, the set of nodes is partitioned into N subsets using the z-ordering. Then each thread acts on its set of nodes. Here we assume that an operation applied to a node may alter only that node. However, it may access the state of other nodes. We also assume that the operations may be applied in any order. The threads may concurrenty alter the state of their nodes without conflict.

Refinement is more complicated than applying an operation to the nodes because it involves inserting and erasing nodes. One could make insertions and deletions thread-safe by performing these operations in OpenMP critical sections. (Recall that only one thread may execute a given critical section at a time.) This appoach is easy to implement, but may not be efficient because of its fine-grained nature. It is usually preferable for threads to cache their modifications and perform them in a single critical section. Note that determining which nodes should be split may be done concurrently, each thread examines its subset of the nodes. After each thread collects the nodes that need refinement, it applies splitting operations to those nodes in a critical section.

The concurrent algorithm for coarsening is similar to that for refinement. However, the partitioning must be done differently. Coarsening is done by repeating sweeps until no further coarsening is required. In a coarsening sweep, a group of nodes may be merged a single time. Before each sweep, the nodes are partitioned such that each potential merging operation involves nodes in only one of the subsets. The threads concurrently collect the groups of nodes that need coarsening. Then each thread performs the merges in a critical section.

The figure below shows two partitions of a 2-D orthtree. The first partition evenly divides the nodes and is suitable for applying an operation to the node data or for refinement. It is not suitable for coarsening because a mergeable group of nodes is divided between the two sets. The second partition can be used for a concurrent coarsening sweep. Each set contains one group of nodes that could be merged.