Topic — A barrier and a broadcast from switch positions

Needs: Lesson 10 — Switches: PEs that take turns on one color, Lesson 11 — A grid of blocks: halo exchange and what it costs; topic Switch protocols: remote advance, pop, rings, self-restoring barriers.

A barrier makes every PE of a group wait until all of them have reached the same point of their programs. A broadcast then gives all of them one value. This topic builds both on one color of a grid, with data wavelets, control wavelets and switch positions. Each PE that takes part, a worker, starts with its switch closed to its neighbours and opens it when it reaches the barrier. One PE, the origin, sends a probe, a data wavelet that can finish its lap only through open workers, so the probe's return means that every worker has arrived. The origin then broadcasts whether to run another round, and a reset returns every switch to its first position, which closes the workers again.

What you will be able to do

• Close a PE's route to its neighbours with a position that connects the core only to itself, and open it with an advance that the PE sends to its own router.
• Build a barrier whose release is the return of one probe, and follow it with a broadcast and a reset on the same color.
• End a branch of a multicast with a position that has no output.
• Describe a protocol as a table of each PE's switch positions, and check that every round ends where it started.
• Tell a working barrier from a broken one by the waits the test prints.

The program

A grid of NX × NY PEs runs R rounds. The origin, at (0, 0), runs origin.w, and the workers run worker.w. The layout has two forms:

• INNER=1: only the inner PEs, x from 1 to NX-2 and y from 1 to NY-2, are workers. The other PEs of the border only route. The tutorial row uses this form, with NX=5 NY=4 R=3.
• INNER=0: every PE except the origin is a worker.

In every round:

1. Each worker sends an advance into its own router: it has arrived.
2. The origin sends a probe and then an advance. The probe comes back to the origin only when every worker has arrived.
3. The origin broadcasts the number of rounds still to come, and then a reset.
4. Each worker receives a copy of the probe and then the broadcast. It stops after the round whose broadcast is 0.

The worker at (1, 1) is late: before each arrival, it spins for 1000 cycles.

The probe's paths in the tutorial row, with INNER=1:

          x=0     x=1     x=2     x=3     x=4
  y=3     TL <--- T <---- T <---- T <---- TR
          v       ^       ^       ^       ^
  y=2     L       W       W       W       R
          v       ^       ^       ^       ^
  y=1     L       W       W       W       R
          v       ^       ^       ^       ^
  y=0     O ----> B ----> B ----> B ----> BR

  O  origin    W  worker    B, BR, L, R, TL, T, TR  border PEs, which only route

The probe goes right along row 0 and up every column. In columns 1 to 3 it can pass a worker only once that worker has arrived, and each T ends it. Up column 4 it reaches TR, turns left along the top row, and comes down column 0 to the origin. Each T lets it pass only after its own column's probe, and the advance behind it, have arrived. So the probe gets back only when all the workers have arrived.

The broadcast takes other paths: right along row 0, up every column, and up column 0, and it ends at every PE of the top row.

check.py reads how many rounds each PE completed, and the test passes when every PE that runs a program completed R of them. It also prints how many cycles each worker waited at the barrier in the last round. For the tutorial row every PE must have completed 3 rounds.

The code

The worker: worker.w

xp param DELAY = 1000;
socket ping;
u32 ADV = 0x09409249;
xp col[1] address(0x7C46);
xp row[1] address(0x7C45);
u16 tsc[1] address(0x7b30);
u16 tsc_control[1] address(0x7b34);
xp rounds[n=1] = {0};
u16 waited[n=1];
{
    tsc_control[0] <- tsc_control[0] | 4;
    sp remaining = 1.0;
    while (remaining > 0.0) {
        if (col[0] == 1 && row[0] == 1) {
            u16 s = tsc[0];
            u16 d = 0;
            while (d < DELAY) {
                d <- tsc[0] - s;
            }
        }
        u16 t = tsc[0];
        ping[] <- control(ADV);
        sp probe = ping[];
        remaining <- ping[];
        waited[0] <- tsc[0] - t;
        rounds[0] <- rounds[0] + 1;
    }
}

• col and row are the Column ID and Row ID registers, which Paint writes with each PE's x and y. Only the worker at (1, 1) runs the spin loop, which reads the timestamp counter of lesson 3 until DELAY cycles have passed.
• ping[] <- control(ADV); is the arrival. ADV is the control word of the switch-protocols topic: command 0 is an advance, and every command has the CE filter set. The worker's own router acts on it first and opens the switch. The worker sends nothing else on ping.
• The worker then receives two wavelets: the probe, which it does not use, and the broadcast. It must read the probe: the broadcast arrives behind it.
• waited keeps the cycles from the arrival to the broadcast, in the last round. Both readings come from the worker's own counter.
• The worker does not know R. It learns from each broadcast whether another round follows.
• The spin stands for the work a PE does between barriers. A real kernel computes before ping[] <- control(ADV);, and goes on after it has received the broadcast.

The origin: origin.w

