Part I · Ch. 6 — Shaping a Problem for the GPU

Part I · Chapter 6 of 29

Shaping a Problem for the GPU

Choose the axes before writing the computation


What repeats, and what is shared?

A math problem almost never arrives with its tensor layout chosen. You decide what repeats, what is shared, and what waits on an earlier result. Shape design is making those choices explicit as axes and lengths. The operations from the last chapter turn that question into a procedure you can repeat.

Start with the first layer of our fixed model. Its weight array has three rows and two columns. Give it two examples, (1,0) and (0,1). Each example meets the same three rows of weights. The example index names independent repetitions, the feature index names contributions to be added, and the output index names the three units produced for each example.

The batch-by-feature input and unit-by-feature weights produce a batch-by-unit output. Output [i,k] reduces feature j in X[i,j] times W[k,j], then adds bias[k].
Choose axes by what repeats and what is shared.

Write the input shape as (2,2): two examples, two features each. The weight shape is (3,2): three output units, two feature multipliers each. The output shape is (2,3): two examples, three results each. The feature length has to agree between input and weights, because each dot product matches those entries one for one.

Let i select an example, j select a feature, and k select an output unit. The indexed rule is “sum over j of XᵢⱼWₖⱼ, then add bₖ.” Only j is reduced. Writing down what the indices mean beats memorizing an unlabeled pattern of dimensions, and it saves you when the same length shows up on several axes.

Two examples, one shared layer

Use W=[[1,0],[0,1],[1,−1]] and b=(0,1,−1). For (1,0), the preactivation row is (1,1,0). For (0,1), it is (0,2,−2). The last result of the second row, for instance, is 1×0−1×1−1=−2. The weight table is reused; each example does not get a learned table of its own.

In row-major storage the last axis varies fastest, so putting frequently traversed features next to each other helps the dot products read efficiently. Contiguity alone doesn’t pick the fastest implementation. The library’s supported operations, its tiling, its temporary storage and its access pattern all count. Fix a clear shape contract first, then measure an implementation.

A polynomial is a table of repeated features

Fitting a polynomial is another way to find shared features. A polynomial combines powers of an input with coefficients. For a line the two features are the constant 1 and the value x. The same coefficient pair serves every example, so changing the coefficients changes every prediction through that one shared rule.

Four panels show polynomial features producing (1,3,5), an advection update that waits for the old state, all-pair scores, and a sign-dependent chain 0 → 1 → −2 → −4.
Similar array shapes can carry different dependencies.

Use x=0,1,2 with targets y=1,3,5. The feature rows are [1,0], [1,1], and [1,2]. Coefficients (1,2) give 1,3,5 by dot products. Fitting means choosing coefficients that shrink the mismatch between predictions and targets. Least squares chooses the coefficients that minimize the sum of squared prediction misses.

The normal equations group sums of products of features and targets into a smaller coefficient problem. We use them here because every number stays small enough to check by hand. Real fitting code usually avoids them, because building them can amplify sensitivity to rounding when feature directions are nearly redundant.

Solve the coefficient equations

The grouped sums are: sum 1=3, sum x=3, sum x²=5, sum y=9, and sum xy=13. So [[3,3],[3,5]](b,a)=(9,13). The first row says 3b+3a=9; the second says 3b+5a=13. Subtract to get 2a=4, so a=2. Then 3b+6=9 gives b=1.

In that pair, b is the constant coefficient and a multiplies x. Their order follows the feature columns [1,x]. Reverse the coefficient list without reversing the feature columns and the prediction changes. A length-two vector isn’t described until you know what its two positions mean.

Some axes repeat; time may still wait

Advection means transport across space. A grid update repeats the same local rule across many positions, so the spatial locations are candidates for parallel work. Time can stay sequential, because the next grid depends on the previous grid’s results. One tensor can hold both independently repeated work and a dependency no number of lanes removes.

One periodic transport step

