Topic — Large layouts: geovars, terminals and transports, link

Needs: Lesson 8 — Space and time: a wavefront along a row, Lesson 9 — Broadcast and reduce along a row, Lesson 11 — A grid of blocks: halo exchange and what it costs.

The main lessons build layouts from rect, union, define and replication, and paint every route by hand. As a layout grows, three needs come up again and again. PEs that run one kernel need different compile-time values. Blocks far apart need a connection. Every PE of a block needs its own data. Paint has a feature for each: geovars, terminals and transports, and link. Each also has forms that build without a message and then run wrong. This topic uses every feature in a form that works, and lists the silent traps with the safe form of each.

What you will be able to do

• Give the PEs of one code() region different compile-time values with a geovar, and know what that costs.
• Connect two regions with a transport that Paint routes, and check that Paint routed it.
• Fill a symbol on every PE of a region at build time with link and a program you write.
• Turn a finished layout with rotate, and replicate regions with rep, arrayplace and diagplace.
• Name the Paint forms that build silently and do the wrong thing, and use their safe forms.

The program

Lesson 9's reduce along a row used three kernels, one each for the head, the middle PEs and the tail. This program does the same reduction with one kernel. A geovar tells each PE its role, and the tail sends the sum to a sink, a PE placed away from the row, through a transport:

  y
  ^
  2 |                                                    [sink]
    |                                                      ^
  1 |                                                    ( . )
    |                                                      ^
  0 |  [head] -> [mid] -> [mid] -> [tail] ->  ( . )  ->  ( . )
    +------------------------------------------------------------> x
         0         1        2        3          4          5

• There are K workers in row 0; the figure shows K=4. Each holds M values in v. link writes them while the image is built: worker x holds (x + 1)·(j + 1) at index j.
• The head sends its v along the row. Each middle PE adds its own v to the stream and passes it on. The tail adds its v, keeps the sum in s, and sends it through the transport.
• The PEs marked ( . ) run no kernel. They carry only the route Paint made for the transport.
• The sink stores the sum in t. For K=4, sink.t is [10, 20, 30, 40].

The figure draws y growing upward, as lesson 4 does.

The code

One kernel, three roles: worker.w

xp param M;
xp param ROLE;
socket r;
socket out;
xp v[n=M];
xp s[n=M];

main {
    let j in [0, M);
    if (ROLE == 0) {
        ∀j r[] <- v[j];
    } else if (ROLE == 1) {
        ∀j r[] <- r[] + v[j];
    } else {
        ∀j s[j] <- r[] + v[j];
        ∀j out[] <- s[j];
    }
}

ROLE is a parameter, so it is a constant when the kernel compiles. The compiler keeps only the branch for that value: the listing of the head's variant holds one send and nothing else. The stream arithmetic r[] <- r[] + v[j] is lesson 9's.

Geovars: a value per PE

bench.paint sets a geovar called role on three regions that cover the row, and passes it to the kernel as @role:

