Lesson 2 — Values, control flow and functions

This lesson writes ordinary code on one PE: scalars and arrays of several types, if and while, and functions kept in a module of their own. It also loads the PE's input before the run, and shows the four places where this program's results differ from what C would give.

What you will be able to do

• Choose an integer or floating-point type, and know how many memory words each value takes.
• Write if/else if/else chains, while loops and functions, and import your own module.
• Put input data into a PE's memory with miset before the run, and read outputs by symbol path with miget.
• Predict floor division, the logical >>, && and comparisons used as values, which all differ from C.

The program

numbers.w runs on one PE. Its input is an array x of N integers between 1 and 99, which ref.py draws at random, seeded with N, so each row gets the same values on every run. miset writes them into the image. For each x[i] the kernel computes:

Output	What it holds
steps[i]	the number of Collatz steps from x[i] to 1: halve an even value, take 3v + 1 of an odd one
root[i]	the integer square root of x[i]
kind[i]	0 below 10, 1 below 50, 2 otherwise
q[i]	(x[i] - 50) / 4
sh[i]	(x[i] - 50) >> 2
big[i]	the value of the comparison x[i] > 50

It also computes three single values: oddbig, the count of odd values above 50; tests, the number of times the function is_odd ran; and mean, the mean of x in SP.

ref.py --x.bin--> miset --> +-------------------+ --> miget --> x, steps, root, kind,
                            | PE: numbers.w     |              q, sh, big, tests,
                            | (imports mymath)  |              oddbig, mean
                            +-------------------+

ref.py computes the same outputs in Python, and the test compares them byte for byte. For the tutorial row (N=12) the results are:

x	61	25	97	94	7	19	20	18	58	35	48	23
steps	19	23	118	105	16	20	7	20	19	13	11	15
root	7	5	9	9	2	4	4	4	7	5	6	4
kind	2	1	2	2	0	1	1	1	2	1	1	1
q	2	-7	11	11	-11	-8	-8	-8	2	-4	-1	-7
sh	2	16377	11	11	16373	16376	16376	16376	2	16380	16383	16377
big	-1	0	-1	-1	0	0	0	0	-1	0	0	0

and oddbig = 2, tests = 12, mean = 42.083336.

Types

A memory word is 16 bits. These are the types a kernel uses, integers first:

Type	Holds	Words per value
xp	16-bit signed integer; the usual type for integers and indices	1
s16	16-bit signed integer; it computes as xp does	1
u16	16-bit unsigned integer	1
s32	32-bit signed integer	2
u32	32-bit unsigned integer	2
u1	a truth value, 0 or 1	1 in an array
hp	IEEE half precision (16-bit float)	1
ep	19-bit float: an 8-bit exponent and a 10-bit mantissa, so HP's precision with SP's range	2
sp	IEEE single precision (32-bit float)	2

A 32-bit value starts at an even word address. An ep value is stored in the same two words as an sp; it exists because the hardware multiplies ep values faster than sp values. The data types section of the reference lists the storage-only 64-bit types as well.

A floating-point literal can carry its type: 0.0:sp is an SP zero. A cast converts a value: (sp)x[i] is the SP value of the integer x[i].

The module: mymath.w

function collatz(xp v) -> xp {
    xp s = 0;
    while (v != 1) {
        if ((v & 1) == 0) v = v >> 1;
        else v = 3 * v + 1;
        s = s + 1;
    }
    return s;
}

function isqrt(xp v) -> xp {
    xp r = 0;
    while ((r + 1) * (r + 1) <= v) {
        r = r + 1;
    }
    return r;
}

• function name(type parameter, ...) -> type { ... } defines a function, and return gives its result.
• A while body must be in braces. while (v != 0) v = v - 1; is a syntax error: invalid syntax in statement.
• v >> 1 halves v here, because v is always positive.
• A scalar parameter is a copy. collatz changes its own v, and the caller's x[i] keeps its value: the test reads x back after the run and finds the input unchanged.

