Lesson 4 — Sockets, wavelets, colors and routes

Lessons 1 to 3 ran on one PE. A PE cannot read another PE's memory: PEs cooperate only by sending data to each other through the routers. This lesson sends a stream of numbers through four PEs. One PE makes the numbers, one squares them, and two receive the squares.

What you will be able to do

• Send and receive values between PEs with sockets, and bind each socket to a color in Paint.
• Write the route of a color on each PE, and trace a route from its sender to every receiver.
• Deliver one stream to two PEs with one color (multicast).
• Say how values travel as wavelets, and what a color shares with the other colors.

The program

send computes a[i] = 3*i - 5 and sends the values. compute receives all of them, then sends their squares. recv0 and recv1 each receive every square.

          rxcolor               txcolor               txcolor
 +------+          +---------+          +-------+          +-------+
 | send | -------> | compute | -------> | recv0 | -------> | recv1 |
 +------+          +---------+          +-------+          +-------+
  [C>R]          rxcolor [L>C]           [L>CR]              [L>C]
                 txcolor [C>R]
   x=0               x=1                   x=2                x=3

With N=4, send sends -5, -2, 1, 4, and both receivers end with a = {25, 4, 1, 16}. The second test row uses N=10.

The code

Sockets

send.w:

xp param N;

socket tx;
xp a[n=N];

let i in [0, N);
∀i a[i] <- 3 * i - 5;
∀i tx[] <- a[i];

A socket is a kernel's end of a stream between PEs. socket tx; declares one without a type. The kernel's use decides the direction: tx[] <- a[i] sends a[i] on tx, and a[i] <- rx[] receives one value from rx. Paint decides which color a socket uses.

compute.w:

xp param N;

socket rx;
socket tx;

xp a[n=N];

let i in [0, N);
∀i a[i] <- rx[];
∀i tx[] <- a[i] * a[i];

The statements run in order, so compute receives all N values into a before it sends the first square. A receive waits until a value arrives. A send waits when there is no room for the value; lesson 6 shows how much room there is.

recv.w:

xp param N;

socket rx;
xp a[n=N];

let i in [0, N);
∀i a[i] <- rx[];

Both receivers run recv.w. Each PE holds its own copy of the program and of a in its own memory. name('recv0) and name('recv1) give the two copies of a the symbols recv0.a and recv1.a.

Colors and routes: bench.paint

let rxcolor = color()
let txcolor = color()

