Get/Send Algorithm (cont.)

Start with every site (abstract processor) having the processor number as its unique label (i.e., the root of its own tree). Each iteration consists of the following steps:

1. Local label propagation

2. Send --- if a processor's label changes during step (1), it sends the new label to the root of its current sub-cluster (i.e., the processor number given by its old label), which picks the smallest of all the labels it receives as its new label.

3. Scan (optional) --- propagate labels fast along rows and columns, using scan or parallel prefix operations.

4. Get --- every site gets the (possibly new) label from the root processor for its current label.

5. Check for completion --- continue if any labels have changed.

The Get/Send and MultiGrid algorithms are logarithmic in the lattice size L, unlike the simple local label propagation algorithm which usually takes time of order L, but can be order for complex clusters like spirals.

2. Get/Send algorithm after a send.

3. Get/Send algorithm after a few iterations.

4. The final cluster labels.