Topic — Sorting networks along a row

Needs: Lesson 2 — Values, control flow and functions, Lesson 6 — Blocking, buffering and deadlock.

A row of four PEs sorts 4·B integers, B on each PE. Neighbouring PEs swap data in a fixed pattern, the same for every input, so the whole sort is a sequence of pairwise exchanges with no central coordinator. With B=1 it is the classic odd-even transposition sort; with larger B each exchange becomes a merge-split of two sorted blocks.

What you will be able to do

• Run an odd-even transposition sort on a row of PEs and say which PEs pair in each phase.
• Extend it from one value per PE to one sorted block per PE with merge-split.
• Write a pairwise exchange that cannot deadlock, whatever the block size.
• Give the PEs that play different roles their own kernels and colors, and share the common code through a module.

The network: one value per PE

In each phase, neighbouring PEs form pairs and compare their values: the left PE of a pair keeps the smaller value and the right PE the larger. The pairs alternate. Even phases pair (t0,t1) and (t2,t3); odd phases pair (t1,t2), and t0 and t3 sit out. The row starts with an even phase, so phases 1 and 3 are even and phases 2 and 4 are odd.

The row single (B=1) runs this on the values 40, 10, 30, 20:

Phase	Pairs	t0	t1	t2	t3
input		40	10	30	20
1, even	(t0,t1) (t2,t3)	10	40	20	30
2, odd	(t1,t2)	10	20	40	30
3, even	(t0,t1) (t2,t3)	10	20	30	40
4, odd	(t1,t2)	10	20	30	40

On a row of P PEs, P phases sort any input, and fewer do not always suffice: the reversed input 40, 30, 20, 10 is sorted only after phase 4. The pattern of pairs does not depend on the data, which is what makes it a sorting network.

Blocks: merge-split

With B values per PE, each PE first sorts its own block. Then the same phases run, but a pair exchanges whole blocks: each PE sends its B values to its partner and receives the partner's B. The left PE keeps the B lowest of the 2B values and the right PE the B highest. This is a merge-split. After P phases the row holds the sorted input, the lowest B values on t0.

The row reversed (B=4, the values 16 down to 1) shows why all four phases are needed:

After	t0	t1	t2	t3
local sort	13–16	9–12	5–8	1–4
phase 1, even	9–12	13–16	1–4	5–8
phase 2, odd	9–12	1–4	13–16	5–8
phase 3, even	1–4	9–12	5–8	13–16
phase 4, odd	1–4	5–8	9–12	13–16

The program

Four PEs in a row. The two ends run edge.w, the two inner PEs inner.w, and both kernels import the module sortlib.w. Each pair type has one color for each direction:

           t0              t1               t2              t3
      +----------+   +-------------+   +-------------+   +----------+
      |  edge.w  |   |   inner.w   |   |   inner.w   |   |  edge.w  |
      |  SIDE=0  |   | EVEN_SIDE=1 |   | EVEN_SIDE=0 |   |  SIDE=1  |
      +----------+   +-------------+   +-------------+   +----------+
even_east   ---------------->               ---------------->
even_west   <----------------               <----------------
odd_east                     ---------------->
odd_west                     <----------------

ref.py writes each PE's B input values, which the Makefile loads into val with miset. At the end each PE's val holds its quarter of the sorted input: for the tutorial row (B=4), t0 holds 1, 2, 3, 4 and t3 holds 13, 14, 15, 16. The rows of test.rc:

Row	B	Input
tutorial	4	16 values in mixed order
reversed	4	16 down to 1
single	1	40, 10, 30, 20
odd	3	random, with repeated values possible
large	100	random, each PE's block already sorted

The code

bench.paint: one color per direction and pair type

let even_east = color()
let even_west = color()
let odd_east  = color()
let odd_west  = color()

t1 sends east to t2 in the odd phases and receives from t0, also travelling east, in the even phases. If one color carried both streams, t1's router would need two inputs for it, the core and the left neighbour, and a color has one input at a time (lesson 4). So the even pairs and the odd pair travel on different colors, and each color alternates between sending and receiving PEs along the row:

PE	even_east	even_west	odd_east	odd_west
t0	[C>R]	[R>C]
t1	[L>C]	[C>L]	[C>R]	[R>C]
t2	[C>R]	[R>C]	[L>C]	[C>L]
t3	[L>C]	[C>L]

Each PE binds its sockets to the colors of its role:

t1 : code('inner [tx_even:even_west rx_even:even_east
                   tx_odd:odd_east   rx_odd:odd_west
                   EVEN_SIDE:1 B:B])

sortlib.w: the sort and the merge-split

sort_block is an insertion sort of v[0..n):

function sort_block(xp v[], xp n) {
    ∀j in [1, n) {
        xp key = v[j];
        xp h = j;
        xp moving = 1;
        while (moving == 1) {
            moving = 0;
            if (h > 0) {
                if (v[h - 1] > key) {
                    v[h] = v[h - 1];
                    h = h - 1;
                    moving = 1;
                }
            }
        }
        v[h] = key;
    }
}

The two ifs are nested on purpose. h > 0 && v[h - 1] > key would read v[-1] when h is 0, because && evaluates both sides (lesson 2). Arrays are passed by reference, so sort_block sorts the caller's array in place. A function without -> type returns nothing.

Each side of a pair needs only the half it keeps, so it merges only B values. The left PE merges from the bottom of both sorted blocks:

function keep_low(xp mine[], xp theirs[], xp merged[], xp n) {
    xp i = 0;
    xp j = 0;
    ∀m in [0, n) {
        if (mine[i] <= theirs[j]) {
            merged[m] = mine[i];
            i = i + 1;
        } else {
            merged[m] = theirs[j];
            j = j + 1;
        }
    }
    ∀m in [0, n) mine[m] = merged[m];
}

At step m, i + j = m, so both indices stay below n: the merge cannot run off either block, and it needs no bounds checks. keep_high is the mirror image. It starts at index n - 1 of both blocks, takes the larger value, and fills merged from the top.

edge.w and inner.w: the phases

An end PE takes part in the two even phases:

main {
    sort_block(val, B);

    ∀phase in [0, 2) {
        parallel {
            ∀k in [0, B) tx[] <- val[k];
            ∀k in [0, B) other[k] <- rx[];
        }
        if (SIDE == 0) keep_low(val, other, merged, B);
        else keep_high(val, other, merged, B);
    }
}

An inner PE runs two rounds of an even phase followed by an odd phase, on the sockets of each pair. EVEN_SIDE says which side it plays in the even phases; in the odd phases it plays the other side:

    ∀round in [0, 2) {
        parallel {
            ∀k in [0, B) tx_even[] <- val[k];
            ∀k in [0, B) other[k] <- rx_even[];
        }
        if (EVEN_SIDE == 0) keep_low(val, other, merged, B);
        else keep_high(val, other, merged, B);

        parallel {
            ∀k in [0, B) tx_odd[] <- val[k];
            ∀k in [0, B) other[k] <- rx_odd[];
        }
        if (EVEN_SIDE == 0) keep_high(val, other, merged, B);
        else keep_low(val, other, merged, B);
    }

SIDE, EVEN_SIDE and B are parameters, so each if on them is decided when the kernel is compiled.

What the hardware does

Phases need no barrier. Nothing tells a PE that a phase has ended. A PE moves on when its receive has its partner's B values. The receive also orders the phases: t1 cannot merge with t2 before it has merged with t0, because the odd exchange comes after the even one in its code.

An end PE runs ahead. After phase 1, t0 sends its phase-3 block at once, while t1 and t2 are still in phase 2. Those wavelets wait in the routers' buffers and in t1's input queue for even_east, and t0's receive waits until t1 sends its phase-3 block. Each pair type has its own colors, so these early values never mix with the odd exchange.

Both partners send at the same time. Each exchange is symmetric: both PEs send B values and both receive B. Written in sequence,

∀k in [0, B) tx[] <- val[k];
∀k in [0, B) other[k] <- rx[];

both PEs start by sending, and nobody receives until a PE has sent its whole block. That works only while the path between them can hold a block. Beyond that, both senders stop with a full queue and wait for each other forever, as in lesson 6. In this program the sequential form passed with B=48 and hung with B=56, below lesson 6's 64. An inner PE has two receive sockets, and Carbide puts the second, rx_odd, on input queue 2, which holds 8 wavelets when doubled, against queue 0's 16. The amount depends on the kernel and the compiler's choices, so do not design to it. parallel starts the send and the receive as two microthreads, so each PE drains its partner's data while it sends its own, and the exchange completes for any B. The large row exchanges 100 values per phase.

What it costs. The last memory write of each row:

Row	B	Last write (cycle)
single	1	346
odd	3	730
tutorial	4	957
large	100 (blocks presorted)	16,994

The local insertion sort's time grows with B² on random data, and each phase moves and merges B values. The large row starts with sorted blocks, so its insertion sort makes one pass over each block without moving a value. Its time is that pass, the exchanges and the merges.

Run it

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

cd tutorial/ext-algorithms/sorting-networks
make TEST=tutorial       # B=4, the mixed input
make TEST='*'            # every row of test.rc

A passing row prints one line, such as sorting-networks : 0:03.29 PASS tutorial [ B=4 INPUT=mixed ARCH=sdr ]. test-tutorial/make-log shows ref.py's blocks after each phase. A failing row prints FAIL, and its make-log names the first PE whose result differs, for example t1-ref.bin t1-sim.bin differ: byte 1, line 1. Run make clean after you edit a source file: make reuses an existing test-*/ directory.

Pitfalls

• A sequential exchange hangs once the blocks are large. Send and receive a partner's block inside parallel, or have one side of each pair receive first.
• One color for all eastward traffic. Paint keeps the first paint() of a color on a PE and ignores a second one without a message (lesson 4). With odd_east replaced by even_east, t1 gets even_east [L>C] and then even_east [C>R]. Its odd-phase sends have no route, so t2 never receives t1's block and waits in phase 2 forever. The test fails (checked). Give each pair type its own colors.
• Guards with &&. Both sides of && are evaluated, so a guard that protects an array index must be an outer if.
• Every PE needs the same B. The phases pair blocks element for element, so B is one Paint variable passed to every kernel.

Exercise

Remove the parallel blocks from edge.w and inner.w, so that each exchange sends and then receives. Predict which rows still pass, run make clean and make TEST='*', and check.

Then, still without parallel, fix the hang a second way. In each exchange, make the PE that keeps the high half receive its partner's block before it sends its own, and the other PE send first. Choose the order with SIDE in edge.w and with EVEN_SIDE in inner.w; an inner PE changes sides between the even and the odd exchange. Why can this not deadlock?

Next

Topic — Physics on a grid of points: boundary conditions exchanges values between all four neighbours of every PE of a grid, and sets what lies beyond its edge.

References

• Functions and imports
• Parallel blocks
• Logical operators
• Rules that differ from C
• The CE's queues
• Direction codes