Lesson 10 — Switches: PEs that take turns on one color

Lesson 9 collected one total. Often each PE of a row has its own results, and one PE must receive them all. One color per sender would use up the colors quickly, and a route can take its input from only one port at a time. A switch solves this: a route can have several positions, each with its own input, and the routers move between positions while the program runs. In this lesson K producers send their values to one receiver, all on one color, one producer at a time: a serial drain.

What you will be able to do

• Write a route with switch positions, and say what moves it from one position to the next and what returns it to the first.
• Use flip to hand a shared color to the next PE once a PE has sent its data.
• Read a control wavelet's 32 bits field by field, and use a reset to start a new round.
• Avoid the rules that Paint and Carbide do not check: the same outputs in every position, at most four positions, and a flip only after a send from an array.

The program

A receiver sits at x=0. Producers sit at x=1 to K-1, and the farthest producer at x=K. In each of R rounds, every producer sends N values, 100 × id + 10 × round + i, where id is its x position. The receiver must get them nearest producer first, in every round:

  x=0         x=1            x=2                     x=K
+------+    +----------+   +----------+           +----------+
| rcv  |<---| producer |<--| producer |<-- ... <--| farthest |
|[R>C] |    |[C>L;R>L] |   |[C>L;R>L] |           | [C>L]    |
+------+    +----------+   +----------+           +----------+
                 all on one color c

For the tutorial row (K=3, N=2, R=2) the receiver must get:

100 101 200 201 300 301   110 111 210 211 310 311

ref.py writes this order, and cmp compares it with what the receiver stored. The other rows are k2 (K=2, N=2, R=2: one producer besides the farthest) and k5 (K=5, N=4, R=3).

Switch positions

A rule with a ; has switch positions:

producers : paint(c [C>L ; R>L])

The router is in one position at a time and starts in the first, position 0. Here position 0, C>L, takes the producer's own data from its core and sends it left. Position 1, R>L, takes the data of the producers to its right and passes it left. A route can have up to four positions, and each position has its own input and outputs. Only 16 of the 24 colors can switch; Paint gives a rule with positions one of those colors.

Two kinds of event move a switch:

• An advance moves it to the next position. Without ring (a modifier for the switch-protocols topic), a switch in its last position stays there.
• A reset returns it to position 0.

Both come from control wavelets, and an advance can also come from a flip.

The code

The producers: producer.w

{
    let i in [0, N);
    ∀r in [0, R) {
        ∀i a[i] <- 100 * id[0] + 10 * r + i;
        ∀i tx[] <- a[i];
        flip tx[];
    }
}

flip tx[]; marks the send just before it: the last word of that send carries a flip, and when the router takes that word from the core, the router's switch advances. The flip costs no extra wavelet, and it moves only this PE's own switch. Here it moves the producer from C>L to R>L: having sent its own data, the producer passes on everyone else's.

Each PE's id comes from miset order="x n", as in lesson 8.

The farthest producer: last.w

u32 RST = 0x01800000;

{
    let i in [0, N);
    ∀r in [0, R) {
        ∀i a[i] <- 100 * id[0] + 10 * r + i;
        ∀i tx[] <- a[i];
        tx[] <- control(RST);
    }
}

The farthest producer has nobody to its right, so its route has one position, [C>L], and it does not flip. After its data it sends control(RST), a control wavelet: a wavelet with its control bit set, whose 32 bits the routers read as commands. RST resets every switch it passes on the way to the receiver.

The layout

let c = color()