import mymath; at the top of numbers.w makes these functions part of the kernel. The compiler looks for mymath.w in the kernel's own directory and in the directories that Paint's lib= names; the Makefile passes lib=.., the lesson directory.

The kernel: numbers.w

import mymath;

xp param N;

xp x[n=N];
xp steps[n=N];
xp root[n=N];
xp kind[n=N];
xp q[n=N];
xp sh[n=N];
xp big[n=N];
xp tests[n=1] = {0};
xp oddbig[n=1] = {0};
sp mean[n=1];

function is_odd(xp v, xp count[]) -> xp {
    count[0] = count[0] + 1;
    return v & 1;
}

main {
    ∀i in [0, N) {
        steps[i] = collatz(x[i]);
        root[i] = isqrt(x[i]);
        if (x[i] < 10) kind[i] = 0;
        else if (x[i] < 50) kind[i] = 1;
        else kind[i] = 2;
        q[i] = (x[i] - 50) / 4;
        sh[i] = (x[i] - 50) >> 2;
        big[i] = x[i] > 50;
        xp hit = x[i] > 50 && is_odd(x[i], tests) == 1;
        oddbig[0] = oddbig[0] + hit;
    }
    sp total = 0.0:sp;
    ∀i in [0, N) total = total + (sp)x[i];
    mean[0] = total * (1.0:sp / (sp)N);
}

• x has no initializer; miset fills it before the run (below).
• is_odd takes an array parameter, xp count[]. An array parameter names the caller's array: count[0] = count[0] + 1 adds 1 to the caller's tests.
• main { ... } is a named block. The name is only a label, and the block runs where it stands.
• ∀i in [0, N) { ... } declares its iterator inline and runs the whole block for each i.
• if, else if and else form a chain, as in C: exactly one of the three assignments to kind[i] runs.
• xp hit = ...; declares a scalar inside the loop body.
• 1.0:sp / (sp)N depends only on the parameter N, so Carbide computes it at compile time and mean costs one multiply.

This lesson writes assignments with =; lesson 1's <- compiles to the same code.

Where the results differ from C

The program meets four rules where Tungsten differs from C. Each shows in its outputs:

Code	x[i]	Tungsten	C	Rule
q[i] = (x[i] - 50) / 4	25	-7	-6	Signed division of run-time values rounds toward minus infinity, as Python's // does.
sh[i] = (x[i] - 50) >> 2	25	16377	-7	At run time >> shifts in zeros, even on a negative xp. For a negative value use /, or the arithmetic shift x>>: (x[i] - 50) x>> 2 is -7.
big[i] = x[i] > 50	61	-1	1	A comparison used as a value is -1 when true.
x[i] > 50 && is_odd(x[i], tests) == 1	all 12	tests = 12	tests = 4	&& and || always evaluate both operands, and give 0 or 1.

The last row means that && does not guard its right side: is_odd ran for every element, not only for the four above 50. A C idiom such as i < N && a[i] > 0 still reads a[i] when i is N. The value of && is 0 or 1, not the -1 of a bare comparison, so hit adds 1 to oddbig for each odd value above 50.

The Tungsten overview's Rules That Differ from C lists these rules and the others, each with the value it gives.

Input and output: miset and miget

bench.paint names the PE's region:

let pe = tile()
pe : code('numbers [N:N])
pe : name('pe)

name('pe) puts the region's name in front of each kernel symbol in bench.map, so the kernel's x is pe.x:

pe.x                  [ n<12             ] ( 0x1+n        0 0 )

The Makefile replaces the usual rule for bench.img with one that writes x into it:

out-ref.bin:
	python3 ../ref.py $(N)

x.bin: out-ref.bin

bench.img: bench.obj x.bin bench.map
	cp $< $@
	miset image=$@ out=$@ map=bench.map symbol=pe.x order="n" data=x.bin

out-%.bin: bench-%.core bench.map
	rm -f $@
	for s in x steps root kind q sh big tests oddbig mean; do miget image=$< map=bench.map symbol=pe.$$s data=$$s.bin; cat $$s.bin >> $@; done

• ref.py writes the input x.bin and the expected out-ref.bin.
• miset copies the values of x.bin into pe.x in the image. order="n" says that the file holds the elements in the order of the dimension n.
• miset edits the image file before the simulator starts. The PE starts with x already in its memory; nothing is transferred while the program runs.
• miget reads each output by its symbol path from the final core and appends it to out-sim.bin, in the order ref.py writes them.

What the hardware does

The CE has 16 general registers of 16 bits each, and a 32-bit value takes two of them. This kernel is scalar code: each element runs the Collatz and square-root loops one instruction at a time, on registers, with compares and branches. Lesson 1's loop was one instruction for the whole array; this one runs every step for every element.

The compiler's listing (lesson 3 shows where it is) makes two of the rules above visible. The division by 4 and the shift by 2 compile to different instructions, an arithmetic and a logical shift right:

	sar16 [T2a] = R5, R0;  //@../numbers.w:28
	...
	slr16 [T2b] = R5, R0;  //@../numbers.w:29

Each listing line ends with the source line it came from. Lines from a function say where it was called: //@../mymath.w:4[collatz] < @../numbers.w:23 is mymath.w line 4, inside collatz, called from line 23 of numbers.w. Carbide copied these small functions into each place that calls them, so a call needs no call instruction, but each call adds a copy of the function's code to the PE's memory. A larger function called from more than one place usually becomes a subroutine instead, which each call jumps to. The reference's Inline Functions section gives the exact rules.

Run it

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

cd tutorial/main-1-one-pe/02-values-and-control
make TEST=tutorial

A passing test prints a PASS line, as in lesson 1. The Makefile's for loop leaves each output in its own file in the row's directory, such as test-tutorial/q.bin. To look at one output:

python3 -c "import numpy as np; print(np.fromfile('test-tutorial/q.bin', dtype=np.int16))"

It prints the q row of the table above. miget's decimal output is unsigned, so it would show -7 as 65529. A failing test prints FAIL, and cmp in test-tutorial/make-log gives the first byte that differs. out-sim.bin holds the outputs in the order of the Makefile's for loop, so the byte offset tells you which output differs.

The n40 row runs the same program on 40 values. Scalar loops are slow: its last write to memory happened at about cycle 18,700, so the Makefile sets the cap at cycles=30000.

Pitfalls

Besides the four differences from C above and the braces of while:

• A function call cannot be the condition of an if or a while. Carbide stops with function calls are not supported in expression site [if.cond]. Compute the value into a variable first, as hit does.
• Arithmetic on literals and param values follows C. The compiler computes -7 / 2 as -3 and -25 >> 2 as -7, and the same for a param such as N, while at run time p / 2 with p = -7 is -4, and p >> 2 with p = -25 is 16377. Test a division or a shift on run-time values, not on constants.
• A comparison reads as 1 only as an operand of + or -. (a < b) + 0 is 1, but (a < b) * 3 is -3. To get 0 or 1 everywhere, store the comparison in a u1 first.
• A function that writes to an array argument changes the caller's array. Copy the array first if the caller needs the old values.

Exercise

Add a function gcd(xp a, xp b) -> xp to mymath.w that finds the greatest common divisor by repeated subtraction: while a and b differ, subtract the smaller from the larger. Add an output g[i] = gcd(x[i], 36), extend ref.py with math.gcd, add g to the Makefile's miget list in the same position as in ref.py, and run make clean and the test.

Next

Lesson 3 — How a PE runs a loop measures how long loops take, and shows which ones become a single instruction.

References

• Data types
• Typed literals and casts
• If / else if / else
• While loops
• Expressions and operators
• Functions
• Imports
• Rules That Differ from C
• miset and miget
• Naming regions: name()