Topic — Data in and out: filters, fan-out and funnels

Needs: Lesson 7 — Tasks: code that runs when a wavelet arrives, Lesson 10 — Switches: PEs that take turns on one color; topic Switch protocols: remote advance, pop, rings, self-restoring barriers.

Data often enters a layout through one PE and must leave through one PE. One stream then has to feed many rows of PEs, and the rows' results have to merge back into one stream. This topic builds both directions. A fan-out sends one stream up a column, and each PE's input filter keeps only that row's share. A funnel merges the rows' streams back into one, in the original order, with the switches of lesson 10.

What you will be able to do

• Configure a counter filter that keeps one chunk of every period of a stream, and set where in the period each PE's chunk falls.
• Spread one stream over a column of PEs, and merge the column's streams back into the original order.
• Close a route to its neighbours with a * start position, and open it with a reset the PE sends itself.
• Choose between a counter filter and a range filter.

The program

A column of H rows. src sends the values 1, 2, …, N·H·C, in N periods of H·C values. In every period, the PEs of row y handle chunk y: the C values from y·C + 1 to y·C + C of the period.

          x=0      x=1      x=2      x=3        x=4
  y=H-1            fan  ──► tap  ──► funnel
   …                ▲                  │
  y=1              fan  ──► tap  ──► funnel
                    ▲                  ▼
  y=0     src  ──► fan  ──► tap  ──► funnel ──► dst

  color inc: src, then up the fan column; every fan PE sees every value
  color row: one stream per row, fan → tap → funnel
  color out: down the funnel column, then to dst

• fan keeps its row's chunks and sends them along its row.
• tap records what its row received, and passes it on.
• funnel merges the column: in each period, row 0's chunk, then row 1's, and so on up to row H-1.
• dst must receive 1, 2, …, N·H·C in order.

For the tutorial row, H=5 C=3 N=2, the taps must hold:

row 0:  1  2  3  16 17 18
row 1:  4  5  6  19 20 21
row 2:  7  8  9  22 23 24
row 3: 10 11 12  25 26 27
row 4: 13 14 15  28 29 30

and dst must hold 1 to 30. check.py checks both.

The code

src.w and dst.w

src fills an array with 1 to M and sends it. dst receives M values. The taps run dst.w too, with M = N·C.

The fan column

The routes of inc on the fan column:

let fan_bottom = rect(1 0 1 1)
fan_bottom : paint(inc [L>CU ; C>C*])
let fan_body = rect(1 1 1 H-2)
fan_body : paint(inc [D>CU ; C>C*])
let fan_top = rect(1 H-1 1 1)
fan_top : paint(inc [D>C ; C>C*])

Position 0 is the broadcast: take the stream from the left or from below, give the core a copy, and pass it up. Position 1, C>C, takes input only from the PE's own core and delivers it only to that core: the PE is closed to its neighbours. The * makes each fan PE start in position 1. The stream from src waits at the closed router until the PE opens it.

The fan's kernel, fan.w:

xp param C;
xp param H;
socket rx;
socket tx;
xp rowid[1] address(0x7C45);
u32 RST = 0x09809249;
filter keep[counter] = {.limit = C * H - 1, .maxpass = C - 1, .state = 64, .socket = rx};
sp mem[n=256];
sp fifo ff = {.mem = mem};
main {
    xp w = C * (H - 1 - rowid[0]);
    ∀i in [0, w) rx[] <- 0.0;
    rx[] <- control(RST);
    parallel {
        ∀i in [0, ∞) ff[] <- rx[];
        ∀i in [0, ∞) tx[] <- ff[];
    }
}

∀i in [0, ∞) repeats one transfer without end; ∞ may be written INF. Its body must be that one transfer: a { } body with two statements fails with unimplemented: expr_type EXPR_INF. To repeat any other body without end, use forever (lesson 5), as the funnel's second arm below does. See Infinite Iterators in the Tungsten reference.

The filter. keep is a counter filter on rx. Every wavelet that arrives for rx passes it or is dropped before it reaches the core. The counter alternates between dropping .limit - .maxpass wavelets and passing .maxpass + 1; one period is .limit + 1 wavelets. .state = 64 starts it in the dropping phase. With .limit = C·H - 1 and .maxpass = C - 1, the filter drops C·(H-1) wavelets, passes C, and repeats with a period of C·H. The Counter Filter section of the Tungsten reference describes .limit alone, which passes one wavelet per period.

The phase. The filters of all fan PEs start at the same point of the period. Each PE therefore moves its own counter forward first, so that its first pass falls on its own chunk. rowid[0] is the PE's row, from the Row ID register that Paint writes. The PE sends w = C·(H-1-y) values of 0.0 into its own closed router, which delivers them back to its own filter. The filter drops them, because they all fall in the dropping phase. After them, the filter has only C·y drops left before its first pass, so the first chunk it passes is chunk y.

The opening. rx[] <- control(RST) sends a reset into the PE's own router, which returns it to position 0, the broadcast. The reset carries the CE filter, so the core never receives it, and the counter does not count it. From then on the PE takes the stream from its neighbour.

The relay. The two parallel arms move kept values into a FIFO and from the FIFO onto row. While the row is busy, the FIFO keeps taking values, so this PE does not hold up the broadcast for the rows above it. A multicast moves at the speed of its slowest receiver (lesson 4). FIFOs are from lesson 5.

The funnel column

The routes of out:

let funnel_bottom = rect(3 0 1 1)
funnel_bottom : paint(out [C>R ; U>R])
let funnel_body = rect(3 1 1 H-2)
funnel_body : paint(out [C>D ; U>D])
let funnel_top = rect(3 H-1 1 1)
funnel_top : paint(out [C>D])

