Topic — Reductions in the router: the fabric adder

Needs: Lesson 9 — Broadcast and reduce along a row.

In lesson 9, the core of each PE adds its value to a stream as the stream passes through: r[] <- r[] + v[j] takes every value from the fabric, adds, and sends the sum on. The router of a WSE-3 PE (ARCH=sdr) can do that addition itself, on the chip revision named under Limits below. On a PE in fabric adder mode, a wavelet that arrives from a neighbour is an sp (fp32) value, the core sends one hp (fp16) value, and the router sends their sum, an sp value, on to the next PE. The core only supplies its contribution.

This topic uses the fabric adder for a convolution, in which an input stream and the adder chain run side by side.

What you will be able to do

• Build an adder chain: a head that starts each sum, PEs that add to it, a tail that receives it.
• Keep the operands paired: every adding PE sends exactly one hp value per sum, in the same order.
• Stream an input past the adding PEs instead of copying it to each of them.
• State the adder's limits, and recognize the mistakes that compile and run but give wrong sums.

The smallest chain

Four PEs in a row: a head sends 100.0 as sp, two adding PEs send 2.0 and 3.0 as hp, and the tail receives 105.0.

    head              add0               add1              tail
   100.0:sp           2.0:hp             3.0:hp
     |                  |                  |
  [C>R] --100.0--> [L>R; fabadder] --102.0--> [L>R; fabadder] --105.0--> [L>C]

• The head's rule [C>R] is an ordinary route: its core sends the first sp operand.
• fabadder turns on the adder for that color in that router. [L>R; fabadder] takes the sp operand from the left (L), adds the hp value that the PE's own core sends on the same color, and sends the sum right (R). The rule does not name C: the router takes the core's operand by itself.
• fabadder is a modifier, not a second switch position (lesson 10). Modifiers follow the last position, after an optional ;; the topic Switch protocols uses two more, ring and pop=. Color 10 cannot switch, so an adder rule has one position.
• The tail's [L>C] is an ordinary route to its core, which receives sp values.

The program

A convolution of an input x with K = 3 coefficients h:

y[n] = h[0]·x[n] + h[1]·x[n−1] + h[2]·x[n−2],   with x[m] = 0 for m < 0

Five PEs in a row and two colors:

   src --data--> tap0 --data--> tap1 --data--> tap2          recv
                  |              |              |              ^
                  +---result---> + ----result-> + ---result----+
                [C>R]     [L>R; fabadder] [L>R; fabadder]    [L>C]

• data carries x from src. Each tap's rule [L>CR] gives every sample to its core and passes it right; the last tap's [L>C] passes nothing on.
• result is the adder chain. tap0 is the head: it sends h[0]·x[n] as sp. tap1 and tap2 add h[1]·x[n−1] and h[2]·x[n−2] as hp. recv is the tail and stores y[n].

Each tap holds only its own coefficient. The input is not copied to the taps: it streams past them, and each tap keeps the few samples it still needs in a delay array.

With h = [1, 2, 3] and x = [4, 3, 2, 1], the tutorial row expects:

y[0] = 1·4 + 2·0 + 3·0 =  4
y[1] = 1·3 + 2·4 + 3·0 = 11
y[2] = 1·2 + 2·3 + 3·4 = 20
y[3] = 1·1 + 2·2 + 3·3 = 14

The n64 row convolves 64 random samples with random coefficients.

The code

The layout: bench.paint

let data   = color()
let result = color()

