GPU Compute

On this page

Compute entry points
The kernel's interface
Failures: the error buffer
Slices on the GPU
Math on the GPU
Closures on the GPU
What a GPU lacks
A package's kernels
A package's gpu/ folder
Atomics
Workgroup memory
Barriers
Barriers on the CPU
The CPU twin: a workgroup run together

Note: Not implemented: textures in a kernel, a checked form of workgroup memory and of the buffers a kernel writes, one package's gpu/ folder used by another's, f16, and any GPU target but SPIR-V's Vulkan form.

A GPU runs one function, a kernel, thousands of times at once, each run an invocation working on its own part of the data. Cone writes a kernel as an ordinary function marked as a compute entry point. Compiled for a GPU, it is a compute shader whose parameters are what the program's dispatch binds; compiled for the CPU, it is an ordinary function, which a loop over the invocations runs, so one source is both the GPU's work and its twin on the CPU.

Compute entry points#

struct Part {
  pub w Array[f32, 4];
  pub k u32;
}

fn @compute(64) bake(inv Invocation, parts &Array[Part], out &mut Array[f32]) {
  imm i = usize.from(inv.globalId[0]);
  if i < out.len {
    out[i] = parts[i].w[0] * f32.from(parts[i].k);
  }
}

@compute, written after fn, makes the function a compute entry point and gives its workgroup's size: how many invocations run together, along x, y and z, those not written being 1: @compute(64), @compute(8, 8), @compute(4, 4, 4). Each is a constant integer of at least 1, and a workgroup holds at most 256 invocations and 64 along z, the limits every WebGPU device guarantees. An entry point is a function of its module: not a method, not generic, not inline, not @c. An extern one, as a package's include file declares it, is called on the CPU as any function is.

Compiled for a GPU, the entry points of a module are written as SPIR-V's Vulkan form: conec --triple=spirv1.6-unknown-vulkan1.3 writes <name>.spv, holding each entry point under its function's name. SPIR-V's OpenCL form (--triple=spirv64-unknown-unknown) has kernels of another kind, and a compute entry point compiled for it is refused (Error 1263). For a package, Congo builds the module (A package's kernels, below).

An entry point returns nothing: what a kernel makes, it writes into a slice it was given. Its parameters are what a dispatch binds, each of one of three kinds, in any order:

Invocation, at most once: which invocation is running. It is core's Invocation, a plain struct: globalId, the invocation's id in the whole dispatch, localId, its id in its workgroup, and groupId, its workgroup's, each an Array[u32, 3]; localIndex, its place in its workgroup counted x fastest; and groupCount, how many workgroups the dispatch has each way. On the GPU it is filled from the invocation's built-in values; on the CPU, the loop that calls the function fills it.
A slice, one storage buffer: &Array[T] the kernel only reads, and &mut Array[T] it writes as well. Its length is the buffer's. Every invocation may write any element of a &mut Array[T] buffer; that two do not write one element is the program's to arrange, a trusted exception to Cone's rule against threads sharing what they change, until a checked form is designed.
A struct taken by value, one small read-only storage buffer holding one value: the kernel's settings. (WebGPU has no push constants, and a uniform buffer lays an array out in 16-byte steps, which is not Cone's layout.)

A kernel binds at most seven buffers: WebGPU's eight storage buffers a stage, less the error buffer (below).

