Topic — Memory: placing data, address(), and the memory budget

Needs: Lesson 2 — Values, control flow and functions, Lesson 3 — How a PE runs a loop: vector instructions and cycles.

A PE has 48 KB of memory for its code, its data and its stack. Carbide places everything, and it stops the build only when the arrays leave too little room for what follows them. Some overflows give no error at all. This topic shows where Carbide puts things, how to read a kernel's memory budget, how to place an array on purpose, and what happens at the limit.

What you will be able to do

• Read a kernel's memory layout from bench.map or with meminsp, and say how much memory is free.
• Give one block of memory two names with address(&a + k).
• Place an array with bank() or align(), and use placement to avoid memory-bank conflicts.
• Recognise the errors at the memory limit, and the overflows that give no error.

The program

memory.w runs on one PE. It has two parts.

1. pool is one block of 2*N SP values. The kernel gives its first half the name u and its second half the name v. check.py writes N random whole numbers from 0 to 255 into u with miset. The kernel then smooths the values STEPS times: each step replaces every value except the two end ones by a weighted average of itself and its neighbours, 0.25, 0.5, 0.25. The steps alternate between u → v and v → u, so no step copies data. STEPS must be even: each pass of the loop does two steps.
2. Five arrays of 64 SP values, x, y, z, p and q, are placed with bank(). The kernel times two multiplications, p = x * y and q = x * z, which differ only in where their operands sit.

After the run, check.py compares u and v with its own smoothing, checks where x, y and z landed, and prints the cycle counts. budget.py prints the kernel's memory budget from bench.map.

check.py --u0.bin--> miset pe.u --> +-----------------------+ --> miget --> pool, p, q, where --> check.py
                                    | PE: memory.w          |
                                    | smooth u <-> v        |             t --> check.py (cycles)
                                    | p = x*y, q = x*z      |
                                    +-----------------------+    bench.map --> budget.py (table)

For the tutorial row (N=64, STEPS=4) the PE's memory looks like this:

0x0000  pool  = u (128 words) followed by v (128 words)
0x0100  x     (bank(0))
0x0180  y     (bank(0))
0x0202  z     (bank(2))
0x0282  p, then q, t and where
0x0390  task table
0x03d0  code: main, then its handlers, up to 0x04df
        free: 23,328 words
0x6000  top of main memory; the stack grows down from here

What fills the memory

Main memory runs from address 0x0000 to 0x5fff. Addresses count 16-bit words, so this is 24,576 words; the memory is not byte-addressable. Lesson 2's table gives the words each type takes: one for xp, u16 and hp, two for sp and u32. A 32-bit value must start at an even address, so Carbide leaves a gap before a 32-bit array when it has to.

Carbide fills the memory in this order:

1. The arrays, from address 0 up, in the order you declare them. An array that must start at a particular kind of address (an even one, or one that bank() or align() asks for) can leave a gap.
2. The task table, one entry per task, which the hardware uses to find the code of the task it starts. Its address is in the PE's entry-table register, which the Makefile reads from the image with miget for budget.py.
3. The code, and the descriptors that do not fit in the PE's descriptor registers.
4. The stack, which starts at the top, 0x6000, and grows down. Function calls that need it use it at run time; Carbide reserves no room for it.

Every array costs memory whether the code uses it or not: an array that no statement reads still gets its place.

Reading the budget

bench.map

The build writes bench.map in the test directory (test-tutorial/bench.map). It has one line per symbol, with the symbol's dimensions and its address:

pe.pool               [ n<128 _word<2    ] ( 0x0+2*n+_word   0 0 )
pe.u                  [ n<64 _word<2     ] ( 0x0+2*n+_word   0 0 )
pe.v                  [ n<64 _word<2     ] ( 0x80+2*n+_word  0 0 )
pe.x                  [ n<64 _word<2     ] ( 0x100+2*n+_word 0 0 )

pe. is the PE's name, from name('pe) in bench.paint. n<64 _word<2 says that u has 64 elements of two words each, and 0x0+2*n+_word says where element n, word _word, sits. The map also lists the code (pe.main, pe.main_split_handler), the descriptors, and the PE's registers, whose addresses are above 0x6000.

budget.py

budget.py adds up the map's entries below 0x6000. For the tutorial row:

 address  words  symbol
  0x0000    128  u
  0x0000    256  pool
  0x0080    128  v
  0x0100    128  x
  0x0180    128  y
  0x0202    128  z
  0x0282    128  p
  0x0302    128  q
  0x0382      5  t
  0x0387      3  where
