Topic — Message passing: routing by address

Needs: Lesson 4 — Sockets, wavelets, colors and routes, Lesson 6 — Blocking, buffering and deadlock, Lesson 10 — Switches: PEs that take turns on one color.

Every route in the main lessons is painted before the run. A switch can change a route at run time, but only among the positions Paint painted, so a PE can only send to the PEs those routes reach. Message passing is a second routing mode. A message is a header wavelet followed by data wavelets, up to 31 of them in the form this topic uses. The header holds the column and row of the destination PE, and the routers steer the message there by themselves. A PE can therefore send to any PE of the region, and it can choose the destination at run time, from its data.

This topic builds a histogram on two rows of PEs. The destination of every value depends on the value's key, and about half of the messages change rows, so they exercise the header's north and south bits.

What you will be able to do

• Enable message passing on a region with Paint's bank() and mp().
• Build a message header with a union and a function: destination column and row, the north or south bit, and the length.
• Send a message to a PE chosen at run time, and receive messages from several senders.
• End a stream of messages whose number the receiver does not know in advance.
• Count what message passing costs: five colors per message-passing bank, on every PE that takes part, and the core's time per message.

The program

Message passing names directions by the compass, so recall lesson 4: Paint's x is the PE's column and grows to the east; y is its row, and row 0 is the north row, so a larger y lies further south.

Two sources in column 0 each hold N (key, value) pairs with keys 0 to 7. Eight buckets sit in a 4 × 2 block east of them, one per key. Each source sends every value to the bucket for its key. Each bucket adds up the values it receives and counts them. When a source has sent its data, it sends an end message to all eight buckets. A bucket stops when it has an end message from both sources. Then the buckets of each row send their sums west to the source of their row on an ordinary color, by the serial drain of lesson 10.

Bucket k is at column 1 + (k mod 4) and row k / 4. The figure draws y growing upward, as lesson 4 does, so south is up on the page:

            x=0       x=1      x=2      x=3      x=4
  y=1     src[1]    bucket4  bucket5  bucket6  bucket7     south row
  y=0     src[0]    bucket0  bucket1  bucket2  bucket3     north row

  message passing (message-passing bank 0): any source to any bucket,
      east first, then north or south
  gather (one ordinary color, each row on its own): bucket -> ... -> source, westward

A value with key 6 from src[0] travels east along row 0 to column 3, then south to row 1. A value with key 1 from src[1] travels east along row 1 to column 2, then north.

The tutorial row uses these pairs:

Source	Keys	Values
src[0] (row 0)	2 0 7 1 0 2 5 3	10 5 7 3 8 4 6 9
src[1] (row 1)	6 0 1 7 2 0 5 1	1 2 30 40 5 6 70 8

and gives:

Bucket	0	1	2	3	4	5	6	7
sum	21	41	19	9	0	76	1	47
count	4	3	3	1	0	2	1	2

Bucket 4 receives no value: it gets only the two end messages.

test.rc has three rows:

Row	What it runs
tutorial	the pairs above
n40	40 random pairs per source (SEED=1)
shifted	the pairs above, with the whole layout moved to start at column 3, row 2

The shifted row checks that the program builds every header from real fabric coordinates.

The code

The layout: bench.paint

let b0 = bank(0)
let mpc = color(b0)
let gather = color()

let all = rect(X0 Y0 5 2)
all : mp(b0)

• bank(0) reserves message-passing bank 0, a block of five colors (see "What the hardware does").
• color(b0) is the message-passing bank's CE color. Every message reaches the destination's core on this color, so a kernel binds its message socket to it.
• all : mp(b0) turns message passing on in the router of every PE in the 5 × 2 block. A message crosses the routers between its source and its destination, and each of them must have mp() for the message-passing bank, even a PE whose kernel never touches the message.

