Global indexing of shared nodes in parallel
Assume you have an array (random access sequence) of tuples &lt;q, j, x, y, first, k_tmp, k&gt; 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.


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.
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

resort the array lexicographically on q, and j.
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.
resort the array lexicographically on x and y and q.
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.
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.