Reverse with Divacon

Interactive Divacon Computation Graph

Below is a live, interactive view of the PDC reverse function unrolling in Divacon computation/communication graph.

This demonstrates the post-adjustment PDC pattern where:

• pre = id (identity - no preadjustment)
• post = !other : # ! corr (communication then local operation)
• All divisions happen first, then post-processing works back up

The Communication Pattern

The remarkable characteristic of this communication pattern, expressed in George's term "lockstep", is that an entire half of the set of all positions communicates with a second entire half of the set, all in one timestep. The whole marching band takes one step in one direction at once.

Conveniently you can cut the whole set into halves 3 different orthogonal ways, like into 8 1-arrays, 4 2-arrays, and 2 4-arrays.

Talk between halves that are cut up this way, then that way, then the other way, you're done. Is that a miracle?

I think it's a miracle. I can't see it at all, then it seems perfectly obvious, then I can't see it again. At all. So go through the steps of the unrolled computation graph, and see if any part isn't perfectly obvious. Then have a cup of tea, and begin to accept it, and soon, very soon, try some more examples, and maybe some exercises, and try to do some for yourself.

Post-Adjustment Sequence

By this method, reverse takes log-N steps, each with:

1. One level of the log-N sub-divisions between the full input and atomic arrays
2. Communication (# ! corr) - corresponding elements exchange
3. Local operation (!other) - each position picks the "other" value
4. Combine (c_lr) - concatenate left-then-right for reversal