Expand description
§Chapter 11.6 — SIMD kernels (pulp)
§Purpose
The kernels of Chapter 11.5 on vector registers, with the same results bit for bit (invariant K1). Nothing here defines a kernel: the definitions are Algorithms C and B of Chapter 11.5 and their scalar reference; this chapter says how four of those scalar computations are carried side by side, and why nothing changes when they are.
§Notation
As in Chapters 11.1, 11.2 and 11.5. W = 4. A quad is four f64
values v = (v_0, v_1, v_2, v_3), its lanes; an operation on quads
(+, −, ·, the fused a b + c, negation) is the f64 operation of
the same name on each lane, correctly rounded — what NEON and AVX2 + FMA
provide. A double-double quad is a pair of quads (h, ℓ). 2Sum,
Fast2Sum, 2Prod and the algorithms A2, M1, M2 of Chapter 11.2 on
quads are the same sequences of operations with every f64 operation
replaced by the quad one, and without step E. A slice is cut into
chunks of four consecutive elements (element 4c + k of the slice is
lane k of chunk c) and a tail of fewer than four.
A quad is one 256-bit register on x86 (AVX2) and two 128-bit registers
on aarch64 (NEON): W = 4 on every target, the narrower one emulating
it (Chapter 11.5).
§Algorithm V (vectorized accumulation: sum2, dot2, dot2_err)
V1. [Lanes.] p ← 0, s ← 0, e ← 0 (quads).
V2. [Chunks.] For each chunk x (and y): step C2 on quads — sum2:
(p, q) ← 2Sum(p, x), t ← q + 0; dot2: (g, r) ← 2Prod(x, y),
(p, q) ← 2Sum(p, g), t ← q + r — then s ← s + t and, for
dot2_err only, e ← e + |t|.
V3. [Tail and result.] Store the quads as the lanes p_k, s_k, e_k
of Algorithm C, run step C2 on the tail (element j of the tail in
lane j) and steps C3–C5, all in the scalar code of Chapter 11.5.
Lane k of the quads goes through exactly the operations that the
reference applies to the elements i ≡ k (mod 4), in the same order,
each correctly rounded: the lanes hold the same bits after V2, and V3
is the reference. (sum2 and dot2 do not compute e, which their
result does not use.)
§Algorithm W (vectorized double-double BLAS)
W1. [axpy, the column update c ← c ⊖ a ⊗ t.] For each chunk:
compute z ← y ⊕ (α ⊗ x) (resp. c ⊕ (−(a ⊗ t))) on quads; if
every lane of z_h and of z_ℓ is finite, store z; otherwise
compute the four elements of the chunk with the scalar operations
of Chapter 11.2 (from the operands, which were not yet
overwritten). The tail is scalar.
W2. [dot, dot_mixed, dot4.] a ← 0 (a double-double quad);
for each chunk a ← a ⊕ (x ⊗ y) on quads. If some lane of a_h or
a_ℓ is not finite, discard everything and run the reference kernel
on the whole input. Otherwise store a as the four accumulators of
step B1 (B4) and finish in scalar code: the tail, then ((a_0 ⊕ a_1) ⊕ a_2) ⊕ a_3 (B4: the fifth accumulator over the tail and ((a_0 ⊕ a_1) ⊕ (a_2 ⊕ a_3)) ⊕ t).
Why step E can be left out (the proof of K1 for Algorithm W). The
scalar operations end in step E, which is the identity when the
leading and the trailing component of the result are both finite, and
which is the only place where the scalar code branches. Two facts about
A2, M1 and M2 without step E, for arbitrary f64 operands:
(N1) Finite out, finite inside. If z_h and z_ℓ are finite, every
intermediate quantity was finite. (Every intermediate enters the
result through additions, subtractions and products only; none of
those maps a non-finite operand to a finite result.)
(N2) Non-finite is absorbing. If an operand has a non-finite
component, or an intermediate quantity is not finite, then z_h
is not finite. (In A2: a non-finite s_h makes s_ℓ a NaN, a
non-finite t_h or s_ℓ makes c, then v_h, then z_h
non-finite; an overflow of v_h gives v_ℓ = −∞ or NaN and z_h
a NaN. In M1 and M2: every term enters c_ℓ3, and z_h = c_h + c_ℓ3.)
Now compare the quad computation of one chunk with the scalar one,
operation by operation. As long as the scalar code meets no non-finite
value, each of its step E is the identity and the two computations are
the same sequence of correctly rounded operations: the same bits. At
the first non-finite value of the scalar computation the quad
computation holds the same non-finite value, and by (N2), applied to
the operation where it occurs and to every later one that consumes its
result, the quad result of that lane is not finite: W1 then recomputes
the chunk, and W2 the whole kernel, with the scalar code itself.
Conversely, if the quad result is finite then by (N1) no non-finite
value occurred. In W2 “later operations” are the accumulations a ← a ⊕ … of the following chunks: a lane of a that became non-finite stays
so until the test. Hence the stored result is always the reference’s —
NaN signs and payloads included in Algorithm W, since those results
come from the scalar code. In Algorithm V a NaN is produced by the
vector instruction, and only “NaN where the reference has a NaN” is
claimed (invariant K1 of Chapter 11.5).
The argument does not use normalization (D1). The tests nevertheless
use valid double-doubles only: on other pairs the reference itself is
outside its contract (its Fast2Sum asserts its precondition in debug
builds).
§The vector arithmetic: Lanes
The algorithms are written once, over the trait Lanes — a quad type
and its operations — with two implementations on pulp’s safe
interface: X4 (one four-lane register; pulp::x86::V3) and X2
(two two-lane registers; pulp::aarch64::Neon). The fused
multiply-add is pulp’s mul_add_f64s, which is vfmaq_f64 on NEON
and _mm256_fmadd_pd on x86 — a true FMA on both, never a
multiplication followed by an addition (mul_add_e_f64s is the one
that may be either, and is not used). A double-double slice is read
and written through the accessors of DoubleDouble, four elements at
a time: the crate has no unsafe, so there is no reinterpretation of
&[DoubleDouble] as &[f64]; the compiler turns the gathers into
shuffles.
§Invariants
(K1) of Chapter 11.5, tested there against the reference on random and
exceptional inputs of every length 0..=67 and some large ones.
(L1) A Lanes operation is the correctly rounded f64 operation on
each lane; mul_add is fused. (The contract of the two
implementations; checked lane by lane against f64, on the
backend of the machine, by the test of this module.)
(L2) X4 is built only on a four-lane backend and X2 only on a
two-lane one: checked at compile time by their constructors.
§What was run where
The NEON path is the one tested and measured (Apple M2). The AVX2 path
is the same generic code instantiated with X4; it has been
type-checked only as generic code and has not been compiled for, or
run on, an x86 target in this cycle — the tests of Chapter 11.5 run
it wherever backend() is "avx2".
§References
Chapter 11.5 (the definitions) and Chapter 11.2 (A2, M1, M2, step E).
Ogita, Rump & Oishi (2005), §8 (they note that Sum2 and Dot2 use only
+, −, · and so vectorize). pulp 0.22.3: Simd, WithSimd,
aarch64::Neon, x86::V3 (the API, read: src/aarch64.rs,
src/x86/v3.rs).
Structs§
- X2 🔒
- A quad in two two-lane registers of the backend
S(NEON): lanes 0–1 and lanes 2–3. - X4 🔒
- A quad in one four-lane register of the backend
S(AVX2).
Traits§
- Lanes 🔒
- Four
f64lanes and their arithmetic (invariant L1).
Functions§
- add_q 🔒
- Algorithm A2 of Chapter 11.2 on quads, without step E.
- axpy 🔒
- Step W1 for
axpy. - dot 🔒
- Step W2 for
dot. - dot2 🔒
- Algorithm V for
dot2(BOUND = false: the laneseare not computed) anddot2_err(BOUND = true). - dot4 🔒
- Step W2 for
dot4(step B4 of Chapter 11.5): the chunks on quads, the tail and the pairwise combination in scalar code, as the reference. - dot_
mixed 🔒 - Step W2 for
dot_mixed. - fast_
two_ 🔒sum_ q - Algorithm F of Chapter 11.1 on quads.
- load_dd 🔒
- The double-double quad of a chunk.
- mul_
f64_ 🔒q - Algorithm M1 of Chapter 11.2 on quads, without step E.
- mul_q 🔒
- Algorithm M2 of Chapter 11.2 on quads, without step E.
- splat_
dd 🔒 - The double-double quad
(x, x, x, x). - store_
dd 🔒 - The four double-doubles of a quad (finite, hence the pairs the scalar operations return: no invariant is re-checked).
- sum2 🔒
- Algorithm V for
sum2: the lanes after steps V1–V3 (C1–C2). - two_
prod_ 🔒q - Algorithm P of Chapter 11.1 on quads.
- two_
sum_ 🔒q - Algorithm S of Chapter 11.1 on quads.
Type Aliases§
- Dq 🔒
- A double-double quad
(h, ℓ).