Semantic conjugate gradient

Overview

The conjugate-gradient program is the first end-to-end pressure test of the semantic GPU graph layer. The solver itself contains no WebGPU buffers, command nodes, bindings, WGSL, dispatch counts, or indirect-command implementation details.

At a glance

Question	Answer
Problem	Express preconditioned conjugate gradient as one portable semantic GPU graph.
Reads / writes	Reads external CSR and vector state while updating logical solver vectors and scalars.
Ownership	External inputs remain caller-owned; compiler-created scratch and gates are graph-owned.
Output contract	A bounded approximate solution with GPU-resident convergence state.
Expected work	Initialization plus bounded iterations of SpMV, reductions, scalar math, and vector updates.
Chunks	The baseline program uses explicit dense vectors and one CSR matrix domain.
Conditions / budgets	WebGPU lowers convergence to a bounded GPU-gated command sequence.
Neighborhood	CSR system + solver settings → semantic PCG → backend command graph.

CostMaximum iterations bound graph size; active work falls after convergence.

Common mistakeDo not synchronize residual state through the CPU between solver iterations.

GPUGraph
  external CSR matrix
  external rhs + initial solution
  scalar literals
  initial SpMV
  residual/search initialization
  dot
  GPULoopOperation(residual² > tolerance²)
    SpMV
    dot
    scalar divide
    vector MADD
    scalar compare
        |
        v
GPUGraphCompiler (WebGPU)
        |
        +-- external vectors -> imported graph buffers
        +-- scratch vectors  -> transient graph storage
        +-- scalars          -> packed GPUValueArena
        +-- SpMV             -> adaptive WebGPU strategy
        +-- loop             -> bounded GPU-gated dispatch sequence
        v
GPUCommandGraph

External resource binding

GPUGraph declares logical external vectors. Typed GPUData chunks are supplied only when the program is compiled:

const solver = createGPUConjugateGradientGraph({
  size: n,
  nonZeros: nnz,
  maxIterations: 128,
  toleranceSquared: 1e-10
});

const compilation = new GPUGraphCompiler(device).compile(solver.program, {
  vectors: {
    [solver.rowOffsets.id]: rowOffsetsData,
    [solver.columnIndices.id]: columnIndicesData,
    [solver.values.id]: valuesData,
    [solver.rhs.id]: rhsData,
    [solver.solution.id]: solutionData
  }
});

The current CSR backend requires one physical chunk for each operand. Wrap existing buffers in GPUData with their format and length; binding never concatenates batches.

A future CUDA compiler can bind the same logical vectors to CUDA allocations without changing the program.

Adaptive SpMV inside runtime control

SpMV is an important compiler test because one semantic operation may emit one or two compute nodes depending on the selected strategy. The WebGPU lowering records exact dispatch geometry for every emitted node. This lets the runtime-control lowering gate each concrete dispatch independently rather than assuming one operation equals one dispatch.

Iteration semantics

The first PCG iteration is unconditional. It computes the convergence flag on the GPU. Remaining iterations are pre-encoded to the declared maximum and every compute dispatch is gated by that GPU-resident flag. Once the residual reaches tolerance, subsequent work receives a zero indirect dispatch dimension and performs no numerical work.

There is no convergence readback between iterations.

This is a WebGPU realization, not part of PCG semantics. A backend with native graph loops can lower the same GPULoopOperation differently.