3
$\begingroup$

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?

Two adjacent quadrilaterals with 3 shared nodes

Seven quadrilaterals with multiple shared nodes along with final global indexing of nodes

$\endgroup$
  • $\begingroup$ New image added. $\endgroup$ – aycarus Mar 21 at 14:54
  • $\begingroup$ do you need the assigned labels, k to be the same as are produced by your sequential algorithm, or do they just need to be unique? Do you need the assignment to be deterministic? $\endgroup$ – Wandering Logic Mar 22 at 12:59
  • $\begingroup$ also, in your image, the nodes all start with a preassigned unique identifier. Why not just use that? (And are you already using it? How does the is coincident function work?) $\endgroup$ – Wandering Logic Mar 22 at 13:00
  • $\begingroup$ for example, if you start with a list <q,k> where q is a quadrilateral identifier and k is a node identifier, then your problem is just to find the inverted index <k,q>, which could be done with, for example a hashing algorithm (assuming you have a way of producing a decent hash(k)). $\endgroup$ – Wandering Logic Mar 22 at 13:13
  • $\begingroup$ Yes the assigned labels need to be the same as the ones produced by the sequential algorithm. $\endgroup$ – aycarus Mar 22 at 22:38
1
$\begingroup$

Assume you have an array (random access sequence) of tuples <q, j, x, y, first, k_tmp, k> where q is the (integer) identifier of a quadrilateral, j is the local index (within the quadrilateral) of a node, x, y are the coordinates of a node contained in quadrilateral q, and first, and k_tmp, and k are fields to be filled in later.

  1. sort the array lexicographically on x, then y, then q (i.e. all the array elements corresponding to the node at x,y will be adjacent in increasing order by q). The sort can be done in parallel. See for example Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha, "A comparison of sorting algorithms for the connection machine CM-2", Proc ACM Symp Parallel Alg and Arch, SPAA-3:3-16, 1991, or Arpaci-Duesseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson, "High-Performance Sorting on Networks of Workstations", SIGMOD Conference, 1997:243-254.
  2. foreach element e of the array, in parallel:
    • array[e].first = if (array[e].x = array[e-1].x and array[e].y = array[e-1].y) then 0 else 1
  3. resort the array lexicographically on q, and j.
  4. calculate array[].k_tmp as the parallel prefix sum (sometimes called a "scan" operation) of the array[].first fields. A good paper on parallel prefix sum is Chatterjee, Blelloch, and Zagha, "Scan Primitives for Vector Computers," Proceeedings of Supercomputing, 1990:666-675.
  5. resort the array lexicographically on x and y and q.
  6. calculate array[].k as the segmented copy scan of array[].k_tmp using array[].first as the bit vector to determine the segment boundaries (see Section 3.2 of the paper by Chatterjee, Blelloch, and Zagha). Briefly: The segmented copy scan will use array[].k_tmp if array[].first is 1, else it will use the array[].k_tmp from the first element to the left where array[].first is 1.
  7. you can now resort the array lexicographically on q and j and the k field should be correct for each array element.

The fact that we sorted the array back and forth and back and forth seems to indicate that we should probably, in practice, use two data structures (one sorted on q and j and one sorted on x and y) with pointers back and forth between them.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .