Topic — Switch protocols: remote advance, pop, rings, self-restoring barriers

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

Lesson 10 drains a row into one PE with local flips and ends each round with a reset from the far end. This topic moves switches with control wavelets instead. A control wavelet moves the switch of the PE that sends it and then the next PE's, a route can remove the command it has just carried out, and a switch can wrap from its last position to its first. With these you can write a protocol that leaves every switch where it started, so the same color serves round after round.

What you will be able to do

• Decode a control word, and write one that gives successive routers different commands.
• Advance one switch at a time with pop=adv, and return a switch to its first position with ring instead of a reset.
• Tell when a flip is not allowed, and move the switch with a control wavelet instead.
• Write a protocol as a table of switch positions, and check that it restores itself by running it several times.

The program

A row of P PEs computes a sum-allreduce on one color: in each of R rounds, PE x contributes the value 100·(r+1) + x, and every PE ends the round holding the sum of the row's values. The layout holds the same job twice, with two protocols, one per row:

             x = 0           x = 1 … P-2        x = P-1
  y = 1   gather_root ◄── gather_members ◄── gather_tail     color b
  y = 0   chain_root  ◄── chain_members  ◄── chain_tail      color a
                      ──────────────────────►  the sum, multicast back

• chain (row y = 0, color a): a partial sum starts at the tail and moves left one PE at a time, and each PE adds its own value before passing it on. The root adds its value, multicasts the total back along the row, and a ring returns every switch to its first position.
• gather (row y = 1, color b): every value travels to the root unchanged, the farthest one first. The root adds them, multicasts the total, and sends a reset.

With P=4 R=2 every PE of both rows ends with [406, 806]: 100 + 101 + 102 + 103 in round 0, and 200 + 201 + 202 + 203 in round 1. The gather root also records what it received, in arrival order: [103, 102, 101] in round 0 and [203, 202, 201] in round 1.

The code

Each PE's value

Every kernel computes its value from the Column ID register, which Paint writes on every PE it lays out:

xp col[1] address(0x7C46);

col[0] is the PE's x. See Hardware Register Access in the Tungsten reference.

Three control words

A control word holds eight 3-bit commands. A router acts on command 0, in bits 24:22. Each command's bits 1:0 are an opcode (00 NOP, 01 switch advance, 10 switch reset) and its bit 2 is the CE filter: a wavelet whose command 0 has the filter set is never delivered to a core. The Control Wavelets section of the Tungsten reference gives the bit positions of the other commands.

The program uses three words:

Word	Upper half	Command 0	Command 1	Commands 2-7
ADV = 0x09409249	0x0940	101: advance, filtered	100: NOP, filtered	100
ADV2 = 0x0B409249	0x0B40	101: advance, filtered	101: advance, filtered	100
RST = 0x09809249	0x0980	110: reset, filtered	100: NOP, filtered	100

The lower half, 0x9249, sets commands 3 to 7 to filtered NOPs and holds bit 2 of command 2. The upper half sets commands 0 and 1 in bits 27:22; bits 29:28 are the low bits of command 2, here 00.

Lesson 10's reset, 0x01800000, filters command 0 only. This topic sets the filter on every command, because a route that pops moves command 1 into command 0, and the wavelet must stay out of every core it then reaches.

Protocol 1: chain, restored by ring

The routes:

chain_root : paint(a [R>C ; C>R ; ring])
chain_members : paint(a [R>C ; C>L ; L>CR ; ring])
chain_tail : paint(a [C>L ; L>C ; ring])

The member's kernel, chain_member.w:

xp param R;
socket red;
xp col[1] address(0x7C46);
sp s[n=R];
u32 ADV = 0x09409249;
{
    ∀r in [0, R) {
        sp t = red[];
        red[] <- t + (sp)(100 * (r + 1) + col[0]);
        red[] <- control(ADV);
        s[r] <- red[];
    }
}

The tail, chain_tail.w, sends its value without receiving first. The root, chain_root.w, receives the partial sum, adds its value, and sends the total and then an ADV:

        sp t = red[];
        s[r] <- t + (sp)(100 * (r + 1) + col[0]);
        red[] <- s[r];
        red[] <- control(ADV);

One round, step by step:

Step	What happens	Switches after it
1	The tail sends its value from position 0 (C>L), then ADV. The ADV first reaches the tail's own router, which advances to L>C. It then leaves to the left.	tail at 1
2	Member P-2, at R>C, delivers the value to its core. The ADV behind it advances the member to C>L, leaves towards the core, and is dropped there, because it is filtered.	member P-2 at 1
3	The member's core adds its value and sends the sum from C>L, then its own ADV. The ADV advances the member's own switch to L>CR, then leaves to the left and advances the next member.	member P-2 at 2
4	Steps 2 and 3 repeat down the row. The ADV from member 1 advances the root to C>R.	root at 1, members at 2
5	The root sends the total from C>R. Each member, at L>CR, delivers it to its core and passes it on; the tail, at L>C, keeps it.
6	The root sends ADV. Its own switch is in its last position, so ring wraps it to position 0. The ADV then wraps each member and finally the tail.	all at 0

An ADV in this protocol moves two switches: the sender's own and its left neighbour's. It travels no further, because at the neighbour it leaves towards the core and the filter drops it. Only the root's ADV travels the whole row, because every member's position 2 also sends to the right.

Protocol 2: gather, with pop=adv, restored by a reset

In the gather, a member passes the values from its right without touching them. It cannot learn from its core when its turn comes, so the switches decide: a member injects its own value only after the value from its right has passed.

The routes:

gather_root : paint(b [R>C ; C>R])
gather_members : paint(b [R>L ; C>L ; L>CR ; pop=adv])
gather_tail : paint(b [C>L ; L>C ; pop=adv])

The members and the tail run the same kernel, gather_member.w:

xp param R;
socket red;
xp col[1] address(0x7C46);
sp s[n=R];
u32 ADV2 = 0x0B409249;
{
    ∀r in [0, R) {
        red[] <- (sp)(100 * (r + 1) + col[0]);
        red[] <- control(ADV2);
        s[r] <- red[];
    }
}

The root, gather_root.w, receives P-1 values, adds them to its own, and sends the total and then a reset:

        ∀j got[r][j] <- red[];
        sp t = (sp)(100 * (r + 1) + col[0]);
        ∀j t <- t + got[r][j];
        s[r] <- t;
        red[] <- t;
        red[] <- control(RST);

pop=adv makes a router remove command 0 from a control wavelet when that command advanced its switch. The router shifts commands 1 to 7 down one place and sends the wavelet on, so the next router acts on what was command 1. One round:

Step	What happens	Switches after it
1	Every member starts at R>L, passing through. The tail sends its value; it passes every member and reaches the root.
2	The tail sends ADV2. Its own router advances to L>C and pops; the remaining ADV advances member P-2 to C>L, which pops it too. What is left is a filtered NOP, which passes the other members and is dropped at the root.	tail at 1, member P-2 at 1
3	Member P-2's value leaves from C>L and passes the members to its left. Its ADV2 advances its own switch to L>CR, pops, and the next member advances to C>L and pops.	member P-2 at 2, the next member at 1
4	Step 3 repeats down the row. Member 1's last ADV advances the root to C>R.	root at 1, members at 2
5	The root sends the total, which every member delivers and passes on.
6	The root sends RST. Its own switch returns to R>C; each member returns to R>L and the tail to C>L. A reset is not an advance, so pop=adv does not remove it.	all at 0

The values arrive farthest first, which gather_root.got shows. A member that reaches the allreduce late does not hold up the values from its right: they pass through its router while its core is still busy.

Why neither protocol can use flip

The hardware allows a local flip only on a switch whose positions all have the same outputs. A flip moves only the input switch, and the output switch keeps the outputs of the position it was in. The members' switches here do not have the same outputs in every position: a chain member's positions send to C, L, and C with R; a gather member's to L, L, and C with R. So only control wavelets may move them. Control wavelets move the input switch when they arrive and the output switch when they leave, which keeps the two in step.

The same rule holds on a grid. Consider a grid allreduce whose PEs route [L>CR ; C>L* ; R>L], start in C>L, and move to R>L with flip red[]. Position 0 sends to C and R, and the other positions send to L. The hardware does not support that flip, even though it moves between two positions that both send to L: a flip needs the same outputs in every position. Such a program passes in the simulator, which does not report the flip, but a passing run does not make the form legal. The chain protocol above does a row's share of that job with control wavelets only.

Two more topics move switches with control wavelets only. A route through every PE sends one color through every PE of a rectangle and back to its sender, whose rule, [C>U ; R>C ; ring], alternates between sending and receiving, one ADV per value. A barrier and a broadcast from switch positions starts each worker's switch in a closed position, C>C, that accepts nothing from its neighbours. The worker opens it with an ADV that its own router acts on, so the probe, a data wavelet, can complete its return only after every worker has reached the barrier.

What the hardware does

Lesson 10 showed that a router keeps an input switch and an output switch for each switching color, and that a control wavelet leaves by the outputs of the old position. Three more rules make these protocols work:

• The sender's own router acts first. A control wavelet from a core enters its own router before any other, and that router carries out command 0 like any other. In both protocols here, the own-router advance is part of the design.
• Advance, ring and reset. An advance moves the switch to the next position unless the switch is in position 3 or the next position is not configured. Then a switch with ring returns to position 0, and one without ring stays where it is. A reset always returns the switch to position 0, the first position listed. A * after a position, as in C>C*, only makes the switch start there.
• Pop. A route's pop setting removes command 0 from a control wavelet as it leaves the router, and shifts commands 1 to 7 down one place; the freed command 7 becomes a filtered NOP. pop=all pops every control wavelet, pop=adv one whose command 0 is an advance, and pop=advnop an advance or a NOP. Without ring, pop=adv and pop=advnop pop only if the switch was not already in its last position when the wavelet arrived: the tail's ADV2 in the gather moves the tail into its last position and is still popped. With ring, pop=adv pops every advance, and pop=advnop every advance or NOP.

A flip, in contrast, is allowed only if every position has the same outputs, and only on a route without pop=adv or pop=advnop. Nothing in Paint or Carbide checks these rules.

The Paint reference's Switch Positions section lists the modifiers.

Cost. In the gather, values cross the routers without stopping. In the chain, each member's core must receive, add and send before the partial sum moves on. The table gives the cycle of each protocol's last memory write when the protocol runs alone, with R = 3. The test does not print this figure.

P	chain	gather
4	294	210
8	570	330
16	1122	570

Both grow linearly with P; each PE the gather adds costs it less than half what one costs the chain.

Run it

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

cd tutorial/ext-collectives/switch-protocols
make TEST=tutorial

Success is a line ending in PASS tutorial [ P=4 R=2 ARCH=sdr ]. The end of test-tutorial/make-log shows what check.py read back:

chain: the sum each PE holds, one row per PE, one column per round
[[406. 806.]
 [406. 806.]
 [406. 806.]
 [406. 806.]]
gather: the sum each PE holds, one row per PE, one column per round
[[406. 806.]
 [406. 806.]
 [406. 806.]
 [406. 806.]]
gather: the values the root received, one row per round
[[103. 102. 101.]
 [203. 202. 201.]]
PASS

make TEST='*' runs every row of test.rc: P from 3 to 16 and R from 1 to 3. A row with R above 1 passes only if every switch ends each round where it started. If a protocol leaves a switch out of place, the next round stalls: the simulation stops at its cycle limit (cycles=4000 in the Makefile), the sums of the later rounds stay 0, and check.py prints FAIL. Run make clean before running a row again after an edit; make reuses an existing test-<row>/ directory.

Pitfalls

• Without pop=adv the gather stalls. Remove pop=adv from the members' and the tail's rules, and the tail's ADV2 advances every member and the root at once. The root then takes input only from its core and never receives a member's value. With P=4 R=2 the root received the tail's 103 and nothing else.
• ring and pop=adv together pop every advance. If the gather ends its round with an ADV and ring instead of RST, member 1 wraps and pops the ADV, and no other switch moves. With P=4 R=2 round 0 completed, and the root received nothing in round 1.
• An advance moves its sender's switch. A control wavelet whose command 0 is an advance acts first on its sender's own router. If that router's switch has a next position, the advance moves it before the wavelet reaches a neighbour. The protocols here rely on that; a design that does not plan for it moves one switch too many. A reset sent by a PE returns that PE's own switch to position 0 in the same way, and a NOP changes nothing.
• Filter every command. A word whose later commands lack the CE filter becomes deliverable once a pop moves one of them into command 0. The core then receives it as a wavelet of the stream.
• P must be at least 3. With P=2 the members' rectangle is empty, and the Makefile fails when it reads the members' results.

Exercises

1. Restore the chain with a reset instead of ring. Remove ring from the three chain rules. In chain_root.w, replace u32 ADV = 0x09409249; with u32 RST = 0x09809249;, and replace red[] <- control(ADV); with red[] <- control(RST);. Predict whether every row still passes, then run make TEST='*'. Then explain why the gather could not do the reverse.
2. Write the chain's switch table for P=3: for the root, the one member and the tail, the position after each control wavelet of one round. Check that every switch ends in position 0, and mark which wavelet moved it there.

Next

Topic — A barrier and a broadcast from switch positions moves the switches of a whole grid with control wavelets, so that one probe can complete its lap only when every worker has reached the barrier.

References

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