Skip to main content

Module kernels

Module kernels 

Source
Expand description

§Chapter 11.5 — Slice kernels: definitions, scalar reference, dispatch

§Purpose

The inner loops of extended-precision linear algebra: compensated sums and dot products of f64 data that return a double-double (Ogita, Rump & Oishi 2005), one of them with a rigorous error bound, and the double-double dot, axpy and small-block gemm. This chapter fixes, operation by operation, what each kernel computes, and holds the scalar reference implementation of that definition (the private module reference). The SIMD versions (Chapter 11.6, feature simd) return the same bits (invariant K1), so the order of accumulation is part of each definition, not an implementation detail. The public functions of this module choose between the two at run time (Algorithm X below).

§Notation

u = 2⁻⁵³, η = 2⁻¹⁰⁷⁴, γ_k = k u / (1 − k u). 2Sum and 2Prod are the error-free transformations of Chapter 11.1, ⊕ ⊖ ⊗ the double-double operations of Chapter 11.2 (Algorithms A2, M2, M1). W = 4 is the number of accumulators — lanes — on every target: the width of AVX2; narrower targets emulate it, wider ones use it, so that there is one answer everywhere. Element i belongs to lane i mod W.

§Algorithms

Algorithm C (compensated accumulation: sum2, dot2, dot2_err). Input x ∈ Fⁿ (and y ∈ Fⁿ). Output a double-double r (and β).

C1. [Lanes.] p_k ← 0, s_k ← 0, e_k ← 0 for k = 0, …, W − 1. C2. [Accumulate.] For i = 0, …, n − 1, with k = i mod W: form the term — sum2: (p_k, q) ← 2Sum(p_k, x_i), t ← q; dot2 and dot2_err: (h, r) ← 2Prod(x_i, y_i), (p_k, q) ← 2Sum(p_k, h), t ← RN(q + r) — then s_k ← RN(s_k + t) and, for dot2_err, e_k ← RN(e_k + |t|). C3. [Combine.] p ← p_0, s ← s_0, e ← e_0. For k = 1, …, W − 1: (p, q) ← 2Sum(p, p_k); s ← RN(s + RN(s_k + q)); e ← RN(e + RN(e_k + |q|)). C4. [Result.] (r_h, r_ℓ) ← 2Sum(p, s), then step E of Chapter 11.2: r ← (r_h, r_ℓ), with r_ℓ replaced by 0 if it is not finite. C5. [Bound, dot2_err only.] If n = 0, β ← 0. If 2(n + 3)u ≥ 1, or p, s, e, r or the error term r_ℓ of the 2Sum of C4 before step E is not finite, β ← +∞. Otherwise, in f64 arithmetic, δ ← (n + 3)u / (1 − 2(n + 3)u) and β ← ((δ e + 3η/u) (1 + 8u)).

Algorithm B (double-double BLAS: dot, dot_mixed, axpy, gemm_sub).

B1. [dot, dot_mixed.] a_k ← 0; for i = 0, …, n − 1: a_k ← a_k ⊕ (x_i ⊗ y_i) with k = i mod W; return ((a_0 ⊕ a_1) ⊕ a_2) ⊕ a_3. In dot_mixed, y_i is an f64 and ⊗ is Algorithm M1. B2. [axpy.] y_i ← y_i ⊕ (α ⊗ x_i) for each i (no accumulation). B3. [gemm_sub.] For j = 0, …, n − 1, for l = 0, …, k − 1, for i = 0, …, m − 1: c_ij ← c_ij ⊖ (a_il ⊗ b_lj). Each c_ij receives its k updates in increasing l; the loop over i — the column update c ← c ⊖ a ⊗ t of one column of C by one column of A and one scalar t = b_lj — is the one a SIMD version vectorizes. The entries of C do not interact, so the loops over j, l and i may be blocked for the cache in any way that keeps l increasing for each (i, j): the kernels run in blocks of BLOCK_ROWS rows and BLOCK_K columns of A, the scheme of xingo_sparse::NaiveDense (Chapter 5.16).

B4. [dot4, the step D of Algorithm W of Chapter 5.16 of xingo-sparse; crate-private, for the solves of Chapter 11.7.] a_k ← 0; for the first 4⌊n/4⌋ elements a_k ← a_k ⊕ (x_i ⊗ y_i) with k = i mod W; t ← 0 and t ← t ⊕ (x_i ⊗ y_i) for the rest, in order; return ((a_0 ⊕ a_1) ⊕ (a_2 ⊕ a_3)) ⊕ t. It differs from B1 in the tail (one more accumulator instead of the lanes) and in the combination (pairwise), the order of the generic solve of xingo-sparse, whose bits it must return.

