Lesson 6 — Blocking, buffering and deadlock

Any send can wait: lesson 4 said that a send waits when there is no room for its value. This lesson measures how much room there is between two neighbouring PEs, shows a program that hangs because the room runs out, and shows how to write the program so that it cannot hang.

What you will be able to do

• Say when a send or a receive waits, and what else stops while it waits.
• Account for the buffering between two neighbouring PEs.
• Recognize a deadlock in a test result.
• Remove a deadlock with parallel or with a different order, and say what more buffering can and cannot do.
• Check a protocol with a communication ledger.

The program

Two PEs swap arrays. Each fills mine with BASE + i, sends its N values to the other PE, and receives the other's N values into theirs. left has BASE 1000 and right 2000. Each direction has its own color.

                 ab:  [C>R] on left, [L>C] on right
   +------+  ------------------------------>  +-------+
   | left |                                   | right |
   +------+  <------------------------------  +-------+
                 ba:  [C>L] on right, [R>C] on left

PAR chooses how each PE runs its send and its receive:

Row	N	PAR	What happens
tutorial	16	0	send all, then receive all; both PEs finish
par	512	1	send and receive at the same time; both PEs finish
hang	512	0	send all, then receive all; both PEs wait forever, and the test checks that they do

The code

exchange.w:

xp param N;
xp param BASE;
xp param PAR;

socket tx;
socket rx;

xp mine[n=N];
xp theirs[n=N] = {0};
xp started[1] = {0};
xp done[1] = {0};

let i in [0, N);
∀i mine[i] <- BASE + i;
started[0] <- 1;
if (PAR == 1) {
    parallel {
        ∀i tx[] <- mine[i];
        ∀i theirs[i] <- rx[];
    }
} else {
    ∀i tx[] <- mine[i];
    ∀i theirs[i] <- rx[];
}
done[0] <- 1;

PAR is a parameter, so the compiler knows its value and keeps only one branch of the if. started and done are progress markers: started[0] is set just before the exchange, and done[0] just after it. theirs and both markers start at 0, and every value written to them is nonzero, so a 0 shows that the write has not run.

Both PEs run the same kernel with different bindings, in bench.paint:

let left = tile()
left : code('exchange [tx:ab rx:ba N:N BASE:1000 PAR:PAR])
left : paint(ab [C>R])
left : paint(ba [R>C])
left : name('left)

let right = tile()
right : code('exchange [tx:ba rx:ab N:N BASE:2000 PAR:PAR])
right : paint(ba [C>L])
right : paint(ab [L>C])
right : name('right)

left's tx is right's rx, and the other way round.

The Makefile reads started, done and theirs from both PEs, and check.py prints them and compares them with the row's EXPECT value. EXPECT=done, the default, requires both markers set and theirs holding the other PE's values. EXPECT=hang requires started set, theirs untouched and done still 0 on both PEs: the program reached the exchange and stopped inside it.

What the hardware does

When a transfer waits

With PAR=0, the send and the receive run on the main thread; the listing declares both with .upr=NONE. A send on the main thread that finds its output queue full suspends the main thread until there is room. A receive that finds its input queue empty suspends it until a value arrives. While the main thread is suspended, no new task starts on that PE, and microthreads keep running.

How much the path holds

Between left's core and right's core, the values of color ab can wait in four places:

Place	Wavelets
left's output queue	8
the buffer of ab in left's router	4
the buffer of ab in right's router	4
right's input queue	16
total	32

32 wavelets hold 64 xp values. The PAR=0 exchange finishes with N=64 and hangs with N=65. At 64, each send fits completely into the path, each PE then reaches its receive, and the receives empty the path. At 65, the last value finds no room.

The input queue's size is not fixed. A core has 8 input queues of 4 or 8 wavelets. When a kernel has at most four receive sockets, Carbide gives each one a doubled queue, which borrows the storage of the next queue. This kernel's only receive socket gets queue 0, 8 wavelets doubled to 16. A kernel with five receive sockets gets no doubling. So the amount of buffering depends on the kernel and on the compiler's choices. Never write a program that is correct only because the buffering is large enough.

Deadlock

In the hang row each PE sends 512 values. After 32 wavelets, both paths are full. left's send waits for right to receive, and right receives only after its own send has finished. right is in the same position. Neither PE can move again. This is a deadlock: a cycle of activities in which each waits for the next.

Nothing reports a deadlock. The simulator runs to the cycle cap (CYCLES ?= 4000 in the Makefile), and the test reads memory then. In the hang row check.py prints:

left : started=1 done=0 theirs: 0 of 512 words written
right: started=1 done=0 theirs: 0 of 512 words written
expected: hang; as expected

That is how a hang looks in any test: the run ends at the cap, markers written before the stall are set, markers after it are not, and arrays that should have been filled are empty or only partly written. A row that expected the program to finish fails. Here, started set and theirs untouched show that both PEs stopped between the two: in the send.

With parallel

With PAR=1, the send and the receive are two arms of a parallel block, and each runs as a microthread. The listing declares both with .upr=HIGH. The receive drains the input queue while the send waits for room, so neither path stays full.

The listing also shows how the statement after the block waits for both arms:

send tx_w_X0 register(T21) = {.length=512, .utid=0, .upr=HIGH, .qid=0, .transform=0, .lp=1, .control=0, .fs=0, .xc=0, .doneaction=ACTIVATE, .ondone=9, };
recv rx_r_X3 register(T00) = { .length=512, .utid=1, .transform=0, .fa=0, .fi=0, .lp=1, .terminate=0, .upr=HIGH, .qid=0, .au=UNBLOCK, .ondone=9, .rch_sjt=1, };

The end of the send activates task 9, and the end of the receive unblocks it. A task runs only when it is both activated and unblocked, and task 9 is the code that sets done[0].

Tasks wait too

A suspended main thread starts no new task. Lesson 7 shows kernels whose code runs as tasks when wavelets arrive. On such a PE, a task that waits in a send stops every other task until the send can go on.

The three fixes

Each fix uses something an earlier lesson taught.

1. Run the receive while the send waits. That is parallel (lesson 5), as in the par row.
2. Change the order. If right receives first and sends second, while left sends first and receives second, right's receive drains left's values and the cycle is gone, for any N. Lesson 4's compute already works this way: it receives everything before it sends. Exercise 2 builds this version.
3. Buffer in memory. More buffering only moves the size at which a program hangs. A FIFO in memory (lesson 5) can hold far more than the fabric, but only an activity that runs while the send waits can fill it, so it is fix 1 with a buffer added. In lesson 5, the FIFO lets the first arm run ahead of the second.

Sending in chunks small enough to fit into the path, and receiving after each chunk, also works, but only as long as every chunk fits. That depends on the buffering, which the previous section says not to rely on.

Check a protocol with a ledger

Before running a program with several streams, write one row per stream:

Stream	Producer	Route	Consumer	Count	Order on the producer's PE
ab	left.tx	[C>R] on left, [L>C] on right	right.rx	N values	send, then receive
ba	right.tx	[C>L] on right, [R>C] on left	left.rx	N values	send, then receive

Then check:

1. Every send has a consumer, or a route that passes it on to one.
2. Every receive is supplied with all the values it waits for.
3. The counts match exactly, in values and in their width: one 32-bit send needs one 32-bit receive.
4. Every cycle of waiting is broken by an order or by concurrency. Buffering alone does not break it.

The ledger above fails check 4 when PAR=0. left's send waits for right's receive, which comes after right's send, which waits for left's receive, which comes after left's send. The path holds a small amount of data, and that is why the program passes at N=16.

Run it

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

cd tutorial/main-2-between-pes/06-blocking-and-deadlock
make TEST=tutorial
make TEST=par
make TEST=hang

Each run prints check.py's lines into test-<row>/make-log, and a line ending in PASS. For tutorial and par they read:

left : started=1 done=1 theirs: 16 of 16 words written
right: started=1 done=1 theirs: 16 of 16 words written
expected: done; as expected

with 512 in place of 16 for par. The hang row prints the lines shown under Deadlock and passes, because it expects the deadlock.

Pitfalls

• Small tests pass and large runs hang. A program with a cycle of waiting works as long as the data fits into the buffering. Test at the size you will run.
• The buffering is not a constant. It depends on how many receive sockets a kernel has and on the compiler's queue choices.
• A hang is silent. Give every phase a marker before and after it, so that a failed test shows where the program stopped.

Exercises

1. Change the buffering. Write socket rx [[iq=2]]; in exchange.w: the attribute puts the receive socket on input queue 2, which holds 4 wavelets, and Carbide does not double a queue that the program chose. Use the table under How much the path holds to predict the largest N for which PAR=0 still finishes. Then find it with rows such as n30 N=30 PAR=0 ARCH=sdr and n50 N=50 PAR=0 ARCH=sdr.
2. Make PAR=0 safe at N=512 without parallel. Add xp param FIRST; to exchange.w, pass FIRST:1 to left and FIRST:0 to right in bench.paint, and make the PAR=0 branch receive first when FIRST is 0. Add a row ordered N=512 PAR=0 ARCH=sdr, and explain why it finishes for any N.

Next

Lesson 7 — Tasks: code that runs when a wavelet arrives

References

• Parallel and serial blocks
• Socket attributes and input queues
• Architecture notes: Colors, The CE's Queues, Microthreads