Skip to main content

Module simd

Module simd 

Source
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 f64 lanes 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 lanes e are not computed) and dot2_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, ℓ).