Topic — Vector-step loops, predication and memory iterators

Needs: Lesson 3 — How a PE runs a loop: vector instructions and cycles.

Lesson 3 showed that a loop whose body is one operation over arrays becomes one vector instruction, and that a loop with a condition runs one element at a time. This topic shows the hardware's other loop mode, vector step. It runs a body of several statements, conditions included, as vector instructions over a few dozen elements at a time. The program uses it to pick out the elements of an array that pass a test, and compares it with two loops that do the same work more slowly.

What you will be able to do

• Turn a loop body of several statements, with a condition, into a hardware vector-step loop, and size its scratch arrays.
• Predict the length of every step from pref_len, max_len and the trip count.
• Pack the elements that pass a test at the front of an array with a memory-iterator cursor, and count them.
• Check the listing for a hardware vector-step loop, and recognise the forms that Carbide silently turns into a slow ordinary loop.
• Keep a cursor that carries on where the previous call stopped.

The program

vstep.w runs on one PE. Its inputs are two xp arrays a and b of N values, which ref.py draws at random (a from 50 to 149, b from 0 to 49) and miset writes into the image, as in lesson 2. For every i the kernel computes a[i] - b[i], keeps the differences greater than T, and packs them at the front of an output array. It does this three times:

Loop	Output	Form
1	val	a vector-step loop with one cursor
2	val2, idx2	the same loop, which also records each kept element's index
3	val3	an ordinary loop with an if

count holds the number of kept elements that each loop found. Part 4 adds rows of numbers into a 4 × 8 SP array m through a cursor that persists from one function call to the next.

ref.py --a.bin, b.bin--> miset --> +------------------------+ --> miget --> val, count, d, val2, idx2,
                                   | PE: vstep.w            |             val3, m --> cmp with ref.py
                                   | a - b > T, packed      |
                                   | cycle counter          |             t --> cycles.py (table)
                                   +------------------------+

For the tutorial row (N=64, T=75), 36 of the 64 differences are greater than 75. val starts 84, 116, 101, 79, 79, 124, … and holds 36 values followed by 28 zeros, and count is 36, 36, 36.

Vector-step loops

Why a loop needs steps

The body of loop 1 has three statements: a subtraction, a comparison and a conditional store. Each needs the result of the one before. Run as three instructions over all N elements, every intermediate result would need an array of length N. The comparison is also a problem: a vector instruction can act on a condition element by element only through the vector flags, and the PE has 32 of them in a set, one per element.

In vector-step mode the hardware cuts the loop's range into steps of a few dozen elements. It runs every instruction of the body over one step, then over the next. An intermediate result needs only one step's worth of storage, and a step of at most 32 elements fits the vector flags.

The attributes

    [[vectorize.pref_len(PREF), vectorize.max_len(MAXL), vectorize.iter(j)]]
    ∀i in [0, N) {
        d[j] <- a[i] - b[i];
        keep[j] <- d[j] > T;
        if (keep[j]) {
            wv[] <- d[j];
        }
    }

The attribute list goes directly before the ∀ loop.

• vectorize.pref_len(PREF) is the preferred step length. It is required.
• vectorize.max_len(MAXL) is the longest step allowed, and it defaults to pref_len.
• vectorize.iter(j) names the auxiliary iterator, the position of an element within its step.

Inside the body, i is each element's own index, as in an ordinary loop. j runs from 0 to the step length minus 1, in every step. An array indexed by j is a scratch array: it holds one step. Here d and keep are scratch arrays:

xp d[n=MAXL];
u1 keep[MAXL];

u1 is the one-bit type that holds a condition, 0 or 1 (see Booleans and predicates).

Step lengths

Before each step the hardware compares the number of elements left with max_len:

• if at most max_len elements are left, the step takes them all;
• otherwise the step takes pref_len elements.

So max_len sets when the last step may be longer than pref_len. For the rows of test.rc:

Row	N	pref_len	max_len	Steps
tutorial	64	16	16	16 + 16 + 16 + 16
p32	64	32	32	32 + 32
tail	35	12	23	12 + 23
short	35	12	12	12 + 12 + 11
none	35	12	23	12 + 23, nothing kept (T=149)
all	35	12	23	12 + 23, everything kept (T=0)
long	200	32	32	6 × 32 + 8

ref.py prints the steps of its row. The longest step decides the size of a scratch array, so d and keep have MAXL elements, not PREF.

The test checks the step lengths. After the loop, d holds what the last step wrote, and the slots the last step did not reach still hold the step before. In the tail row the last step has 23 elements, so all of d comes from it. In the short row the last step has 11 elements, so d[11] still holds element 23, from the second step. ref.py computes d from the same rule, and cmp compares it with the PE's.

Conditions

keep[j] <- d[j] > T; stores one condition per element, and if (keep[j]) uses it. Carbide turns this into a comparison that sets the vector flags and a store that acts only on the elements whose flag is set. The condition must be stored per element, in a u1 scratch array indexed by j (see Pitfalls).

The cursor

let k in [0, N);
iterator wv = ∀k val[k];

iterator wv = ∀k val[k]; declares a memory iterator: a name for a walk over memory, here over val[0], val[1], and so on. It keeps its position, the cursor, between uses. wv[] <- d[j]; writes d[j] at the cursor and moves the cursor to the next element. Under the condition, only the elements whose flag is set are written, and the cursor moves only for them. The kept values therefore land side by side at the front of val.

The cursor's position is an address, wv.base. The kernel reads it before and after the loop, and the difference is the number of values written, because one xp is one word:

    xp start1 = wv.base;

    count[0] <- wv.base - start1;

An index variable cannot do this job: one c would serve every element of a step. With val[c] <- d[j]; c += 1; in the if, Carbide stops with unimplemented: codeblock statement of a per-lane if that is not a lane loop. The cursor's address is part of the store's descriptor, so the hardware advances it per element.

What Carbide made of it

The listing is test-tutorial/vstep_artefacts/vstep1.yeti (lesson 3 shows how to read it). Loop 1 is these instructions:

	movcfgi vs_len = 0x0040;  //@../vstep.w:52
	movcfgi vs_size = 0x410;  //@../vstep.w:52

main_bb1: 
	sub16 [T29] = [T02], [T1e];  //@../vstep.w:53
	lddwds T2b = [(__frame_slots+0x0004)];
	lt16 [VF0] = R8, [T1f];  //@../vstep.w:54
	[VF0]? select16 [T2a] = R0, R1, P0;  //@../vstep.w:52
	[VF0]? imov16 [T2b] = [T10];  //@../vstep.w:52
	stdwds [(__frame_slots+0x0004)] = T2b;
	jv main_bb1;  //@../vstep.w:52

• movcfgi vs_len = 0x0040 sets the vector-step length register to 64, the trip count.
• movcfgi vs_size = 0x410 sets the step-size register: max_len times 64 plus pref_len, here 16 × 64 + 16.
• sub16 computes one step of d. lt16 [VF0] = R8, [T1f] compares T (in R8) with each element of d and writes the flags VF0.
• The two instructions marked [VF0]? act only where the flag is set: select16 writes keep, and imov16 [T2b] = [T10] writes d through the cursor's descriptor T2b.
• Carbide keeps the cursor's descriptor in memory, in __frame_slots. lddwds loads it before the write and stdwds stores it back after, so the next step starts where this one stopped.
• The cursor's descriptor has .ua=0: its address moves only when the flag lets the write happen. The descriptor that reads d for the write, T10, has .ua=1: it moves on every element, written or not, so it stays in step with j.
• jv subtracts the step length from the remaining length, and jumps back while elements are left.

The descriptors show what i and j mean to the hardware:

vector a_src0_1 register(T02) = {.base=(a+0), .length=0, .stride=1, .step=1, .save=1, .vp=1, .ua=0, .rchoasjt=0, };
vector d_dst_0 register(T29) = {.base=(d+0), .length=0, .stride=1, .step=1, .save=0, .vp=1, .ua=0, .rchoasjt=0, };

