Topic — A route through every PE: a closed loop on one color

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 route does not have to end at another PE. This topic builds one route that leaves a PE, passes through every other PE of a rectangle once, and comes back to the PE it started from. Only that PE runs a program. Every other PE only routes, with a rule of one position that turns the color or passes it straight on. The sending PE needs a switch: it sends into the loop, then receives from it, and the same control wavelet that follows each value moves its switch both times.

What you will be able to do

• Build a closed route through every PE of a rectangle from one-position turn rules, with hstack, vstack and their repeated forms.
• Reuse a layout with x and y swapped, with rotate and hflip, and choose between two layouts with setif.
• Let one PE send on a color and then receive on it, with a two-position switch that ring wraps, and one control wavelet per value.
• Say how long a lap takes, and why the loop carries one value at a time.
• Check that a route passes every PE, by following it through the description of the layout that Paint writes.

The program

The PE at (0, 0), the origin, sends the values 0, 1, …, N-1 into the loop and receives each one back. For the tutorial row, a 4 × 4 rectangle with N=4, the loop is:

         x=0   x=1   x=2   x=3
  y=3     + --> +     + --> +
          ^     v     ^     v
  y=2     +     +     +     +
          ^     v     ^     v
  y=1     +     + --> +     +
          ^                 v
  y=0     O <-- + <-- + <-- +

The color leaves O upwards, climbs column 0, snakes down and up through columns 1 and 2 between rows 1 and 3, comes down column 3 to row 0, and runs left along row 0 back into O. Each + is a PE with one rule and no program.

The origin must get back [0, 1, 2, 3], in that order, and the route must pass all 16 PEs before it returns. check.py checks both. The other rows of test.rc are 2 × 3, 6 × 2, 5 × 4, 2 × 2 and 8 × 6, each with N=3.

The code

The origin: origin.w

xp param N;
socket ping;
u32 ADV = 0x09409249;
u16 tsc[1] address(0x7b30);
u16 tsc_control[1] address(0x7b34);
sp got[n=N];
u16 stamp[n=N+1];
{
    let i in [0, N);
    ∀i got[i] <- -1.0;
    tsc_control[0] <- tsc_control[0] | 4;
    stamp[0] <- tsc[0];
    ∀i {
        ping[] <- (sp) i;
        ping[] <- control(ADV);
        got[i] <- ping[];
        stamp[i + 1] <- tsc[0];
    }
}

• ping is the one socket. The origin sends on it and receives on it, on the same color.
• got starts at -1.0 everywhere, so a value that never comes back shows as -1 and cannot be mistaken for the value 0.
• Each step of the loop sends a value and then ADV, the control word of the switch-protocols topic: command 0 is an advance, and every command has the CE filter set, so no core ever receives it.
• The step then waits until the value comes back, and the next step sends the next value.
• stamp keeps the timestamp counter of lesson 3 at the start and each time a value has come back. check.py prints the differences; they never decide the test.

The origin's switch

The origin's rule has two positions and ring:

    let start = paint(tile() c [C>U ; R>C ; ring])

Position 0, C>U, sends from the core up into column 0. Position 1, R>C, takes what arrives from the right and gives it to the core. One lap:

Step	What happens	Origin's switch after it
1	Value i leaves the core by position 0 and goes up.	0
2	ADV follows. The origin's own router acts on it first: the input switch moves to R>C, and ADV leaves by the old output, up, behind the value. Then the output switch moves too.	1
3	The value and ADV go round the loop. Every router there has one position, so the advance does nothing, and each router passes it on.	1
4	The value comes back from the right and goes to the core.	1
5	ADV comes back. The switch is in its last position, so ring wraps it to position 0. ADV leaves towards the core, and its filter keeps it out.	0
6	Value i+1, which the core sent after it received value i, leaves.	0

Each ADV moves the origin's switch twice: once on the way out, at the origin's own router, and once on the way back. A switch with two positions and ring therefore alternates between sending and receiving, one ADV per value.

Rules of one position

loop paints nine rules, each with one position. A rule's name is its input and then its output: dr takes the color from below and sends it right.

    let du = paint(tile() c [D>U])
    let ud = paint(tile() c [U>D])
    let lr = paint(tile() c [L>R])
    let rl = paint(tile() c [R>L])
    let dr = paint(tile() c [D>R])
    let ld = paint(tile() c [L>D])
    let ur = paint(tile() c [U>R])
    let lu = paint(tile() c [L>U])
    let ul = paint(tile() c [U>L])

