Skip to main content

Topic — Locks, until conditions, rings and timer tasks

Needs: Lesson 5 — One core, many activities: parallel and FIFOs, Lesson 7 — Tasks: code that runs when a wavelet arrives.

The kernels of the main lessons know how many values they receive. This topic is about activities on one PE that do not: a message whose length the receiver learns only when it ends, a FIFO that holds however many values a loop left in it, a stream that never ends, and code that runs at a fixed interval rather than when data arrives. It also shows how to order two arms of a parallel block with a lock.

What you will be able to do​

  • Receive a message of unknown length that ends with a control wavelet, and remove the control wavelet from the queue.
  • Count the values in a FIFO, and read it until it is empty.
  • Order two arms of a parallel block with a lock, and know what Carbide does with the lock.
  • Keep the latest values of an endless stream in a ring.
  • Run code at a fixed interval with a timer task, and know when it can run.

The program​

Two PEs in a row share one color, c, from clock to sink.

+-----------------------------+       c       +-----------------------------------+
| clock  (x=0)                | ------------> | sink  (x=1)                       |
| main:  sends 100 .. 99+K,   | [C>R]   [L>C] | 1. until control: message -> FIFO |
|        then an end marker   |               |    count it, read it out          |
| timer task, every ~216      |               | 2. parallel + lock: first B       |
| cycles: sends 0, 1, 2, ...  |               |    samples, then their sum        |
+-----------------------------+               | 3. ring: the latest R samples     |
                                              +-----------------------------------+
  • clock sends a message of K values, 100 to 100+K-1, and then a control wavelet that marks its end. From then on its timer task sends a sample at a fixed interval: 0, 1, 2, and so on.
  • sink does not know K. It receives the message until the end marker, counts it and copies it out. It then receives the first B samples and adds them up, and keeps the latest R samples in a ring for as long as the run lasts.

The timer never stops, so the run ends at the cycle limit of 20,000, as forever programs do (lesson 5). check.py then reads both PEs' memories. For the tutorial row (K=5, MAX=16, B=4, R=8) it expects the message 100 … 104, a count of 5, the end marker 0x002a0000, the first samples 0, 1, 2, 3 with the sum 6, and a ring that holds 8 consecutive sample numbers.

The clock: clock.w​

xp param K;
socket tx;

u16 tsc[1] address(0x7b30);
u16 tsc_control[1] address(0x7b34);
xp ticks[n=1];
xp smem[n=4];
xp ring stamps = {.mem = smem};

main {
    tsc_control[0] <- tsc_control[0] | 4;
    ∀i in [0, K) tx[] <- 100 + i;
    tx[] <- control(0x002a0000);
}

[[timer(on), timer.limit(200)]]
forever {
    tx[] <- ticks[0];
    stamps[] <- tsc[0];
    ticks[0] += 1;
}

tx[] <- control(w); sends the 32-bit word w as a control wavelet, a wavelet with its control bit set. A router reads a control wavelet's word as commands for its switches (lesson 10); here all the commands are zero, which means no operation, so the routers pass it on like data. Bits 21 to 16 are the task ID that a control wavelet carries (lesson 7). This program starts no task with it; 42 (0x2a) only makes the word easy to recognise. The other half of the file, the timer, is explained below.

Receiving until an end marker: until control​

    i in [0, MAX) until control ff[] <- rx[];
    cw[0] = (u32)rx[];
    n[0] = ff.count;
    until empty i in [0, MAX) msg[i] <- ff[];

until control ends the loop when a control wavelet reaches the front of the socket's input queue, or after MAX values, whichever comes first. The loop writes each value into the FIFO ff, whose array fmem has MAX elements.

The control wavelet that ends the loop is not removed from the queue. The next read on the socket receives it as data. cw[0] = (u32)rx[]; removes it with one 32-bit read, and keeps its word: check.py finds 0x002a0000 in cw.

The full row sends K=16, exactly MAX. The loop then ends because its count runs out, before it sees the marker, and the marker is still waiting in the queue. The same 32-bit read removes it, so the same code handles both cases.

In the listing, test-tutorial/sink_artefacts/sink2.yeti, the receive's descriptor has its terminate-on-control bit set, .terminate=1:

