diff options
| author | Onur Gündüz <ogunduz@gmail.com> | 2026-10-08 06:49:33 +0200 |
|---|---|---|
| committer | Onur Gündüz <ogunduz@gmail.com> | 2026-10-08 07:21:37 +0200 |
| commit | a5af9c3d351085f4005a949f8c382a3aad4e0b29 (patch) | |
| tree | 0ad133d931553e68a68588e983976a66b3309083 /kernels.c | |
| download | svad-a5af9c3d351085f4005a949f8c382a3aad4e0b29.tar.gz svad-a5af9c3d351085f4005a949f8c382a3aad4e0b29.zip | |
initv0.1.0
Diffstat (limited to 'kernels.c')
| -rw-r--r-- | kernels.c | 429 |
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 +} |