paint(tile() c [D>U]) paints one PE at (0, 0) and returns it. The rows below place copies of these PEs; each copy keeps its rule.

The rows

    let bottom = hstack(start hstackrep(rl nx-2) ul)
    let top2 = hstack(dr hstackrep(lr nx-2) ld)
    let turn = hstack(du hstackrep(hstack(ur lu) (nx-2)//2) ud)
    let middle = vstackrep(hstackrep(hstack(du ud) nx//2) max(0 ny-3))
    let top = hstackrep(hstack(dr ld) nx//2)

    setif(ny==2 vstack(bottom top2) vstack(bottom turn middle top))

hstack puts regions side by side along x, as in lesson 4. vstack puts them on top of each other along y, the first one lowest. hstackrep(r n) and vstackrep(r n) are lesson 11's repeats; a count of 0 gives an empty region. // divides and drops the remainder, and max(0 ny-3) is the larger of 0 and ny-3.

For ny of 3 or more, the rows are, from the bottom:

Row	Region	4 × 4
0	bottom: the origin, then rl up to the last PE, which turns ul	start rl rl ul
1	turn: up in column 0, pairs ur lu that join a downward column to the next upward one, down in the last column	du ur lu ud
2 to ny-2	middle: pairs du ud, straight up and straight down	du ud du ud
ny-1	top: pairs dr ld that join an upward column to the next downward one	dr ld dr ld

Columns 1 to nx-2 go down and up in turn, and the last column must go down to reach row 0. That needs an even nx. For ny = 2 there is no room for the snake, and top2 takes the color along row 1 to the last column instead.

setif builds both of its layouts before it chooses one (below), so for ny = 2 Paint also builds middle, and ny-3 would be -1. max(0 ny-3) keeps the count at 0. A count of -1 is not an empty region: in a test layout that used a region repeated -1 times, Paint crashed without a message.

Swapping x and y

The layout puts loop together with the origin's code:

let origin = tile(0 0)
origin : code('origin [ping:c N:N])
origin : name('origin)

let route = setif(NX%2==0 loop(NX NY c) hflip(rotate(loop(NY NX c) R90)))

union(origin route)

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

For an odd NX, the program builds the loop for an NY × NX rectangle and swaps its x and y. rotate(r R90) turns a region a quarter turn counter-clockwise, so +x becomes +y. hflip(r) then mirrors it left to right. Together they swap x and y, and every rule turns with its PE: R and U trade places, and so do L and D. The origin's rule becomes [C>R ; U>C ; ring]. In the 5 × 4 row the color goes right along row 0, snakes through rows 1 to 3, and comes down column 0.

A rectangle with odd NX and odd NY has no such loop. A lap from the origin back to itself takes an even number of steps, because every step changes x + y by one, odd and even in turn. A lap through every PE has as many steps as the rectangle has PEs, and an odd × odd rectangle has an odd number of them. So the program needs NX and NY of at least 2, and at least one of them even.

Checking the route: check.py

Values that come back in order show that the route is closed. They do not show that it passes every PE: a shorter loop returns them too. So check.py also follows the route itself. Paint writes a description of the layout into bench-region.json in every build, as its regiondump= option asks. It is a tree like the layout's expressions, and the function rules walks it and adds up the offsets of repeated regions. For each PE it finds the rule: irt holds the input of each position and ort its outputs, as bits, with 1 for R, 2 for U, 4 for L, 8 for D and 16 for the core. Then:

step = {1: (1, 0), 2: (0, 1), 4: (-1, 0), 8: (0, -1)}
facing = {1: 4, 2: 8, 4: 1, 8: 2}
here, out = (0, 0), rule[(0, 0)]["ort"][0]
path = [here]
while out in step and len(path) <= nx * ny:
    there = (here[0] + step[out][0], here[1] + step[out][1])
    position = 1 if there == (0, 0) else 0
    if there not in rule or rule[there]["irt"][position] != facing[out]:
        break
    here, out = there, rule[there]["ort"][position]
    path.append(here)
closed = here == (0, 0) and out == 16

The walk starts with the output of the origin's position 0. At each PE it checks that the PE's input faces the PE before it: a color sent right arrives from the left. It stops at a PE with no rule, at an input that does not face the route, or back at the origin, whose position 1 must take the color and give it to the core. The test passes only if the route comes back to the origin after NX × NY steps, the PEs it passed are exactly those of the NX × NY rectangle, and the origin got every value back in order.

What the hardware does

• An advance moves a switch only if it has somewhere to go. A router that receives an advance moves to its next position if it has one. Otherwise a switch with ring returns to position 0, and a switch without ring stays where it is. The loop's routers have one position and no ring, so the ADV passes through them without effect. A router on the loop with a second position would advance too.
• The core never sees the ADV. Its command 0 has the CE filter set, so the origin's router drops it on the way to the core in step 5.
• The loop carries one value at a time. The origin's router takes the next value from the core only in position 0, and it returns to position 0 only when the ADV behind the previous value comes back. A value that the core sent earlier would wait at the router.
• The origin cannot use flip. Its two positions send to different outputs, up and the core. A flip moves only the input switch and leaves the output switch where it was, so the hardware allows it only on a route whose positions all have the same outputs.

Cost. The test prints the cycles from the start until value 0 is back, and then from each return to the next. On a loop of P PEs, each value came back 2·P + 15 cycles after the one before, within one cycle, in every row:

Row	Rectangle	P	Cycles from one return to the next
w2h2	2 × 2	4	23
w6h2	6 × 2	12	39
tutorial	4 × 4	16	47
w8h6	8 × 6	48	111

A 16 × 16 loop gives 527. A wavelet takes about two cycles to cross a PE. The other 15 cycles do not grow with the loop: they are spent at the origin, between its router and its program. The timings never decide whether the test passes.

Run it

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

cd tutorial/ext-routing/space-filling-route
make TEST=tutorial

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

the route from the origin passes 16 of the 4 x 4 PEs and returns to the origin
the origin got back: [0. 1. 2. 3.]

then a line of cycle counts, and PASS.

If the route skips PEs, the first line says how many it passes, and check.py prints FAIL. If the loop does not close, the first line ends and does not return, and the values never come back: the simulation stops at its cycle limit (cycles=2000 in the Makefile), and got still holds -1.0 where a value is missing. make TEST='*' runs every row. Run make clean before running a row again after an edit; make reuses an existing test-<row>/ directory.

Pitfalls

• Without ring the loop runs once. With [C>U ; R>C], the first ADV comes back to a switch already in its last position, which stays in R>C. The origin can then never send again: with the tutorial row it got back [0, -1, -1, -1].
• Paint does not check that a route closes. Each rule only names where the color comes from and where it goes. A rule whose input does not face the previous PE's output stops the color there, and nothing reports it. With NX=3 NY=3, Paint built a layout with two PEs that have no rule at all and a PE that sends left into a PE that takes input from above. Nothing came back, and check.py reported a route that passes 5 of the 9 PEs and does not return.
• Values that come back do not show that the loop passes every PE. With loop(2 NY c) in place of loop(NX NY c), the loop runs through columns 0 and 1 only. The origin still got back [0, 1, 2, 3] in the tutorial row, and only the route check failed it: the route passes 8 of the 16 PEs. A test that checks only the values cannot see a short loop, and below a few dozen PEs neither can a glance at the cycle counts.
• A flip in place of the ADV runs, and nothing comes back. With flip ping[]; after each value in place of ping[] <- control(ADV);, the input switch moves to R>C but the output switch stays at C>U, so each returning value goes up into the loop again. The simulator gives no message; the origin got back nothing.
• setif builds both layouts. A branch that Paint cannot build stops the build even when the other branch is chosen. Both branches here are valid Paint for any size, even where the unchosen one is not a loop.

Exercise

Carry two values per lap. In origin.w, replace the loop ∀i { … } with:

    ∀j in [0, N / 2) {
        ping[] <- (sp) (2 * j);
        ping[] <- (sp) (2 * j + 1);
        ping[] <- control(ADV);
        got[2 * j] <- ping[];
        stamp[2 * j + 1] <- tsc[0];
        got[2 * j + 1] <- ping[];
        stamp[2 * j + 2] <- tsc[0];
    }

Predict which values come back, in what order, and how the cycles between returns change. Then run make clean and make TEST='*'. Why does only the tutorial row pass?

Next

This is the last topic of the group. The next group, Numerics, starts with Topic — Precision: how the PE rounds, and references that match, which shows how the PE rounds hp, ep and sp arithmetic, and how to write a host reference that rounds the same way.

References

• Switch positions, Stacking, Flipping and rotation and Conditionals in the Paint reference
• Control wavelets in the Tungsten reference
• Switch positions in the architecture notes