.vp=1 puts a descriptor in vector-step mode. a, indexed by i, has .save=1: its address is kept at the end of a step, so the next step reads the next elements. d, indexed by j, has .save=0: it starts again at d[0] in every step.

Loop 2 has no movcfgi and no jv. It writes the loop index through a cursor under the condition, wi2[] <- i;, and that form has no hardware loop. Carbide accepted the attributes and built an ordinary loop that computes each step's length itself and then runs element by element. A second cursor is not the cause: writing an array element, wi2[] <- ix[i];, keeps the hardware loop. cycles.py's last line counts the hardware loops: hardware vector-step loops in the listing (jv): 1.

The cost

cycles.py prints these for each row; the test does not check them.

Loop	tutorial, 64 elements, steps of 16	per element	p32, steps of 32	per element
1: vector step, one cursor	89	1.39	65	1.02
2: also writes i, no hardware loop	2990	46.7	2883	45.1
3: ordinary loop with if	1153	18.0	1153	18.0

Loop 1 does the work in a step's few instructions. Loop 3 branches on every element. Loop 2 is the trap: it carries the attributes of a vector-step loop and runs 2.5 times slower than the plain loop. The listing is the only place that shows the difference.

Longer steps cost less per element, because each instruction has a fixed start cost. The datapath processes 128 bits per cycle and its pipeline is 3 cycles deep, so a step needs at least 24 16-bit or 12 32-bit elements to keep it busy. With a condition the limit is 32.

Which loops become hardware vector-step loops

The hardware vector-step loop forms only within these limits. Most forms outside them become ordinary loops without a diagnostic. Some of those give wrong results, and two forms are rejected; the table says which. Each was compiled and run:

Form	What happens
pref_len or max_len above 63	ordinary loop
a condition in the body, and a length above 32	ordinary loop (with pref_len(40), loop 1 took 2174 cycles for 64 elements)
max_len below pref_len	ordinary loop
the loop index written through a cursor under a condition, wi2[] <- i; in loop 2	ordinary loop
a comparison of an expression stored without a scratch array, keep[j] <- (a[i] - b[i]) > T;	ordinary loop, and wrong results (see Pitfalls)
a condition stored in a scalar, keep <- d[j] > T; with u1 keep;	ordinary loop, and wrong results (see Pitfalls)
a nested ∀ loop in the body	rejected: Invalid pragma placement. Pragma must be applied to the innermost loop.
a socket access (lesson 4) in the body	rejected (Streams are not supported in vector step loops.) unless the list has uthread.enable(off); with it, an ordinary loop that can wait forever on its last step (see Pitfalls)

To vectorize the inner loop of a nest, put the attribute list directly before the inner ∀, inside the outer loop's body.

A cursor that persists across calls

A memory iterator declared outside any block, at module scope, is set up once, and its cursor keeps its place across uses. Part 4 uses this:

let pass in [0, ∞);
let row in [0, 4);
let col in [0, 8);
iterator walk = ∀pass ∀row ∀col m[row][col];

function add_row(sp s) {
    ∀col walk[] <+- s * coef[col];
}

walk visits m row by row. Its outer range pass is infinite, so after the last element of m it starts again at m[0][0]. Each call of add_row consumes one row: walk[] <+- x adds x to the element at the cursor and moves the cursor on. main calls it five times, with s = 1 to 5. Calls 1 to 4 fill rows 0 to 3, and call 5 wraps round to row 0 again, which ends up as (1 + 5) * coef:

m[0] = 6, 12, 18, ..., 48
m[1] = 2,  4,  6, ..., 16
m[2] = 3,  6,  9, ..., 24
m[3] = 4,  8, 12, ..., 32

In the listing, walk is one descriptor with the shape {0, 4, 8} (0 is the infinite range) and .save=1, and each call is the single instruction fmacs [T07] = [T07], [T1b], Da;. The function does no address arithmetic for the row. The price is a rule that every caller must keep: each call must consume exactly the elements the walk expects next, in order. A call that consumed 7 elements would shift every later row by one.

