aboutsummaryrefslogtreecommitdiff
path: root/kernels.c
diff options
context:
space:
mode:
authorOnur Gündüz <ogunduz@gmail.com>2026-10-08 06:49:33 +0200
committerOnur Gündüz <ogunduz@gmail.com>2026-10-08 07:21:37 +0200
commita5af9c3d351085f4005a949f8c382a3aad4e0b29 (patch)
tree0ad133d931553e68a68588e983976a66b3309083 /kernels.c
downloadsvad-0.1.0.tar.gz
svad-0.1.0.zip
initv0.1.0
Diffstat (limited to '')
-rw-r--r--kernels.c429
1 files changed, 429 insertions, 0 deletions
diff --git a/kernels.c b/kernels.c
new file mode 100644
index 0000000..2a6b8a2
--- /dev/null
+++ b/kernels.c
@@ -0,0 +1,429 @@
+/* Scalar and SIMD implementations of the matvec primitive.
+ *
+ * Every variant blocks four output rows together and, when there is more than
+ * one output time step, all the steps as well. Blocking rows amortises the
+ * activation loads, which stay in registers across the four rows; blocking
+ * steps amortises the weight loads, which are what the model is actually
+ * limited by. A 4x4 block issues eight vector loads for sixteen fused
+ * multiply-adds, against ten loads for eight in the single-step shape.
+ *
+ * The step count is folded in at the call site, so each specialisation has a
+ * fixed accumulator count and keeps them all in registers.
+ *
+ * Accumulation order differs between the variants, so their results differ in
+ * the last bits. tests/test_kernels.c and tests/test_parity.c bound that. */
+
+#include "kernels.h"
+
+#include <stddef.h>
+
+#if defined(__GNUC__) || defined(__clang__)
+# define SVAD_INLINE static inline __attribute__((always_inline))
+#else
+# define SVAD_INLINE static inline
+#endif
+
+/* ---- portable C ------------------------------------------------------ */
+
+SVAD_INLINE void mv_scalar_k(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ const int steps) {
+ int i = 0;
+ for (; i + 4 <= m; i += 4) {
+ const float *w0 = W + (size_t)i * n;
+ const float *w1 = w0 + n, *w2 = w1 + n, *w3 = w2 + n;
+ float acc[4][SVAD_MAX_STEPS] = {{0.0f}};
+ for (int j = 0; j < n; ++j) {
+ const float a = w0[j], b = w1[j], c = w2[j], d = w3[j];
+ for (int s = 0; s < steps; ++s) {
+ const float xv = x[(size_t)s * xs + j];
+ acc[0][s] += a * xv;
+ acc[1][s] += b * xv;
+ acc[2][s] += c * xv;
+ acc[3][s] += d * xv;
+ }
+ }
+ for (int s = 0; s < steps; ++s)
+ for (int r = 0; r < 4; ++r)
+ y[(size_t)s * ys + i + r] = bias ? bias[i + r] + acc[r][s] : acc[r][s];
+ }
+ for (; i < m; ++i) {
+ const float *w = W + (size_t)i * n;
+ float acc[SVAD_MAX_STEPS] = {0.0f};
+ for (int j = 0; j < n; ++j)
+ for (int s = 0; s < steps; ++s)
+ acc[s] += w[j] * x[(size_t)s * xs + j];
+ for (int s = 0; s < steps; ++s)
+ y[(size_t)s * ys + i] = bias ? bias[i] + acc[s] : acc[s];
+ }
+}
+
+static void matvec_scalar(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ int steps) {
+ switch (steps) {
+ case 1:
+ mv_scalar_k(y, ys, W, x, xs, bias, m, n, 1);
+ return;
+ case 2:
+ mv_scalar_k(y, ys, W, x, xs, bias, m, n, 2);
+ return;
+ case 4:
+ mv_scalar_k(y, ys, W, x, xs, bias, m, n, 4);
+ return;
+ default:
+ for (int s = 0; s < steps; ++s)
+ mv_scalar_k(y + (size_t)s * ys, 0, W, x + (size_t)s * xs, 0, bias, m, n, 1);
+ return;
+ }
+}
+
+static float dot_scalar(const float *a, const float *b, int n) {
+ float s0 = 0.0f, s1 = 0.0f, s2 = 0.0f, s3 = 0.0f;
+ int j = 0;
+ for (; j + 4 <= n; j += 4) {
+ s0 += a[j + 0] * b[j + 0];
+ s1 += a[j + 1] * b[j + 1];
+ s2 += a[j + 2] * b[j + 2];
+ s3 += a[j + 3] * b[j + 3];
+ }
+ for (; j < n; ++j)
+ s0 += a[j] * b[j];
+ return (s0 + s1) + (s2 + s3);
+}
+
+static const svad_kernels kernels_scalar = {"scalar", matvec_scalar, dot_scalar};
+
+const svad_kernels *svad_kernels_scalar(void) { return &kernels_scalar; }
+
+/* ---- AArch64 NEON ---------------------------------------------------- */
+
+#if defined(__aarch64__) && defined(__ARM_NEON)
+# define SVAD_HAVE_SIMD 1
+# include <arm_neon.h>
+
+/* One output step: two accumulators per row cover the multiply-add latency
+ * without needing a second weight stream. */
+SVAD_INLINE void mv1_neon(float *y, const float *W, const float *x, const float *bias, int m, int n) {
+ int i = 0;
+ for (; i + 4 <= m; i += 4) {
+ const float *w0 = W + (size_t)i * n;
+ const float *w1 = w0 + n, *w2 = w1 + n, *w3 = w2 + n;
+ float32x4_t a0 = vdupq_n_f32(0.0f), a1 = a0, a2 = a0, a3 = a0;
+ float32x4_t c0 = a0, c1 = a0, c2 = a0, c3 = a0;
+ int j = 0;
+ for (; j + 8 <= n; j += 8) {
+ const float32x4_t x0 = vld1q_f32(x + j);
+ const float32x4_t x1 = vld1q_f32(x + j + 4);
+ a0 = vfmaq_f32(a0, vld1q_f32(w0 + j), x0);
+ c0 = vfmaq_f32(c0, vld1q_f32(w0 + j + 4), x1);
+ a1 = vfmaq_f32(a1, vld1q_f32(w1 + j), x0);
+ c1 = vfmaq_f32(c1, vld1q_f32(w1 + j + 4), x1);
+ a2 = vfmaq_f32(a2, vld1q_f32(w2 + j), x0);
+ c2 = vfmaq_f32(c2, vld1q_f32(w2 + j + 4), x1);
+ a3 = vfmaq_f32(a3, vld1q_f32(w3 + j), x0);
+ c3 = vfmaq_f32(c3, vld1q_f32(w3 + j + 4), x1);
+ }
+ for (; j + 4 <= n; j += 4) {
+ const float32x4_t x0 = vld1q_f32(x + j);
+ a0 = vfmaq_f32(a0, vld1q_f32(w0 + j), x0);
+ a1 = vfmaq_f32(a1, vld1q_f32(w1 + j), x0);
+ a2 = vfmaq_f32(a2, vld1q_f32(w2 + j), x0);
+ a3 = vfmaq_f32(a3, vld1q_f32(w3 + j), x0);
+ }
+ const float s0 = vaddvq_f32(vaddq_f32(a0, c0));
+ const float s1 = vaddvq_f32(vaddq_f32(a1, c1));
+ const float s2 = vaddvq_f32(vaddq_f32(a2, c2));
+ const float s3 = vaddvq_f32(vaddq_f32(a3, c3));
+ y[i + 0] = bias ? bias[i + 0] + s0 : s0;
+ y[i + 1] = bias ? bias[i + 1] + s1 : s1;
+ y[i + 2] = bias ? bias[i + 2] + s2 : s2;
+ y[i + 3] = bias ? bias[i + 3] + s3 : s3;
+ }
+ for (; i < m; ++i) {
+ const float *w = W + (size_t)i * n;
+ float32x4_t a = vdupq_n_f32(0.0f), c = a;
+ int j = 0;
+ for (; j + 8 <= n; j += 8) {
+ a = vfmaq_f32(a, vld1q_f32(w + j), vld1q_f32(x + j));
+ c = vfmaq_f32(c, vld1q_f32(w + j + 4), vld1q_f32(x + j + 4));
+ }
+ for (; j + 4 <= n; j += 4)
+ a = vfmaq_f32(a, vld1q_f32(w + j), vld1q_f32(x + j));
+ const float s = vaddvq_f32(vaddq_f32(a, c));
+ y[i] = bias ? bias[i] + s : s;
+ }
+}
+
+/* Several output steps: a 4-row by steps-column register block, so each weight
+ * vector is loaded once and used `steps` times. */
+SVAD_INLINE void mv_ms_neon(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ const int steps) {
+ int i = 0;
+ for (; i + 4 <= m; i += 4) {
+ const float *w0 = W + (size_t)i * n;
+ const float *w1 = w0 + n, *w2 = w1 + n, *w3 = w2 + n;
+ float32x4_t acc[4][SVAD_MAX_STEPS];
+ for (int r = 0; r < 4; ++r)
+ for (int s = 0; s < steps; ++s)
+ acc[r][s] = vdupq_n_f32(0.0f);
+
+ int j = 0;
+ for (; j + 4 <= n; j += 4) {
+ const float32x4_t wv0 = vld1q_f32(w0 + j);
+ const float32x4_t wv1 = vld1q_f32(w1 + j);
+ const float32x4_t wv2 = vld1q_f32(w2 + j);
+ const float32x4_t wv3 = vld1q_f32(w3 + j);
+ for (int s = 0; s < steps; ++s) {
+ const float32x4_t xv = vld1q_f32(x + (size_t)s * xs + j);
+ acc[0][s] = vfmaq_f32(acc[0][s], wv0, xv);
+ acc[1][s] = vfmaq_f32(acc[1][s], wv1, xv);
+ acc[2][s] = vfmaq_f32(acc[2][s], wv2, xv);
+ acc[3][s] = vfmaq_f32(acc[3][s], wv3, xv);
+ }
+ }
+ for (int s = 0; s < steps; ++s)
+ for (int r = 0; r < 4; ++r) {
+ const float v = vaddvq_f32(acc[r][s]);
+ y[(size_t)s * ys + i + r] = bias ? bias[i + r] + v : v;
+ }
+ }
+ for (; i < m; ++i) {
+ const float *w = W + (size_t)i * n;
+ float32x4_t acc[SVAD_MAX_STEPS];
+ for (int s = 0; s < steps; ++s)
+ acc[s] = vdupq_n_f32(0.0f);
+ int j = 0;
+ for (; j + 4 <= n; j += 4) {
+ const float32x4_t wv = vld1q_f32(w + j);
+ for (int s = 0; s < steps; ++s)
+ acc[s] = vfmaq_f32(acc[s], wv, vld1q_f32(x + (size_t)s * xs + j));
+ }
+ for (int s = 0; s < steps; ++s) {
+ const float v = vaddvq_f32(acc[s]);
+ y[(size_t)s * ys + i] = bias ? bias[i] + v : v;
+ }
+ }
+}
+
+static void matvec_neon(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ int steps) {
+ switch (steps) {
+ case 1:
+ mv1_neon(y, W, x, bias, m, n);
+ return;
+ case 2:
+ mv_ms_neon(y, ys, W, x, xs, bias, m, n, 2);
+ return;
+ case 4:
+ mv_ms_neon(y, ys, W, x, xs, bias, m, n, 4);
+ return;
+ default:
+ for (int s = 0; s < steps; ++s)
+ mv1_neon(y + (size_t)s * ys, W, x + (size_t)s * xs, bias, m, n);
+ return;
+ }
+}
+
+static float dot_neon(const float *a, const float *b, int n) {
+ float32x4_t s0 = vdupq_n_f32(0.0f), s1 = s0;
+ int j = 0;
+ for (; j + 8 <= n; j += 8) {
+ s0 = vfmaq_f32(s0, vld1q_f32(a + j), vld1q_f32(b + j));
+ s1 = vfmaq_f32(s1, vld1q_f32(a + j + 4), vld1q_f32(b + j + 4));
+ }
+ for (; j + 4 <= n; j += 4)
+ s0 = vfmaq_f32(s0, vld1q_f32(a + j), vld1q_f32(b + j));
+ float s = vaddvq_f32(vaddq_f32(s0, s1));
+ for (; j < n; ++j)
+ s += a[j] * b[j];
+ return s;
+}
+
+static const svad_kernels kernels_simd = {"neon", matvec_neon, dot_neon};
+#endif /* aarch64 NEON */
+
+/* ---- x86-64 AVX2 -----------------------------------------------------
+ *
+ * These are compiled for every x86 build, whatever the baseline the rest of
+ * the file is built for, by carrying the instruction set on the functions
+ * themselves rather than on the command line. Selection then happens at
+ * startup against the running processor, which is what lets one binary be both
+ * safe on a host without AVX2 and fast on one with it; on the measured e2-medium
+ * that is the difference between 131 and 42 microseconds per chunk.
+ *
+ * Every function reachable from an AVX2 entry point needs the same attribute,
+ * including the always-inlined ones, or the compiler refuses to inline across
+ * the mismatch. */
+
+#if (defined(__x86_64__) || defined(__i386__)) && (defined(__GNUC__) || defined(__clang__))
+# define SVAD_HAVE_SIMD 1
+# define SVAD_X86_DISPATCH 1
+# include <immintrin.h>
+
+# define SVAD_AVX2 __attribute__((target("avx2,fma")))
+# define SVAD_AVX2_INLINE static inline __attribute__((always_inline, target("avx2,fma")))
+
+SVAD_AVX2_INLINE float hsum256(__m256 v) {
+ __m128 lo = _mm256_castps256_ps128(v);
+ __m128 hi = _mm256_extractf128_ps(v, 1);
+ lo = _mm_add_ps(lo, hi);
+ lo = _mm_add_ps(lo, _mm_movehl_ps(lo, lo));
+ lo = _mm_add_ss(lo, _mm_shuffle_ps(lo, lo, 0x55));
+ return _mm_cvtss_f32(lo);
+}
+
+SVAD_AVX2_INLINE void mv_avx2_k(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ const int steps) {
+ int i = 0;
+ for (; i + 4 <= m; i += 4) {
+ const float *w0 = W + (size_t)i * n;
+ const float *w1 = w0 + n, *w2 = w1 + n, *w3 = w2 + n;
+ __m256 acc[4][SVAD_MAX_STEPS];
+ for (int r = 0; r < 4; ++r)
+ for (int s = 0; s < steps; ++s)
+ acc[r][s] = _mm256_setzero_ps();
+
+ int j = 0;
+ for (; j + 8 <= n; j += 8) {
+ const __m256 wv0 = _mm256_loadu_ps(w0 + j);
+ const __m256 wv1 = _mm256_loadu_ps(w1 + j);
+ const __m256 wv2 = _mm256_loadu_ps(w2 + j);
+ const __m256 wv3 = _mm256_loadu_ps(w3 + j);
+ for (int s = 0; s < steps; ++s) {
+ const __m256 xv = _mm256_loadu_ps(x + (size_t)s * xs + j);
+ acc[0][s] = _mm256_fmadd_ps(wv0, xv, acc[0][s]);
+ acc[1][s] = _mm256_fmadd_ps(wv1, xv, acc[1][s]);
+ acc[2][s] = _mm256_fmadd_ps(wv2, xv, acc[2][s]);
+ acc[3][s] = _mm256_fmadd_ps(wv3, xv, acc[3][s]);
+ }
+ }
+ for (int s = 0; s < steps; ++s)
+ for (int r = 0; r < 4; ++r) {
+ float v = hsum256(acc[r][s]);
+ const float *w = W + (size_t)(i + r) * n;
+ for (int t = j; t < n; ++t)
+ v += w[t] * x[(size_t)s * xs + t];
+ y[(size_t)s * ys + i + r] = bias ? bias[i + r] + v : v;
+ }
+ }
+ for (; i < m; ++i) {
+ const float *w = W + (size_t)i * n;
+ __m256 acc[SVAD_MAX_STEPS];
+ for (int s = 0; s < steps; ++s)
+ acc[s] = _mm256_setzero_ps();
+ int j = 0;
+ for (; j + 8 <= n; j += 8) {
+ const __m256 wv = _mm256_loadu_ps(w + j);
+ for (int s = 0; s < steps; ++s)
+ acc[s] = _mm256_fmadd_ps(wv, _mm256_loadu_ps(x + (size_t)s * xs + j), acc[s]);
+ }
+ for (int s = 0; s < steps; ++s) {
+ float v = hsum256(acc[s]);
+ for (int t = j; t < n; ++t)
+ v += w[t] * x[(size_t)s * xs + t];
+ y[(size_t)s * ys + i] = bias ? bias[i] + v : v;
+ }
+ }
+}
+
+SVAD_AVX2 static void matvec_avx2(float *y,
+ int ys,
+ const float *W,
+ const float *x,
+ int xs,
+ const float *bias,
+ int m,
+ int n,
+ int steps) {
+ switch (steps) {
+ case 1:
+ mv_avx2_k(y, ys, W, x, xs, bias, m, n, 1);
+ return;
+ case 2:
+ mv_avx2_k(y, ys, W, x, xs, bias, m, n, 2);
+ return;
+ case 4:
+ mv_avx2_k(y, ys, W, x, xs, bias, m, n, 4);
+ return;
+ default:
+ for (int s = 0; s < steps; ++s)
+ mv_avx2_k(y + (size_t)s * ys, 0, W, x + (size_t)s * xs, 0, bias, m, n, 1);
+ return;
+ }
+}
+
+SVAD_AVX2 static float dot_avx2(const float *a, const float *b, int n) {
+ __m256 s = _mm256_setzero_ps();
+ int j = 0;
+ for (; j + 8 <= n; j += 8)
+ s = _mm256_fmadd_ps(_mm256_loadu_ps(a + j), _mm256_loadu_ps(b + j), s);
+ float r = hsum256(s);
+ for (; j < n; ++j)
+ r += a[j] * b[j];
+ return r;
+}
+
+static const svad_kernels kernels_avx2 = {"avx2", matvec_avx2, dot_avx2};
+
+/* AVX2 also needs the operating system to have enabled the wider register
+ * state, which __builtin_cpu_supports checks along with the processor's own
+ * feature bits. */
+static int cpu_has_avx2(void) {
+# if defined(__has_builtin)
+# if __has_builtin(__builtin_cpu_init)
+ __builtin_cpu_init();
+# endif
+# elif defined(__GNUC__)
+ __builtin_cpu_init();
+# endif
+ return __builtin_cpu_supports("avx2") && __builtin_cpu_supports("fma");
+}
+#endif /* x86 */
+
+const svad_kernels *svad_kernels_simd(void) {
+#if defined(SVAD_X86_DISPATCH)
+ /* Resolved once; the answer cannot change while the process runs. */
+ static const svad_kernels *chosen;
+ if (!chosen)
+ chosen = cpu_has_avx2() ? &kernels_avx2 : &kernels_scalar;
+ return chosen;
+#elif defined(SVAD_HAVE_SIMD)
+ return &kernels_simd;
+#else
+ return &kernels_scalar;
+#endif
+}