xp param R;
socket ping;
u32 ADV = 0x09409249;
u32 RST = 0x09809249;
xp rounds[n=1] = {0};
{
    ∀r in [0, R) {
        ping[] <- (sp) r;
        ping[] <- control(ADV);
        sp probe = ping[];
        rounds[0] <- r + 1;
        ping[] <- (sp) (R - 1 - r);
        ping[] <- control(RST);
    }
}

The probe is the value r, followed by ADV. sp probe = ping[]; waits for the probe to come back: that receive is the barrier. The broadcast is the number of rounds still to come, R - 1 - r, and RST, the reset of the switch-protocols topic, follows it.

The routes with INNER=1

inner_routes in bench.paint paints one rule for each kind of PE:

PE	Rule	What each position does
origin, (0, 0)	[C>R ; U>C ; C>RU]	0: sends the probe right. 1: takes the probe back from above. 2: sends the broadcast right and up.
row 0	[L>RU]	Passes everything right and up its column.
(NX-1, 0)	[L>U]	Turns up the right column.
column 0	[U>D ; D>U]	0: brings the probe down. 1: takes the broadcast up.
workers	[C>C ; D>CU]	0: closed. 1: gives the core what comes from below, and passes it up.
column NX-1	[D>U]	Passes up.
top left	[R>D ; D>]	0: turns the probe down. 1: ends the broadcast.
top row	[D> ; R>L ; D>]	0: ends its column's probe. 1: passes the probe left. 2: ends the broadcast.
top right	[D>L ; D>]	0: turns the probe left. 1: ends the broadcast.

C>C takes input only from the PE's own core and gives it only to that core. In that position the PE accepts nothing from its neighbours: what they send waits at the router. D> takes what comes from below and sends it nowhere, so a branch of a multicast ends there.

One round, step by step:

Step	What happens	Switches after it
1	Each worker sends ADV. Its own router moves to D>CU, and ADV leaves towards the core, which its filter keeps it out of.	each worker at 1
2	The origin sends the probe from C>R, then ADV. Its own router moves to U>C, and ADV follows the probe right.	origin at 1
3	The probe goes along row 0 and up each column, through workers that have arrived; each worker's core takes a copy. The top-row PE ends it. The ADV behind it passes the workers, which are in their last position and stay there, and moves the top-row PE to R>L.	top row at 1
4	Up the right column the probe reaches the top right, turns left, and passes each top-row PE that step 3 has moved. It turns down at the top left, comes down column 0, and reaches the origin's core. The barrier is released.
5	The ADV behind the probe moves the top right to D>, each top-row PE to D>, the top left to D>, column 0 to D>U, and the origin to C>RU.	all at their last position
6	The origin broadcasts R - 1 - r. Every worker's core receives it; the top row and the two top corners end it.
7	The origin sends RST. It follows the broadcast on every path and returns every switch it passes to position 0, the origin's own first.	all at 0

A worker that is already back at the barrier when the broadcast arrives sends its next ADV at once. That ADV cannot enter its router until RST has returned the switch to C>C, so it waits.

The routes with INNER=0

When every PE is a worker, every rule except the origin's starts with the closed position, and the positions that bring a PE its probe and its broadcast also give them to its core:

PE	Rule
origin	[C>R ; U>C ; C>RU]
row 0	[C>C ; L>CRU]
(NX-1, 0)	[C>C ; L>CU]
column 0	[C>C ; U>CD ; D>CU]
all other PEs below the top row, column NX-1 included	[C>C ; D>CU]
top left	[C>C ; R>CD ; D>C]
top row	[C>C ; D>C ; R>L ; D>C]
top right	[C>C ; D>CL ; D>C]

The border PEs, which only routed with INNER=1, are workers now. Each of their rules is its INNER=1 rule with the closed position in front and C added where the PE receives its probe or the broadcast, so each of their positions has a number one higher than before. The inner workers keep [C>C ; D>CU] and its position numbers. Each worker must receive exactly one probe and one broadcast in every round, as worker.w does. A top-row PE receives its own column's probe in position 1, passes the probe that goes round the border in position 2 without keeping it, and receives the broadcast in position 3. That rule uses all four positions a switch can have.

The layout

bench.paint builds the routes with lesson 4's hstack, lesson 11's define, hstackrep and vstackrep, and vstack, which stacks the rows, the first lowest:

    vstack(
        hstack(origin hstackrep(bottom nx-2) bottomright)
        vstackrep(hstack(left hstackrep(worker nx-2) right) ny-2)
        hstack(topleft hstackrep(top nx-2) topright))

The programs sit on separate regions, so that check.py can read each one's symbols as a rectangle: inner with INNER=1; row0, col0 and rest with INNER=0. The last line chooses between the two forms:

setif(INNER
    union(origin inner inner_routes(NX NY c))
    union(origin row0 col0 rest all_routes(NX NY c)))

setif(cond a b) gives a when cond is not 0 and b otherwise. Paint builds both before it chooses, so both must be valid layouts.

What the hardware does