What a buffer holds is shared byte for byte between the CPU and the GPU, so it may hold only what the two lay out alike: 32-bit numbers (i32, u32, f32), their atomics (Atomic[u32] and Atomic[i32], below), and structs and fixed arrays of them, nested as deep as wanted. A bool, a number of 8, 16 or 64 bits, usize or isize (as wide as each target's addresses), a reference, slice or pointer, an enum or an Option is refused, with the field that holds it. A struct of three f32s is twelve bytes on both sides: Cone never makes one of a GPU's vector types, which a buffer aligns to sixteen.

The kernel's interface#

The buffers are bound in descriptor set 0, numbered by their place among the buffer parameters, from 0: in bake above, parts is binding 0 and out binding 1. The kernel's entry point in the SPIR-V module is named as the function is.

Failures: the error buffer#

A GPU has no program to end. On one, a failed index or range check, a panic, an assert, an unreachable or a todo records what failed in the kernel's error buffer and stops that invocation, the others going on. The checks are kept in every build. The error buffer is a read-write storage buffer bound after the last of the kernel's buffers (binding 2 in bake), of eight 32-bit words, zero before the dispatch:

Word	Holds
0	How many invocations failed; 0 when none did
1	What failed: 1 an index past the end, 2 a range not within its array or slice, 3 a panic (an assert among them), 4 an allocation
2	The source file's id: the name its module lists for it, in the debug string "cone.file <id> <name>" (an OpSourceExtension); 0 when not known
3	The line
4, 5, 6	The failed invocation's globalId
7	The index that was out of bounds, or the end of the range; else 0

The first invocation to fail writes words 1 to 7, so they describe one failure whole; any that fail after it only count. The gpuwork package binds a zeroed error buffer to each dispatch and reads it afterwards, reporting a failure in the job's completion, and the program goes on.

Slices on the GPU#

A GPU has no pointer arithmetic: it reaches an element from the variable that holds it. So in a kernel a slice is indexed in what it came from: a buffer parameter, or a fixed array, all of it or part, a local, a constant or a field of a buffer's struct, however many functions it was handed through and however it was cut. A slice that came from anything else, a pointer to a single value say, is refused where it is indexed.

Math on the GPU#

No GPU has the C library. A call to one of its math functions, the libc package's or any @c function of the same C name, is on a GPU the GPU's own instruction (GLSL.std.450's, in SPIR-V), as are f32's and f64's sqrt, sin and cos methods. On the CPU nothing changes: the C library is called.

C function (and its f form)	On the GPU	Vulkan's precision	Measured against the CPU
fabs, floor, ceil	FAbs, Floor, Ceil	exact	bit for bit
fmod	OpFRem (the sign of x, as C's)	from x - y trunc(x / y)	bit for bit where the driver fuses it, which it may not
sqrt	Sqrt	from 1 / InverseSqrt	within 1 ulp
asin, acos, atan, atan2	Asin, Acos, Atan, Atan2	atan and atan2 4096 ulp; asin and acos from atan2	within 2 ulp
exp, log, pow	Exp, Log, Pow	3 + 2\|x\| ulp; 3 ulp outside [0.5, 2], absolute 2^-21 inside; from exp2(y log2 x)	exp within 8 ulp over [-10, 10]; log within 87 ulp (near 1, where it is near 0, 1e-6 absolute); pow within 27 ulp
sin, cos, tan	Sin, Cos, Tan	absolute 2^-11 in [-pi, pi]; tan from sin / cos	absolute 4e-7 in [-pi, pi], 1e-5 in [-100, 100]; tan 4e-5 in [-1.5, 1.5]

What was measured was an RTX 4060 against the Windows C runtime, 65,536 arguments a function. Where a precision is an approximation, two GPUs differ from each other as well as from the CPU, and nothing computed from such a function is the same everywhere. The f64 forms of the exact functions and of sqrt and fmod are the GPU's at 64 bits, which needs a device with 64-bit floats (WebGPU has none); Vulkan has no 64-bit sin, cos, tan, inverse trigonometry, exp, log or pow, and refuses a module that asks for one.

A GPU's driver may also fuse a multiply and an add into one rounding, or reorder a sum, which the CPU does not. conec forbids both in everything it compiles for the GPU: each float addition, subtraction, multiplication, division and negation is rounded on its own, in the order written, as the CPU rounds it (SPIR-V's NoContraction, on every such result). Vulkan rounds an addition, a subtraction and a multiplication correctly, so arithmetic built only from those, floor, ceil, fabs and comparisons gives the same bits on every GPU as on the CPU, a subnormal result aside, which Vulkan lets a GPU flush to zero. noise's fBm, measured, matches the CPU at every one of its bake's 262,144 points, value and derivatives, as do its value and gradient noise, its other fractal sums and its warps. What takes a square root, a division (Vulkan's bound 2.5 ulp, measured within 2) or another function of the table above is close, not identical. A remainder, fmod, is left free to fuse, since that is how the RTX 4060 computes C's exact remainder: forbidden, it matched at 62% of arguments. The CPU never fuses, on any CPU conec targets, one with fused multiply-add instructions too (--cpu=native).

Closures on the GPU#

A closure may be written in GPU code in its static form only: given to a generic bound by a signature, as in shade(p => p.dot(p) - radius * radius, pt) for fn shade[F fn(p Vec3) f32](f &F, p Vec3) f32. The generic is instanced for the closure and inlined into the kernel with every other call, so the closure is only some locals of the invocation, and a hand-written struct with a () method goes through the same generic. A closure holds what a GPU has: numbers, structs and arrays of them, and borrows of memory the GPU has (a local, a buffer's slice), whether listed as its state or borrowed from the code around it; an owning reference (So, Rc), a function reference, a virtual reference or a raw pointer anywhere inside is refused, naming the variable. A GPU has no pointers to code, so a closure made a function reference, &fn(...), or a virtual reference is refused too.

What a GPU lacks#

A GPU has no pointers to code, no tables of them, no allocator, no threads and no operating system, and GPU code that writes any of them is refused, naming it, wherever it is written, whether or not a kernel reaches it:

a reference to a function (&double, or an anonymous &fn(...) {...}), since every call is inlined into the kernel;
a reference made a virtual reference (&<Shape from a &Ball), which would be called through a table;
an allocation (new So[T], new Rc[T], trynew), and an owning reference type written at all, So[T], Rc[T], Arc[imm, T], a lock's Rc[Rwcell, T], in a parameter, a field, a return type or a local, since a kernel's memory is its locals and the buffers it is bound, and nothing could own more;
threads: an actor declaration, a parallel each and an await, which run on worker threads. A kernel is already one function run by thousands of invocations at once, each taking its part by its id;
a call of a function defined elsewhere, which is code that is not there: the C library's allocator, files, streams and the rest of what libc binds, and any extern function a program declares. Only the C library's math (sqrt, sin, cos, tan, asin, acos, atan, atan2, exp, log, pow, fabs, floor, ceil, fmod and their float forms), which a GPU has as instructions of its own, and core's panic, which a GPU records, are there. A binding's inline function that calls what it wraps (libc.errno()) is refused where a kernel calls it.

Calling a function by name, a generic bound by a signature or a trait ([F fn(...)], [S Shape], inlined), a borrow of a local or of a buffer's slice, atomics, and building a struct as a value are the way to do the same. Locks need an owner, or the sync package, so a lock is refused as they are; the packages that hold threads, locks, files and collections are not marked for the GPU, so Congo refuses the build that imports them, naming the import, before the compiler is run.

A package's kernels#

Whether a package may run on a GPU is said by the package: its manifest marks it, targets = ["native", "gpu"] in Congo's congo.toml (a spelling that may yet change). Congo compiles a marked library whose source holds compute entry points for the GPU as well as for the CPU, into one SPIR-V module, <package>.spv, holding each of its kernels, and copies it beside every program that imports the package, where gpuwork's readSpirv reads it. Every package a kernel's package imports, at any depth, must be marked too, or Congo refuses the build before compiling anything, naming the imports that reached the unmarked one.

On a GPU every function a kernel calls is inlined into it, so no function is marked for the GPU on its own and none carries its body in an include file: the marked packages a kernel imports are compiled into its module from their source. Only what a kernel reaches becomes part of it. Which of a marked package's features a GPU lacks is the compiler's to say, where they are used. (tools/congo/README.md, "Kernels for the GPU", is how Congo does it.)

A package's gpu/ folder#

Marking a whole package suits a library that is GPU code throughout. A package that is partly GPU code, a program that dispatches its own kernels say, keeps that part in a gpu/ folder beside its src/. Being in the folder is what marks it: nothing in the manifest, and nothing on any function. gpu/ is compiled into the package for the CPU, so that src/ calls the same functions and both halves share one declaration of each buffer's struct, and compiled for the GPU, without src/, into the package's one <package>.spv, holding every compute entry point in gpu/. A program's main stays in src/ and never reaches the GPU.

gpupart/
  congo.toml          output = "executable"
  src/gpupart.cone    mod gpupart; ... use pattern Settings, Cell;
  src/main.cone       calls pattern.cell(i, s) on the CPU, dispatches 'fill' on the GPU
  gpu/pattern.cone    mod pattern; import noise use pcg, toUnit; cell, and the kernel 'fill'

The modules in gpu/ are submodules of the package's root module, laid out as they would be in src/: a file opening with its own mod line is a module of one file named for the file, and a folder holding its designated file is a module folder. So src/ reaches them as it reaches any submodule, by path (pattern.cell(i, s)) or folded with use, and nothing new is written to reach them. The rules:

gpu/ may not use src/: a module of gpu/ importing or extending a module of src/, or importing a name of the root, is an error, since gpu/ is compiled for the GPU without it. src/ may use all of gpu/, and the modules of gpu/ import one another as sisters.
Every package gpu/ imports, at any depth, must be marked for the GPU, as every package a marked package imports must be: so I/O, threads, actors, locks and collections, whose packages are not marked, are refused there, naming the import that reached each.
What a GPU lacks inside gpu/ is the compiler's to refuse, as it is inside a marked package; everything in gpu/ is compiled for the GPU, whether a kernel calls it or not.
A file directly in gpu/ with no mod line, a folder there with no designated file, and a module named as one of src/'s are errors, and a package marked for the GPU has no gpu/ folder.
A gpu/ folder with no compute entry point builds no .spv.

The modules of one package's gpu/ cannot yet be used by another package's GPU code: only a marked package can be imported there. (tools/congo/README.md, "A package's gpu/ folder", is how Congo does it.)

Atomics#

fn @compute(64) compact(inv Invocation, input &Array[u32], count &mut Array[Atomic[u32]], out &mut Array[u32]) {
  imm i = usize.from(inv.globalId[0]);
  if i < input.len and input[i] % 3u32 == 0u32 {
    imm slot = count[0usize].addOrdered(1u32, MemOrder.Relaxed);
    out[usize.from(slot)] = input[i];
  }
}

A buffer of Atomic[u32] or Atomic[i32] holds numbers that invocations change together, each change indivisible: a counter several invocations add to, or one that hands each kept element its slot, as above. It is core's Atomic, the same type and the same methods as on the CPU: four bytes, its number and nothing more, as WebGPU's atomic<u32> is, so the CPU reads the buffer as numbers. An atomic may also be a field of a buffer's struct, or an element of a workgroup global. An Atomic of anything else (a u64, a bool, a pointer) is refused in a buffer, as its number would be.

Every method an integer Atomic has works on a GPU: load, store, swap, add, sub, min, max (signed for an i32, unsigned for a u32), bitAnd, bitOr, bitXor and compareSwap, each with its Ordered form. Each acts at the scope of the memory it changes: a buffer's is the device, every invocation of the dispatch; a workgroup global's is its workgroup. Vulkan has no sequentially consistent ordering, so on a GPU SeqCst, what the everyday forms promise, is acquire-release; Relaxed, Acquire, Release and AcqRel are as written. A counter needs no ordering beyond its own change, so Relaxed is the right one for claiming a slot.

An atomic acts on memory invocations share. One on a local Atomic, or on a module's global that is not @workgroup, each invocation's own, is refused in the kernel.

Workgroup memory#

mut @workgroup scan Array[u32, 256];

fn @compute(256) prefix(inv Invocation, input &Array[u32], out &mut Array[u32]) {
  imm g = usize.from(inv.globalId[0]);
  imm l = usize.from(inv.localIndex);
  scan[l] = if g < input.len {input[g];} else {0u32;};
  workgroupBarrier();
  mut step = 1usize;
  while step < 256usize {
    imm add = if l >= step {scan[l - step];} else {0u32;};
    workgroupBarrier();
    scan[l] = scan[l] + add;
    workgroupBarrier();
    step = step * 2usize;
  }
  if g < out.len { out[g] = scan[l]; }
}

A module's global written with @workgroup after its permission is workgroup memory: on a GPU, one copy for each workgroup, which its invocations share, and which is far faster than a buffer. It is written as @threadlocal is: a module's global, mut, of a fixed size, holding what a buffer may hold (32-bit numbers, their atomics, and structs and fixed arrays of them) and nothing that needs finalizing. It has no initial value: a workgroup's copy starts undefined, so the invocations write what they will read, then wait at a barrier before reading what the others wrote. An initial value is refused, zero among them.

Invocations reading and writing one global is a trusted exception to Cone's rule against threads sharing what they change, as a &mut Array[T] buffer is: that one invocation does not read a place another is writing, without a barrier between, is the program's to arrange. (A checked form, each invocation owning its own place and reading the others' only after a barrier, is to come.)

On the CPU a workgroup global is an ordinary global, one copy, and the workgroups run one after another, so that copy serves the workgroup running. A loop that runs a workgroup's invocations one at a time gives the GPU's answer for a kernel whose invocations read, after a barrier, only what the invocations before them in that order wrote (the last invocation of a workgroup gathering what the others counted, say). One whose invocations read what invocations after them write, as the prefix sum above does, needs its workgroup's invocations run together, on threads that meet at each barrier: what the barrier hook is for, and what gpuwork does for a kernel's CPU twin. Nothing resets the one copy between workgroups, which on a GPU starts undefined anyway.

Barriers#

pub fn @intrinsic workgroupBarrier()
pub fn @intrinsic storageBarrier()

Core's two barriers: every invocation of the workgroup waits at one until all have reached it, and what each wrote before it every other reads after it. After workgroupBarrier, that is what was written to workgroup memory; after storageBarrier, what was written to the buffers the kernel binds, as the other invocations of the same workgroup see it. Every invocation of a workgroup must reach the same barrier, so one is never written where some invocations of a workgroup go and others do not.

Barriers on the CPU#

pub extern {
  fn setBarrierHook(hook &fn(ctx *u8, kind u32), ctx *u8);
  fn clearBarrierHook();
}

On the CPU a kernel is an ordinary function, and what a barrier must do depends on how the program runs it. Run one invocation at a time, there is no one to wait for, and a barrier does nothing. Run with a workgroup's invocations on threads, one a thread, each thread must wait at every barrier until the others have reached it. So on the CPU each barrier calls a function the running thread names, its barrier hook, and does nothing when the thread has named none. A thread that runs invocations together sets its hook to a real barrier, and every barrier the kernel reaches on that thread waits there.

setBarrierHook(hook, ctx) sets this thread's hook: each barrier calls hook(ctx, kind), where ctx is what was given here, the barrier itself say, and kind is 0 at a workgroupBarrier and 1 at a storageBarrier. clearBarrierHook() takes it away. Each thread has its own hook, none until it sets one, so a thread pool's thread sets its hook once, two twins can run workgroups at once on threads of their own, and a thread that set none runs a kernel one invocation at a time as before. On the CPU memory is the same for both kinds, so one barrier serves both. Both are core's, the work conestd's, and on a GPU the hook is never called.

fn wait(ctx *u8, kind u32) {
  imm b = ctx as *Barrier;     // the program's own: a count and a generation, say
  ...                          // every invocation's thread waits here for the others
}

fn lane(l Lane) {              // one invocation of each workgroup, on its own thread
  setBarrierHook(&wait, l.bar as *u8);
  ...                          // the kernel, called for this thread's invocations
  clearBarrierHook();
}

The hook is called on the thread the barrier is on, and what it does is the program's: it must not return until every invocation of the workgroup has reached the barrier, and must order memory as a lock does, what each wrote before seen by every other after (the sync package's atomics and futex do both). A hook that returns at once, or one set on a thread that runs a workgroup's invocations one at a time, makes the barrier nothing; one whose wait never ends, because an invocation of the workgroup never comes, never returns. The compiler's test concurrency_compute_barrier_threads runs the prefix sum above this way, its four invocations on four threads.

With no hook set, a barrier costs the load of the thread's hook and a branch not taken. Measured on an i7-13700HX, the prefix sum above, with 17 barriers an invocation, ran in 13 to 15 ns an invocation against 2.7 to 3.5 ns with its barriers taken out, about 0.6 ns a barrier. That is the load (on Windows a thread-local is reached by four loads) and what the optimizer may no longer do across a barrier, since a hook, if set, lets other threads change workgroup memory there. On WebAssembly a barrier is nothing.

The CPU twin: a workgroup run together#

The gpuwork package runs a kernel's CPU twin with runTwin, over the same buffers a dispatch has, workgroup by workgroup, x fastest. A kernel with no barrier runs its invocations one at a time, x fastest, on the calling thread. A kernel with one (Kernel.make finds an OpControlBarrier in its SPIR-V, in the entry point or in any function it calls, however deep) runs each workgroup's invocations together: one thread for each invocation, at most 256 to a workgroup (a larger one is refused), started by runTwin and joined before it returns. Each thread sets its barrier hook to a barrier that waits for every thread of the workgroup and orders memory as a lock does, so a prefix sum across a workgroup, or a tree reduction, whose invocations read after a barrier what others wrote, gives the GPU's answer on its twin. A storageBarrier waits as a workgroupBarrier does.

The threads meet again after each workgroup, so the workgroups still run one after another and the one copy of each @workgroup global is the running workgroup's. As on the GPU, every invocation must reach every barrier the others of its workgroup reach: one that returns early, or fails, leaves the others waiting for ever.