Algorithm X (dispatch). For a call of a kernel κ:

X1. [Feature.] Without the feature simd, run the reference κ. X2. [Detect.] On aarch64, if NEON is available (it always is), run the SIMD κ of Chapter 11.6 with two-lane vectors; on x86 and x86_64, if AVX2 and FMA are available, run it with four-lane vectors. The detection is pulp’s (cached after the first call). X3. [Fallback.] Otherwise run the reference κ.

backend reports the choice of X1–X3. AVX-512 is deliberately not a backend: W = 4 is the width of AVX2, and a wider accumulator would be a different kernel (another order of accumulation).

§Bounds

Sum2 and Dot2 are analysed by Ogita, Rump & Oishi for the sequential order; their argument uses the order only through “a floating-point sum of m terms, in any order, errs by at most γ_{m−1} Σ|terms|” (their (2.4)) and so carries over to Algorithm C, with n + 3 in place of n (the three 2Sum of step C3 add three error terms). Barring overflow:

  • sum2: |r − Σx_i| ≤ γ²_{n+3} Σ|x_i| (their Proposition 4.5 has γ²_{n−1} for the sequential order, plus u|Σx_i| for rounding the result to one f64, which C4 does not do);
  • dot2: |r − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2 (their Proposition 5.5: γ²_n, and 5nη for the Dekker product in place of the FMA).

Proof of step C5. Barring overflow, and with every 2Prod exact, xᵀy = p + Σ_i (q_i + r_i) + Σ_c q_c exactly, where the q_c are the three errors of step C3. s is a floating-point sum, in some order, of the N = n + 3 terms t_i = RN(q_i + r_i) and q_c, so with E = Σ|t_i| + Σ|q_c|: |xᵀy − p − s| ≤ u Σ|t_i| + γ_{N−1} E ≤ γ_{n+3} E. And e is a floating-point sum of the same N nonnegative magnitudes, so E ≤ (1 + u)^{n+2} e. Hence |xᵀy − p − s| ≤ (n + 3)u / (1 − (2n + 5)u) · e. A 2Prod out of its exact range adds at most η/2 (invariant T2 of Chapter 11.1): n η/2 in all. Step C5 evaluates an upper bound of that in round-to-nearest: δ is computed from exact operands by one division (δ ≥ (1 − u) times the exact coefficient above, whose denominator is the larger 1 − (2n + 5)u), the product δ e errs by at most a factor (1 − u) and η/2, the two remaining operations by (1 − u) each (the term 3η/u = 3 · 2⁻¹⁰²¹ keeps them out of the subnormal range), and `(1

  • 8u)(1 − u)⁴ ≥ 1, 3η/u − η/2 ≥ n η/2 + η/2`.

Overflow. The argument needs every operation exact or rounded as stated, and that is lost only by an overflow — of a sum, of a product, or of an intermediate step of a 2Sum whose first operand is ±Ω (invariant T1 of Chapter 11.1: then the error term is ±∞ or NaN, and conversely a 2Sum whose error term is finite had no step overflow and is exact). In steps C2 and C3 every such value flows into p, s or e through additions and absolute values, none of which maps a non-finite value back to a finite one, and C5 tests the three. The one exception is step C4: its error term r_ℓ goes only into r, and step E replaces it by 0 — a non-finite value made finite — so r can be finite and wrong by up to ulp(Ω)/2 = 2⁹⁷⁰ (p = Ω − 2⁹⁷¹, s = −2⁹⁷⁰ − …, found by review X0.3i). C5 therefore tests r_ℓ itself, before step E; with it finite the 2Sum is exact and r = p + s. (Until X0.3i C5 tested only r, and (K2) was false in that corner.) This is Algorithm 5.8 and Corollary 5.9 of Ogita, Rump & Oishi adapted to the lanes, to the FMA product and to a double-double result (their bound has one more term, u|res|, for the final rounding to f64).

The kernels of Algorithm B inherit the bounds of ⊕ and ⊗: each term errs by at most 4u² relative, each accumulation by 3u² + 13u³.

§Invariants

(K1) One answer. Every kernel is the fixed sequence of f64 operations above for a given n; the SIMD implementation returns the same bits for every input — finite or not, normalized or not — with one reservation: where a result is a NaN, both are NaN, and the sign and payload of that NaN are not specified (Rust does not specify them for f64 arithmetic either). Chapter 11.6 has the argument; the tests of this module compare the two implementations bit for bit on random and on exceptional data. backend names the implementation in use. (K2) Rigour. dot2_err returns (r, β) with |xᵀy − r| ≤ β for every input; β = +∞ when a hypothesis fails (invariant C3 of Chapter 11), the overflow of an intermediate step of the 2Sum of C4 included (the proof of C5, “Overflow”). Checked against exact rationals, near Ω too.

