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, plusu|Σx_i|for rounding the result to onef64, which C4 does not do);dot2:|r − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2(their Proposition 5.5:γ²_n, and5nη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
f64operation 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$lanesis the backend’s four-lane arithmetic (crate::simd::Lanes), evaluated insidepulp’svectorize(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 indexl) per block; seeBLOCK_ROWS. - BLOCK_
ROWS 🔒 - Rows of
CandAhandled per block of step B3 (a cache-blocking size, not a numerical threshold; not tuned):BLOCK_ROWS × BLOCK_Kdouble-doubles ofA— 128 KiB — stay in cache while the columns ofCpass over them. - LANES 🔒
W, the number of lanes (the chapter).- U 🔒
2⁻⁵³.
Traits§
- Column
Update 🔒 - The column update of step B3,
c_i ← c_i ⊖ (a_i ⊗ t)for everyi: the one loop that the kernels of Algorithm B built ongemmvectorize (and the dense kernels of Chapter 11.7 with them). Implemented by the scalarreference::Referenceand 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 featuresimd, 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ᵀyof double-double vectors, overW = 4lanes combined left to right (step B1 of Chapter 11.5). Panics if the lengths differ.- dot2
xᵀyoff64vectors as a double-double (Dot2, overW = 4lanes: Algorithm C of Chapter 11.5):|result − xᵀy| ≤ γ²_{n+5} |x|ᵀ|y| + n η/2barring 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 orderu;dot2_errreports 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ᵀywithxdouble-double andyf64(a row of anf64matrix against an extended vector: the residual of a polished solution); the order ofdot. 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 them × kblockaand them × nblockc(column-major),lincreasing for each entry. - gemm_
sub C ← C − A Bfor small column-major blocks (Aism × k,Bisk × n,Cism × n); the update of a supernodal block. Each entry ofCreceives itskupdates in increasing column ofA(step B3 of Chapter 11.5). Panics if a slice has the wrong length.- sum2
Σ xᵢoff64values as a double-double, as accurate as if summed in twice the working precision (Sum2 of Ogita, Rump & Oishi, overW = 4lanes: 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 orderu.