Examples

Each example carries one problem the whole way along the derivation used throughout this reference. Nothing is elided: the structure is stated, the concept is written, the algorithm is written against the concept, the cost is computed, the hardware mapping is made, and the measurement protocol is given.

1. AbstractionThe mathematical object and its structure.
2. SpecificationOperations, laws, admissible domain.
3. Type / conceptThe C++ encoding of the specification.
4. ImplementationGeneric algorithm against the concept.
5. ComplexityOperations and traffic under a stated model.
6. Hardware mappingLayout, locality, vector width, decomposition.
7. MeasurementWhat is to be measured and how.

Examples

Example	Problem	Principal lesson
Inner Product	$\langle x, y\rangle$ over a field	A bandwidth-bound kernel; associativity and accumulator count
Matrix Multiplication	$C \mathrel{+}= AB$	Raising arithmetic intensity by blocking
Conjugate Gradient	$Ax = b$, $A$ symmetric positive definite	An algorithm written against an operator, not a matrix

Reading them

The examples are written to be read in order, since each uses the previous: the inner product is a kernel of conjugate gradient, and the blocking analysis of matrix multiplication is the model for every dense kernel.

The code in each is complete and compiles as shown against C++20 unless the entry says otherwise. Where a later revision offers a better formulation, both are given.