arrays:                          904 words
code and descriptors:             96 words
task table starts at:         0x0390
highest address in use:       0x04df
free below 0x6000:             23328 words of 24576

The big row (N=5000) uses most of the memory: its arrays take 20,648 words, and 3,584 words are free.

meminsp

meminsp reads a memory image and the map. It works on the image before the run, bench.img, and on the core image after it. symbols lists every symbol with its address and size, and info describes one. The layout is the same in both images, so bench.img will do:

meminsp img_path=test-tutorial/bench.img map_path=test-tutorial/bench.map tile_str=T0.0 cmd_str="info pe.v"

  name:    pe.v
  program: pe
  addr:    0x0080 - 0x00ff (128 words)
  tile:    x=[0,0] y=[0,0]
  dword:   yes
  dims:    n<64 _word<2

dword: yes means 32-bit elements. cmd_str="print pe.z" prints the values, and cmd_str="read 0x80 8" prints eight raw words from address 0x80. For the values after the run, make the core image again, as lesson 4 shows; make deletes it when a row finishes:

cd test-tutorial
make -f ../Makefile VPATH=.. TEST=tutorial bench.map bench-sim.core
meminsp img_path=bench-sim.core map_path=bench.map tile_str=T0.0 cmd_str="print pe.u"
cd ..

One block, two names

sp pool[n=2*N];
sp u[n=N] address(&pool);
sp v[n=N] address(&pool + 2*N);

address(&pool) places u at the address of pool instead of giving it memory of its own. u and the first half of pool are then the same memory under two names. &pool + 2*N is an address 2*N words after pool: N SP values, so v is the second half. The offset counts words, not elements.

Carbide checks none of this. It accepts two arrays at the same address without a warning, and it does not check that u and v stay inside pool. That is how the applications in the gallery use it: the heat-equation kernel carves one block into its two fields with a one-value gap between them, and the molecular-dynamics kernel gives each row of a block its own name, so the code can loop over the whole block or use one row by name. Those kernels also write extern on such names; an alias appears in the map without it.

The smoothing function takes the two halves as arrays:

function smooth(sp src[N], sp dst[N]) {
    sp w0 = 0.5;
    sp w1 = 0.25;
    dst[0] <- src[0];
    dst[N-1] <- src[N-1];
    ∀i in [0, N-2) dst[i+1] <- w0 * src[i+1];
    ∀i in [0, N-2) dst[i+1] <+- w1 * src[i];
    ∀i in [0, N-2) dst[i+1] <+- w1 * src[i+2];
}

a <+- e adds e to a. Each of the three loops is one vector instruction: a multiply into dst, then two multiply-adds into it. An array parameter names the caller's array (lesson 2), so smooth(u, v) reads u and writes v. The loop calls it twice per pass, with the roles swapped:

    while (s < STEPS) {
        smooth(u, v);
        smooth(v, u);
        s += 2;
    }

After an even number of steps the newest values are in u, and v holds the step before. Carbide copied smooth's body into each call, so each call's loops are vector instructions over fixed arrays: the listing shows a fmuls and two fmacs per call, as in lesson 3.

The weights are powers of two and the inputs are whole numbers from 0 to 255. Each step adds two bits after the binary point, so for the rows of test.rc (at most 6 steps) every result fits in SP's 24 significant bits and is exact. check.py can then compare bit for bit, however Carbide groups the multiply-adds. Longer runs can round; a reference for them must follow the kernel's order of operations.

Placing an array

sp x[n=64] bank(0);
sp y[n=64] bank(0);
sp z[n=64] bank(2);

• bank(n) places the array at an address whose low 4 bits are n, from 0 to 15.
• align(n) places the array at a multiple of n words.
• address(a) places the array at the word address a. Two arrays at the same address share their memory, without a warning.

The 16 values of n are not 16 memory banks. For sp arrays only the address modulo 8 matters (next section): bank(0) and bank(8) give the same memory banks, and bank(2), bank(4) and bank(6) each give memory banks different from those of bank(0).

check.py reads where the arrays landed: x at 0x0100, y at 0x0180 and z at 0x0202.

Why placement changes speed

Lesson 3 showed that memory delivers four 32-bit words per cycle, one from each of four memory banks, and that two 32-bit words whose addresses differ by a multiple of 8 lie in the same memory bank. An instruction whose two operands need the same memory bank in the same cycle waits a cycle.

x and y both start at an address whose low 4 bits are 0, so x[i] and y[i] always share a memory bank. z starts 2 words later in the pattern, so x[i] and z[i] never do.

Statement	Operands' memory banks	Cycles for 64 elements
p[i] <- x[i] * y[i]	the same	130
q[i] <- x[i] * z[i]	different	66

