Topic — Variable-length exchanges and teardown

Needs: Lesson 6 — Blocking, buffering and deadlock, Lesson 11 — A grid of blocks: halo exchange and what it costs.

In lesson 11 every PE sends the same number of values to each neighbour, so every receive loop has a length fixed when the program is compiled. A particle simulation cannot work that way. Which particles sit near a block's edge changes from step to step, so each PE sends a different number, and often none. The sender therefore sends the count first, and the receiver reads the count and then that many values. This topic exchanges such messages over a grid in two passes, so that each PE also receives its diagonal neighbours' particles. It also starts two colors closed with teardown and opens them from the program, as the molecular-dynamics applications of the project gallery do.

What you will be able to do

• Send a message whose length is known only at run time, as a count followed by a payload, and receive it into a buffer of fixed capacity.
• Collect the diagonal neighbours' data without diagonal routes, by forwarding in a second pass.
• Write a moat that answers each message with an empty one.
• Start a color closed with tip, and open it from the program.

The program

A grid of W × H PEs, ringed by moats as in lesson 11. Each PE owns a list of n items, 0 ≤ n ≤ CAP. The PE with number k = y·W + x owns the values 100·(k+1) + j for j from 0 to n-1; here x and y number the grid's PEs from 0, without the moats. One exchange has two passes:

1. x pass. Each PE sends its list to its left and right neighbours, and receives their lists into left and right.
2. y pass. Each PE sends its own list followed by left and right, as one message, to the PEs below and above it, and receives their messages into below and above.

After the exchange each PE holds the items of all eight neighbours. A moat answers every message with an empty one, so a PE at the edge receives empty lists from outside the grid.

           m   m   m   m   m        m: moat.w, the ring of moats
   y=H-1   m  PE  PE  PE   m       PE: pe.w, the grid of W × H PEs
   y=0     m  PE  PE  PE   m
           m   m   m   m   m
             x=0   …  W-1

   x pass:  PE ◄──► PE on colors a and b
   y pass:  PE ◄──► PE on colors c and d, carrying own + left + right

ref.py draws each PE's n from a fixed random seed. It then sets the first three PEs of row 0 to CAP, so that the PE above the middle one receives a full message of 3·CAP items, and the last PE to 0. In the tutorial row, W=3 H=2 CAP=4, the PEs own these counts:

row 1:  4  2  0
row 0:  4  4  4

The counts they receive, in the order left, right, below, above, are:

row 0:  [0 4 0 6]   [4 4 0 6]   [4 0 0 2]
row 1:  [0 2 8 0]   [4 0 12 0]  [2 0 8 0]

PE (1, 1) receives 12 items from below: its neighbour below and both of that neighbour's x neighbours hold 4. ref.py also checks every item and its place in each buffer.

The code

Count, then payload

The x pass, in pe.w:

    xp n = n_own[0];
    parallel {
        { a[] <- (sp)n; ∀j in [0, n) a[] <- own[j]; }
        { b[] <- (sp)n; ∀j in [0, n) b[] <- own[j]; }
        { sp f = a[]; cnt[0] <- (xp)f; ∀j in [0, cnt[0]) left[j] <- a[]; }
        { sp f = b[]; cnt[1] <- (xp)f; ∀j in [0, cnt[1]) right[j] <- b[]; }
    }

Sockets a and b are lesson 11's colorpairs: a sends to the right and receives from the left, and b the reverse. Each sending arm sends the count, converted to sp, and then n items. The count travels as an sp like the items, so every wavelet on these colors carries one 32-bit value.

Each receiving arm reads the count at the width it was sent, sp f = a[];, converts it with (xp)f, and stores it in cnt. Its payload loop then runs cnt[0] times, a length the program learns only when the count arrives. A count of 0 makes the loop do nothing, and the message is complete.

The four arms run in one parallel block, so a PE sends and receives at the same time. In serial code that sent before receiving, every PE's messages would have to fit in the fabric's buffers, as lesson 6 showed.

The second pass

    xp m = n + cnt[0] + cnt[1];
    parallel {
        { c[] <- (sp)m; ∀j in [0, n) c[] <- own[j]; ∀j in [0, cnt[0]) c[] <- left[j]; ∀j in [0, cnt[1]) c[] <- right[j]; }
        { d[] <- (sp)m; ∀j in [0, n) d[] <- own[j]; ∀j in [0, cnt[0]) d[] <- left[j]; ∀j in [0, cnt[1]) d[] <- right[j]; }
        { sp f = c[]; cnt[2] <- (xp)f; ∀j in [0, cnt[2]) below[j] <- c[]; }
        { sp f = d[]; cnt[3] <- (xp)f; ∀j in [0, cnt[3]) above[j] <- d[]; }
    }

One y message is three lists sent one after the other, behind one count, m. The receiver does not need to know where one list ends; it stores all m items in order. Because each PE forwards what it received in the x pass, the PE above it receives the items of the three PEs below it: the one straight below and the two diagonal ones, with no diagonal route. The molecular-dynamics applications also exchange one direction after another, in several passes per direction.

The buffers hold CAP items for an x message and 3·CAP for a y message, because a y message carries at most three lists. Nothing in the receive loop checks the count against the buffer. A count larger than the buffer makes the loop write past its end, into whatever follows it in memory, so the sender must keep its lists within the capacity the receiver has.

The moats

moat.w runs four loops in parallel, one per direction:

        forever { sp f = b[]; ∀j in [0, (xp)f) junk[0] <- b[]; a[] <- 0:sp; }