let send = tile()
send : code('send [tx:rxcolor N:N])
send : paint(rxcolor [C>R])
send : name('send)

let compute = tile()
compute : code('compute [rx:rxcolor tx:txcolor N:N])
compute : paint(rxcolor [L>C])
compute : paint(txcolor [C>R])
compute : name('compute)

let recv0 = tile()
recv0 : code('recv [rx:txcolor N:N])
recv0 : paint(txcolor [L>CR])
recv0 : name('recv0)

let recv1 = tile()
recv1 : code('recv [rx:txcolor N:N])
recv1 : paint(txcolor [L>C])
recv1 : name('recv1)

hstack(send compute recv0 recv1)

Statement	Meaning
let rxcolor = color()	Make a symbolic color. Paint picks its number.
code('send [tx:rxcolor N:N])	Run send.w on this PE, bind its socket tx to rxcolor, and set its N.
paint(rxcolor [C>R])	On this PE's router, rxcolor takes its input from the PE itself (C) and sends it right (R).
paint(txcolor [L>CR])	txcolor comes in from the left and goes both to this PE and on to the right.
hstack(send compute recv0 recv1)	Put the four PEs in a row, at x = 0, 1, 2 and 3.

Every socket a kernel declares must be bound in its code(). An unbound socket fails the build with socket [rx] is not initialized.

A route rule [IN>OUTS] names one input and any set of outputs:

Letter	Meaning
C	the PE itself: as input, what the PE sends; as output, delivery to the PE
L, R	the neighbour at x-1, at x+1
D, U	the neighbour at y-1, at y+1

The rules this lesson uses, and one more:

Rule	Meaning
[C>R]	send this PE's values right
[L>C]	deliver values from the left to this PE
[L>CR]	deliver values from the left here, and pass them on to the right
[L>R]	pass values from the left on to the right; the PE never sees them

Reading a route

Check a layout one color at a time. Start at the PE that sends on the color, and follow it to every PE that should receive it:

• rxcolor enters at send ([C>R]), goes right, and ends at compute ([L>C]).
• txcolor enters at compute ([C>R]), goes right to recv0, which takes a copy and passes it on ([L>CR]), and ends at recv1 ([L>C]).

Then check the contract at both ends:

1. The sender's socket and the receiver's socket are bound to the same color.
2. Each step of the route goes to the PE that hstack put next to it.
3. Every receiver expects the type the sender sends.
4. Every receiver receives exactly as many values as the sender sends.

A route that is right but has wrong counts still hangs: a receiver that waits for an eleventh value waits forever.

What the hardware does

The path of a value

A PE has three parts: the core, which the hardware calls the CE and Paint calls C; its memory; and a router. The router has five ports: north, south, east, west, and the CE. The routers and the links between neighbouring routers form the fabric. The CE reaches other PEs only through its router, and the router passes data on without the CE's help.

A value that compute sends goes into one of the CE's output queues, then into the router, across one link to the next router, and so on along its route. At a PE whose route includes C, the router puts it into one of that CE's input queues, and a receive takes it from there. The architecture notes give the queue sizes (The CE's Queues).

Lesson 3 showed that one instruction can process a whole array through a vector operand, a DSD. A socket is a vector operand too. In the listing of compute.w (in test-tutorial/compute_artefacts/), the multiply writes its products straight to the output queue:

	imov16 [T22] = [T12];  //@../compute.w:9
	imul16 [T23] = [T01], [T13];  //@../compute.w:10

The first instruction is the receive loop; T12 describes the input queue. The second is the square-and-send loop; T23 describes the output queue.

Wavelets

The fabric moves data in wavelets: 32 bits of data, the wavelet's color, and a control bit. Lesson 7 uses the control bit.

An xp or hp value is 16 bits. Two 16-bit values share a wavelet when the output queue can pack them. A lone value can leave as a half-wavelet, which carries 16 bits. An sp or u32 value fills a wavelet.

Nothing checks that the receiver reads the type the sender sent. A cast on a receive chooses how the incoming bits are read; it does not convert the value. A sender sent the xp values 3, 15360 and 3, and the receiver ran:

h[0] <- (hp)rx[];
h[1] <- (hp)rx[];
xp n <- rx[];
h[2] <- (hp)n;

h[0] holds the bit pattern 0x0003, a tiny hp number of about 1.8e-7. h[1] is 1.0, because 15360 is 0x3C00, the bits of hp 1.0. Only h[2] is 3.0: read the value with the type it was sent with, then cast.

Colors

A color is a virtual channel through the routers. A router has 24 colors.

• Each color has its own buffer of 4 wavelets in every router, so a color that is stuck does not stop the others.
• All colors share the links. Each port moves one wavelet per cycle in each direction, and colors that wait for the same port take turns. A stream split over two colors on one link is not faster.
• On each router, a color takes its input from one port at a time. It can send to any set of ports.

The last rule is why compute needs two colors. On compute's router, rxcolor takes its input from the left. The squares come from C, so they need a color whose input on that router is C.

Multicast

recv0's router copies each wavelet of txcolor to its CE and to the right. recv0's program never touches recv1's copy.

A color serves the wavelet at the head of its buffer, and that wavelet waits until every output of its route has taken it. So a multicast moves at the speed of its slowest receiver. When one receiver stops reading, the others stop too, once the buffers in front of it are full. Exercise 2 shows it.

Coordinates

Paint gives each PE an x and a y. x is the column, and R leads to x+1. y is the row, and U leads to y+1.

     y
     ^
   2 |  (0,2)  (1,2)  (2,2)        U: toward y+1
   1 |  (0,1)  (1,1)  (2,1)        D: toward y-1
   0 |  (0,0)  (1,0)  (2,0)
     +------------------------> x
          0      1      2

The hardware numbers rows from the north edge of the wafer: row 0 is the northernmost row. Paint's y is that row number, so U leads south and D leads north. The main sequence's figures draw y growing upward, so that U points up on the page; the architecture notes draw the same grid with row 0 at the top (The Fabric). No program in the main sequence depends on compass directions.

The color budget

A router has 24 colors, and 16 of them can switch routes while the program runs (lesson 10). Two features in the extension topics take colors. Message passing takes 5 colors for each message-passing bank, the block of colors that Paint's bank() reserves, and a program can use two banks. The fabric adder works only on color 10.

This layout uses a new color for every stage, so a chain of K compute stages would need K+1 colors. Lesson 8 runs a whole row with two.

A CE also has only 8 input queues and 8 output queues, one color each, so a kernel receives on at most 8 colors and sends on at most 8.

Run it

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

cd tutorial/main-2-between-pes/04-sockets-and-routes
make TEST=tutorial

ref.py writes the squares twice, once for each receiver. The Makefile reads recv0.a and recv1.a from the simulated PEs' memory and compares the two files with cmp. A pass prints a line ending in PASS tutorial [ N=4 ARCH=sdr ]. make TEST='*' runs both rows.

To read a result yourself, make the core file again in the row's directory. make deletes bench-sim.core, the simulated memory, and bench.map, the table of where each symbol lives, when a row finishes, because it treats both files as intermediate steps:

cd test-tutorial
make -f ../Makefile VPATH=.. TEST=tutorial bench.map bench-sim.core
miget image=bench-sim.core map=bench.map symbol=recv1.a decimal
cd ..

The second line makes both files again and keeps them. miget prints 25 4 1 16. decimal prints each word as an unsigned number, so send.a's -5 would print as 65531; hp in place of decimal prints half-precision values.

When data does not arrive, nothing reports an error. The receiver waits, the simulator stops at the cycle cap (SIMFLAGS=cycles=2000 in the Makefile), and the test compares what is in memory then. The line ends in FAIL, and test-tutorial/make-log ends with the cmp report. With [L>C] in place of [L>CR] on recv0, recv1 receives nothing, and cmp reports:

out-ref.bin out-sim.bin differ: byte 9, line 1

Byte 9 is the first byte of recv1's values: recv0's four values take the first 8 bytes.

After you edit a file, run make clean before make (lesson 1).

Pitfalls

• One color for a receive and a send on the same PE. Binding compute's rx and tx to one color, with both rules on it, builds without a warning. Paint keeps the first paint() of a color on a region and ignores the second, also without a warning. compute receives its values, but its sends go nowhere and the receivers get nothing.
• Counts that differ. A receiver that expects more values than the sender sends waits forever. Fewer is not reported either: the extra values wait in the queues, and a sender with many extra values waits for room.
• Casts on receives. (hp)rx[] reads the bits as hp; it does not convert an xp to hp.
• A missing C or a missing direction. [L>R] on a receiver starves its own program. [L>C] on a PE that should pass values on starves every PE after it.
• Relaying straight from a receive. Keep a stage's receive and its send in separate loops, as compute.w does. A relay written as ∀i tx[] <- rx[]; loses its last value when it relays an odd number of 16-bit values.

Exercises

1. Add a second compute stage between compute and recv0 that adds 1 to each value. Write its kernel, give it a new color, change the routes and ref.py, and run both rows.
2. See the slowest receiver set the pace. Give recv1 its own count: change its code() to code('recv [rx:txcolor N:2]), and add a row hol N=100 ARCH=sdr to test.rc. Predict what recv0.a holds, then run make TEST=hol. The row fails, because the receivers no longer match ref.py. Read recv0.a as in Run it, with test-hol and TEST=hol in place of test-tutorial and TEST=tutorial. recv0 received 38 of the 100 values. Explain why it stopped long before 100: which buffers are full, and why recv0's copy of each wavelet waits for recv1's.

Next

Lesson 5 — One core, many activities: parallel and FIFOs

References

• Sockets
• Type casting
• Paint colors
• Paint routing and direction codes
• Stacking
• Naming regions
• Architecture notes: Wavelets, Colors, Color Limitations