The SP multiplier does one multiply per cycle, so 66 cycles is its full rate. The two statements compile to the same instruction, fmuls; only the addresses differ. Without attributes, two sp arrays of N elements declared one after the other start 2·N words apart, so their elements share memory banks when N is a multiple of 4. These arrays have 64 elements: without the attributes, x, y and z would all share memory banks.

Moving an array at run time: .base

An array's .base is its address in words. Assigning it makes later accesses use the new address; no data moves. Swapping the .base of two arrays looks like a cheap way to alternate two buffers, but it has costs:

• Carbide then runs every loop over those arrays one element per iteration. In a test of ∀i in [0, N) v[i] <- w0 * u[i]; over 64 SP values, the loop took 66 cycles, and 136 cycles in the same program with a .base swap of u and v later on.
• Each swap rewrites the address in every descriptor of the two arrays: one store per descriptor.
• Reading .base after assigning it can return the old address. Keep the addresses in variables.
• bench.map, and therefore miget, still name the declared addresses. After an odd number of swaps, miget of u reads the memory that the program calls v.

Swapping the roles in the code, as smooth(u, v); smooth(v, u); does, has none of these costs.

At the limit

The big row is close to the limit. Larger values of N stop the build with errors like these:

• [WMC TASK ALLOC] Task table starting at [0x5ec0] with size [0x200] exceeds the main memory limit [0x6000]. (N=5900). The task table comes right after the arrays, and Carbide needs 0x200 (512) words from its start to 0x6000, for the table and the code. The message names the task table, but the arrays are what is too big.
• [Symbol Table]: Ran out of memory when allocating symbol [ pool ] with size 48000 bytes at address 0x2. (a test with a pool of 24,000 SP values). It names the first symbol that Carbide cannot place. When the array that is too big is declared first, Carbide places it anyway, and the error names the symbol after it, or the task table. The size it prints as bytes is in 16-bit words.

The stack is not part of either check. A program whose arrays fill the memory builds, and its stack can then overwrite its own code. In a test with 24,050 words of arrays, a recursive function called 100 deep never returned: neither its result, 5,050, nor the statement after the call was ever written.

Run it

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

cd tutorial/ext-single-pe/memory-budget
make TEST='*'

Each of the three rows prints a PASS line. The checks and the budget are in each row's log:

sed -n '/check.py [0-9]/,$p' test-tutorial/make-log

For the tutorial row check.py prints:

u (pool half 0) holds step 4: exact
v (pool half 1) holds step 3: exact
x at 0x0100, low 4 bits 0
y at 0x0180, low 4 bits 0
z at 0x0202, low 4 bits 2
v starts 128 words after u
4 smoothing steps over 64 points:    784 cycles
p = x * y (same memory banks):         130 cycles for 64 elements
q = x * z (different memory banks):     66 cycles for 64 elements

and budget.py prints the table above. A failing row prints FAIL, and the log ends with outputs differ from the reference after the line that says WRONG, or after an address with the wrong low bits. The cycle counts never decide the test.

Pitfalls

• The error at the limit names the task table, not your array. Read it as "the arrays end less than 512 words below 0x6000".
• The budget leaves out the stack. Recursive and deeply nested calls need room above the code. Keep a margin, and test the deepest call.
• Out-of-bounds writes are not checked. a[i] past the end of a writes the next array in memory, without an error. Compile with fsanitize=bounds while you develop: run make clean, then make TEST=tutorial PAINTOPTS='toolflag w fsanitize=bounds' (see Array access).
• address() aliases are not checked. A view that runs past its block, or two arrays given the same address by mistake, compile without a warning.
• Same-sized arrays declared one after another can share memory banks. If a loop over two of them is slow, look at their addresses in bench.map.
• miget reads the declared address. After moving an array with .base, read it by the address the program used.

Exercises

1. From the big row's budget, predict the largest N that still builds. Change the row's N, run make clean and make TEST=big, and find the boundary.
2. Replace the two calls with one call and a .base swap: smooth(u, v);, then swap u.base and v.base through two variables, and change s += 2 to s += 1. Predict where the newest values end up after 4 steps and after 3. Add the row odd N=64 STEPS=3 ARCH=sdr, fix check.py for it, and compare the smoothing's cycle count with the one above.

Next

Topic — Locks, until conditions, rings and timer tasks uses memory as queues and buffers between activities on one PE.

References

• Array attributes
• Base address access
• Type sizes
• Hardware register access: address()
• Array bounds verification
• Memory layout
• meminsp