Complete examples

Appendix A: Complete Example — Vector Addition

A simple program that adds a constant to every element of an array:

xp param N;
xp a[n=N];        // no initialiser — data loaded via miset
xp b = 1;

i in [0, N) a[i] <- a[i] + b;

Appendix B: Complete Example — Send and Receive

A pair of programs communicating through sockets.

Sender (send.w):

xp param N = 4;
socket tx;
xp a[n=N] = {1, 2, 3, 4};

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

Receiver (recv.w):

xp param N = 4;
socket rx;
xp a[n=N];

i in [0, N) a[i] <- rx[];

Layout (bench.paint): one color carries tx of the sender to rx of the receiver, its east neighbor. After simulation, the receiver's a is 1, 2, 3, 4.

let c = color()

let send = tile()
send : code('send [tx:c])
send : paint(c [C>R])
send : name('send)

let recv = tile()
recv : code('recv [rx:c])
recv : paint(c [L>C])
recv : name('recv)

hstack(send recv)

Appendix C: Complete Example — Dispatch (RPC)

The Section 18 example as a complete program on three tiles, side by side: the sender sends store and flush messages to the dispatcher, and the dispatcher sends the stored values to the receiver. After simulation, the receiver's a equals the sender's.

Sender (send.w):

xp param N = 4;
socket requests;                   // to the dispatcher

hp a[n=N] = {1.0, 2.0, 3.0, 4.0};

// One store(i, value) message per element, then one flush() message.
i in [0, N) requests[] <- store(i, a[i]);
requests[] <- flush();

Dispatcher (dispatch.w):

xp param N = 4;
socket requests;                   // messages from the sender
socket results;                    // stored values, to the receiver

hp a[n=N];

// Each incoming message runs the handler with its name and arguments.
forever main dispatch(requests) {
    store(xp i, hp value) {        // keep value at index i
        a[i] <- value;
    }
    flush() {                      // pass the stored values on, in order
        i in [0, N) results[] <- a[i];
    }
}

Receiver (recv.w):

xp param N = 4;
socket results;

hp a[n=N];

i in [0, N) a[i] <- results[];

Layout (bench.paint): one color carries requests from the sender to the dispatcher, another carries results on to the receiver.

let reqcolor = color()
let rescolor = color()

let send = tile()
send : code('send [requests:reqcolor])
send : paint(reqcolor [C>R])
send : name('send)

let dispatch = tile()
dispatch : code('dispatch [requests:reqcolor results:rescolor])
dispatch : paint(reqcolor [L>C])
dispatch : paint(rescolor [C>R])
dispatch : name('dispatch)

let recv = tile()
recv : code('recv [results:rescolor])
recv : paint(rescolor [L>C])
recv : name('recv)

hstack(send dispatch recv)

Appendix D: Complete Example — Cosine Similarity

A kernel that computes the three sums behind the cosine similarity of two vectors: their dot product and the squared norm of each. It is a sketch: it compiles, but it does not run on its own. Each tile holds N pairs of rows bufA[n], bufB[n] of L elements. For each pair it computes three partial sums and combines each with the other tiles' over the fabric: hr[] <+- acc receives a partial sum on hr, adds acc and sends the result on along hr, and the full sum comes back on bc. Two parts are not shown: the kernel of the first tile in the hr chain, which sends acc instead of adding a received sum to it, and the layout, which chains hr through the tiles and broadcasts the total on bc. The host computes each cosine as dotAB[n] / sqrt(normA[n] * normB[n]).

bufA.base <- abase points bufA at row n, so bufA[0][i] reads that row; an sp element takes two words, so abase <+- 2*L steps one row.

xp param N;
xp param L;

socket hr;
socket bc;

sp bufA[n=N][l=L];
sp bufB[n=N][l=L];

xp abase = bufA.base;
xp bbase = bufB.base;

sp dotAB[n=N];
sp normA[n=N];
sp normB[n=N];
sp acc;

serial {
    n in [0, N) {
        bufA.base <- abase;
        bufB.base <- bbase;

        acc <- 0;
        i in [0, L) acc <+- bufA[0][i] * bufB[0][i];
        hr[] <+- acc;
        dotAB[n] <- bc[];

        acc <- 0;
        i in [0, L) acc <+- bufA[0][i] * bufA[0][i];
        hr[] <+- acc;
        normA[n] <- bc[];

        acc <- 0;
        i in [0, L) acc <+- bufB[0][i] * bufB[0][i];
        hr[] <+- acc;
        normB[n] <- bc[];

        abase <+- 2*L;
        bbase <+- 2*L;
    }
}

Appendix E: Complete Example — 3×3 Convolution

A stencil computation with halo exchange:

xp param Y = 8;
xp param X = 8;

hp A[r=3][s=3];
hp u[yy=Y][xx=X];
hp v[yy=Y+2][xx=X+2] = {};

let i in [0, Y);
let j in [0, X);
let r in [0, 3);
let s in [0, 3);

socket a, b, c, d;

hp α;
{
    ∀r ∀s {
        α <- A[r][s];
        ∀i ∀j v[i+r][j+s] <+- u[i][j] * α;
    }
    // Reduce right/left halos: send each halo column to the neighbor
    // that owns it, and add the neighbor's halo into the edge column.
    parallel {
        ∀i in [0, Y+2) b[] <- v[i][0];
        ∀i in [0, Y+2) a[] <- v[i][X+1];
        ∀i in [0, Y+2) v[i][1] <+- a[];
        ∀i in [0, Y+2) v[i][X] <+- b[];
    }
    // Reduce top/bottom halos (the corners arrived with the columns)
    parallel {
        ∀j in [1, X+1) d[] <- v[0][j];
        ∀j in [1, X+1) c[] <- v[Y+1][j];
        ∀j in [1, X+1) v[1][j] <+- c[];
        ∀j in [1, X+1) v[Y][j] <+- d[];
    }
}

v holds the tile's Y×X interior at rows and columns 1…Y and 1…X, with a one-element halo around it. Each tile sends a halo strip to the neighbor that owns those cells and adds the strip it receives into its own edge row or column: a and b run east and west over every row 0…Y+1, so the corners travel with the columns, and c and d then run between rows over the interior columns 1…X.

v starts at zero (= {}) because the convolution accumulates into it.

The kernel is the program of a tile that has a neighbor on all four sides. On a grid with edges, a tile on an edge has no neighbor on that side, so its receive from that side never completes: an edge tile needs a kernel that leaves out the missing sides, and the layout needs routes for the four sockets. The 9-point stencil in the Paint examples lays out a grid with one kernel for its edge tiles and another for the rest.