This is lesson 10's drain turned on its side. Every funnel PE starts by sending its own data, then flips to pass on the data from above. funnel.w:

main {
    parallel {
        ∀i in [0, ∞) ff[] <- rx[];
        forever {
            ∀j in [0, C) tx[] <- ff[];
            flip tx[];
            if (rowid[0] == H - 1) tx[] <- control(RST);
        }
    }
}

In each period, row 0 sends its chunk and flips, then row 1's chunk passes through it, and so on. The top PE flips too, but its route has one position, so its switch does not move. It then sends RST, which returns every funnel PE below it to position 0 for the next period. The first arm keeps taking the row's values into a FIFO while the PE waits for its turn.

These flips are legal: in every funnel position the outputs are the same (D, or R on row 0), and no funnel route pops. Lesson 10 asks for a flip after a send from an array; a send from a FIFO is one transfer too. The listing, test-tutorial/funnel_artefacts/funnel5.yeti, shows one send DSD of length C with .fs=1, so the flip rides on the chunk's last value.

Keeping a block by index: range filters

A counter filter suits a stream whose pattern repeats. When each wavelet carries an index, a range filter keeps the wavelets whose index lies in a range. with mine(i) attaches the filter to a wavelet handler and names the argument it tests. The sender then puts that argument in the wavelet's upper 16 bits, the index field that a range filter reads. The argument can come first, as here, or second, as i does in lesson 7's wavelet(hp x, xp i):

filter mine[range] = {.min = 4, .max = 8};
forever dispatch(rx) {
    wavelet(xp i, hp x) with mine(i) {
        b[i - 4] <- x;
    }
}

Of a stream of wavelet(i, …) for i from 0 to 11, the handler ran for i from 4 to 7. A range filter passes every control wavelet, so a named message sent after the stream, here eov(), still reached its handler. Like lesson 7's flush(), the name is the program's choice. The range is half-open, as Range Filter in the Tungsten reference says.

.min and .max must be numbers written in the kernel. A param, or an expression of params, is rejected with .min initializer must be a compile-time constant integer. So one kernel cannot keep a different block on each PE with a range filter. A handler can test the index itself instead, with params LO and B: if (i >= LO && i < LO + B) b[i - LO] <- x; keeps a different block on each PE, but the core then receives every wavelet.

What the hardware does

• Filters sit before the input queues. The core has six filters. Each one watches one color and drops wavelets on their way from the router to an input queue. A dropped wavelet takes no space in the queue and starts no task.
• A counter filter counts half-wavelets. The hardware counts in 16-bit halves, so a 32-bit wavelet ticks it twice. Carbide converts .limit and .maxpass, which count wavelets, to those units. With 16-bit values, two values can share one wavelet, and the filter then keeps or drops them in pairs.
• The counter's phase is not a parameter. Carbide sets the filter's start from .state alone: at the start of the passing phase, or with .state = 64 at the start of the dropping one. Bit 6 of the hardware's state register is the drop bit. Anything finer, such as the fan's per-row phase, the program must make by sending wavelets through the filter.
• A range filter reads the index. It compares bits 31:16 of a data wavelet with its range and passes control wavelets untouched.
• A closed position still connects the core to itself. C>C takes input from the PE's own core and delivers to the same core. A data wavelet sent on it goes through the PE's filters like any other; a control wavelet sent on it acts on the PE's own switch.

Run it

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

cd tutorial/ext-routing/data-in-and-out
make TEST=tutorial

Success is a line ending in PASS tutorial [ H=5 C=3 N=2 ARCH=sdr ]. The end of test-tutorial/make-log shows what dst and the taps received, row 0 of the taps first.

The fan and funnel PEs never end, so every run lasts until the cycle cap, cycles=3000 in the Makefile. The h8 row, the largest, made its last memory write at cycle 372. A row whose values do not all arrive before the cap fails with values still 0. make TEST='*' also runs h2 (H=2 C=1 N=3) and h8 (H=8 C=4 N=2). Run make clean before running a row again after an edit.

Pitfalls

• Start the counter in the dropping phase. If the filter starts by passing, the first values a PE sends into its own router pass too, and the core relays them as data. In a version without .state that wound row y's counter by C·((H-y) mod H) values, the taps of rows 1 to 4 started with three 0.0 values each.
• Count what the filter sees. The counter ticks for every wavelet of its color that reaches it, the program's own winding values included. A send of 16-bit values can pack two into one wavelet.
• Size the FIFOs for the wait. A funnel PE holds its row's values until its turn, and a fan PE holds them while its row is busy. Here each FIFO holds 256 values and a row receives at most N·C. A FIFO that fills stops its arm, and then the broadcast waits for that PE, and every row waits with it.
• No flip with pop=adv or pop=advnop, and no flip on positions with different outputs. Neither Paint nor Carbide reports it, and the simulator runs such a funnel without complaint.
• Every receiver of one stream needs the same handlers. A filter changes where the sender puts the arguments. In a test where one PE's wavelet(xp i, hp x) handler had a range filter on i and the other PEs on the same stream had the same handler without one, the unfiltered handlers ran with the two arguments swapped: their i held the bits of x, and their x the index. Nothing reported it.
• fan is a name Paint already uses. let fan = rect(…) fails with fan already in scope; this layout calls the region fans.

Exercise

Delete the winding loop, ∀i in [0, w) rx[] <- 0.0;, from fan.w. Predict what each tap receives and what dst receives, then run make clean and make TEST=tutorial.

Next

Topic — A route through every PE: a closed loop on one color sends one color through every PE of a rectangle and back, with one switch that ring wraps.

References

• Counter Filter and Range Filter in the Tungsten reference
• FIFOs and Parallel Blocks in the Tungsten reference
• Switch positions in the Paint reference