Architecture Notes

This page describes the machine that Tungsten and Paint programs run on: the processing element, the fabric between processing elements, and how data moves through them.

---

Architecture

The tutorial targets Schrödinger (sdr), the WSE-3 / CS-3 system. Every example names it in test.rc:

tutorial N=4 ARCH=sdr

Or on the command line:

make TEST=1 ARCH=sdr

The compilers take the same value as an option: carbide arch=sdr, paint arch=sdr.

---

The Fabric

The Cerebras wafer-scale engine is a 2D grid of processing elements (PEs). Paint's tile() makes a region of one PE.

         X ->           (north)
    +----+----+----+----+
Y   |PE  |PE  |PE  |PE  |  y=0
v   |0,0 |1,0 |2,0 |3,0 |
    +----+----+----+----+
    |PE  |PE  |PE  |PE  |  y=1
    |0,1 |1,1 |2,1 |3,1 |
    +----+----+----+----+
    |PE  |PE  |PE  |PE  |  y=2
    |0,2 |1,2 |2,2 |3,2 |
    +----+----+----+----+
                        (south)

Row 0 is the northernmost row, and row IDs grow southward. Paint's y is the row ID, and its U direction is +Y, toward larger row IDs: U is the router's south port and D its north port.

The Processing Element

A PE has three parts:

• the compute engine (CE), an in-order processor that runs the PE's program;
• memory: 48 KB of main memory for code, data and the stack, and a 256-word data cache (see Memory Layout);
• the router, a switch with five ports: north, south, east, west, and the CE. Paint calls the CE's port C.

The CE reaches the fabric only through its router. The router moves wavelets between its ports without the CE's help.

Wavelets

A wavelet is the unit of data on the fabric: 32 bits of data, the wavelet's color, and a control bit.

Kind	Data	Control bit
data wavelet	32 bits	0
half-wavelet	16 bits	0
control wavelet	32 bits: switch commands for the routers, and a task ID for the CE	1

A data wavelet can also carry a 16-bit index in its upper half and a 16-bit value in its lower half; Tungsten's wavelet(x, i) builds one.

Two 16-bit sends usually share one wavelet: the output queue packs them when it can, and a lone 16-bit value may leave as a half-wavelet. Lesson 4 introduces this rule. Message-passing colors forbid half-wavelets (MP Constraints).

Colors

• A color is a virtual channel through the routers. A router has 24 colors.
• Each color has its own 4-wavelet buffer in each router, so a blocked color does not block the others.
• All colors share the links. Each port moves one wavelet per cycle in each direction, and the colors waiting for the same output port take turns, round robin. Spreading a stream over several colors on one link does not make it faster.
• A router stops sending on a color when the next router's buffer for that color is full. A receiver that stops reading therefore stalls its color hop by hop back to the sender.
• A color serves only the wavelet at the head of its buffer, and that wavelet waits until every output of its route has taken it. On a route that broadcasts to several PEs, one PE that does not take its copy stops the color for all of them.

The CE's Queues

The CE sends and receives through queues that sit between it and the router.

• There are 8 input queues and 8 output queues. Each queue serves one color, so a CE receives on at most 8 colors and sends on at most 8. In Tungsten, each socket that receives takes an input queue (Input Queues).
• A queue holds 4 to 16 wavelets.
• The router delivers at most one wavelet per cycle to the CE.

What blocks:

Situation	Effect
A receive on the main thread finds its input queue empty	The main thread suspends until data arrives. Microthreads keep running, but no new task starts.
A send on the main thread finds its output queue full	The main thread suspends until there is space, with the same effect.
A microthread's queue is empty or full	Only the microthread sleeps; other tasks run.
An input queue is full	The router cannot deliver the next wavelet, so the color stops at every PE on its route and backs up toward the sender.

Carbide runs a socket transfer on the main thread unless the transfer is an arm of a parallel block or has #pragma uthread enable on; those run as microthreads. A main-thread receive whose data never arrives therefore stops the PE's program.

Tasks

The CE runs code as tasks.

• A wavelet that reaches an input queue makes a task ready. A data wavelet readies its queue's task. A control wavelet readies the task that the low six bits of its index name.
• The task picker starts one ready task at a time, round robin, and copies the wavelet that started it into registers. The task runs until an instruction marked terminate ends it; then the picker starts the next task.
• Tasks 8 to 30 can also be started by software (activated) instead of by wavelets. A task can be blocked and unblocked, and a blocked task does not start; this is how tasks wait for each other.