§References

Ogita, Rump & Oishi, “Accurate sum and dot product”, SIAM J. Sci. Comput. 26 (2005): Algorithm 4.4 (Sum2) and Proposition 4.5, Algorithm 5.3 (Dot2) and Proposition 5.5, Algorithm 5.8 (Dot2Err) and Corollary 5.9. Higham, Accuracy and Stability of Numerical Algorithms (2002), §4.2 (the order-independent bound). Chapter 5.16 of xingo-sparse (the blocked loop order of gemm_sub).

Modules§

reference 🔒
The scalar reference kernels: Algorithms C and B of the chapter, one f64 operation at a time. They are the definition of the kernels, the oracle of the SIMD versions (invariant K1) and the fallback of the dispatch (Algorithm X).

Macros§

dispatch 🔒
Algorithm X, steps X1–X2: if a SIMD backend is compiled in and available, returns from the enclosing function with the value of $simd, an expression in which $lanes is the backend’s four-lane arithmetic (crate::simd::Lanes), evaluated inside pulp’s vectorize (which enables the target features for the code inlined into it). Otherwise falls through to step X3, written after the macro call.

Structs§

Compensated 🔒
The state of Algorithm C: the lanes p_k, s_k, e_k.

Constants§

BLOCK_K 🔒
Columns of A (the summation index l) per block; see BLOCK_ROWS.
BLOCK_ROWS 🔒
Rows of C and A handled per block of step B3 (a cache-blocking size, not a numerical threshold; not tuned): BLOCK_ROWS × BLOCK_K double-doubles of A — 128 KiB — stay in cache while the columns of C pass over them.
LANES 🔒
W, the number of lanes (the chapter).
U 🔒
2⁻⁵³.

Traits§

ColumnUpdate 🔒
The column update of step B3, c_i ← c_i ⊖ (a_i ⊗ t) for every i: the one loop that the kernels of Algorithm B built on gemm vectorize (and the dense kernels of Chapter 11.7 with them). Implemented by the scalar reference::Reference and by the vectors of Chapter 11.6.

Functions§

axpy
y ← y + α x, element by element (step B2 of Chapter 11.5). Panics if the lengths differ.
backend
The name of the implementation the dispatch selected ("scalar", "avx2", "neon"), for benchmarks and bug reports: Algorithm X of Chapter 11.5. "scalar" without the feature simd, or when the CPU has neither NEON nor AVX2 with FMA. ("avx512", which the contract listed, is never returned: the chapter says why.)
dot
xᵀy of double-double vectors, over W = 4 lanes combined left to right (step B1 of Chapter 11.5). Panics if the lengths differ.
dot2
xᵀy of f64 vectors as a double-double (Dot2, over W = 4 lanes: Algorithm C of Chapter 11.5): |result − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2 barring overflow. Overflow includes an intermediate step of a 2Sum whose first operand is ±Ω (invariant T1 of Chapter 11.1): there the result may be finite with a relative error of order u; dot2_err reports that case with β = +∞. Panics if the lengths differ.
dot2_err
As dot2, with a rigorous bound: returns (r, β) with |xᵀy − r| ≤ β (Dot2Err; step C5 of Chapter 11.5 and its proof). β = +∞ when a hypothesis fails (overflow — of an intermediate step of a 2Sum at ±Ω too —, NaN, 2(n + 3)u ≥ 1): invariant C3. Panics if the lengths differ.
dot_mixed
xᵀy with x double-double and y f64 (a row of an f64 matrix against an extended vector: the residual of a polished solution); the order of dot. Panics if the lengths differ.
gemm_blocked 🔒
Step B3 with the blocks of the chapter: c_ij ← c_ij ⊖ Σ_l a_il ⊗ t(j, l) for the m × k block a and the m × n block c (column-major), l increasing for each entry.
gemm_sub
C ← C − A B for small column-major blocks (A is m × k, B is k × n, C is m × n); the update of a supernodal block. Each entry of C receives its k updates in increasing column of A (step B3 of Chapter 11.5). Panics if a slice has the wrong length.
sum2
Σ xᵢ of f64 values as a double-double, as accurate as if summed in twice the working precision (Sum2 of Ogita, Rump & Oishi, over W = 4 lanes: Algorithm C of Chapter 11.5): |result − Σxᵢ| ≤ γ²_{n+3} Σ|xᵢ| barring overflow. Overflow includes an intermediate step of a 2Sum whose first operand is ±Ω (invariant T1 of Chapter 11.1): there the result may be finite with a relative error of order u.