When to use vector step

• A loop whose body is one operation over arrays is already one vector instruction (lesson 3). Vector step adds setup and gains nothing there.
• Use it for a body of several statements whose intermediate results you would otherwise store at full length, and for a body with a condition over more than 32 elements.
• Before you keep a vector-step loop: check the listing for movcfgi vs_len (or a store to the vector-step length register when the trip count is a run-time value) and jv; size every scratch array for max_len; measure it against the plain loop, with the same inputs and a clean build; and run the same reference check on both.

Run it

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

cd tutorial/ext-single-pe/vector-step
make TEST='*'

Each of the seven rows prints a PASS line. A row's log shows the steps and the cycle table:

grep -A4 -E '^steps|cycles.py' test-tutorial/make-log

steps: 16 + 16 + 16 + 16 | survivors: 36 of 64
...
1: vector-step, one cursor       89 cycles    1.39 per element
2: vector-step, writes i       2990 cycles   46.72 per element
3: ordinary loop               1153 cycles   18.02 per element
hardware vector-step loops in the listing (jv): 1

A row that fails prints FAIL, and its log ends in the cmp line that found the first difference between out-ref.bin and the PE's outputs. The outputs are concatenated in this order: val, count, d, val2, idx2, val3, m. To read one output, make the core file again, as lesson 4 shows; make deletes it when a row finishes:

cd test-tutorial
make -f ../Makefile VPATH=.. TEST=tutorial bench.map bench-sim.core
miget image=bench-sim.core map=bench.map symbol=pe.val decimal
cd ..

Pitfalls

• A scalar condition gives wrong results without an error. With u1 keep; and keep <- d[j] > T;, one register serves every element of a step. In tests with 35 elements and steps of 12 + 23, the register held the test of each step's last element. Each step whose last element passed copied its first 12 differences unfiltered, and each other step copied nothing. Store the condition in a u1 array indexed by j.
• A scratch array sized for pref_len overflows. With steps of 12 + 23 and xp d[n=12];, the last step's 11 extra values overwrote the array declared after d, and the outputs were still right, so nothing showed the damage. Size scratch arrays for max_len.
• The attributes do not guarantee a hardware loop. Most forms in the table above compile to an ordinary loop without a diagnostic. Check the table's restrictions, and the listing after every change to the body.
• Index the full-length arrays with i, and only scratch arrays with j. a[j] reads a[0] to a[S-1] in every step.
• Sockets in a vector-step loop. [[vectorize.pref_len(8), uthread.enable(off)]] before a loop that receives with d[j] <- rx[]; (a socket receive, lesson 4; uthread.enable(off) keeps it on the main thread instead of a microthread, lesson 5) compiles, but it is an ordinary loop that receives pref_len values in every step, also in a shorter last step. With 20 values and steps of 8, the last step waited for 8 values when 4 were left, and the PE stopped there. Receive into an array with an ordinary loop first, then run the vector-step loop over the array.
• Store an expression in a scratch array before you compare it. keep[j] <- (a[i] - b[i]) > T; compiled to an ordinary loop that set every flag to 1, while the same statement in a loop without the attributes gave the right flags. Loop 1 computes d[j] first and compares d[j].
• Give pref_len whenever you give max_len. max_len alone stops the compiler with an internal error.

Exercises

1. Change the tail row to MAXL=20 and predict the steps and the final contents of d. Run make clean and make TEST=tail, and compare.
2. Make loop 2 a hardware vector-step loop that still records the indexes. Add an input array xp ix[n=N]; that holds 0 to N-1 (write it in ref.py and load it with miset, like a), and write wi2[] <- ix[i]; in place of wi2[] <- i;. Check the listing for two jv instructions, and the cycle table for the cost.

Next

Topic — Memory: placing data, address(), and the memory budget shows where a kernel's arrays sit in the PE's memory, and how much room it has left.

References

• Vector step loops
• Memory iterators
• Named iterators (let)
• Booleans and predicates (u1)
• Base address access
• Execution domains and hardware instructions
• Vector operands (DSDs)