let rcv = tile(0 0)
rcv : code('recv [rx:c TOTAL:K*N*R])
rcv : paint(c [R>C])
rcv : name('rcv)

let producers = rect(1 0 K-1 1 'x)
producers : code('producer [tx:c N:N R:R])
producers : paint(c [C>L ; R>L])
producers : name('producers)

let farthest = tile(K 0)
farthest : code('last [tx:c N:N R:R])
farthest : paint(c [C>L])
farthest : name('farthest)

union(rcv producers farthest)

All K + 1 PEs route the one color c. tile(x y) is a single PE at (x, y). The producers between the receiver and the farthest PE share one rectangle, one kernel and one two-position rule. 'x keeps the rectangle's dimension in the map even with a single producer, as lesson 9 explains; the k2 row checks that.

The receiver: recv.w

{
    let k in [0, TOTAL);
    ∀k got[k] <- rx[];
}

It counts TOTAL = K × N × R values and needs to know nothing about the switches.

What the hardware does

One round

1. Every producer starts in position 0 and sends. Producer 1's data reaches the receiver. Producer 1's router takes no input from the right yet, so producer 2's data waits in the buffers on the way, and with enough data producer 2's sends block (lesson 6). The same holds further right.
2. Producer 1's last word carries the flip. Its switch moves to R>L, and producer 2's data flows through.
3. Producer 2 flips after its last word, and producer 3's data flows through producers 2 and 1. So it goes, to the farthest producer.
4. The farthest producer sends its data and then RST. RST follows the data to the left. Each producer's router resets to C>L as RST arrives, so the next round starts the same way. At the receiver, RST changes nothing, because its route has one position, and its core never sees it (below).

Each producer may already be computing its next round: its sends wait until the reset gives its core the route again.

Input and output switches

A router keeps two switch positions per color: one for the input and one for the outputs. A control wavelet moves the input switch as soon as it arrives, and the output switch after it has left, so it leaves by the old outputs. A flip moves only the input switch: it is a side signal from the core, and the output switch never sees it. After a flip, the two switches stand in different positions. That split gives the first rule below, and the hardware adds the second:

• Every position must have the same outputs. [C>L ; R>L] sends left in both positions, so it does not matter which output position the router is in. [C>L ; R>CL] would break the rule.
• Only a data wavelet, or a control wavelet whose command 0 is a NOP, may carry a flip.

Neither Paint nor Carbide checks either rule: Paint accepts [C>L ; R>CL] without a message, and Carbide compiles a flip after tx[] <- control(RST);.

An advance in a control wavelet moves the switch of every router that receives it on that color. That includes the sending PE's own router, which receives it from the core. The exercise uses this.

The control word

A control wavelet holds eight 3-bit commands and a task ID. Each router acts on command 0. RST = 0x01800000:

Bits	Field	0x01800000
31:30	not used by the switches	00
29:28	command 2, bits 1:0	00
27:25	command 1	000: NOP
24:22	command 0	110: CE filter, reset
21:16	task ID, for a core that receives the wavelet	0
15:13, 12:10, 9:7, 6:4, 3:1	commands 7, 6, 5, 4, 3	000: NOP
0	command 2, bit 2	0

In each command, bit 2 is the CE filter: a router does not deliver the wavelet to its core. Bits 1:0 are the opcode: 00 NOP, 01 advance, 10 reset, 11 teardown. A teardown shuts a color down until the program reopens it; no main lesson uses it (see the topic Variable-length exchanges and teardown). So command 0 of RST is a reset that no core receives: the receiver counts only data. The other commands matter only on a route that pops command 0 and moves the next one into its place, which no route here does; the topic Switch protocols: remote advance, pop, rings, self-restoring barriers uses them.

Run it

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

cd tutorial/main-3-rows/10-switches
make TEST=tutorial

Success is a line ending in PASS tutorial [ K=3 N=2 R=2 ARCH=sdr ]. make deletes the simulated memory image when the row finishes, so to see the order the receiver got, rebuild it as lesson 4 shows:

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

A wrong order makes cmp print out-ref.bin out-sim.bin differ. A run that stalls shows up the same way: the simulation stops at its cycle limit with part of got still 0. make TEST='*' runs all three rows.

Pitfalls

Each of these compiles without a message. The results are from runs and from the route registers Paint wrote.

• A flip after values computed in the send. ∀i tx[] <- 100 * id[0] + 10 * r + i; flip tx[]; sends the values one at a time, and every one of those sends carries the flip. The switch flips after the first value. With K=3, N=3, R=2 the receiver got 100 200 300 301 302 101 201 310 311 312 102 202, and the run stalled. Fill an array first and send from it, as producer.w does. The listing, test-tutorial/producer_artefacts/producer2.yeti, then shows one send DSD of length N that carries the flip, .fs=1; the trap version has a send DSD of length 1 with .fs=1.
• A flip before the farthest PE's reset. If the farthest producer also had [C>L ; R>L] and flipped before sending RST, its switch would take input only from the right, and RST could not leave its core. The receiver got round 0 and then nothing.
• No reset. Without RST, every producer stays in R>L after round 0. Only the farthest producer's data still gets through: the receiver got 100 101 200 201 300 301 310 311, and the run stalled.
• A fifth position. Paint accepts more than four positions, and the extra one changes position 0. With [C>L ; R>L ; R>L ; R>L ; U>D], position 0 sends right (R) instead of left (L), away from the receiver.
• Positions in the wrong order. [R>L ; C>L] starts by passing data from the right. A producer's own sends wait for an advance, but its flip rides on its own last send, so nothing moves it. The receiver got only the farthest producer's values, 300 301 310 311, and the run stalled.

Exercise

Replace flip tx[]; in producer.w with tx[] <- control(ADV);, and declare u32 ADV = 0x09409249;, a control wavelet whose command 0 is an advance with the CE filter. Predict the order the receiver gets, using the rule that an advance moves the sending PE's own switch too, and the routers it reaches after that. Then run make clean and make TEST='*'.

Next

Lesson 11 — A grid of blocks: halo exchange and what it costs leaves the row: a 2-D grid of PEs, each holding a block of a field and exchanging its edges with four neighbours.

References

• Switch positions in the Paint reference
• flip and control wavelets in the Tungsten reference
• Switch positions in the architecture notes