Lesson 5 — One core, many activities: parallel and FIFOs

In lesson 4, compute did one thing at a time: it received every value, then sent every square. Many kernels must do several things at once, such as receive two streams, compute, and send. A PE has one core. This lesson shows how a Tungsten program describes activities that run at the same time, and what the PE runs to carry them out.

What you will be able to do

• Run two loops at the same time on one PE with parallel.
• Pass values from one loop to the other through a FIFO, and say when a FIFO write or read waits.
• Describe what the core runs: tasks on its main thread, and microthreads.
• Write a kernel that never ends, and test it.

The program

Four PEs. xsend sends x = 1, 2, ..., N, and ysend sends y = N+1, ..., 2N. composition sends x + y² for each pair, and recv stores the results.

                       +-------------+
                       |    ysend    |  y=1
                       +-------------+
                              |  yrxcolor
                              v
 +-------+  xrxcolor   +-------------+  txcolor   +------+
 | xsend | ----------> | composition | ---------> | recv |  y=0
 +-------+             +-------------+            +------+
    x=0                      x=1                    x=2

The figure draws y growing upward, as lesson 4 explains. With N=4, x is 1, 2, 3, 4 and y is 5, 6, 7, 8, and recv.a ends as {26, 38, 52, 68}. The second row, n16, sends 16 values of each.

The code

The senders

Both senders run send.w:

xp param N;

socket tx;
hp a[n=N];  // each sender's values are loaded with miset

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

ref.py writes x and y to x.bin and y.bin, and the Makefile loads them into the two PEs' copies of a before the run, with miset (lesson 2):

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

One kernel, two PEs, two sets of data: xsend.a and ysend.a are different arrays in different memories.

compose.w

xp param F;

hp f[n=F];
hp fifo ff = {.mem=f};

socket xrx;
socket yrx;
socket tx;

parallel {
    forever {
        hp y <- yrx[];
        ff[] <- y * y;
    }
    forever {
        tx[] <- xrx[] + ff[];
    }
}

• forever { ... } repeats its body without end.
• hp fifo ff = {.mem=f}; makes a FIFO, a first-in first-out queue, that keeps its values in the array f. It holds at most F values, the length of f. ff[] <- v writes v at the back; ff[] reads and removes the value at the front. A write to a full FIFO waits until a read makes room, and a read from an empty FIFO waits until a write supplies a value.
• parallel { A B } runs its statements, called arms, at the same time. Here each arm is a forever loop. The first receives a y and writes y*y to the FIFO. The second receives an x, reads one square from the FIFO, and sends their sum. The statement after a parallel block runs when every arm has finished, so it would never run here.
• hp y <- yrx[]; declares a scalar inside the loop body and receives into it. A scalar declaration takes its first value with <- or =; only an array's {...} list needs =.

Why the program needs parallel: statements outside it run in order, and a forever loop does not finish. Without parallel, the second loop would never start. The first loop would fill the FIFO with F squares and then wait for room forever, and recv would get nothing.

Serial blocks

{ ... } and serial { ... } both group statements that run in order, one after the other. The program's top level runs in order too, so a block matters mainly inside parallel: an arm can be a block of several statements, which run in order inside that arm.

lock ready;
xp a[n=1];
xp b[n=1];
parallel {
    { a[0] = 1; signal ready; }
    { wait ready; b[0] = a[0]; }
}

This example also uses a lock, which lock ready; declares. An arm that executes wait ready; stops until another arm of the same parallel block executes signal ready;. Here the second arm copies a[0] only after the first arm has set it, and b[0] ends as 1. The reference lists the rules (Locks and Synchronization). A FIFO already orders a writer and a reader, so this lesson's program needs no lock.

The layout: rect and union

