Skip to main content

Module dense

Module dense 

Source
Expand description

§Chapter 11.7 — DdDense: the dense kernel of xingo-sparse in double-double

§Purpose

xingo_sparse::SupernodalLdl<T, K> spends its time in the dense operations of a DenseKernel<T> (Chapter 5.16 of xingo-sparse). For T = DoubleDouble the only kernel so far was the generic NaiveDense, one scalar double-double operation at a time. DdDense is the same kernel with its inner loop — the column update of Chapter 11.5, step B3 — on vector registers (Chapter 11.6). It returns the bits of NaiveDense, so a factorization does not change when the kernel is swapped; only its speed does.

§Notation

As in Chapter 5.16: a DenseBlock A is rows × cols, column-major; square blocks are read and written in their lower triangle. c ← c ⊖ a ⊗ t is the column update of Chapter 11.5 (c, a columns of equal length, t a double-double), ⊘ the division D2 of Chapter 11.2.

§Algorithm K (the five operations)

K1. [gemm_sub: C ← C − A Bᵀ.] Step B3 of Chapter 11.5 with t(j, l) = b_jl, in its blocks: for each entry, l increasing. K2. [syrk_sub: C ← C − A Aᵀ, lower triangle.] For l in blocks of BLOCK_K, for each column j of C: the column update of the rows i ≥ j with a = A[j.., l] and t = a_jl. K3. [trsm_lower, B ← B L⁻ᵀ.] For j = 0, …, n − 1: for l < j, the column update of column j of B with a = column l of B (already solved) and t = l_jl; then b_ij ← b_ij ⊘ l_jj. K4. [trsm_lower, B ← L⁻¹ B.] For each column c of B, for l = 0, …, n − 1: x ← b_lc ⊘ l_ll, b_lc ← x, then the column update of the rows below l with a = L[l + 1.., l] and t = x. K5. [potrf, left-looking (Algorithm P of Chapter 5.16 since xingo-sparse 0.4.0).] For j = 0, …, n − 1: for k < j, the column update of the rows i ≥ j of column j with a = L[j.., k] and t = l_jk; then the pivot test and l_jj ← √a_jj of NaiveDense, and l_ij ← a_ij ⊘ l_jj for i > j. K6. [sytrf.] That of NaiveDense, unchanged: its eliminations update a full working copy row and column at once, and the block factorization is not where the supernodal factorization spends its time.

K7. [solve_unit_lower, Algorithm V of Chapter 5.16.] For j = 0, …, n_c − 1: the column update of y[o..] with a = L[o.., j] and t = y_j. K8. [solve_unit_lower_t, Algorithm W.] For j = n_c − 1, …, 0: y_j ← y_j ⊖ (D(L[o..n_c, j], y[o..n_c]) ⊕ D(L[n_c.., j], y[n_c..])), with D the kernel dot4 of Chapter 11.5 (step B4) on SIMD registers (step W2 of Chapter 11.6). K9. [solve_min_rows.] SOLVE_MIN_ROWS: the supernodes of SupernodalLdl with at least that many rows are solved through K7–K8 (step S0′ of Chapter 5.17), the others by the generic loops. A cost switch (invariant (D5) of Chapter 5.16): the bits are the same either way.

Task L1.8. Until xingo-sparse 0.3.x the generic potrf summed each entry along a row of L (Σ_k l_ik l_jk, left to right, subtracted once), which lanes would reorder, so it was NaiveDense’s here too; 0.4.0 subtracts term by term down a column, the statement of K1–K4, and K5 vectorizes it with the same bits.

K1–K5, K7 are the loops of NaiveDense (Chapter 5.16, “Loop order”), which compute each entry as x ← x − a · t with the same operands in the same order; the column update is that statement for a whole column, and it is bit for bit the scalar one (invariant K1 of Chapter 11.5). The product is a ⊗ t with the entry of the column first: the double-double product M2 is not commutative in its last bits, so the order of the operands is part of the definition.

§What the contract said

The approved contract describes DdDense as “potrf, sytrf and the triangular solves are those of NaiveDense; gemm_sub and syrk_sub go through kernels::gemm_sub”. Two differences, neither visible in a result: the triangular solves also use the vectorized column update (their results are still NaiveDense’s, bit for bit), because the supernodal factorization calls trsm_lower once per panel; and gemm_sub/syrk_sub go through the column update of kernels::gemm_sub rather than through that function, whose B is k × n where the trait’s is n × k (transposed).

§Invariants

(X1) Same bits. Every operation of DdDense leaves in its output block the bits NaiveDense would (NaN payloads aside, invariant K1 of Chapter 11.5). Tested entry by entry on random blocks, and on whole factorizations in tests/sparse_dd.rs. (X2) (D3) of Chapter 5.16: the strict upper triangle of a square block is untouched. (X3) Same bits in the solve (task L1.8): K7–K8 return the bits of the provided solve_unit_lower, solve_unit_lower_t of DenseKernel — (D4) of Chapter 5.16 — so SupernodalLdl solves to the same bits with DdDense as with NaiveDense, whatever SOLVE_MIN_ROWS is. Tested on blocks and on whole solves in tests/sparse_dd.rs.

§References

Chapter 5.16 of xingo-sparse (DenseKernel, NaiveDense: the loop order and the cache blocks); Chapters 11.5 and 11.6.

Structs§

DdDense
The dense kernel of xingo-sparse for double-double blocks, with the results of NaiveDense bit for bit (Chapter 11.7): gemm_sub, syrk_sub and the triangular solves run the column update of crate::kernels::gemm_sub on SIMD registers (feature simd), and so does potrf (left-looking since xingo-sparse 0.4.0); sytrf is that of NaiveDense. With it SupernodalLdl<DoubleDouble, DdDense> spends its time in SIMD.

Constants§

SOLVE_MIN_ROWS 🔒
Step K9: the smallest supernode block, in rows, that the solves of SupernodalLdl<DoubleDouble, DdDense> send through K7–K8 (a cost switch). Measured in task L1.8 with dd_bench ldl (NEON, Apple M2): 1, 8 and 32 within the noise of each other on the four systems (2-D grid simplicial and forced supernodal, 3-D grid, dense 200), all 1.3–1.8× faster than the generic loops; 8 keeps the gather out of the smallest blocks.

Functions§

check_solve 🔒
The argument checks of K7–K8 (those of the provided methods).
is_consistent 🔒
rows · cols entries.
potrf_columns 🔒
Step K5 (the error of a non-positive pivot is NaiveDense’s).
solve_backward 🔒
Step K8, with the kernel dot of step B4.
solve_forward 🔒
Step K7.
solve_offset 🔒
o = j + 1 + [skip_j] of Algorithms V and W of Chapter 5.16.
square 🔒
The order of a consistent square block.
syrk 🔒
Step K2.
trsm_plain 🔒
Step K4.
trsm_transposed 🔒
Step K3.