let src = rect(X0 Y0 1 2 'x 'y)
src : code('src [mp:mpc rx:gather N:N X0:X0 Y0:Y0])
src : paint(gather [R>C])
src : name('src)

let buckets = rect(X0+1 Y0 4 2 'x 'y)
buckets : code('bucket [mp:mpc tx:gather SOURCES:2])
buckets : name('bucket)

The two sources are one region running src.w, and the eight buckets one region running bucket.w. X0 and Y0 are the layout's corner, from test.rc; the sources get them as parameters. The gather routes are lesson 10's serial drain, one rule per rectangle:

let pass = rect(X0+1 Y0 3 2)
pass : paint(gather [C>L ; R>L])

let last = rect(X0+4 Y0 1 2)
last : paint(gather [C>L])

union(all src buckets pass last)

Both rows use the one color gather. Its routes run east to west only, so the two rows never meet.

The header: message.w

Both kernels import message;, a module that holds a union and one function:

union word {
    u32 u;
    xp w[2];
};

A union stores its members in the same memory. word is one 32-bit wavelet seen two ways: as the u32 u, which a socket sends and receives whole, and as two xp halves, w[0] with bits 15:0 and w[1] with bits 31:16.

The header packs five fields into the 32 bits:

Bits	Field
31:20	destination column
19:8	destination row
7	north: the destination row is smaller than the sender's
6	south: the destination row is larger than the sender's
5	0: the length is in bits 4:0 (always 0 in this topic)
4:0	number of data wavelets after the header, 0 to 31

function header(xp col, xp row, xp here, xp len) -> u32 {
    union word h;
    xp dir = 0;
    if (row < here) dir = 0x80;
    if (row > here) dir = 0x40;
    h.w[1] = (col << 4) | (row >> 8);
    h.w[0] = (row << 8) | dir | len;
    return h.u;
}

here is the sender's own row. A destination on the sender's own row gets neither bit. The column fills bits 31:20, which are bits 15:4 of w[1]. The row straddles the halves: its top four bits go to bits 3:0 of w[1], and its low eight bits to bits 15:8 of w[0], where the shift row << 8 drops the top four.

The sources: src.w

xp row_id[1] address(0x7C45);

address() (lesson 3) places row_id on the PE's Row ID register. Paint writes each PE's row there, and its column into the Column ID register at 0x7C46.

    ∀i in [0, N) {
        xp k = key[i];
        hdr.u = header(X0 + 1 + (k & 3), Y0 + (k >> 2), my_row, 1);
        msg.w[0] = value[i];
        msg.w[1] = 0;
        mp[] <- hdr.u;
        mp[] <- msg.u;
    }

k & 3 is k mod 4 and k >> 2 is k / 4, so the destination comes from the data. Each message is the header and one data wavelet. The data wavelet carries two 16-bit values: the value in w[0], and a tag in w[1], 0 for data. Every send is a whole u32.

    ∀b in [0, 8) {
        hdr.u = header(X0 + 1 + (b & 3), Y0 + (b >> 2), my_row, 1);
        msg.w[0] = 0;
        msg.w[1] = 1;
        mp[] <- hdr.u;
        mp[] <- msg.u;
    }

    t[1] <- tsc[0];

    ∀j in [0, 4) sums[j] <- rx[];

The end messages carry tag 1. t[1] reads lesson 3's timestamp counter after the last send (see "The cost" below). Then the source receives its row's four sums, nearest bucket first.

The buckets: bucket.w

    while (ends < SOURCES) {
        hdr.u <- mp[];
        xp len = hdr.w[0] & 0x1F;
        ∀j in [0, len) {
            msg.u <- mp[];
            if (msg.w[1] == 1) {
                ends = ends + 1;
            } else {
                s = s + msg.w[0];
                c = c + 1;
            }
        }
    }

The receiving core gets the header too. The bucket reads the length from bits 4:0 and then reads that many data wavelets. The header says where the message goes, not where it came from, so a receiver that must tell kinds of message, or senders, apart needs a tag in the data. Here the tag tells a value (0) from an end message (1). A bucket cannot know how many values it will get, because the keys decide that; the end messages tell it when to stop. A ∀ range can end at a value computed at run time, as [0, len) ends at the length read from the header.

    sum[0] = s;
    count[0] = c;
    tx[] <- sum[0];
    flip tx[];

The bucket then drains its sum west, as in lesson 10, sending from memory before the flip.

The test

ref.py writes the keys and values, and the expected sums and counts. The Makefile loads the sources' data with miset ... order="y x n", the region's row, then column, then element. It reads the sums that reached the sources and each bucket's count directly, so a value that reached the wrong bucket fails the test even when a sum happens to match. Then cycles.py prints how long each source took to send its messages; it never fails.

What the hardware does

A message-passing bank is five colors. Each of its five colors buffers the messages that enter a router from one direction:

Message-passing bank	East	North	CE	South	West
0	14	15	16	17	18
1	19	20	21	22	23

A message that turns moves into the buffer for the direction it now arrives from; the router does that by itself. At the destination, the core receives it on the message-passing bank's CE color, 16 for message-passing bank 0 and 21 for message-passing bank 1, whatever direction it came from. mp() sets the five colors of every PE in the region to this mode. Paint prints deprecated use of hard-coded color assignment for the fixed colors of the message-passing bank; the message is expected.

East or west first, then north or south. The router moves a message along the row until the column matches, then along the column, then hands it to the core. The north and south bits alone decide the second leg. With both bits clear, a message for another row stops on the sender's own row, at the right column, and that PE's core receives it. With the wrong bit, the message heads away from its row and never arrives.

Order. Each color has a first-in, first-out buffer in every router. All messages from one source to one bucket take the same path, so they arrive in the order sent, and each source's end message arrives after its data. Messages from the two sources reach a bucket in no fixed order.

A message moves as a unit. Once a header leaves, the path it takes stays reserved for that message until its last wavelet passes. A PE that sends a header must send the whole message, or the path stays locked against every other message.

Full wavelets only. The routers mark the end of a message with the wavelet's control bit, which they set from the length field. A message-passing color must carry only full 32-bit wavelets: the hardware does not define what a 16-bit half-wavelet does there. That is why every send above is a u32. On these colors the usual control-wavelet functions are off: no teardown, and no switching.

The cost. A message-passing bank takes five of the 24 colors, on every PE of the region. Colors 16 and 17 of message-passing bank 0, and 20 and 21 of message-passing bank 1, are among the 16 colors that can switch, so a message-passing bank also takes two of the colors that switch routes (lesson 10). This program uses six colors: the message-passing bank and gather. Each source and each bucket uses one input queue.

The core pays too. src.w reads lesson 3's timestamp counter into t[0] before its first send and into t[1] after its last, and cycles.py prints the difference. Each source sends N data messages and 8 end messages:

Row	Messages per source	Cycles to send them	Per message
tutorial	16	503	31
n40	48	1495	31

Most of each message's cycles go to building its header.

Run it

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

cd tutorial/ext-routing/message-passing
make TEST=tutorial

Success is one line per row with PASS, for example message-passing : 0:03.40 PASS tutorial [ N=8 SEED=0 X0=0 Y0=0 CYCLES=2000 ARCH=sdr ]. make TEST='*' runs all three rows. test-tutorial/make-log ends with the lines of cycles.py, such as src[0] sent its messages in 503 cycles. make deletes the simulator's memory image when a row finishes, so to see the counts, rebuild it as lesson 4 does:

cd test-tutorial
make -f ../Makefile VPATH=.. TEST=tutorial bench.map bench-sim.core
miget image=bench-sim.core map=bench.map symbol=bucket.count order="y x n" decimal
cd ..

A failure prints FAIL, and test-tutorial/make-log shows which cmp failed. If the sums and counts are all 0, the buckets were still waiting for end messages when the run stopped at its cycle limit: a message went astray. Run make clean after each edit.

Pitfalls

• mp[] <- header(...) is not a send of the header. A function call on the right of a send to a socket sends a message that calls a handler of that name on the receiving PE (lesson 7). No handler is named header, so the build fails with RPC function declaration for [header] not found in scope. Store the result first, as hdr.u = header(...) does.
• The north and south bits are not hints. Leave them clear for a message to another row, and it is delivered to the wrong PE without an error. Set the wrong one, and the run hangs.
• Every PE on the path needs mp(). Nothing reports a PE that lacks it. Leave mp() off column 2 of this layout, and no message gets past that column: the sources stall and the run hangs.
• Only 32-bit sends on a message-passing color. Send each 16-bit value inside a u32, as msg.u does.
• At most 31 data wavelets per message when the length is in the header. Send a longer payload as several messages.
• Dimension names are positional. In rect(x y w h 'a 'b) the first name is the x dimension. rect(X0 Y0 1 2 'y) names the one-wide x dimension y: bench.map then lists src.key [ y<2 y<1 n<8 ], and miset ... order="y x n" stops with order: 'x' is not a name or number. Name both.
• A fixed receive count only works for fixed data. A bucket that waits for a set number of messages hangs, or stops early, when the keys change. Use end messages, or send the count first.

Exercises

1. Clear both direction bits in header() (delete the two if lines), run the tutorial row and read src.sums and bucket.count. Predict first which bucket each misrouted value reaches. With the pairs above, the row 0 buckets count 2 values each and the sums that reach src[0] are 13, 9, 14 and 16. Explain why every bucket still finishes.
2. Send fewer headers. For each bucket, let the source copy the values with that key into an array buf, then send them as one message: a header with the number of values as its length, then the values, one u32 each. Skip a bucket with no values, and keep the end messages. bucket.w needs no change: it already reads len words per message. In all three rows, no source has more than 31 values for one bucket. Raise CYCLES in test.rc first, to three times its value: with this change cycles.py printed 1784 cycles instead of 503 for the tutorial row. Explain where the time goes.

Next

Topic — Variable-length exchanges and teardown exchanges messages whose length is known only at run time.

References

• Message passing in Tungsten and the header format
• Union declarations
• Raw wavelet send and receive through a union
• Hardware register access (address())
• Functions as remote-call targets
• Imports
• Message passing in Paint: bank, mp