let ysend = rect(1 1 1 1)
ysend : code('send [tx:yrxcolor N:N])
ysend : paint(yrxcolor [C>D])
ysend : name('ysend)

rect(x y w h) is a w×h region with its corner at (x, y); rect(1 1 1 1) is the single PE at x=1, y=1. The four PEs are not in one row, so hstack cannot place them. Each is a rect at its own position, and union(ysend xsend composition recv) joins them as they are.

ysend is at y=1 and sends D, toward y-1. composition takes yrxcolor from U, the neighbour at y+1. composition has three colors: two that it receives and one that it sends.

What the hardware does

Tasks and the main thread

The core runs code as tasks. A task runs until it ends; then the core picks another task that is ready and runs it. Only one task runs at a time, on the core's main thread. A task becomes ready when a wavelet arrives for it (lesson 7), or when another task or a finished microthread activates it.

Microthreads

A microthread is one transfer instruction whose source or destination is one of the CE's input or output queues (lesson 4), or a FIFO. It starts as part of the current task. When it runs out of data or room, it sleeps, and the task goes on with its next instruction. When data or room arrives, the microthread wakes and goes on moving data. When it is done, it can activate a task. The core has 8 general microthreads, and 4 more that run only the umov copy instructions.

The main thread and the microthreads share the core's one pipeline. At each step the core picks one ready thread, by priority, to advance. Transfers that run at the same time therefore share the core's arithmetic and memory accesses; they do not add to them.

A transfer on the main thread works differently. When a receive on the main thread finds its input queue empty, or a send finds its output queue full, the main thread is suspended until the queue is ready. While it is suspended, no other task can start; microthreads keep running.

What Carbide makes of compose.w

Carbide divides each arm into transfers and the work between them. Most transfers become microthreads, and each one's completion activates a task that does the next step and starts the next transfer. One transfer stays on the main thread, as the table shows. This table follows the listing test-tutorial/compose_artefacts/compose3.yeti:

Task	What it does	Activated by
main, ID 8	activates tasks 13 and 14, and ends	ready at the start
main_bb1, ID 13	starts the receive of one y as a microthread	task 8
main_bb4, ID 9	squares y, and starts the FIFO write as a microthread	the end of the receive
main_bb5, ID 10	jumps back into task 13's code, which starts the next receive	the end of the FIFO write
main_bb6, ID 14	starts the FIFO read as a microthread	task 8
main_bb9, ID 11	reads one x on the main thread, adds, and starts the send as a microthread	the end of the FIFO read
main_bb10, ID 12	jumps back into task 14's code, which starts the next FIFO read	the end of the send

The receive of y in task 13 is one instruction:

	fmov16 [T20] = [T10];  //@../compose.w:12

T10 describes the input queue of yrx, which the listing declares as:

recv yrx_r_X0  = { .length=1, .utid=0, .transform=0, .fa=0, .fi=0, .lp=1, .terminate=0, .upr=HIGH, .qid=0, .au=ACTIVATE, .ondone=9, };

.length=1 moves one value. .upr set to anything but NONE makes the transfer a microthread, and HIGH or LOW is its priority; the FIFO's .rupr and .wupr, both LOW here, work the same way. .au=ACTIVATE, .ondone=9 activates task 9 when the transfer is done.

The transfer that stays on the main thread is in task 11: the x that the addition reads directly from the input queue, declared with .upr=NONE. While it waits for x, no other task can start. Another build may divide the work differently; the results do not depend on it.

FIFOs

A FIFO is the array f in memory plus a read position and a write position, which the hardware keeps. Each position wraps to the start of f after its last element. In the n16 row, 16 squares pass through a 4-element FIFO, so both positions wrap around f four times. The row checks wraparound. It is not built to make the FIFO full: the two streams arrive at the same rate, and nothing slows the second arm on purpose.

The wait for a full or an empty FIFO is forever only when no other activity can read or write the FIFO. This single-PE program writes six values into a four-element FIFO in serial code:

xp f[n=4];
xp fifo ff = {.mem=f};
xp out[n=6];
xp mark[n=2] = {0};
{
    let i in [0, 6);
    mark[0] <- 1;
    ∀i ff[] <- i + 1;
    mark[1] <- 2;
    ∀i out[i] <- ff[];
}

The markers start at 0 and are written with nonzero values, so a 0 shows that its write has not run. The run ends with f = {1, 2, 3, 4} and mark = {1, 0}. The fifth write waits for a read that no other activity will make, so mark[1] is never written.

Programs that never end

compose.w never ends, and the test does not wait for it. The simulator runs until the cycle cap, CYCLES ?= 2000 in the Makefile, and the test then reads recv.a from memory. The n16 row's last memory write comes about 550 cycles after the start. If you raise N, raise the cap with CYCLES= in the row of test.rc. A cap that is too small leaves recv.a partly written, and the test fails.

Run it

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

cd tutorial/main-2-between-pes/05-parallel-and-fifos
make TEST=tutorial

A pass prints a line ending in PASS tutorial [ N=4 F=4 ARCH=sdr ]; the results are {26, 38, 52, 68}. make TEST=n16 runs the second row, whose results go from 290 to 1040. The listing of composition's program is in test-tutorial/compose_artefacts/.

Pitfalls

• Two forever loops without parallel. The second never starts. With this program, recv.a stays {0, 0, 0, 0}.
• A FIFO that fills in serial code. Writing more values than it holds, with no other activity reading, stops the PE at that write; so does reading more values than were written.
• A cycle cap that is too small. A forever program has no end to wait for, so a short cap reads results that are not complete yet.

Exercises

1. Set F=1 in both rows of test.rc, run make clean and make TEST='*', and predict the results first. They do not change: after each write the FIFO is full, so each write after the first must wait until the second arm has read the square before it.
2. Make composition send x² + y² instead. Give x an arm of its own that squares it into a second FIFO, and make a third arm send the sum of the two FIFOs' values. Change ref.py to match, and run both rows.

Next

Lesson 6 — Blocking, buffering and deadlock

References

• FIFOs
• Parallel and serial blocks
• Forever blocks
• Locks and synchronization
• rect() and union()
• Architecture notes: Tasks, Microthreads, The CE's Queues