Carbide builds the tasks from the program. The top-level code runs as a task that is active from the start, and each handler of a dispatch block is a task that arriving wavelets start.

Microthreads

A microthread is one instruction that runs on its own. It runs while its fabric or FIFO operand is ready, sleeps when it is not, and wakes when data or space arrives. Meanwhile the main thread goes on with the next instruction.

Microthreads do not add compute. They share the CE's one pipeline with the main thread: each time the pipeline advances, the highest-priority ready thread issues, so a microthread that wakes can interrupt the main thread, even in the middle of a vector instruction. What overlaps is waiting for the fabric with useful work.

The CE has 8 general microthreads, and 4 more that run only the umov copy instructions.

Vector Operands (DSDs)

Most CE instructions take a whole vector as an operand. A data structure descriptor (DSD) describes the vector: an array in memory, by base address, length and stride, or a stream to or from a queue. One instruction then processes the whole vector, up to four 32-bit or eight 16-bit elements per cycle.

Carbide turns a loop into such an instruction where it can. Over 8-element xp arrays, ∀i c[i] <- a[i] + b[i]; compiles to one add16 whose three operands are DSDs, and ∀i tx[] <- a[i]; to one move whose destination is a fabric DSD.

Static Color Routing

Standard inter-PE communication uses statically-configured colors:

let c = color()
sender   : paint(c [C>R])    (* send right *)
receiver : paint(c [L>C])    (* receive from left *)

Paint sets each color's route on every router when it builds the image. A route takes one input direction and sends to any set of outputs. A switching color can change its route while the program runs.

Switch Positions

• 16 of the 24 colors can switch: 0-9, 12, 13, 16, 17, 20 and 21. A switching color has up to four positions, each with its own input and outputs. Paint separates them with ;, as in [L>R ; C>R].
• A control wavelet whose command 0 is advance moves the switch to the next position, and reset returns it to position 0. The input switch changes when the control wavelet arrives and the output switch after it leaves, so the control wavelet leaves by the old outputs.
• A control wavelet keeps its commands as it travels, unless a route pops command 0 (pop=adv in Paint). Without a pop, one advance moves the switch of every router on its path.
• A send can also advance its own PE's input switch with its last word (flip in Tungsten). The output switch does not move, so every position of such a color must have the same outputs.

Color Swapping

Why it is needed

A color on a router sends whatever it takes to all of its outputs, so one color cannot both bring the left neighbour's data to the core and carry the core's data to the right. In lesson 4 the compute PE therefore receives on rxcolor and sends on txcolor. A longer chain needs a new color for every hop, or two colors that alternate from PE to PE, which makes two kinds of PE. A color swap moves a wavelet onto a second color inside the router, so every PE of a row can run the same program on one socket with the same two rules, however long the row is.

What a swap does

A router normally keeps a wavelet on the color it arrived on. With a color swap, a color takes its input from its partner color instead: the wavelets that arrive on the partner from that direction continue on this color. The router does it as part of routing; no core handles the data.

In Paint a color's partner is the color numbered one away, c ^ 1 (0 and 1, 2 and 3, and so on), and colorpair(region a b) makes the color solver number a and b as a pair. The swap replaces > in the route rule and names the inputs that read the partner:

Rule	Inputs read from the partner
[L>R]	none
[LHR]	left and right
[LVR]	up and down
[LXR]	all four neighbours, and the core

Only X swaps the input from the core. A swap belongs to the color on that router, not to one switch position, so every position of a rule must use the same modifier. Paint does not check this: it applies the first position's modifier to every position, without a warning.

Inputs a rule does not swap still read the color's own wavelets, even on a router where the color has no rule. A wavelet goes to every color that reads it, which is how a router copies a wavelet onto several colors, and each of those colors must take its input from the side the wavelet arrives on. If one does not, the wavelet waits and the fabric stalls; if no color reads it, the simulator stops with "arriving wavelet could not land". So a swap usually needs its partner to swap as well, as every step below does.

Step 1: change a wavelet's color

The simplest swap changes the color of one stream. The sender sends on a, and the receiver's router moves the wavelets onto b for its core:

let a = color()
let b = color()