let t1 = tile()
t1 : code('tap_inner [rx_data:data tx_res:result N:N TAP:1])
t1 : paint(data   [L>CR])
t1 : paint(result [L>R; fabadder])
t1 : name('tap1)

tap2 is the same with TAP:2 and [L>C] on data. Paint puts a color that has a fabadder rule on physical color 10, the only color with an adder, and prints color result with virt color 1 uses fabadder. The Makefile adds float16_dtype=10 to PAINTFLAGS: it tells the adder that the core's operand is IEEE fp16, the format of hp.

The head: tap_head.w

    ∀n in [0, N) {
        sample = rx_data[];
        tx_res[] <- (sp)(coeff[0] * sample);
    }

The product is hp; the cast sends it as sp, the format the adder expects from the fabric.

The adding taps: tap_inner.w

hp coeff[n=1];
hp delay[n=TAP] = {0.0};

main {
    xp pos = 0;
    ∀n in [0, N) {
        tx_res[] <- coeff[0] * delay[pos];
        delay[pos] = rx_data[];
        pos = pos + 1;
        if (pos == TAP) pos = 0;
    }
}

delay holds the last TAP samples, and pos points at the oldest, x[n−TAP]. The tap sends its product before it receives x[n] into the same slot. delay starts at 0, so for n < TAP the tap sends 0: every tap sends exactly one value for every output, which keeps the sums paired.

The source and the tail: src.w, recv.w

    ∀i in [0, N) tx[] <- x[i];

    ∀i in [0, N) y[i] <- rx[];

The test

ref.py computes y the way the chain does: each product rounded to hp, then the three terms added in sp, tap 0 first. The n64 data are multiples of 1/8 between −31/8 and 31/8, so every product and every sum is exact, and the check is bit for bit.

What the hardware does

Pairing. An adder holds its operands in two queues, one for the fabric's sp values and one for the core's hp values. It adds when both queues have a value at their head, whichever came first. Operands pair by order, not by time: the n-th sum from the left meets the n-th value from the core. So every adding PE must send one value per sum, in the order the sums arrive. A PE that sends nothing stalls the chain; a PE that sends an extra value shifts every later pair.

Packing. The core may send two hp values in one 32-bit wavelet (lesson 4); the adder takes them as two operands.

Numbers. The sum is always fp32 and rounded to nearest, ties to even. A denormal fp32 operand from the fabric, and a denormal sum, become 0. Denormal fp16 operands from the core are kept.

Limits.

• Color 10 only. Paint assigns it, and in adder mode color 10 carries no other traffic. A stream such as x needs its own color.
• The core's operand is hp, with float16_dtype=10. Without the option, Paint stops with Invalid float16 data type 0 used with SDR fabric adder.
• One exit port: after >, exactly one of R, L, U and D. The sum cannot go to the core; the tail uses a plain rule such as [L>C].
• The core of an adding PE sends only data on the adder color: a control wavelet from that core gives undefined results. A control wavelet that the head sends reaches each adding PE on a fabric port, and it passes through unchanged, in order with the sums, out of the same port.
• Only the B0 revision of the WSE-3 chip has a fabric adder; the A0 revision does not. The rows of this topic pass on the simulator. These pages cannot tell which revision a given system has: check with whoever runs your system before you rely on the adder.

The cost. The adding PEs execute no instruction for the sum; their cores only send. The exercise below measures what that saves against lesson 9.

Streamed or copied input

The other way to give each tap its samples is to copy all of x to every tap:

	Input copied to every tap	Input streamed (this program)
Tap memory	all of x on every tap	TAP samples on tap TAP
x[m] for m < 0	tap TAP sends 0.0 until n ≥ TAP	delay starts at 0
Colors	1	2: the stream needs its own

Copying costs no color but K copies of x. Streaming keeps one copy, and the [L>CR] multicast moves each sample at the pace of the slowest tap (lesson 4).

Splitting the inner dimension

The same chain computes a matrix product C = A·B with the inner dimension K spread over the PEs: PE k holds column k of A and row k of B, and sends A[i][k]·B[k][j] for every (i, j) in the same order. The chain adds over k, and the tail receives each C[i][j] as sp. As in the convolution, every PE must send the products in the same (i, j) order.

Run it

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

cd tutorial/ext-collectives/fabric-adder
make TEST='*'

Success is a PASS line for tutorial and for n64, such as fabric-adder : 0:02.70 PASS tutorial [ N=4 SEED=0 CYCLES=1000 ARCH=sdr ]. make deletes the simulator's memory image when a row finishes, so to print the outputs, rebuild it as lesson 4 does:

cd test-tutorial
make -f ../Makefile VPATH=.. TEST=tutorial bench.map bench-sim.core
miget image=bench-sim.core map=bench.map symbol=recv.y sp
cd ..

A failure prints FAIL, and test-tutorial/make-log shows that cmp found y-ref.bin and y-sim.bin different. Run make clean after each edit.

Pitfalls

• An sp contribution gives a wrong sum without any error. The adder reads a 32-bit wavelet from the core as two packed fp16 operands. With tx_res[] <- (sp)(coeff[0] * delay[pos]); in tap_inner.w, the tutorial row gives 4, 3, 2 and 3.5 instead of 4, 11, 20 and 14.
• Every adding PE must send every time. Skipping a term instead of sending 0 stalls the chain or shifts the pairs.
• Paint accepts some rules the hardware does not. [L>C; fabadder] and [L>RU; fabadder] compile without a warning, and their result is undefined.
• Do not pin the adder color. Paint pins it to 10 by itself, and color(N) with another number on a fabadder color makes Paint abort.

Exercises

1. Redo lesson 9's reduction with the fabric adder, in a copy of lesson 9's directory. Store the values v as hp: ref.py writes float16 values, and miset loads them without _word, because an hp value is one word. Put the reduction on one color with [C>R] on the head, [L>R; fabadder] on the middle PEs and [L>C] on the tail, in place of the colorpair. The head sends (sp)v[j], the middle PEs send v[j], and the tail computes s[j] <- r[] + (sp)v[j] before it broadcasts. Remember float16_dtype=10. Lesson 9's cycles.py then measures the new chain:

   PEs (K), 8 values each	Lesson 9: the head had the whole total after	With the fabric adder
   4	68 cycles	50 cycles
   8	124 cycles	70 cycles
   16	236 cycles	110 cycles

   Explain why the gap grows with the number of PEs.

2. Add a fourth tap: a PE with TAP:3 between tap2 and recv, and h[3] in ref.py and the Makefile. Which rules change on tap2?

Next

Topic — Switch protocols: remote advance, pop, rings, self-restoring barriers builds row collectives from switches that restore themselves.

References

• Fabric adder in Paint
• Direction codes
• C-style casts