Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of quadrilaterals together. In each quadrilateral we distribute np nodes, with some nodes located along the boundary of the quadrilateral. This gives rise to a 2D indexing of nodes (i,j) where i=1,..,N is the quadrilateral index and j=1,..,np is the local index of the node within that quadrilateral.
We now wish to develop a map from (i,j) to a global index of nodes that accounts for coincident nodes that may exist along the boundary of the quadrilaterals (e.g., see attached image of two quadrilaterals with three shared nodes -- np=9 but global index goes from 1..15). In serial, a simple algorithm would be as follows:
let k = 1 let X = map from local index (i,j) to global index k for each quadrilateral i for each node j in quadrilateral i if (i,j) is coincident with a node (i',j')->k' in X assign index k' to (i,j) else assign index k to (i,j) in X k = k + 1
In parallel, only elements of this map that are associated with quadrilaterals on the local thread need to be stored. We can further assume that each thread has complete knowledge of the quadrilateral indices and nodes of its own quadrilaterals and those quadrilaterals and nodes that are spatially adjacent.
So the question is: Is there a parallel algorithm that performs better than the serial algorithm above?