It reads the count, reads and discards that many items, and replies with a count of 0: an empty message. It must read the whole message, so that the next wavelet it reads is a count. The moats never stop, so every run lasts until the cycle cap.

Teardown: colors that start closed

Two rules in bench.paint end with tip:

beach : paint(c  [D|DXC ; tip])
beach : paint(d  [U|UXC ; tip])

tip is a modifier, not a switch position: modifiers follow the last position, after an optional ;, as ring and pop= do in the topic Switch protocols. Each of these rules has one position.

On every PE, colors c and d start in teardown: the router accepts no wavelet on them until the PE's program opens them. These are the colors on which a PE receives its y messages. A program opens a color by clearing bit 15 of that color's configuration register; the registers start at address 0x7C00, one word per color. The module teardown.w does it, under the name the molecular-dynamics applications use:

xp color_config[n=24] address(0x7C00);

function clear_teardown(xp color) {
    color_config[color] <- color_config[color] & 0x7FFF;
}

pe.w imports it and opens its y colors between the two passes:

    if (OPEN > 0) {
        clear_teardown(CC);
        clear_teardown(CD);
    }

moat.w opens the same two colors as soon as it starts.

The program needs the physical number of each color it opens. color(19) in bench.paint fixes which of the 24 colors c is, and the param CC:19 gives the kernel the same number. A Paint color cannot be passed as a param: CC:c fails with unsupported option value type for parameter 'CC'. cp and dp are fixed beside them, at 18 and 16. A router lets a color take the core's output from its own number or from the number that differs in the lowest bit, so a colorpair is two such numbers. For these fixed colors Paint prints deprecated use of hard-coded color assignment, then one line per color; the message is expected.

While a color is closed, the y messages sent to a PE wait in the fabric, and they arrive when the PE opens the color. In the held row the PEs never open their y colors (OPEN=0). Every x count arrives, and every y count stays at its initial -1. ref.py checks exactly that.

A color that starts closed and opens when the PE is ready works as a gate: wavelets sent on it wait in the fabric until the PE opens it. This program needs no gate. The molecular-dynamics applications need one. They choose at run time which color each of their input and output queues serves, and they open their colors only after that, so that no wavelet reaches a queue before it is set up. Their colors have no Paint rule at all: Paint leaves every color without a rule on a PE in teardown, with its input disabled, and those applications write their own route configuration into the image.

What the hardware does

• The teardown bit. Bit 15 of each color's configuration register is teardown in progress. While it is set, the router flow-controls every input of that color: wavelets wait in the senders' buffers. Software clears it to enable the color, and may change the color's route in the same write. Paint sets it on a color whose rule has tip, and on every color that has no rule.
• Teardown wavelets. A control wavelet whose command is a teardown (opcode 11) sets the bit on every router it passes and notifies each PE's core, so that software can reprogram the color and then reopen it. That is how a color is rerouted while a program runs. This topic does not send one.
• Messages of run-time length. On an ordinary color nothing marks where a message ends. A count is one convention, and a closing named message, such as lesson 7's flush(), is another. The molecular-dynamics applications send all counts in one phase and the payloads in the next.
• A receive loop of length 0. A loop whose run-time length is 0 transfers nothing and does not wait. The empty messages in every row rely on it.

Run it

In your copy of the tutorial (see Lesson 1):

cd tutorial/ext-routing/variable-length-exchange
make TEST=tutorial

Success is a line ending in PASS tutorial [ W=3 H=2 CAP=4 OPEN=1 ARCH=sdr ]. The end of test-tutorial/make-log prints the counts every PE received, row 0 first. make TEST='*' also runs:

Row	Size	What it covers
big	W=4 H=3 CAP=8	y messages of up to 24 items
one	W=1 H=1 CAP=3	one PE, with only moats around it: every message empty
held	W=3 H=2 CAP=4 OPEN=0	y colors never opened

A mismatch prints the PE, the buffer, the count it got and the count it wanted, and then FAIL. Every run lasts until the cycle cap, cycles=2000 in the Makefile. The big row made its last memory write at cycle 304. Run make clean before running a row again after an edit.

Pitfalls

• Read the count at the width it was sent. The count is an sp. With cnt[0] <- a[]; the receiver reads only 16 bits, the low half of the sp. For the count 4.0 that is 0, so every left count came out 0, and the y messages, whose length is built from those counts, left out the left items.
• Name only fixed colors. clear_teardown needs a color's number, which only color(N) fixes. An unfixed color() can land on any number.
• A closed color stops the exchange, not only the receiver. Messages to a closed PE wait in the fabric's buffers, and a message longer than those buffers also stops its sender. In the held row no PE finishes its y pass, because its receiving arms never complete.
• Check the capacity. The receive loop trusts the count. Keep n ≤ CAP, or give the receiver a test that discards what does not fit.

Exercises

1. Remove tip from the two rules and both clear_teardown calls from pe.w. Predict which rows pass, then run make TEST='*'.
2. Make every PE own CAP items: in ref.py, set every count to cap. Predict the largest count any PE receives in the big row, and where. Then run it.

Next

Topic — Eight neighbours: spiral routing on a budget reaches the diagonal neighbours of a grid through an extra hop.

References

• Hardware Register Access and Parallel Blocks in the Tungsten reference
• Teardown (tip) in the Paint reference
• The short-range molecular dynamics and embedded-atom applications