let head = tile(0 0)
head : geovar('role 0)
let mids = rect(1 0 K-2 1)
mids : geovar('role 1)
let tail = tile(K-1 0)
tail : geovar('role 2)
tail : paint(o [C>R])
tail : terminal('out 'sum RIGHT o [1 1] [1 1] 1)
tail : name('tail)

let row = rect(0 0 K 1 'x)
row : code('worker [r:r out:o M:M ROLE:@role])
row : paint(rp [CXR|R])
row : paint(r [L|LXC])
row : colorpair(r rp)
row : union(head mids tail)
row : link($v "x n" "./ramp" [k:K m:M])
row : name('row)

The form matters. code() goes on row, a rect of its own over the same PEs, and row : union(head mids tail) then joins the three geovar regions to it. They lie on the same PEs as row, one after another along the row. Paint compiles each PE with the value of the geovar region it lies in. @role=0 is a shorter way to write geovar('role 0). A geovar must cover every PE of the code() region; Paint stops with Geovar role does not cover region when it does not.

Each distinct value compiles the kernel once more: this row compiles worker.w three times, with ROLE=0, 1 and 2, whatever K is. A geovar with a different value on every PE compiles the kernel once per PE. When the value need not be a constant, read it at run time instead: lesson 12 takes each PE's role from its row and column ID registers.

The map has one entry per symbol, such as row.v [ x<4 n<4 ], for all the variants. Paint takes the addresses in it from the first variant. miget, miset and link are therefore right only if every variant puts its arrays at the same addresses. They do here, because every variant declares the same arrays with the same sizes. Never size an array by a geovar.

The routes are lesson 9's color-swap row, painted on row, a single rect. A | term acts at the edges of each rectangle a region is built from, so on one rect it acts at the row's ends.

A transport to the sink

The tail and the sink each get a terminal: a named end point on a color. A transport joins two terminals, and Paint finds a route between them:

let sink = tile(K+1 2)
sink : code('sink [rx:o M:M])
sink : paint(o [>C])
sink : terminal('in 'sum CENTER o [1 1] [1 1] 1)
sink : name('sink)

let arc = transport('row.tail.out 'sink.in 'arc)
let all = union(row sink arc)

[>C] names only an output, delivery into the sink's core. The transport supplies the input.

The arguments of terminal are its name, a tag, a side, a color, a shape, a split and a chunk count:

• The tag ('sum) must be the same at both ends.
• The side says where the route starts or ends. RIGHT starts it on the PE to the right of the tail, (4, 0). CENTER ends it on the sink itself.
• Paint finds the terminal's PE, its pin, from the region's own paint() rule for the color: a rule that routes o through that side, such as the tail's [C>R] and the sink's [>C]. With no such rule, Paint stops with has no pins defined.
• [1 1] [1 1] is one pin on one PE, and the chunk count 1 is not used by the router.
• Both terminals use the same color, o. Paint gives a transport one physical color from end to end.

transport names each terminal by its path of region names: the tail's terminal is 'row.tail.out, because tail lies inside row. The transport is a region of its own, and it must be in the final union. For this layout Paint routes o east from (4, 0) to (5, 0), then along +y to the sink at (5, 2). The router makes straight and L-shaped routes. A sink behind the tail, such as tile(0 2), stops Paint with Away wire orientation is not supported.

Paint the routes yourself when the path is part of the algorithm, as in every main lesson. A transport saves you painting the PEs between two blocks that lie apart. It joins one terminal to one terminal; to send one stream to several PEs, paint a multicast yourself, as lesson 9 does. When a PE must choose the destination at run time, use message passing.

link: data from a program, written at build time

row : link($v "x n" "./ramp" [k:K m:M])

link asks for $v of region row, that is row.v, to be filled by the program ./ramp. The order "x n" is the one miset uses: x outermost, n fastest, so the program writes K·M words. Paint records the request; milink, which the build runs after Paint, calls the program with one key=value argument per entry, numbers in hexadecimal, and the file to write:

./ramp k=0x4 m=0x4 out=/dev/fd/4

The program writes little-endian 16-bit words to that file, exactly as many as the order names. ramp.py is the program:

#!/usr/bin/env python3
import struct
import sys

args = dict(a.split('=', 1) for a in sys.argv[1:])
k = int(args['k'], 0)
m = int(args['m'], 0)
words = [(x + 1) * (j + 1) for x in range(k) for j in range(m)]
with open(args['out'], 'wb') as f:
    f.write(struct.pack(f'<{len(words)}h', *words))

The Makefile copies it into the test directory as an executable ramp, before Paint runs:

bench.obj: ramp

ramp: ramp.py
	cp $< $@
	chmod +x $@

Lesson 8 loaded per-PE data with miset and a file the Makefile writes. link does the same job from inside the layout. The layout carries its own data recipe, and the program takes its parameters from the layout: Paint variables such as K and M, and colors as their physical numbers.

Turning the layout

setif(ROT rotate(all R90) all)

rotate(all R90) turns the whole layout a quarter turn: +x becomes +y. The routes, the color swaps, the | terms and the transport's route turn with the PEs, and the same kernels run. With ROT=1, the row becomes a column at x = 2, rows 0 to 3, and the sink moves to (0, 5). row.v keeps its dimension name x, although x now steps along the column:

row.v        [ x<4 n<4          ] ( 0x0+n        2   0+x )

setif(c a b) is Paint's choice of a value: it returns a when c is not 0 and b otherwise. It evaluates both a and b first, so both must be valid layouts.

Other ways to replicate

• rep(r 'x count dx dy) makes count copies one step apart and names the dimension, as rect does. Step along one axis: set dx or dy to 0.
• For a diagonal, use diagplace(r count dx dy), which puts copy i at (i·dx, i·dy).
• arrayplace(r offsets [name:values]) puts copies of r at the y offsets in offsets, names them x0, x1, and so on, and gives copy i the i-th value of the geovar name. Attach code() to r before arrayplace. Each copy is its own region, so its symbols read x0.a, x1.a; a rect or rep gives one symbol with a dimension instead.
• hstackrep and vstackrep are lesson 11's.

Run it

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

cd tutorial/ext-layouts-debugging/large-layouts
make TEST=tutorial

make prints a line ending in PASS tutorial [ K=4 M=4 ROT=0 ARCH=sdr ], and test-tutorial/make-log holds the line sink.t = [10, 20, 30, 40]. The other rows are k8 (K=8, M=8) and turned (K=4, M=4, the rotated layout).

Three checks show the features at work, each read from the same build:

grep 'ucid=' test-tutorial/make-log | grep -o 'set=ROLE=[0-9]*'
grep '^xp .*address' test-tutorial/worker_artefacts/*.yeti
grep 'not found' test-tutorial/make-log

The first prints set=ROLE=0, set=ROLE=1 and set=ROLE=2: one compile per role. The second prints the arrays of each variant's listing; v is at 0x0000 and s at 0x0004 in all three. The third prints nothing: Paint connected every transport.

A failure prints the expected and the received sink.t.

Traps and their safe forms

Each form on the left builds without a message, unless the table says otherwise.

Trap	What happens	Safe form
code() on a union, hstack or stack of the geovar regions themselves	Every PE compiles with one value, the first region's	code() on a separate rect that covers them, then union them to it, as row does; or attach code() before arrayplace
An array sized by a geovar	The variants put their arrays at different addresses; the map holds the first variant's, so miget, miset and link read and write the wrong words on the other PEs	The same declarations in every variant; compare the address lines of the variants' listings
A | term on a region made with hstack, vstack or union	Paint applies the term at the edges of each rectangle the region is built from, and to every PE of each rectangle after the first: routes are cut	Paint | rules on one rect that covers the region
A second paint() of the same color on the same region	Ignored; the first rule stays. Where two regions of a union overlap, the later region's rule wins	One rule per color per PE
A second code() on the same region	Both programs are placed at the same addresses	One code() per region
name() before terminal(), a misspelt terminal name, or different tags	Paint prints port(s) of arc ... not found, drops the transport and still builds; the receiver waits forever	name() after terminal(), one tag at both ends; grep 'not found' in the build log
A transport left out of the final union	No route and no message; the receiver waits forever	Put every transport in the final union
Two different colors for the two terminals of a transport	Paint makes them one physical color, and drops a color pinned with color(N)	One color for both terminals
rep with a step in both axes	The kernels are placed as if the y step were 0, while the overlap check uses the diagonal	diagplace
A negative number in a Paint list, as in [0 -2 4]	Paint has no negative literals: this is the two-element list [-2 4]	0-2, in parentheses inside a list: [0 (0-2) 4]
Two coded regions without names	Their symbols have the same name; miget warns and reads the first	Name every region whose memory you read

Three related mistakes stop the build: a geovar that does not cover its code() region, a terminal without a pin rule, and a transport whose destination lies behind its source side. A link on a region without name() makes milink crash, so name every region you link.

The Paint reference gives the full syntax of each feature.

Exercises

1. Move the sink to tile(K+3 4) and run all three rows. Paint finds the new route by itself. Then move it to tile(0 2) and read Paint's message.
2. Remove the link line, and compute v in the kernel from the PE's column instead. Paint writes each PE's x into its column ID register at address 0x7c46 (lesson 12 reads it). Declare xp col_id[1] address(0x7c46);, and before the if, write xp x = col_id[0]; and ∀j v[j] = (x + 1) * (j + 1);. The tutorial and k8 rows pass. Why does turned fail, and which of the two ways of filling v follows the layout when it turns?

Answers

1. The router finds the L-shaped path to (K + 3, 4). For tile(0 2) Paint stops with Away wire orientation is not supported: the sink lies west of a terminal that faces east.
2. In the turned layout the row runs down column 2, so every worker reads column 2 and computes 3·(j + 1), and sink.t is [12, 24, 36, 48]. link writes along the named dimension x, wherever the rotation puts it. A kernel that reads its position must read the register that changes along the row: here the row ID.

Next

Topic — Debugging and profiling a multi-PE run finds out what a multi-PE run did, PE by PE: how far each PE got, what it received, and where its cycles went.