recv rx_r_X0 register(T13) = { .length=16, .utid=0, .transform=0, .fa=0, .fi=0, .lp=1, .terminate=1, .upr=HIGH, .qid=0, .au=ACTIVATE, .ondone=9, .ta=ACTIVATE, .onterm=9, };

.upr=HIGH makes the loop one microthread (lesson 5). .ondone=9 and .onterm=9 say that when it finishes, by count or by the control wavelet, it activates task 9, which continues with the next statements.

Counting and draining a FIFO: ff.count and until empty​

ff.count is the number of values in the FIFO: 5 in the tutorial row, 0 in the empty row, 16 in the full row. It compiles to one instruction, qdepth R2 = [T14];.

until empty i in [0, MAX) msg[i] <- ff[]; reads the FIFO until it is empty, at most MAX times. It reads exactly the values the message left, without using the count. In the empty row the FIFO is empty from the start, and the loop writes nothing. A plain loop of MAX reads would wait forever for values that never come (lesson 5).

The FIFO's descriptors show both behaviours. Its read side has .ra0=1, .ra1=0: an empty FIFO ends the instruction. Its write side has .wa0=0, .wa1=1: a full FIFO makes the writer wait.

Ordering two arms: a lock​

    parallel {
        {
            wait got;
            ∀i in [0, B) total[0] <+- first[i];
        }
        {
            i in [0, B) first[i] <- rx[];
            signal got;
        }
    }

lock got; declares the lock. wait got; holds back the rest of its arm until another arm of the same parallel block has executed signal got;. Here the first arm adds up first, and the lock makes it wait until the second arm has received the B samples.

What Carbide makes of it: it runs these two arms on the main thread, one after the other. Without a lock it keeps the order you write, so the sum would run first, on an empty first. With the two lock lines removed, total is 0. With the lock, Carbide puts the signalling arm first: in the listing the receive of first (source line 29) comes before the sum's loop (line 26). The receive also runs on the main thread here, .upr=NONE.

The lock's rules, which Carbide checks:

  • a parallel block waits on a lock at most once;
  • the wait must not be inside a loop or a branch of its arm;
  • the signal must come from an arm of the same block.

An arm that never ends after its signal. Carbide runs the whole signalling arm before the waiting arm, not just the part before signal. With the endless ring receive of the next section placed in the second arm after signal got;, the first arm never ran and total stayed 0. That is why the ring receive comes after the parallel block.

Keeping the latest values: a ring​

xp hmem[n=R];
xp ring hist = {.mem = hmem};
    i in [0, ∞) hist[] <- rx[];

A ring is a circular buffer over an array, like a FIFO, but it has no full or empty state. A write goes into the next slot, wraps to slot 0 after the last one, and never waits: it overwrites the oldest value. The array therefore always holds the latest R values received.

i in [0, ∞) is an endless loop: the receive's length is 0x7fff, the length the hardware treats as infinite. Neither of the obvious alternatives works here. A FIFO would fill after R values and stop the receive. An array written with a[i] <- rx[] would be written past its end, into whatever follows it in memory.

The ring's first value is sample B, so sample m lands in slot (m - B) mod R. check.py checks that hmem holds R consecutive sample numbers in those slots, for example 84, 85, 86, 87, 88, 89, 90, 91 after 92 ticks. Which samples these are depends on how many ticks the run had time for; the check accepts any R consecutive ones.

To read a ring in a program, declare a second ring over the same array, xp ring rd = {.mem = hmem};, and read rd[]. Each ring has its own position, and both start at slot 0, so the reader does not follow the writer. One ring cannot be both written and read.

Running code at an interval: a timer task​

[[timer(on), timer.limit(200)]]
forever {
    tx[] <- ticks[0];
    stamps[] <- tsc[0];
    ticks[0] += 1;
}

timer(on) on a forever loop makes the loop's body a task, the timer task (task 30). When execution reaches the statement, Carbide starts the PE's 16-bit timer at timer.limit, 200 here. The timer counts down once per cycle, and when it reaches 0 the timer task becomes ready. The body runs, and Carbide starts the timer again at its end. The listing of clock shows the start:

	imov16 R4 = 0x00c8;  //@../clock.w:17
	st16 [__tungsten_timer_config] = R4;  //@../clock.w:17

0x00c8 is 200, and __tungsten_timer_config is the timer's register, at address 0x7e03.