Take the teaching row [1,3,1] and a transport fraction of 1/2. Each new cell is half itself plus half its left neighbor, wrapping around at the edge. The first becomes (1+1)/2=1, the second (3+1)/2=2, and the third (1+3)/2=2. The new row is [1,2,2]. Every calculation reads the old row.

A rule that reads a fixed neighborhood of cells like this is called a stencil. This one is a teaching rule, not a weather model’s. The cells of one new row can be calculated together, and the next time step needs that row complete.

A table of pair scores

Use the three vectors (1,0), (0,1), and (1,1). All pair dot products form [[1,0,1],[0,1,1],[1,1,2]]. The last entry is 1×1+1×1=2. Two position axes survive into the pair table, while the two-coordinate feature axis is reduced inside each dot product.

Attention, later in the book, builds on this kind of comparison table. The array structure is what matters now: every row position meets every column position. When examples have different lengths, padding adds entries to reach a common size, and a mask says which entries to leave out of the real work.

A branch that needs its predecessor

Let the rule be s_next=s+x when s is nonnegative, and s_next=s−x otherwise. Start s=0 and use [1,−3,2]. The states are 1, −2, −4. At the final input the negative previous state selects subtraction: −2−2=−4. That branch cannot be chosen without the state before it.

Chunking handles groups of manageable size while respecting dependencies like that one. You can batch many independent sequences, each with its own state, or cut a long sequence into pieces and pass state between them. Either changes organization and memory demand. Neither turns a state-dependent branch into an independent output cell.

How much work per byte moved?

Arithmetic intensity counts arithmetic operations per byte moved under a stated traffic model. Achieved performance divides arithmetic work by elapsed seconds. A roofline puts that achieved rate against two guides: a compute ceiling and a memory-transfer ceiling. At low intensity, movement can limit performance; at higher intensity, arithmetic becomes the limit.

CPU and GPU panels plot measured FLOPs per second against modeled FLOPs per byte on logarithmic axes. Each panel draws timed matrix products under that processor's fastest measured compute rate and copy speed; the byte count assumes 12n squared bytes of float32 traffic.
Timed matrix products under each processor’s measured ceilings.

For square float32 matrix products of side n, use approximate work 2n³ and idealized minimum traffic 12n² bytes. Two input matrices and one output matrix, each with n² four-byte entries, give that figure. Dividing gives modeled intensity n/6 FLOPs per byte. The 12n² assumes each matrix crosses memory exactly once; real hardware moves more than that through its caches.

The points are matrix products we timed at a range of sizes. The ceiling lines come from separate runs that found the fastest matrix-product rate and the fastest memory copy each processor reached. Each panel uses its own processor’s ceilings.

A tera-FLOP is a trillion arithmetic operations, and a gigabyte on this page means a billion bytes. A roofline points at which resource to investigate, and its conclusion is only as good as its byte model and the match between the measured operation and the problem you intend to run.

Where this shows up when you train

Use the designer to state sizes and assign axis roles. Start with independent examples, shared features, and output units. Then try a sequential time role and name the state one time step hands the next.

See it move

The only timings behind the designer are square matrix products and matrix-vector products. For the layer, stencil, and branch recipes it shows the operation and byte counts without a time. Open its roofline panel to plot your own measured work, bytes, seconds, and ceiling rates.

When you design a training calculation, name the repeated example, the shared parameters, and the per-output reduction. Estimate intermediate storage as well as arithmetic. Then keep the dependency graph intact while you choose a layout and an operation the library can run fast. That is enough structure to follow one complete model prediction with none of its numbers hidden.

What you now know

  • The repeated axis is a candidate for batching.
  • A spatial update can be parallel even when time steps depend on one another.
  • A roofline shows whether arithmetic or data movement limits a calculation.

Where we’re headed

The work is shaped. Next: the fixed model’s own numbers, from input to prediction. Continue to the next chapter.