• A PE's own router acts first. A control wavelet from the core enters its own router before any other, as in the switch-protocols topic. In C>C the worker's ADV goes nowhere else: it moves the worker's own switch and stops.
• A closed router holds up its neighbours. A router takes a color's wavelets from one input at a time. While a worker's router is in C>C, the probe waits at the router below it, and so does everything behind the probe on that path.
• A multicast waits for its slowest output. A router keeps a wavelet at the head of the color's queue until every output has taken it, and the wavelets behind it wait. With INNER=1, a PE of row 0 sends the probe right and up. While the worker above it is closed, the probe stays at the head of that PE's queue, so the ADV behind it can go on neither up nor along row 0.
• Control wavelets move both switches, so the positions may differ. A router keeps an input switch and an output switch for each color, as lesson 10 showed. An advance or a reset moves the input switch when it arrives and the output switch when it leaves, so the two stay in step. That is why these rules may give each position its own outputs.
• A flip could not open a worker. A flip moves only the input switch. The hardware allows it only on a route whose positions all have the same outputs, and a worker's positions send to C and to C and U.
• Each wait is measured on one PE. In the simulator every PE starts in the same cycle; on the hardware they do not. waited subtracts two readings of one PE's own counter, so it means the same on both.

Cost. Every worker that is not late waits the same number of cycles. A worker far from the origin receives each broadcast later, and so arrives at the next barrier later, by the same amount. Its wait is about the time between two broadcasts: the late worker's spin, 1008 cycles with the code around it, plus the late worker's own wait. In the tutorial row the late worker waited 56 cycles and every other worker 1064.

The late worker's wait is the time from its arrival until the broadcast reaches it, and most of it is hops. In the tutorial row, when (1, 1) opens, the probe below it goes up, and the ADV behind that probe at (1, 0) can at last go on along row 0. Column 3 gets its ADV only then, so the probe that goes round the border is still waiting at the top of column 3. The path is 13 hops: the ADV from (1, 0) to the top of column 3 (5), the probe along the top row and down column 0 to the origin (6), and the broadcast to (1, 1) (2). A hop costs about two cycles, and the programs at the two ends about 30. A late worker at (3, 2) has a 13-hop path too, 2 + 6 + 5, and waited 56 cycles as well.

With the late worker at (1, 1), the rows all3x3, all5x4 and all10x7 gave it 44, 56 and 88 cycles, and every other worker 1052, 1064 and 1096. The INNER=1 rows of the same sizes give the same waits.

Run it

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

cd tutorial/ext-collectives/barrier-and-broadcast
make TEST=tutorial

Success is a line ending in PASS tutorial [ NX=5 NY=4 R=3 INNER=1 ARCH=sdr ]. The end of test-tutorial/make-log shows what check.py read back, the top row first. A . is a PE without a program:

rounds each PE completed, top row first:
    .     .     .     .     .
    .     3     3     3     .
    .     3     3     3     .
    3     .     .     .     .

Then come the waits, in the same layout, and PASS. In the simulator the late worker at (1, 1) waited 56 cycles and every other worker 1064.

The test checks only the rounds. A barrier that lets a PE through early still completes every round, so read the waits too: every worker except the late one should have waited longer than the spin.

If a switch is left out of place, the next round stalls. The simulation stops at its cycle limit (cycles=6000 in the Makefile), the PEs show fewer than R rounds, and check.py prints FAIL. Each round takes a little more than DELAY cycles, so raise the limit before you raise R much. make TEST='*' runs every row: both forms, from 2 × 3 to 10 × 7. Run make clean before running a row again after an edit; make reuses an existing test-<row>/ directory.

Pitfalls

• A worker without the closed position passes the test, and the barrier is gone. With the workers' rule [D>CU] in inner_routes, every PE still completed 3 rounds, but the late worker waited 4 cycles and the others 21. The probe no longer waits for anyone.
• Without the reset, round 1 never starts. Without RST, every switch stays in its last position. Every PE completed 1 round, and the run stalled.
• A worker must read the probe. Without sp probe = ping[];, a worker takes the probe for the broadcast. In round 0 the probe is 0, so every worker stopped after one round, and the origin waited for a probe that no worker let through.
• Four positions at most. The top-row rule with INNER=0 uses all four. Paint accepts a fifth position without a message and changes position 0 (lesson 10).
• With INNER=1 the grid needs at least 3 × 3 PEs, or there are no inner PEs.
• A while loop needs a body. while (d < DELAY) { } fails with invalid syntax in statement, which is why the spin loop reads the counter inside its body.

Exercises

1. Make another worker late. In worker.w, change col[0] == 1 && row[0] == 1 to col[0] == 1 && row[0] == 2. Count the hops from its arrival to the release and back to it, as Cost does for (1, 1), and predict how long it waits in the last round, and how long the others wait. Then run make clean and make TEST=tutorial.
2. Write the switch table of one round with INNER=1 and NX=3 NY=3, which has one worker: for each of the nine PEs, its position after each wavelet of the round. Check that every switch ends in position 0, and mark which wavelet moved it there.

Next

Topic — Collectives over messages: tree reduction and prefix scan builds a reduction and a scan from messages.

References

• Switch positions, Stacking and Conditionals in the Paint reference
• Control wavelets and Hardware Register Access in the Tungsten reference
• Switch positions in the architecture notes