The body writes the time of each tick into the ring stamps, and check.py prints the intervals between the last four: 216 cycles, the limit plus the time the body takes. The test does not check them.

When the timer task can run:

  • It does not interrupt another task. A task runs until it ends (lesson 5), so the timer task starts only when nothing else is running. A long task delays it.
  • It starts when execution reaches the statement. Here main sends the message first, and only then does the timer start.
  • Nothing after it runs. The timer statement is a forever loop, so the code after it in the program never runs. Write it last.

The rules for the timer statement:

  • timer.limit is required, from 1 to 65535.
  • A program has one timer statement, outside any function, and no break or continue may leave its loop.
  • The body must not carry a scalar variable from one run to the next. Keep such state in an array element, as ticks[0] does.
  • A loop in the body that uses its iterator, such as j in [0, 7) b[j+1] <- b[j] + j;, fails to compile with [builtin-setjt] precedes the branch into the loop its iterator ends. So did a while loop placed after the timer statement.
  • timer.repeat(on) is meant to restart the timer at the start of the body. The period is the same with or without it.

What the hardware does​

  • Terminate on control. A descriptor that reads from an input queue has a terminate-on-control bit. With it set, the instruction ends when a control wavelet is at the front of the queue and values remain to be read. The control wavelet stays in the queue. If the instruction reads its last value first, it ends normally and does not look at the next wavelet. Either way the instruction can activate a task when it ends.
  • FIFO descriptors. A FIFO is memory with a read position and a write position. Each side's descriptor says what happens when the FIFO is empty or full: wait, end the instruction, jump, or stop with a fault. A read that ends on empty is until empty.
  • Rings. A ring is the same circular buffer with no full or empty state.
  • The timer. The PE has one interrupt timer, a 16-bit register at 0x7e03 that counts down. When it reaches 0, task 30 becomes ready. Tasks run one at a time, each to its end (see Tasks).

Run it​

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

cd tutorial/ext-single-pe/locks-and-timers
make TEST='*'

Each of the three rows prints a PASS line. The check is at the end of each row's log:

sed -n '/check.py [0-9]/,$p' test-tutorial/make-log
message: 5 values [100, 101, 102, 103, 104], end marker 0x002a0000: right
first 4 samples [0, 1, 2, 3], total 6: right
ring after 92 ticks: [84, 85, 86, 87, 88, 89, 90, 91], newest 91: right
timer period, last three ticks: [216, 216, 216] cycles

A failing row prints FAIL, and the line that says WRONG shows which part went wrong.

Pitfalls​

  • The control wavelet stays in the queue. Read it with one 32-bit read, assigned to a variable: cw[0] = (u32)rx[];. A bare (u32)rx[]; statement stops the compiler with an internal error. A 16-bit read takes only half of it, and the other half arrives as data.
  • A message longer than the loop. With K=17 and MAX=16, the loop stopped after 16 values. The 32-bit read then took the 17th value (116) and the low half of the marker, and the marker's high half, 42, arrived as the first sample.
  • An endless arm after a signal. The waiting arm then never runs. Put the endless part after the parallel block.
  • A lock does not make arms concurrent. Carbide decides how the arms run; here it ran them one after the other. Check the listing for .upr=HIGH where you need a transfer to overlap other work.
  • The timer statement must come last. Code after it never runs, and a loop after it does not compile.
  • The timer waits for running tasks. Its period is a lower bound, not a guarantee.

Exercises​

  1. Add a row long K=17 MAX=16 B=4 R=8 ARCH=sdr. Predict what check.py reports, run make TEST=long, and explain each line that says WRONG, the ring's included. Then change the row so that a message of up to 32 values works, and rerun.
  2. Remove the two lock lines from sink.w, predict total, and check. Then put them back and swap the two arms; predict whether the result changes.

Next​

This is the last topic of the group. The next group, Algorithms, starts with Topic — Matrix multiplication across PEs, which multiplies two matrices streamed across a grid of PEs, as a systolic array.

References​

Source code​

The Tungsten and Paint files of this example, as the toolset installs them under share/tutorial/ext-single-pe/locks-and-timers/. Select a line number to link to that line.

Explorer · 3 files

Loading clock.w…

Tungsten380 BDownload clock.w