let send = rect(0 0 1 1)
send : code('send [tx:a N:N])
send : paint(a [C>R])
send : name('send)

let recv = rect(1 0 1 1)
recv : code('recv [rx:b N:N])
recv : paint(b [LHC])    (* b takes a from the left, for the core *)
recv : paint(a [LHC])    (* a takes b, so it does not also claim a *)
recv : name('recv)

let row = rect(0 0 2 1)
row : colorpair(a b)

union(row send recv)

b [LHC] makes b read its partner on the left, so what arrives on a continues on b. Without a [LHC], a also reads those wavelets but has no route for them, so the receiver gets nothing. H is enough here because only a side input reads the partner; X works too.

Step 2: one socket for a whole row

A pipeline of K stages sits between a source and a sink. Each stage receives N values from the left, adds 1 to each and sends them right, all on one socket r (stage.w):

xp param N;

socket r;
xp a[n=N];

{
    let i in [0, N);
    ∀i a[i] <- r[];
    ∀i r[] <- a[i] + 1;
}

Every PE, the source and the sink included, has the same two rules:

let r  = color()
let rp = color()

let row = rect(0 0 K+2 1)
row : paint(rp [CXR|R])   (* rp takes what the core sends on r and carries it right *)
row : paint(r  [L|LXC])   (* r takes rp arriving from the left, for the core *)
row : colorpair(r rp)

let src = rect(0 0 1 1)
src : code('send [tx:r N:N])
src : name('send)

let stages = rect(1 0 K 1)
stages : code('stage [r:r N:N])
stages : name('stage)

let sink = rect(K+1 0 1 1)
sink : code('recv [rx:r N:N])
sink : name('recv)

union(row src stages sink)

The cores send and receive on r; between PEs the data travels on rp. rp [CXR|R] takes what the core sends on r and carries it right, and r [L|LXC] takes rp arriving from the left and gives it to the core, so each rule is the other's partner swap. r needs X, not H: with H, r's core input still reads what the core sends on r, r has no route from the core, and nothing reaches the sink. |R and L| end the route at the two ends of the row (boundary operators), and the same layout runs for any K. The Smith-Waterman wavefront of lesson 8 streams this way.

Step 3: four directions

The halo exchange of lesson 11 reaches all four neighbours by repeating step 2 once per direction: four sockets, four color pairs and the same eight rules on every PE, such as ap [CXR|R] with a [L|LXC] for data moving right and bp [CXL|L] with b [R|RXC] for data moving left.

Step 4: turn a route around

A swap can also send a stream back the way it came. In the nine-point heat equation, the moat PE at the right end of a row takes what arrives on c0 and sends it back west on c0x (c0x [LXL]), and c0 [LXL] swaps c0 too, so that c0 does not also claim those wavelets. The grid passes c0x through ([R>L]), and the moat at the left end sends it east again on c0 with the mirror pair, c0 [RXR] and c0x [RXR], so the row wraps around without a core relaying the data.

The figure draws step 2 in Smith-Waterman and step 4 in the heat equation.

On the hardware, each color selects its input color separately for the north/south inputs, the east/west inputs and the core. The north/south and east/west inputs can read the colors one or two away, and the core input only the color itself or c ^ 1. Paint uses c ^ 1 for all three.

Message Passing (MP)

Message passing provides dynamic, coordinate-based routing. Instead of pre-configured color routes, the sender specifies the destination's fabric coordinates in a header wavelet:

Header format (32-bit wavelet):
  bits 31:20 : destination column ID
  bits 19:8  : destination row ID
  bit  7     : 1 if destination is north of source (smaller row ID)
  bit  6     : 1 if destination is south of source (larger row ID)
  bit  5     : 0 = bits 4:0 give the length; 1 = software ends the
               message with the control bit
  bits 4:0   : number of data wavelets to follow, at most 31

A message travels along X first, then along Y, and the destination's router hands it to the CE.

MP uses dedicated banks of colors:

• Bank 0 uses physical colors 14–18, and bank 1 colors 19–23
• Each bank requires 5 colors for the hardware routing protocol, one per input direction (N, S, E, W, CE)
• MP and normal colors coexist on the same PE

MP Constraints

1. All MP wavelets must be 32 bits. A lone 16-bit xp sent directly may leave as a half-wavelet (Wavelets). Half-wavelets may not be sent on message-passing colors, and sending one is undefined behavior.
2. Pack xp into u32, for example with a union:

   union payload { u32 u; xp w[2]; };
   union payload data;
   data.w[0] <- value;
   data.w[1] <- 0;
   sock[]    <- data.u;   // full 32-bit wavelet

   Shifts work too: ((u32)(u16) hi << 16) | (u32)(u16) lo. Without the (u16) step, (u32) of a negative xp sign-extends and fills the upper half with ones.
3. Relay PEs must have mp(bank) enabled even if they don't process the message — the MP hardware needs to forward wavelets through them.
4. Finish every message. A message holds its path until its last wavelet has passed, so a sender that stops partway locks that path for other messages.

Hardware Registers

Address	Register	Description
0x7C46	Column ID	PE's fabric X coordinate
0x7C45	Row ID	PE's fabric Y coordinate

The router reads them to route messages. Access via address():

xp col_id[1] address(0x7C46);
xp my_col = col_id[0];

See the tutorial topics Message passing: routing by address and Collectives over messages for MP patterns.

---

Memory Layout

PE Memory Map (simplified)

0x0000 +------------------------+
       | Main memory, 48 KB     |  code and data, placed by the compiler;
       | (24,576 words)         |  the stack grows down from 0x6000
0x6000 +------------------------+
       | Reserved (reads 0)     |
0x7200 +------------------------+
       | Configuration          |  router and queue setup, row/column ID,
       | registers              |  DSDs, ... (with reserved gaps)
0x7F00 +------------------------+
       | Data cache, 256 words  |
0x7FFF +------------------------+

Addresses are 16-bit word addresses; memory is not byte-addressable. A 32-bit value starts at an even address.

The exact layout is determined by the compiler. You don't usually need to worry about it — just access data via symbols.

---

Color Limitations

• Each PE has 24 physical colors on WSE-3; 16 of them can switch positions: 0-9, 12, 13, 16, 17, 20 and 21
• A color has one routing rule per switch position: one input direction, sent to one or more outputs
• The semicolon syntax ([L>R ; C>R]) gives a switching-capable color up to four positions, which control wavelets or flip advance through
• The CE receives on at most 8 colors and sends on at most 8, one queue each (The CE's Queues)
• MP reserves 5 colors per enabled bank: 14–18 for bank 0, 19–23 for bank 1
• If you run out of colors, you need to reorganize your routing or use message passing for some communication

---

The 3D Address Space

Every piece of data has a 3D address (W, X, Y):

Axis	Meaning	Range
W	Memory word offset within a PE	0x0000–0x7FFF
X	Column (PE X coordinate)	0 to fabric width − 1
Y	Row (PE Y coordinate)	0 to fabric height − 1

This is used by miget/miset to locate symbols in the compiled image.

---

Simulation

simfabric

The simulator executes the program cycle-by-cycle. It runs an ELF, so the build converts the image first and converts the simulator's core back:

mielf image=bench.img elf=bench.elf
simfabric elf=bench.elf core=bench.elf-core json=0 cycles=1000 > bench-sim.log
elfmi image=bench-sim.core elf=bench.elf-core

The Makefile runs these steps for you, with $(SIMFABRIC) as the simulator, simfabric by default. The experimental SDK runs simfabric through SIMFABRIC=simfabric-sdk (Run the tutorials). The simulation log is its standard output. Key options:

Option	Description
elf=	Input program (from mielf)
core=	Output core (final PE state), which elfmi turns into an image
cycles=	Maximum simulation cycles
debug=	Extra log records: hwtile (pipeline), landing (wavelet landings)

Core Dumps

After simulation, bench-sim.core contains the final state of every PE's memory. Make deletes it, and in some lessons the map, once the test has run; rebuild both from the example's directory (test-1/ instead of test-tutorial/ in lessons with two tutorial rows), then use miget to extract symbol values:

make test-tutorial/bench-sim.core test-tutorial/bench.map
cd test-tutorial
miget image=bench-sim.core map=bench.map symbol=recv.a text

---

Useful Commands

# Print Carbide's version
carbide version

# Print paint's and miget's options
paint help
miget help

# Dump the symbol table
cat bench.map

# Run paint by hand in the example's directory. set= supplies what a test.rc
# row would, and the toolname terms select Carbide, as the build does. The
# build also runs milink and weight afterwards, which this does not.
paint source=bench.paint lib=. set=N=4 arch=sdr verbose \
    toolname w carbide toolname yeti carbide \
    image=bench.obj map=bench.map

References

• Architecture Target
• Raw Wavelet Send/Receive via Union
• Hardware Register Access
• Message Header Format
• Paint Direction Codes
• Reading Paint
• Paint Color Pairs
• Paint Color Swap Modifiers
• Paint Switch Positions
• Paint Banks
• Paint Constraints
• The 3D Fabric Address Space