"""DeepSeek NSA-style block-select sparse attention -- fused CUDA solution (RTX PRO 6000 / SM120). Raw CUDA C++ with inline-PTX bf16 tensor-core MMA (m16n8k16); three kernel launches per forward: k_prep exact 8-key prefix sums of K inside every 64-key block (compensated fp32), a two-term bf16 split (hi + lo) of each block sum for tensor-core scoring, and the reset of the work counters. k_select per query block (c >= 8): block importance q . (hi + lo) on tensor cores, the causal partial block from q.k scores, top-9 by a two-level tournament, and an exact (error-free fp32) re-evaluation of every candidate whose approximate value lies within the error band of the 8th/9th boundary -- so the selected set equals the exact-arithmetic top-8 (ties to the higher block, like the reference sort). Emits a selection bitmask (dense region) or (query, block) pairs appended to per-key-block work lists (sparse far field). k_attn (S > 2048) persistent 4-warp workers with an in-kernel ticket scheduler: DENSE tickets (first 8 query blocks): masked attention with online softmax. REMOTE tickets: one key block staged in smem, gathered query rows -> QK^T (mma) -> block softmax -> PV (mma) -> normalized bf16 partial + log-sum-exp. LOCAL tickets: sliding-window blocks c-1, c + online merge of the far-field partials, bf16 output. k_dense8 (S <= 2048) 8-warp workers, two query blocks each: fully dense masked attention driven by the selection bitmask; no intermediate global traffic. Measured on this GPU: an L2-resident global load costs ~400-800 cycles, L2<->SM bandwidth is ~5 TB/s read / ~3 TB/s write and fp64 is ~70x slower than fp32. The design therefore minimises bytes moved per (query, selected block) pair, issues every load a phase early, pools pairs per key block so one staged K/V block serves hundreds of queries, and avoids fp64 on hot paths. """ from __future__ import annotations import math import torch import torch.nn as nn from torch.utils.cpp_extension import load_inline BLOCK_SIZE = 64 TOP_N_BLOCKS = 8 SLIDING_WINDOW = 64 _CUDA_SRC = r""" #include #include #include typedef unsigned int u32; typedef unsigned short u16; #define NEG_BIG (-1.0e30f) __device__ __forceinline__ void mma16816(float* c, u32 a0, u32 a1, u32 a2, u32 a3, u32 b0, u32 b1) { asm volatile( "mma.sync.aligned.m16n8k16.row.col.f32.bf16.bf16.f32 {%0,%1,%2,%3}, {%4,%5,%6,%7}, {%8,%9}, {%0,%1,%2,%3};\n" : "+f"(c[0]), "+f"(c[1]), "+f"(c[2]), "+f"(c[3]) : "r"(a0), "r"(a1), "r"(a2), "r"(a3), "r"(b0), "r"(b1)); } __device__ __forceinline__ float ex2f(float x) { float y; asm("ex2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x)); return y; } __device__ __forceinline__ float lg2f(float x) { float y; asm("lg2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x)); return y; } __device__ __forceinline__ u32 pack_bf16(float lo, float hi) { u32 r; asm("cvt.rn.bf16x2.f32 %0, %2, %1;" : "=r"(r) : "f"(lo), "f"(hi)); return r; } __device__ __forceinline__ float bf_lo(u32 w) { return __uint_as_float(w << 16); } __device__ __forceinline__ float bf_hi(u32 w) { return __uint_as_float(w & 0xffff0000u); } __device__ __forceinline__ float bf2f(u16 h) { return __uint_as_float(((u32)h) << 16); } // fp64 is ~70x slower than fp32 on this GPU, so "exact" sums / dot products use fp32 // error-free transformations (value = s + c, compensated) instead of doubles. __device__ __forceinline__ void two_sum(float& s, float& c, float x) { const float t = __fadd_rn(s, x); const float bb = __fsub_rn(t, s); const float err = __fadd_rn(__fsub_rn(s, __fsub_rn(t, bb)), __fsub_rn(x, bb)); s = t; c = __fadd_rn(c, err); } // s + c += a * b exactly (a*b split into rounded product + FMA residual) __device__ __forceinline__ void two_prod_acc(float& s, float& c, float a, float b) { const float h = __fmul_rn(a, b); const float e = __fmaf_rn(a, b, -h); two_sum(s, c, h); c = __fadd_rn(c, e); } // --------------------------------------------------------------------------------- // k_prep: exact key prefix sums at 8-key granularity inside every 64-key block. // ps8[head][blk][oct][d] (fp32) = sum of keys blk*64 .. blk*64+8*oct+7 (oct=7: block sum) // kb_hi/kb_lo[head][blk][d] (bf16): two-term bf16 split of the block sum (full blocks only) // thread = (head, blk, dim-chunk of 8, octet); 8 adjacent lanes = the 8 octets of one block. // Also zeroes the pair-list counters and the work cursor. // --------------------------------------------------------------------------------- __global__ void __launch_bounds__(128) k_prep(const u16* __restrict__ K, float* __restrict__ ps8, u32* __restrict__ kb_hi, u32* __restrict__ kb_lo, int* __restrict__ cnt, int nCnt, int* __restrict__ ctrl, int nCtl, int NH, int S, int D, int nb, int nbf) { // ctrl[nCtl + head]: bits of max |block-sum element| of the head (atomicMax; reset by k_attn) const int gid = blockIdx.x * 128 + threadIdx.x; if (gid < nCtl) ctrl[gid] = 0; if (gid < nCnt) cnt[gid] = 0; const int DC = D >> 3; const int total = NH * nb * DC * 8; const bool active = gid < total; const int gi = active ? gid : (gid & 7); const int oct = gi & 7; int rest = gi >> 3; const int dch = rest % DC; rest /= DC; const int blk = rest % nb; const int head = rest / nb; const int key0 = blk * 64 + oct * 8; const uint4* p = reinterpret_cast(K + (size_t)head * S * D) + dch; uint4 x[8]; #pragma unroll for (int e = 0; e < 8; e++) x[e] = p[(size_t)min(key0 + e, S - 1) * DC]; float a[8], r[8]; // compensated sums: value = a + r #pragma unroll for (int e = 0; e < 8; e++) { a[e] = 0.f; r[e] = 0.f; } #pragma unroll for (int e = 0; e < 8; e++) { if (key0 + e < S) { two_sum(a[0], r[0], bf_lo(x[e].x)); two_sum(a[1], r[1], bf_hi(x[e].x)); two_sum(a[2], r[2], bf_lo(x[e].y)); two_sum(a[3], r[3], bf_hi(x[e].y)); two_sum(a[4], r[4], bf_lo(x[e].z)); two_sum(a[5], r[5], bf_hi(x[e].z)); two_sum(a[6], r[6], bf_lo(x[e].w)); two_sum(a[7], r[7], bf_hi(x[e].w)); } } // inclusive prefix over the 8 octets of the block (8 adjacent lanes) #pragma unroll for (int off = 1; off < 8; off <<= 1) { #pragma unroll for (int e = 0; e < 8; e++) { const float ta = __shfl_up_sync(0xffffffffu, a[e], off); const float tr = __shfl_up_sync(0xffffffffu, r[e], off); if (oct >= off) { two_sum(a[e], r[e], ta); r[e] = __fadd_rn(r[e], tr); } } } if (!active) return; float f[8], lo[8]; #pragma unroll for (int e = 0; e < 8; e++) { f[e] = __fadd_rn(a[e], r[e]); lo[e] = __fsub_rn(r[e], __fsub_rn(f[e], a[e])); } float4* dst = reinterpret_cast(ps8 + (((size_t)head * nb + blk) * 8 + oct) * D + dch * 8); dst[0] = make_float4(f[0], f[1], f[2], f[3]); dst[1] = make_float4(f[4], f[5], f[6], f[7]); if (oct == 7 && blk < nbf) { uint4 h, l; h.x = pack_bf16(f[0], f[1]); h.y = pack_bf16(f[2], f[3]); h.z = pack_bf16(f[4], f[5]); h.w = pack_bf16(f[6], f[7]); l.x = pack_bf16(__fadd_rn(__fsub_rn(f[0], bf_lo(h.x)), lo[0]), __fadd_rn(__fsub_rn(f[1], bf_hi(h.x)), lo[1])); l.y = pack_bf16(__fadd_rn(__fsub_rn(f[2], bf_lo(h.y)), lo[2]), __fadd_rn(__fsub_rn(f[3], bf_hi(h.y)), lo[3])); l.z = pack_bf16(__fadd_rn(__fsub_rn(f[4], bf_lo(h.z)), lo[4]), __fadd_rn(__fsub_rn(f[5], bf_hi(h.z)), lo[5])); l.w = pack_bf16(__fadd_rn(__fsub_rn(f[6], bf_lo(h.w)), lo[6]), __fadd_rn(__fsub_rn(f[7], bf_hi(h.w)), lo[7])); const size_t o = ((size_t)head * nbf + blk) * (D / 2) + dch * 4; *reinterpret_cast(kb_hi + o) = h; *reinterpret_cast(kb_lo + o) = l; float mx = 0.f; #pragma unroll for (int e = 0; e < 8; e++) mx = fmaxf(mx, fabsf(f[e])); atomicMax(ctrl + nCtl + head, (int)__float_as_uint(mx)); } } // --------------------------------------------------------------------------------- // shared tile helpers (warp = 16 query rows; lane -> (g = lane/4, cc = lane%4)) // The contraction index (dim) is permuted so that lane class cc owns the natural // dims [cc*D/4, (cc+1)*D/4): all operand loads are contiguous wide loads. // --------------------------------------------------------------------------------- template __device__ __forceinline__ void load_q_frags(u32 (*a)[4], const u16* row0, const u16* row1, int cc) { const uint4* q0 = reinterpret_cast(row0) + cc * (D / 32); const uint4* q1 = reinterpret_cast(row1) + cc * (D / 32); #pragma unroll for (int u = 0; u < D / 32; u++) { const uint4 x = q0[u]; const uint4 y = q1[u]; a[2 * u][0] = x.x; a[2 * u][2] = x.y; a[2 * u + 1][0] = x.z; a[2 * u + 1][2] = x.w; a[2 * u][1] = y.x; a[2 * u][3] = y.y; a[2 * u + 1][1] = y.z; a[2 * u + 1][3] = y.w; } } // stage one key block: K natural [key][D/2 words], V transposed [dim][cc(4)][kstep(4)][2 words]. // Split in two halves so a block can be fetched into registers while the previous one is in use. template struct StageRegs { uint4 k[8 * D / NT]; uint4 v0[4 * D / NT], v1[4 * D / NT]; }; template __device__ __forceinline__ void stage_load(StageRegs& R, const u16* Kb, const u16* Vb, int nkeys, int tid) { const uint4* k4 = reinterpret_cast(Kb); const int rowq = D / 8; // uint4 per key row #pragma unroll for (int e = 0; e < 8 * D / NT; e++) { const int x = tid + e * NT; const int key = x / rowq; R.k[e] = k4[(size_t)min(key, nkeys - 1) * rowq + (x - key * rowq)]; } const int lane = tid & 31, warp = tid >> 5; const int ka = min(2 * lane, nkeys - 1), kb = min(2 * lane + 1, nkeys - 1); const uint4* v0 = reinterpret_cast(Vb + (size_t)ka * D); const uint4* v1 = reinterpret_cast(Vb + (size_t)kb * D); #pragma unroll for (int e = 0; e < 4 * D / NT; e++) { R.v0[e] = v0[warp + (NT / 32) * e]; R.v1[e] = v1[warp + (NT / 32) * e]; } } template __device__ __forceinline__ void stage_store(u32* sK, u32* sV, const StageRegs& R, int tid) { uint4* s4 = reinterpret_cast(sK); #pragma unroll for (int e = 0; e < 8 * D / NT; e++) s4[tid + e * NT] = R.k[e]; const int lane = tid & 31, warp = tid >> 5; const int p = lane; // key pair (2p, 2p+1) const int woff = (p & 3) * 8 + (p >> 3) * 2 + ((p >> 2) & 1); #pragma unroll for (int e = 0; e < 4 * D / NT; e++) { const int u = warp + (NT / 32) * e; const uint4 r0 = R.v0[e]; const uint4 r1 = R.v1[e]; u32* dst = sV + (8 * u) * 32 + woff; dst[0 * 32] = (r0.x & 0xffffu) | (r1.x << 16); dst[1 * 32] = (r0.x >> 16) | (r1.x & 0xffff0000u); dst[2 * 32] = (r0.y & 0xffffu) | (r1.y << 16); dst[3 * 32] = (r0.y >> 16) | (r1.y & 0xffff0000u); dst[4 * 32] = (r0.z & 0xffffu) | (r1.z << 16); dst[5 * 32] = (r0.z >> 16) | (r1.z & 0xffff0000u); dst[6 * 32] = (r0.w & 0xffffu) | (r1.w << 16); dst[7 * 32] = (r0.w >> 16) | (r1.w & 0xffff0000u); } } template __device__ __forceinline__ void stage_kv(u32* sK, u32* sV, const u16* Kb, const u16* Vb, int nkeys, int tid) { StageRegs R; stage_load(R, Kb, Vb, nkeys, tid); stage_store(sK, sV, R, tid); } // scores[j][0..3] for key tiles j=0..7 (keys 8j+2cc+{0,1}; rows g, g+8) template __device__ __forceinline__ void qk_tile(float (*sc)[4], const u32 (*a)[4], const u32* sK, int g, int cc) { #pragma unroll for (int j = 0; j < 8; j++) { sc[j][0] = 0.f; sc[j][1] = 0.f; sc[j][2] = 0.f; sc[j][3] = 0.f; } const u32* kb = sK + g * (D / 2) + cc * (D / 8); #pragma unroll for (int s = 0; s < D / 16; s++) { #pragma unroll for (int j = 0; j < 8; j++) { const uint2 b = *reinterpret_cast(kb + j * 8 * (D / 2) + 2 * s); mma16816(sc[j], a[s][0], a[s][1], a[s][2], a[s][3], b.x, b.y); } } } template __device__ __forceinline__ void pv_tile(float (*o)[4], const u32 (*pa)[4], const u32* sV, int g, int cc) { const u32* vb = sV + g * 32 + cc * 8; #pragma unroll for (int s = S0; s < S1; s++) { #pragma unroll for (int jd = 0; jd < D / 8; jd++) { const uint2 b = *reinterpret_cast(vb + jd * 8 * 32 + 2 * s); mma16816(o[jd], pa[s][0], pa[s][1], pa[s][2], pa[s][3], b.x, b.y); } } } __device__ __forceinline__ float grp_max(float x) { x = fmaxf(x, __shfl_xor_sync(0xffffffffu, x, 1)); x = fmaxf(x, __shfl_xor_sync(0xffffffffu, x, 2)); return x; } __device__ __forceinline__ float grp_sum(float x) { x += __shfl_xor_sync(0xffffffffu, x, 1); x += __shfl_xor_sync(0xffffffffu, x, 2); return x; } // --------------------------------------------------------------------------------- // k_select: one CTA per query block c >= 8 (4 warps x 16 queries). // approx importance on tensor cores (q . (hi+lo) bf16 split of the exact block sums; the // causal partial block via q.k scores), top-9 by a two-level tournament, and an exact // (compensated fp32) re-evaluation of every candidate whose approximate value is within // the error band of the 8th/9th boundary. Emits selection masks (dense region) or // far-field (query, block) pairs appended to per-key-block lists (sparse region). // --------------------------------------------------------------------------------- #define NEGV (-3.0e38f) #ifndef SEL_KAPPA2 #define SEL_KAPPA2 (1.0e-4f) #endif #define SEL_FLOOR (0.06f) // exact dot products in compensated fp32 (8 independent (s, c) chains); operand rows are // loaded in one batch (a global load costs a few hundred cycles, so no load may wait on // an earlier one). ACC: float s[8], c[8]. template __device__ __forceinline__ void dot_qf(float* s, float* c, const uint4* qv, const float4* p4) { #pragma unroll for (int hb = 0; hb < D / 64; hb++) { float4 p[16]; #pragma unroll for (int u = 0; u < 16; u++) p[u] = p4[hb * 16 + u]; #pragma unroll for (int u = 0; u < 8; u++) { const uint4 x = qv[hb * 8 + u]; const float4 p0 = p[2 * u], p1 = p[2 * u + 1]; two_prod_acc(s[0], c[0], bf_lo(x.x), p0.x); two_prod_acc(s[1], c[1], bf_hi(x.x), p0.y); two_prod_acc(s[2], c[2], bf_lo(x.y), p0.z); two_prod_acc(s[3], c[3], bf_hi(x.y), p0.w); two_prod_acc(s[4], c[4], bf_lo(x.z), p1.x); two_prod_acc(s[5], c[5], bf_hi(x.z), p1.y); two_prod_acc(s[6], c[6], bf_lo(x.w), p1.z); two_prod_acc(s[7], c[7], bf_hi(x.w), p1.w); } } } template __device__ __forceinline__ void dot_qk(float* s, float* c, const uint4* qv, const uint4* k4) { uint4 kk[D / 8]; #pragma unroll for (int u = 0; u < D / 8; u++) kk[u] = k4[u]; #pragma unroll for (int u = 0; u < D / 8; u++) { const uint4 x = qv[u]; const uint4 y = kk[u]; // bf16 x bf16 products are exact in fp32 two_sum(s[0], c[0], __fmul_rn(bf_lo(x.x), bf_lo(y.x))); two_sum(s[1], c[1], __fmul_rn(bf_hi(x.x), bf_hi(y.x))); two_sum(s[2], c[2], __fmul_rn(bf_lo(x.y), bf_lo(y.y))); two_sum(s[3], c[3], __fmul_rn(bf_hi(x.y), bf_hi(y.y))); two_sum(s[4], c[4], __fmul_rn(bf_lo(x.z), bf_lo(y.z))); two_sum(s[5], c[5], __fmul_rn(bf_hi(x.z), bf_hi(y.z))); two_sum(s[6], c[6], __fmul_rn(bf_lo(x.w), bf_lo(y.w))); two_sum(s[7], c[7], __fmul_rn(bf_hi(x.w), bf_hi(y.w))); } } // exact importance of candidate block `id` for local query i of block c, in "sum over 64 keys" units. // qv: the query row (bf16 words) held in thread-local storage. Only the final scalar combine is fp64. template __device__ __noinline__ double exact_imp(const uint4* qv, const float* ps8h, const u16* Kc, int id, int c, int i) { float s[8], cc[8]; #pragma unroll for (int e = 0; e < 8; e++) { s[e] = 0.f; cc[e] = 0.f; } if (id < c) { dot_qf(s, cc, qv, reinterpret_cast(ps8h + ((size_t)id * 8 + 7) * D)); } else { const int sfull = (i + 1) >> 3; if (sfull > 0) dot_qf(s, cc, qv, reinterpret_cast(ps8h + ((size_t)c * 8 + sfull - 1) * D)); for (int j = sfull * 8; j <= i; j++) dot_qk(s, cc, qv, reinterpret_cast(Kc + (size_t)j * D)); } float S0 = 0.f, C0 = 0.f; #pragma unroll for (int e = 0; e < 8; e++) { two_sum(S0, C0, s[e]); C0 = __fadd_rn(C0, cc[e]); } double v = (double)S0 + (double)C0; if (id >= c) v = v * 64.0 / (double)(i + 1); return v; } // pop the current maximum of a score row (two-level: group maxima rg[], values rs[]); ties -> higher index __device__ __forceinline__ void sel_extract(float* rs, float* rg, int NG, float& outv, int& outi) { float best = rg[0]; int bg = 0; #pragma unroll 4 for (int g2 = 1; g2 < NG; g2++) { const float v = rg[g2]; if (v >= best) { best = v; bg = g2; } } const float4 x = *reinterpret_cast(rs + 8 * bg); const float4 y = *reinterpret_cast(rs + 8 * bg + 4); const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w}; int p = 0; float mx = e[0]; #pragma unroll for (int k = 1; k < 8; k++) { if (e[k] >= mx) { mx = e[k]; p = k; } } float nm = NEGV; #pragma unroll for (int k = 0; k < 8; k++) nm = fmaxf(nm, (k == p) ? NEGV : e[k]); rs[8 * bg + p] = NEGV; rg[bg] = nm; outv = mx; outi = 8 * bg + p; } template __device__ __noinline__ void refine_sel(float* rs, float* rg, int NG, const float* av0, const int* ai0, int n0, float E2, const u16* qrow, const float* ps8h, const u16* Kc, int c, int i, int* out) { const int RM = 16; float xv[RM]; int xi[RM]; uint4 qv[D / 8]; { const uint4* q4 = reinterpret_cast(qrow); #pragma unroll for (int u = 0; u < D / 8; u++) qv[u] = q4[u]; } for (int r = 0; r < n0; r++) { xv[r] = av0[r]; xi[r] = ai0[r]; } int n = n0; while (n < RM && n <= c && xv[n - 1] >= xv[7] - E2) { sel_extract(rs, rg, NG, xv[n], xi[n]); n++; } if (xv[n - 1] >= xv[7] - E2 && n <= c) { // too many near ties (degenerate input): exact evaluation of every candidate double tv[8]; int ti[8]; for (int r = 0; r < 8; r++) { tv[r] = -1.0e300; ti[r] = 0; } for (int id = 0; id <= c; id++) { double cv = exact_imp(qv, ps8h, Kc, id, c, i); int ci = id; for (int r = 0; r < 8; r++) { if (cv >= tv[r]) { const double nv = tv[r]; const int ni = ti[r]; tv[r] = cv; ti[r] = ci; cv = nv; ci = ni; } } } for (int r = 0; r < 8; r++) out[r] = ti[r]; return; } const int hi_r = (xv[n - 1] >= xv[7] - E2) ? n - 1 : n - 2; int lo_r = 7; while (lo_r > 0 && xv[lo_r - 1] <= xv[8] + E2) lo_r--; double ex[RM]; bool used[RM]; for (int r = lo_r; r <= hi_r; r++) { ex[r] = exact_imp(qv, ps8h, Kc, xi[r], c, i); used[r] = false; } for (int r = 0; r < lo_r; r++) out[r] = xi[r]; for (int m = lo_r; m < 8; m++) { int best = -1; for (int r = lo_r; r <= hi_r; r++) { if (used[r]) continue; if (best < 0 || ex[r] > ex[best] || (ex[r] == ex[best] && xi[r] > xi[best])) best = r; } used[best] = true; out[m] = xi[best]; } } #define SEL_CHB 16 // candidate blocks staged per chunk #define SEL_RA 6 // max ambiguous candidates handled by the cooperative re-check template __global__ void __launch_bounds__(128) k_select( const u16* __restrict__ Q, const u16* __restrict__ K, const u16* __restrict__ V, const u16* __restrict__ kb_hi, const u16* __restrict__ kb_lo, const float* __restrict__ ps8, int* __restrict__ cnt, u32* __restrict__ lists, const int* __restrict__ loff, u32* __restrict__ meta, int* __restrict__ ctrl, int S, int nb, int nbf, int nSel, int listCap, int nbR, int NCAP, int scoreWords, int CD, int kmaxOff) { extern __shared__ __align__(16) float smem[]; float* sS = smem; // [64][NCAP] approx importance (first used as the K block c stage) float* sG = smem + scoreWords; // [64][NCAP/8] group maxima u32* sB = reinterpret_cast(smem + scoreWords + 64 * (NCAP / 8)); // [2][SEL_CHB][D/2] hi|lo operands float* sQ1 = smem + scoreWords + 64 * (NCAP / 8) + 2 * SEL_CHB * (D / 2); // [64] |q|_1 per query row const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3; const int head = blockIdx.x / nSel; const int c = 8 + blockIdx.x % nSel; const size_t hoff = (size_t)head * S * D; const int rl0 = warp * 16 + g, rl1 = rl0 + 8; const int tq0 = min(c * 64 + rl0, S - 1), tq1 = min(c * 64 + rl1, S - 1); const int NG = (c >> 3) + 1; const u16* Kc = K + hoff + (size_t)c * 64 * D; const int nq = min(64, S - c * 64); const u16* kh = kb_hi + (size_t)head * nbf * D; const u16* kl = kb_lo + (size_t)head * nbf * D; const int nch = (c + SEL_CHB - 1) / SEL_CHB; const int NPT = (2 * SEL_CHB * (D / 8)) / 128; // operand uint4 per thread per chunk u32 a[D / 16][4]; load_q_frags(a, Q + hoff + (size_t)tq0 * D, Q + hoff + (size_t)tq1 * D, cc); // |q|_1 of the two rows (error-scale floor for the near-tie test) { float qa = 0.f, qb = 0.f; #pragma unroll for (int sx = 0; sx < D / 16; sx++) { const u32 w0 = a[sx][0] & 0x7fff7fffu, w2 = a[sx][2] & 0x7fff7fffu; const u32 w1 = a[sx][1] & 0x7fff7fffu, w3 = a[sx][3] & 0x7fff7fffu; qa += (bf_lo(w0) + bf_hi(w0)) + (bf_lo(w2) + bf_hi(w2)); qb += (bf_lo(w1) + bf_hi(w1)) + (bf_lo(w3) + bf_hi(w3)); } qa = grp_sum(qa); qb = grp_sum(qb); if (cc == 0) { sQ1[rl0] = qa; sQ1[rl1] = qb; } } const float kmaxHead = __uint_as_float((u32)ctrl[kmaxOff + head]); // prefetch this block's V rows into L2 (one touch per 128-byte line; nothing waits on it) u32 vtouch = 0; if (tid * 128 < nq * D * 2) { const volatile u32* vp = reinterpret_cast(V + hoff + (size_t)c * 64 * D) + tid * 32; vtouch = vp[0]; } // operands of the first chunk of block sums (hi | lo), kept in registers until staged uint4 nx[NPT]; #pragma unroll for (int e = 0; e < NPT; e++) { const int i = tid + e * 128; const int sp = i / (SEL_CHB * (D / 8)), r = i % (SEL_CHB * (D / 8)); const int blk = min(r / (D / 8), c - 1); nx[e] = reinterpret_cast((sp ? kl : kh) + (size_t)blk * D)[r % (D / 8)]; } // stage key block c (natural layout) into the score area and form the causal partial sums { const uint4* k4 = reinterpret_cast(Kc); uint4* s4 = reinterpret_cast(sS); #pragma unroll for (int x = tid; x < 64 * (D / 8); x += 128) { const int key = x / (D / 8); s4[x] = k4[(size_t)min(key, nq - 1) * (D / 8) + (x - key * (D / 8))]; } } __syncthreads(); float cur0, cur1; { float sc[8][4]; qk_tile(sc, a, reinterpret_cast(sS), g, cc); float sum0 = 0.f, sum1 = 0.f; #pragma unroll for (int j = 0; j < 8; j++) { const int k0 = 8 * j + 2 * cc, k1 = k0 + 1; sum0 += ((k0 <= rl0) ? sc[j][0] : 0.f) + ((k1 <= rl0) ? sc[j][1] : 0.f); sum1 += ((k0 <= rl1) ? sc[j][2] : 0.f) + ((k1 <= rl1) ? sc[j][3] : 0.f); } cur0 = grp_sum(sum0) * (64.0f / (float)(rl0 + 1)); cur1 = grp_sum(sum1) * (64.0f / (float)(rl1 + 1)); } __syncthreads(); if (tid < 64) { for (int idx = c + 1; idx < 8 * NG; idx++) sS[tid * NCAP + idx] = NEGV; } if (cc == 0) { sS[rl0 * NCAP + c] = cur0; sS[rl1 * NCAP + c] = cur1; } // full blocks 0..c-1 in chunks of SEL_CHB: q . (hi + lo), operands staged once per CTA for (int ch = 0; ch < nch; ch++) { { uint4* b4 = reinterpret_cast(sB); #pragma unroll for (int e = 0; e < NPT; e++) b4[tid + e * 128] = nx[e]; } __syncthreads(); if (ch + 1 < nch) { #pragma unroll for (int e = 0; e < NPT; e++) { const int i = tid + e * 128; const int sp = i / (SEL_CHB * (D / 8)), r = i % (SEL_CHB * (D / 8)); const int blk = min((ch + 1) * SEL_CHB + r / (D / 8), c - 1); nx[e] = reinterpret_cast((sp ? kl : kh) + (size_t)blk * D)[r % (D / 8)]; } } float chh[SEL_CHB / 8][4], cll[SEL_CHB / 8][4]; #pragma unroll for (int x = 0; x < SEL_CHB / 8; x++) { chh[x][0] = 0.f; chh[x][1] = 0.f; chh[x][2] = 0.f; chh[x][3] = 0.f; cll[x][0] = 0.f; cll[x][1] = 0.f; cll[x][2] = 0.f; cll[x][3] = 0.f; } const u32* bh = sB + g * (D / 2) + cc * (D / 8); const u32* bl = bh + SEL_CHB * (D / 2); #pragma unroll for (int sx = 0; sx < D / 16; sx++) { #pragma unroll for (int x = 0; x < SEL_CHB / 8; x++) { const uint2 vh = *reinterpret_cast(bh + x * 8 * (D / 2) + 2 * sx); const uint2 vl = *reinterpret_cast(bl + x * 8 * (D / 2) + 2 * sx); mma16816(chh[x], a[sx][0], a[sx][1], a[sx][2], a[sx][3], vh.x, vh.y); mma16816(cll[x], a[sx][0], a[sx][1], a[sx][2], a[sx][3], vl.x, vl.y); } } #pragma unroll for (int x = 0; x < SEL_CHB / 8; x++) { const int i0 = ch * SEL_CHB + 8 * x + 2 * cc; if (i0 + 1 < c) { *reinterpret_cast(sS + rl0 * NCAP + i0) = make_float2(chh[x][0] + cll[x][0], chh[x][1] + cll[x][1]); *reinterpret_cast(sS + rl1 * NCAP + i0) = make_float2(chh[x][2] + cll[x][2], chh[x][3] + cll[x][3]); } else if (i0 < c) { sS[rl0 * NCAP + i0] = chh[x][0] + cll[x][0]; sS[rl1 * NCAP + i0] = chh[x][2] + cll[x][2]; } } __syncthreads(); } if (tid >= 64) return; // ---- top-k (thread per query) ---- const int i = tid; const int t = c * 64 + i; const bool valid = t < S; float* rs = sS + i * NCAP; float* rg = sG + i * (NCAP / 8); float maxabs = 0.f; const u16* qrow = Q + hoff + (size_t)(valid ? t : (S - 1)) * D; const float* ps8h = ps8 + (size_t)head * nb * 8 * D; float av[9]; int ai[9]; if (NG <= 16) { // group maxima live in registers: argmax over 16 registers, then one 8-value group in smem float gm[16]; #pragma unroll for (int g2 = 0; g2 < 16; g2++) { gm[g2] = NEGV; if (g2 < NG) { const float4 x = *reinterpret_cast(rs + 8 * g2); const float4 y = *reinterpret_cast(rs + 8 * g2 + 4); const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w}; #pragma unroll for (int k = 0; k < 8; k++) { gm[g2] = fmaxf(gm[g2], e[k]); maxabs = fmaxf(maxabs, (e[k] > 0.5f * NEGV) ? fabsf(e[k]) : 0.f); } } } #pragma unroll for (int r = 0; r < 9; r++) { float best = gm[0]; int bg = 0; #pragma unroll for (int k = 1; k < 16; k++) { if (gm[k] >= best) { best = gm[k]; bg = k; } } const float4 x = *reinterpret_cast(rs + 8 * bg); const float4 y = *reinterpret_cast(rs + 8 * bg + 4); const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w}; int p = 0; float mx = e[0]; #pragma unroll for (int k = 1; k < 8; k++) { if (e[k] >= mx) { mx = e[k]; p = k; } } float nm = NEGV; #pragma unroll for (int k = 0; k < 8; k++) nm = fmaxf(nm, (k == p) ? NEGV : e[k]); rs[8 * bg + p] = NEGV; #pragma unroll for (int k = 0; k < 16; k++) gm[k] = (k == bg) ? nm : gm[k]; av[r] = mx; ai[r] = 8 * bg + p; } } else { #pragma unroll 2 for (int g2 = 0; g2 < NG; g2++) { const float4 x = *reinterpret_cast(rs + 8 * g2); const float4 y = *reinterpret_cast(rs + 8 * g2 + 4); const float e[8] = {x.x, x.y, x.z, x.w, y.x, y.y, y.z, y.w}; float gmx = e[0]; #pragma unroll for (int k = 0; k < 8; k++) { gmx = fmaxf(gmx, e[k]); maxabs = fmaxf(maxabs, (e[k] > 0.5f * NEGV) ? fabsf(e[k]) : 0.f); } rg[g2] = gmx; } #pragma unroll for (int r = 0; r < 9; r++) sel_extract(rs, rg, NG, av[r], ai[r]); } #ifdef NSA_DBG_E if (valid) { // debug: worst |approx - exact| over the candidates not yet popped float worst = 0.f; uint4 qv[D / 8]; for (int u = 0; u < D / 8; u++) qv[u] = reinterpret_cast(qrow)[u]; for (int id = 0; id <= c; id++) { if (rs[id] <= 0.5f * NEGV) continue; const double ex = exact_imp(qv, ps8h, Kc, id, c, i); worst = fmaxf(worst, (float)(fabs((double)rs[id] - ex)) / maxabs); } for (int r = 0; r < 9; r++) { const double ex = exact_imp(qv, ps8h, Kc, ai[r], c, i); worst = fmaxf(worst, (float)(fabs((double)av[r] - ex)) / maxabs); } atomicMax(&ctrl[5], (int)__float_as_uint(worst)); } #endif // error scale: the largest candidate, floored by a bound-like term so that inputs whose // importances are all tiny relative to their terms (e.g. identical blocks) still re-check maxabs = fmaxf(maxabs, SEL_FLOOR * sQ1[i] * kmaxHead); const float E2 = SEL_KAPPA2 * maxabs; // ---- near-tie re-check. Rare (a few queries per thousand) but a serial exact evaluation // would stall this CTA for microseconds, so the whole warp serves one flagged query at a // time: the flagged lane finds the ambiguous candidates, all 32 lanes each take D/32 dims // of the exact (compensated fp32) dot products with a single round of loads, and the // flagged lane ranks the results (ties to the higher block index). { const int NDL = D / 32; u32 fm = __ballot_sync(0xffffffffu, valid && !(av[7] - av[8] > E2)); while (fm) { const int L = __ffs(fm) - 1; fm &= fm - 1; const int iL = (tid & ~31) + L; // query row of lane L float* rsL = sS + iL * NCAP; float* rgL = sG + iL * (NCAP / 8); if (NG <= 16) { // the register path does not maintain the group maxima in smem: rebuild them for row iL if (lane < NG) { const float4 x = *reinterpret_cast(rsL + 8 * lane); const float4 y = *reinterpret_cast(rsL + 8 * lane + 4); rgL[lane] = fmaxf(fmaxf(fmaxf(x.x, x.y), fmaxf(x.z, x.w)), fmaxf(fmaxf(y.x, y.y), fmaxf(y.z, y.w))); } __syncwarp(); } int na = 0, lo_r = 8; int ids[SEL_RA]; #pragma unroll for (int k = 0; k < SEL_RA; k++) ids[k] = 0; if (lane == L) { float xv[12]; int xi[12]; #pragma unroll for (int r = 0; r < 9; r++) { xv[r] = av[r]; xi[r] = ai[r]; } #pragma unroll for (int r = 9; r < 12; r++) { xv[r] = NEGV; xi[r] = 0; } int n = 9; #pragma unroll for (int r = 9; r < 12; r++) { if (n == r && r <= c && xv[r - 1] >= xv[7] - E2) { sel_extract(rsL, rgL, NG, xv[r], xi[r]); n = r + 1; } } const float last = (n == 9) ? xv[8] : (n == 10) ? xv[9] : (n == 11) ? xv[10] : xv[11]; const bool more = last >= xv[7] - E2; // the last popped candidate is still inside the band const int hi_r = more ? n - 1 : n - 2; lo_r = 7; #pragma unroll for (int r = 6; r >= 0; r--) { if (lo_r == r + 1 && xv[r] <= xv[8] + E2) lo_r = r; } na = hi_r - lo_r + 1; if ((more && n <= c) || na > SEL_RA) { // many-way near tie (degenerate input): serial fallback with exact evaluation float tv[16]; int ti[16], to[8]; #pragma unroll for (int r = 0; r < 12; r++) { tv[r] = xv[r]; ti[r] = xi[r]; } refine_sel(rsL, rgL, NG, tv, ti, n, E2, qrow, ps8h, Kc, c, i, to); #pragma unroll for (int r = 0; r < 8; r++) ai[r] = to[r]; na = 0; } else { #pragma unroll for (int k = 0; k < SEL_RA; k++) { #pragma unroll for (int r = 0; r < 12; r++) { if (r == lo_r + k) ids[k] = xi[r]; } } } #ifdef NSA_DBG_E atomicAdd(&ctrl[4], 1); #endif } na = __shfl_sync(0xffffffffu, na, L); #pragma unroll for (int k = 0; k < SEL_RA; k++) ids[k] = __shfl_sync(0xffffffffu, ids[k], L); if (na == 0) continue; // one round of loads: this lane's slice of the query row and of every candidate's exact // 64-key (or causal-prefix) key sum, plus the <= 7 loose keys of the causal partial block const int sfull = (iL + 1) >> 3; bool hasCur = false; #pragma unroll for (int k = 0; k < SEL_RA; k++) hasCur = hasCur || (k < na && ids[k] == c); u32 qw[NDL / 2]; { const u32* qp = reinterpret_cast(Q + hoff + (size_t)(c * 64 + iL) * D + lane * NDL); #pragma unroll for (int w = 0; w < NDL / 2; w++) qw[w] = qp[w]; } float pf[SEL_RA][NDL]; #pragma unroll for (int k = 0; k < SEL_RA; k++) { #pragma unroll for (int d = 0; d < NDL; d++) pf[k][d] = 0.f; if (k < na) { const int id = ids[k]; const bool isc = id == c; if (!isc || sfull > 0) { const float* pp = ps8h + ((size_t)id * 8 + (isc ? sfull - 1 : 7)) * D + lane * NDL; #pragma unroll for (int d = 0; d < NDL; d++) pf[k][d] = pp[d]; } } } u32 kw[7][NDL / 2]; #pragma unroll for (int jj = 0; jj < 7; jj++) { #pragma unroll for (int w = 0; w < NDL / 2; w++) kw[jj][w] = 0u; const int j = 8 * sfull + jj; if (hasCur && j <= iL) { const u32* kp = reinterpret_cast(Kc + (size_t)j * D + lane * NDL); #pragma unroll for (int w = 0; w < NDL / 2; w++) kw[jj][w] = kp[w]; } } float qd[NDL]; #pragma unroll for (int w = 0; w < NDL / 2; w++) { qd[2 * w] = bf_lo(qw[w]); qd[2 * w + 1] = bf_hi(qw[w]); } float vh[SEL_RA], vl[SEL_RA]; // exact values as normalized (hi, lo) float pairs const float nf = (float)(iL + 1); #pragma unroll for (int k = 0; k < SEL_RA; k++) { vh[k] = 0.f; vl[k] = 0.f; if (k < na) { float s1 = 0.f, c1 = 0.f; #pragma unroll for (int d = 0; d < NDL; d++) two_prod_acc(s1, c1, qd[d], pf[k][d]); if (ids[k] == c) { #pragma unroll for (int jj = 0; jj < 7; jj++) { #pragma unroll for (int w = 0; w < NDL / 2; w++) { // bf16 x bf16 products are exact in fp32 two_sum(s1, c1, __fmul_rn(qd[2 * w], bf_lo(kw[jj][w]))); two_sum(s1, c1, __fmul_rn(qd[2 * w + 1], bf_hi(kw[jj][w]))); } } } #pragma unroll for (int off = 16; off > 0; off >>= 1) { const float sx = __shfl_xor_sync(0xffffffffu, s1, off); const float cx = __shfl_xor_sync(0xffffffffu, c1, off); two_sum(s1, c1, sx); c1 = __fadd_rn(c1, cx); } float h = __fadd_rn(s1, c1); float l = __fsub_rn(c1, __fsub_rn(h, s1)); if (hasCur) { // common unit: the causal partial block is a mean over iL+1 keys, the others over 64 if (ids[k] == c) { h *= 64.f; l *= 64.f; } else { const float ph = __fmul_rn(h, nf); const float pl = __fadd_rn(__fmaf_rn(h, nf, -ph), __fmul_rn(l, nf)); h = __fadd_rn(ph, pl); l = __fsub_rn(pl, __fsub_rn(h, ph)); } } vh[k] = h; vl[k] = l; } } if (lane == L) { // rank the ambiguous candidates (descending value, ties to the higher block index) #pragma unroll for (int k = 0; k < SEL_RA; k++) { if (k < na) { int rank = 0; #pragma unroll for (int j = 0; j < SEL_RA; j++) { if (j != k && j < na) { const bool gt = (vh[j] > vh[k]) || (vh[j] == vh[k] && (vl[j] > vl[k] || (vl[j] == vl[k] && ids[j] > ids[k]))); rank += gt ? 1 : 0; } } #pragma unroll for (int r = 0; r < 8; r++) { if (r == lo_r + rank) ai[r] = ids[k]; } } } } } } if (valid && c < CD) { // dense region: the attention kernel only needs the selected-block bitmask u32 mask = 0; #pragma unroll for (int r = 0; r < 8; r++) mask |= 1u << ai[r]; meta[(size_t)head * S + t] = mask | (vtouch & 0u); } else if (valid) { // append the far-field pairs to their key-block lists: all atomics first, then the stores int pos[8], off[8]; #pragma unroll for (int r = 0; r < 8; r++) { const int id = ai[r]; pos[r] = 0; off[r] = 0; if (id < c - 1) { off[r] = loff[id]; pos[r] = atomicAdd(&cnt[head * nbR + id], 1); } } int k = 0; u32 hasP = 0; #pragma unroll for (int r = 0; r < 8; r++) { const int id = ai[r]; if (id == c - 1) { hasP = 1; } else if (id != c) { lists[(size_t)head * listCap + off[r] + pos[r]] = (u32)t | ((u32)k << 16); k++; } } meta[(size_t)head * S + t] = (u32)k | (hasP << 8) | (vtouch & 0u); } } // --------------------------------------------------------------------------------- // k_attn: persistent workers (4 warps) with an in-kernel task scheduler. Global loads cost // hundreds of cycles and L2<->SM bandwidth is the scarce resource, so every task issues its // loads early and the three task kinds are chosen to minimise bytes moved: // DENSE ticket (query block c < CD): flash-style masked attention over key blocks 0..c, // next key block prefetched into registers; no intermediate global traffic at all. // REMOTE ticket (far field of query blocks c >= CD): a chunk of (query, key block) pairs of // one key-block list. Key block staged in smem, query rows gathered, QK^T (mma) -> // block softmax -> PV (mma); normalized partial (bf16) + log2-sum-exp go to the query slot. // LOCAL ticket (query block c >= CD): key blocks c-1 and c (sliding window + causal) with // online softmax, interleaved merge of the query's far-field partials, bf16 output. // Dense tickets are implicit (claimable immediately, longest first); CTA 0 meanwhile turns // the pair counts into the ticket table R(h0) R(h1) L(h0) R(h2) L(h1) ... so partials are // consumed while still L2-resident. // --------------------------------------------------------------------------------- struct AttnParams { const u16* Q; const u16* K; const u16* V; u16* out; const u32* lists; const int* loff; const int* cnt; int* pos; u32* tick; int* ctrl; const u32* meta; u32* part_o; float* part_lw; int S, NH, nb, nbR, listCap, CD; float scale2; }; #ifndef CH_PAIRS #define CH_PAIRS 256 #endif #define CTL_CUR 0 #define CTL_READY 2 #define CTL_NTICK 3 #define CTL_HEAD 16 // per head: [DONE, NT] #define TK_EXIT 0xffffffffu #define TK_LOCAL 0x80000000u #define TK_DENSE 0x40000000u // Planner (CTA 0): pair counts -> global ticket sequence. Scratch w (ints, smem when it fits): // w[L] per list: ticket offset inside its 8-list group | n << 16 // wg[h*G8 + j] per group: ticket count, then exclusive prefix inside the head // hs[h] per head: exclusive prefix of remote tickets (hs[NH] = total) __device__ __noinline__ void attn_plan(const AttnParams& P, int* w, int tid) { const int NH = P.NH, nbR = P.nbR, nb = P.nb; const int nLoc = nb > P.CD ? nb - P.CD : 0; // LOCAL tickets per head const int nLists = NH * nbR; const int G8 = (nbR + 7) >> 3; int* wg = w + nLists; int* hs = wg + NH * G8; // pair counts (all loads of a pass are issued before any store) for (int base = tid; base < nLists; base += 128 * 8) { int v[8]; #pragma unroll for (int e = 0; e < 8; e++) { const int L = base + 128 * e; v[e] = (L < nLists) ? P.cnt[L] : 0; } #pragma unroll for (int e = 0; e < 8; e++) { const int L = base + 128 * e; if (L < nLists) w[L] = v[e]; } } __threadfence(); __syncthreads(); // groups of 8 lists for (int gi = tid; gi < NH * G8; gi += 128) { const int h = gi / G8, j = gi % G8; int v[8]; #pragma unroll for (int e = 0; e < 8; e++) { const int bi = 8 * j + e; v[e] = (bi < nbR) ? w[h * nbR + bi] : 0; } int run = 0; #pragma unroll for (int e = 0; e < 8; e++) { const int bi = 8 * j + e; if (bi < nbR) w[h * nbR + bi] = run | (v[e] << 16); run += (v[e] + CH_PAIRS - 1) / CH_PAIRS; } wg[gi] = run; } __threadfence(); __syncthreads(); // groups inside a head for (int h = tid; h < NH; h += 128) { int run = 0; for (int j0 = 0; j0 < G8; j0 += 8) { int v[8]; #pragma unroll for (int e = 0; e < 8; e++) v[e] = (j0 + e < G8) ? wg[h * G8 + j0 + e] : 0; #pragma unroll for (int e = 0; e < 8; e++) { if (j0 + e < G8) wg[h * G8 + j0 + e] = run; run += v[e]; } } hs[h + 1] = run; } __threadfence(); __syncthreads(); if (tid == 0) { int run = 0; for (int h0 = 0; h0 < NH; h0 += 8) { int v[8]; #pragma unroll for (int e = 0; e < 8; e++) v[e] = (h0 + e < NH) ? hs[h0 + e + 1] : 0; #pragma unroll for (int e = 0; e < 8; e++) { if (h0 + e < NH) { hs[h0 + e] = run; P.ctrl[CTL_HEAD + 2 * (h0 + e) + 1] = v[e]; } run += v[e]; } } hs[NH] = run; P.ctrl[CTL_NTICK] = run + NH * nLoc; } __threadfence(); __syncthreads(); for (int L = tid; L < nLists; L += 128) { const int h = L / nbR, bi = L % nbR; const int v = w[L]; const int n = v >> 16; const int base = hs[h] + nLoc * max(h - 1, 0) + wg[h * G8 + (bi >> 3)] + (v & 0xffff); for (int k = 0; k * CH_PAIRS < n; k++) { P.tick[2 * (base + k)] = (u32)L; P.tick[2 * (base + k) + 1] = (u32)(k * CH_PAIRS) | ((u32)min(CH_PAIRS, n - k * CH_PAIRS) << 20); } } for (int i = tid; i < NH * nLoc; i += 128) { const int h = i / nLoc, c = P.CD + i % nLoc; const int base = hs[min(h + 2, NH)] + nLoc * h; P.tick[2 * (base + i % nLoc)] = TK_LOCAL | (u32)(h * nb + c); P.tick[2 * (base + i % nLoc) + 1] = 0; } __threadfence(); __syncthreads(); if (tid == 0) { P.ctrl[CTL_READY] = 1; __threadfence(); } } // far-field partial slots: load / accumulate two slots (both rows of this thread) #define SLOT_LOAD(K_, T0_, T1_) \ if ((K_) < nmax) { \ const uint4* s0_ = reinterpret_cast(P.part_o + (q0 + (K_)) * (D / 2) + cc * (D / 8)); \ const uint4* s1_ = reinterpret_cast(P.part_o + (q1 + (K_)) * (D / 2) + cc * (D / 8)); \ _Pragma("unroll") for (int u_ = 0; u_ < D / 32; u_++) { T0_[u_] = s0_[u_]; T1_[u_] = s1_[u_]; } \ } #define SLOT_FMA(K_, T0_, T1_) \ if ((K_) < nmax) { \ const bool in0_ = (K_) < nr0, in1_ = (K_) < nr1; \ const float w0_ = in0_ ? ex2f(lw0[K_] - m0) : 0.f; \ const float w1_ = in1_ ? ex2f(lw1[K_] - m1) : 0.f; \ const u32 k0_ = in0_ ? 0xffffffffu : 0u, k1_ = in1_ ? 0xffffffffu : 0u; \ l0 += w0_; \ l1 += w1_; \ _Pragma("unroll") for (int u_ = 0; u_ < D / 32; u_++) { \ const uint4 x_ = T0_[u_]; \ const uint4 y_ = T1_[u_]; \ o[4 * u_ + 0][0] = fmaf(w0_, bf_lo(x_.x & k0_), o[4 * u_ + 0][0]); o[4 * u_ + 0][1] = fmaf(w0_, bf_hi(x_.x & k0_), o[4 * u_ + 0][1]); \ o[4 * u_ + 1][0] = fmaf(w0_, bf_lo(x_.y & k0_), o[4 * u_ + 1][0]); o[4 * u_ + 1][1] = fmaf(w0_, bf_hi(x_.y & k0_), o[4 * u_ + 1][1]); \ o[4 * u_ + 2][0] = fmaf(w0_, bf_lo(x_.z & k0_), o[4 * u_ + 2][0]); o[4 * u_ + 2][1] = fmaf(w0_, bf_hi(x_.z & k0_), o[4 * u_ + 2][1]); \ o[4 * u_ + 3][0] = fmaf(w0_, bf_lo(x_.w & k0_), o[4 * u_ + 3][0]); o[4 * u_ + 3][1] = fmaf(w0_, bf_hi(x_.w & k0_), o[4 * u_ + 3][1]); \ o[4 * u_ + 0][2] = fmaf(w1_, bf_lo(y_.x & k1_), o[4 * u_ + 0][2]); o[4 * u_ + 0][3] = fmaf(w1_, bf_hi(y_.x & k1_), o[4 * u_ + 0][3]); \ o[4 * u_ + 1][2] = fmaf(w1_, bf_lo(y_.y & k1_), o[4 * u_ + 1][2]); o[4 * u_ + 1][3] = fmaf(w1_, bf_hi(y_.y & k1_), o[4 * u_ + 1][3]); \ o[4 * u_ + 2][2] = fmaf(w1_, bf_lo(y_.z & k1_), o[4 * u_ + 2][2]); o[4 * u_ + 2][3] = fmaf(w1_, bf_hi(y_.z & k1_), o[4 * u_ + 2][3]); \ o[4 * u_ + 3][2] = fmaf(w1_, bf_lo(y_.w & k1_), o[4 * u_ + 3][2]); o[4 * u_ + 3][3] = fmaf(w1_, bf_hi(y_.w & k1_), o[4 * u_ + 3][3]); \ } \ } // masked online-softmax step for one key block of the LOCAL task (updates m, l, rescales o, builds pa) #define LOCAL_SOFTMAX() \ { \ float mx0 = NEG_BIG, mx1 = NEG_BIG; \ _Pragma("unroll") for (int j = 0; j < 8; j++) { \ const int k0 = 8 * j + 2 * cc, k1 = k0 + 1; \ sc[j][0] = (k0 >= lo0 && k0 <= hi0) ? sc[j][0] * scale2 : NEG_BIG; \ sc[j][1] = (k1 >= lo0 && k1 <= hi0) ? sc[j][1] * scale2 : NEG_BIG; \ sc[j][2] = (k0 >= lo1 && k0 <= hi1) ? sc[j][2] * scale2 : NEG_BIG; \ sc[j][3] = (k1 >= lo1 && k1 <= hi1) ? sc[j][3] * scale2 : NEG_BIG; \ mx0 = fmaxf(mx0, fmaxf(sc[j][0], sc[j][1])); \ mx1 = fmaxf(mx1, fmaxf(sc[j][2], sc[j][3])); \ } \ mx0 = fmaxf(grp_max(mx0), m0); \ mx1 = fmaxf(grp_max(mx1), m1); \ const float al0 = ex2f(m0 - mx0), al1 = ex2f(m1 - mx1); \ m0 = mx0; \ m1 = mx1; \ float s0 = 0.f, s1 = 0.f; \ _Pragma("unroll") for (int j = 0; j < 8; j++) { \ const float p0 = (sc[j][0] > 0.5f * NEG_BIG) ? ex2f(sc[j][0] - m0) : 0.f; \ const float p1 = (sc[j][1] > 0.5f * NEG_BIG) ? ex2f(sc[j][1] - m0) : 0.f; \ const float p2 = (sc[j][2] > 0.5f * NEG_BIG) ? ex2f(sc[j][2] - m1) : 0.f; \ const float p3 = (sc[j][3] > 0.5f * NEG_BIG) ? ex2f(sc[j][3] - m1) : 0.f; \ s0 += p0 + p1; \ s1 += p2 + p3; \ pa[j >> 1][(j & 1) * 2 + 0] = pack_bf16(p0, p1); \ pa[j >> 1][(j & 1) * 2 + 1] = pack_bf16(p2, p3); \ } \ l0 = l0 * al0 + grp_sum(s0); \ l1 = l1 * al1 + grp_sum(s1); \ _Pragma("unroll") for (int jd = 0; jd < D / 8; jd++) { o[jd][0] *= al0; o[jd][1] *= al0; o[jd][2] *= al1; o[jd][3] *= al1; } \ } template __device__ __forceinline__ void remote_task(const AttnParams& P, u32* sK, u32* sV, u32 w0, u32 w1, bool need_stage) { const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3; const int S = P.S; const float scale2 = P.scale2; // ---------------- REMOTE ---------------- const int L = (int)w0, start = (int)(w1 & 0xfffffu), end = start + (int)(w1 >> 20); const int head = L / P.nbR, bi = L % P.nbR; const size_t hoff = (size_t)head * S * D; const u32* lb = P.lists + (size_t)head * P.listCap + P.loff[bi]; const u16* Qh = P.Q + hoff; const int eb0 = start + warp * 16; // this warp's first pair in round 0 (rounds advance by 64 pairs) // raw list entries of the first two rounds u32 un0 = 0, un1 = 0, um0 = 0, um1 = 0; if (eb0 < end) { un0 = lb[min(eb0 + g, end - 1)]; un1 = lb[min(eb0 + g + 8, end - 1)]; } if (eb0 + 64 < end) { um0 = lb[min(eb0 + 64 + g, end - 1)]; um1 = lb[min(eb0 + 64 + g + 8, end - 1)]; } if (need_stage) { stage_kv(sK, sV, P.K + hoff + (size_t)bi * 64 * D, P.V + hoff + (size_t)bi * 64 * D, 64, tid); } __syncthreads(); if (eb0 < end) { // current round state int e0 = eb0 + g, e1 = e0 + 8; bool v0 = e0 < end, v1 = e1 < end; int ec0 = min(e0, end - 1), ec1 = min(e1, end - 1); int t0 = (int)(un0 & 0xffff); int t1 = (int)(un1 & 0xffff); int k0 = (int)(un0 >> 16); int k1 = (int)(un1 >> 16); u32 a[D / 16][4]; load_q_frags(a, Qh + (size_t)t0 * D, Qh + (size_t)t1 * D, cc); for (int eb = eb0;; eb += 64) { float sc[8][4]; qk_tile(sc, a, sK, g, cc); // gather the next round's query rows while this round computes const bool more = eb + 64 < end; int nt0 = 0, nt1 = 0, nk0 = 0, nk1 = 0; bool nv0 = false, nv1 = false; if (more) { const int f0 = eb + 64 + g, f1 = f0 + 8; nv0 = f0 < end; nv1 = f1 < end; const int fc0 = min(f0, end - 1), fc1 = min(f1, end - 1); nt0 = (int)(um0 & 0xffff); nt1 = (int)(um1 & 0xffff); nk0 = (int)(um0 >> 16); nk1 = (int)(um1 >> 16); load_q_frags(a, Qh + (size_t)nt0 * D, Qh + (size_t)nt1 * D, cc); if (eb + 128 < end) { um0 = lb[min(eb + 128 + g, end - 1)]; um1 = lb[min(eb + 128 + g + 8, end - 1)]; } } float m0 = NEG_BIG, m1 = NEG_BIG; #pragma unroll for (int j = 0; j < 8; j++) { sc[j][0] *= scale2; sc[j][1] *= scale2; sc[j][2] *= scale2; sc[j][3] *= scale2; m0 = fmaxf(m0, fmaxf(sc[j][0], sc[j][1])); m1 = fmaxf(m1, fmaxf(sc[j][2], sc[j][3])); } m0 = grp_max(m0); m1 = grp_max(m1); float l0 = 0.f, l1 = 0.f; u32 pa[4][4]; #pragma unroll for (int j = 0; j < 8; j++) { const float p0 = ex2f(sc[j][0] - m0), p1 = ex2f(sc[j][1] - m0); const float p2 = ex2f(sc[j][2] - m1), p3 = ex2f(sc[j][3] - m1); l0 += p0 + p1; l1 += p2 + p3; pa[j >> 1][(j & 1) * 2 + 0] = pack_bf16(p0, p1); pa[j >> 1][(j & 1) * 2 + 1] = pack_bf16(p2, p3); } l0 = grp_sum(l0); l1 = grp_sum(l1); float o[D / 8][4]; #pragma unroll for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; } pv_tile(o, pa, sV, g, cc); const float i0 = 1.0f / l0, i1 = 1.0f / l1; if (v0) { const size_t slot = ((size_t)head * S + t0) * 8 + k0; uint4* dst = reinterpret_cast(P.part_o + slot * (D / 2) + cc * (D / 8)); #pragma unroll for (int u = 0; u < D / 32; u++) { uint4 w; w.x = pack_bf16(o[4 * u + 0][0] * i0, o[4 * u + 0][1] * i0); w.y = pack_bf16(o[4 * u + 1][0] * i0, o[4 * u + 1][1] * i0); w.z = pack_bf16(o[4 * u + 2][0] * i0, o[4 * u + 2][1] * i0); w.w = pack_bf16(o[4 * u + 3][0] * i0, o[4 * u + 3][1] * i0); dst[u] = w; } if (cc == 0) P.part_lw[slot] = m0 + lg2f(l0); } if (v1) { const size_t slot = ((size_t)head * S + t1) * 8 + k1; uint4* dst = reinterpret_cast(P.part_o + slot * (D / 2) + cc * (D / 8)); #pragma unroll for (int u = 0; u < D / 32; u++) { uint4 w; w.x = pack_bf16(o[4 * u + 0][2] * i1, o[4 * u + 0][3] * i1); w.y = pack_bf16(o[4 * u + 1][2] * i1, o[4 * u + 1][3] * i1); w.z = pack_bf16(o[4 * u + 2][2] * i1, o[4 * u + 2][3] * i1); w.w = pack_bf16(o[4 * u + 3][2] * i1, o[4 * u + 3][3] * i1); dst[u] = w; } if (cc == 0) P.part_lw[slot] = m1 + lg2f(l1); } if (!more) break; t0 = nt0; t1 = nt1; k0 = nk0; k1 = nk1; v0 = nv0; v1 = nv1; } } __threadfence(); __syncthreads(); if (tid == 0) atomicAdd(P.ctrl + CTL_HEAD + 2 * head, 1); } template __device__ __forceinline__ void local_task(const AttnParams& P, u32* sK, u32* sV, u32 w0) { const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3; const int S = P.S; const float scale2 = P.scale2; const int li = (int)(w0 & 0x3fffffffu); const int head = li / P.nb, c = li % P.nb; // c >= CD >= 8 const size_t hoff = (size_t)head * S * D; const int rl0 = warp * 16 + g, rl1 = rl0 + 8; const int t0 = c * 64 + rl0, t1 = c * 64 + rl1; const bool v0 = t0 < S, v1 = t1 < S; const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1); const size_t q0 = ((size_t)head * S + tq0) * 8; const size_t q1 = ((size_t)head * S + tq1) * 8; const int nmax = 8; // meta: low byte = number of far-field partial slots, bit 8 = block c-1 fully selected const u32 meta0 = P.meta[(size_t)head * S + tq0]; const u32 meta1 = P.meta[(size_t)head * S + tq1]; float lw0[8], lw1[8]; { const float4* p0 = reinterpret_cast(P.part_lw + q0); const float4* p1 = reinterpret_cast(P.part_lw + q1); const float4 x0 = p0[0], x1 = p0[1], y0 = p1[0], y1 = p1[1]; lw0[0] = x0.x; lw0[1] = x0.y; lw0[2] = x0.z; lw0[3] = x0.w; lw0[4] = x1.x; lw0[5] = x1.y; lw0[6] = x1.z; lw0[7] = x1.w; lw1[0] = y0.x; lw1[1] = y0.y; lw1[2] = y0.z; lw1[3] = y0.w; lw1[4] = y1.x; lw1[5] = y1.y; lw1[6] = y1.z; lw1[7] = y1.w; } u32 a[D / 16][4]; load_q_frags(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc); uint4 ta0[D / 32], ta1[D / 32], tb0[D / 32], tb1[D / 32]; SLOT_LOAD(0, ta0, ta1) SLOT_LOAD(1, tb0, tb1) stage_kv(sK, sV, P.K + hoff + (size_t)(c - 1) * 64 * D, P.V + hoff + (size_t)(c - 1) * 64 * D, 64, tid); __syncthreads(); const int nr0 = meta0 & 0xff, nr1 = meta1 & 0xff; float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f; #pragma unroll for (int k = 0; k < 8; k++) { if (k < nr0) m0 = fmaxf(m0, lw0[k]); if (k < nr1) m1 = fmaxf(m1, lw1[k]); } float o[D / 8][4]; #pragma unroll for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; } float sc[8][4]; u32 pa[4][4]; { // key block c-1: whole block if it was selected, else only the sliding-window tail const int lo0 = ((meta0 >> 8) & 1u) ? 0 : rl0 + 1; const int lo1 = ((meta1 >> 8) & 1u) ? 0 : rl1 + 1; const int hi0 = 63, hi1 = 63; qk_tile(sc, a, sK, g, cc); LOCAL_SOFTMAX() SLOT_FMA(0, ta0, ta1) SLOT_FMA(1, tb0, tb1) SLOT_LOAD(2, ta0, ta1) SLOT_LOAD(3, tb0, tb1) pv_tile(o, pa, sV, g, cc); SLOT_FMA(2, ta0, ta1) SLOT_FMA(3, tb0, tb1) SLOT_LOAD(4, ta0, ta1) SLOT_LOAD(5, tb0, tb1) load_q_frags(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc); __syncthreads(); stage_kv(sK, sV, P.K + hoff + (size_t)c * 64 * D, P.V + hoff + (size_t)c * 64 * D, min(64, S - c * 64), tid); __syncthreads(); SLOT_FMA(4, ta0, ta1) SLOT_FMA(5, tb0, tb1) } { // key block c: causal const int lo0 = 0, lo1 = 0, hi0 = rl0, hi1 = rl1; qk_tile(sc, a, sK, g, cc); LOCAL_SOFTMAX() SLOT_LOAD(6, ta0, ta1) SLOT_LOAD(7, tb0, tb1) pv_tile(o, pa, sV, g, cc); SLOT_FMA(6, ta0, ta1) SLOT_FMA(7, tb0, tb1) } const float i0 = 1.0f / l0, i1 = 1.0f / l1; if (v0) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t0 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0); } if (v1) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t1 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1); } } template __device__ __forceinline__ void dense_task(const AttnParams& P, u32* sK, u32* sV, int head, int c) { const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3; const int S = P.S; const float scale2 = P.scale2; const size_t hoff = (size_t)head * S * D; const int rl0 = warp * 16 + g, rl1 = rl0 + 8; const int t0 = c * 64 + rl0, t1 = c * 64 + rl1; const bool v0 = t0 < S, v1 = t1 < S; const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1); // selected-block bitmasks (every causal block is selected while there are at most 8) u32 mask0 = 0xffffffffu, mask1 = 0xffffffffu; if (c >= 8) { mask0 = P.meta[(size_t)head * S + tq0]; mask1 = P.meta[(size_t)head * S + tq1]; } u32 a[D / 16][4]; load_q_frags(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc); StageRegs R; stage_load(R, P.K + hoff, P.V + hoff, min(64, S), tid); stage_store(sK, sV, R, tid); __syncthreads(); float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f; float o[D / 8][4]; #pragma unroll for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; } for (int bi = 0; bi <= c; bi++) { // fetch the next key block into registers while this one is being used if (bi < c) { stage_load(R, P.K + hoff + (size_t)(bi + 1) * 64 * D, P.V + hoff + (size_t)(bi + 1) * 64 * D, min(64, S - (bi + 1) * 64), tid); } int lo0, lo1, hi0, hi1; if (bi == c) { lo0 = 0; lo1 = 0; hi0 = rl0; hi1 = rl1; // causal } else if (bi == c - 1) { lo0 = ((mask0 >> bi) & 1u) ? 0 : rl0 + 1; // selected, else sliding-window tail lo1 = ((mask1 >> bi) & 1u) ? 0 : rl1 + 1; hi0 = 63; hi1 = 63; } else { lo0 = ((mask0 >> bi) & 1u) ? 0 : 64; lo1 = ((mask1 >> bi) & 1u) ? 0 : 64; hi0 = 63; hi1 = 63; } if (__any_sync(0xffffffffu, (lo0 <= hi0) || (lo1 <= hi1))) { float sc[8][4]; u32 pa[4][4]; qk_tile(sc, a, sK, g, cc); LOCAL_SOFTMAX() pv_tile(o, pa, sV, g, cc); } if (bi < c) { __syncthreads(); stage_store(sK, sV, R, tid); __syncthreads(); } } const float i0 = 1.0f / l0, i1 = 1.0f / l1; if (v0) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t0 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0); } if (v1) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t1 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1); } } template __global__ void __launch_bounds__(128, 2) k_attn(const AttnParams P) { __shared__ __align__(16) u32 sKV[64 * D]; __shared__ u32 sTask[2]; u32* const sK = sKV; u32* const sV = sKV + 64 * D / 2; const int tid = threadIdx.x; volatile int* ctl = P.ctrl; const int cdn = min(P.nb, P.CD); // dense query blocks per head const int nDenseT = P.NH * cdn; // implicit dense tickets: all heads' largest block first const bool hasTable = P.nb > P.CD; if (blockIdx.x == 0) { for (int h = tid; h < P.NH; h += 128) P.ctrl[CTL_HEAD + 2 * P.NH + h] = 0; // k_prep's per-head maxima } if (blockIdx.x == 0 && hasTable) { const int need = P.NH * P.nbR + P.NH * ((P.nbR + 7) >> 3) + P.NH + 2; attn_plan(P, (need <= 64 * D) ? reinterpret_cast(sKV) : P.pos, tid); } int staged = -1; int nTab = -1; // table size, known once the planner is done (thread 0 only) u32 nw0 = TK_EXIT, nw1 = 0; // pre-claimed next ticket (thread 0 only) #define CLAIM_NEXT() \ { \ nw0 = TK_EXIT; \ const int ri_ = atomicAdd(P.ctrl + CTL_CUR, 1); \ if (ri_ < nDenseT) { \ nw0 = TK_DENSE | (u32)((ri_ % P.NH) * P.nb + (cdn - 1 - ri_ / P.NH)); \ } else if (hasTable) { \ if (nTab < 0) { \ while (ctl[CTL_READY] == 0) {} \ nTab = ctl[CTL_NTICK]; \ } \ const int ti_ = ri_ - nDenseT; \ if (ti_ < nTab) { nw0 = P.tick[2 * ti_]; nw1 = P.tick[2 * ti_ + 1]; } \ } \ } if (tid == 0) CLAIM_NEXT() for (;;) { if (tid == 0) { if (nw0 != TK_EXIT && (nw0 & TK_LOCAL)) { // far-field partials of this head must be complete const int h = (int)(nw0 & 0x3fffffffu) / P.nb; while (ctl[CTL_HEAD + 2 * h] != ctl[CTL_HEAD + 2 * h + 1]) {} } sTask[0] = nw0; sTask[1] = nw1; } __syncthreads(); const u32 w0 = sTask[0], w1 = sTask[1]; if (w0 == TK_EXIT) break; // claim the next ticket now; it arrives while this task computes if (tid == 0) CLAIM_NEXT() if (w0 & TK_DENSE) { const int li = (int)(w0 & 0x3fffffffu); dense_task(P, sK, sV, li / P.nb, li % P.nb); staged = -1; } else if (w0 & TK_LOCAL) { local_task(P, sK, sV, w0); staged = -1; } else { remote_task(P, sK, sV, w0, w1, staged != (int)w0); staged = (int)w0; } __syncthreads(); } #undef CLAIM_NEXT } // --------------------------------------------------------------------------------- // k_dense8: sequences short enough to be all-dense (nb <= CD). 8-warp workers, each owning // two consecutive query blocks (128 queries), so every staged K/V block serves twice as many // queries -- this path is bound by L2 bytes for key/value staging, not by the tensor cores. // --------------------------------------------------------------------------------- template __global__ void __launch_bounds__(256, 1) k_dense8(const AttnParams P) { __shared__ __align__(16) u32 sKV[64 * D]; __shared__ int sTask; u32* const sK = sKV; u32* const sV = sKV + 64 * D / 2; const int tid = threadIdx.x, lane = tid & 31, warp = tid >> 5, g = lane >> 2, cc = lane & 3; const int S = P.S; const float scale2 = P.scale2; const int npair = (P.nb + 1) >> 1; // query-block pairs per head const int nT = P.NH * npair; if (blockIdx.x == 0) { for (int h = tid; h < P.NH; h += 256) P.ctrl[CTL_HEAD + 2 * P.NH + h] = 0; // k_prep's per-head maxima } for (;;) { if (tid == 0) sTask = atomicAdd(P.ctrl + CTL_CUR, 1); __syncthreads(); const int r = sTask; if (r >= nT) break; const int head = r % P.NH; const int c0 = 2 * (npair - 1 - r / P.NH); // longest chains first const int cq = c0 + (warp >> 2); // this warp's query block const bool blk_ok = cq < P.nb; const int cmax = min(c0 + 1, P.nb - 1); const size_t hoff = (size_t)head * S * D; const int rl0 = (warp & 3) * 16 + g, rl1 = rl0 + 8; const int t0 = cq * 64 + rl0, t1 = cq * 64 + rl1; const bool v0 = blk_ok && t0 < S, v1 = blk_ok && t1 < S; const int tq0 = min(t0, S - 1), tq1 = min(t1, S - 1); // selected-block bitmasks (every causal block is selected while there are at most 8) u32 mask0 = 0xffffffffu, mask1 = 0xffffffffu; if (cq >= 8) { mask0 = P.meta[(size_t)head * S + tq0]; mask1 = P.meta[(size_t)head * S + tq1]; } u32 a[D / 16][4]; load_q_frags(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc); StageRegs R; stage_load(R, P.K + hoff, P.V + hoff, min(64, S), tid); stage_store(sK, sV, R, tid); __syncthreads(); float m0 = NEG_BIG, m1 = NEG_BIG, l0 = 0.f, l1 = 0.f; float o[D / 8][4]; #pragma unroll for (int jd = 0; jd < D / 8; jd++) { o[jd][0] = 0.f; o[jd][1] = 0.f; o[jd][2] = 0.f; o[jd][3] = 0.f; } for (int bi = 0; bi <= cmax; bi++) { // fetch the next key block into registers while this one is being used if (bi < cmax) { stage_load(R, P.K + hoff + (size_t)(bi + 1) * 64 * D, P.V + hoff + (size_t)(bi + 1) * 64 * D, min(64, S - (bi + 1) * 64), tid); } int lo0, lo1, hi0, hi1; if (!blk_ok || bi > cq) { lo0 = 64; lo1 = 64; hi0 = 63; hi1 = 63; // not causal for this warp's block } else if (bi == cq) { lo0 = 0; lo1 = 0; hi0 = rl0; hi1 = rl1; // causal } else if (bi == cq - 1) { lo0 = ((mask0 >> bi) & 1u) ? 0 : rl0 + 1; // selected, else sliding-window tail lo1 = ((mask1 >> bi) & 1u) ? 0 : rl1 + 1; hi0 = 63; hi1 = 63; } else { lo0 = ((mask0 >> bi) & 1u) ? 0 : 64; lo1 = ((mask1 >> bi) & 1u) ? 0 : 64; hi0 = 63; hi1 = 63; } if (__any_sync(0xffffffffu, (lo0 <= hi0) || (lo1 <= hi1))) { float sc[8][4]; u32 pa[4][4]; qk_tile(sc, a, sK, g, cc); LOCAL_SOFTMAX() pv_tile(o, pa, sV, g, cc); } if (bi < cmax) { __syncthreads(); stage_store(sK, sV, R, tid); __syncthreads(); } } const float i0 = 1.0f / l0, i1 = 1.0f / l1; if (v0) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t0 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][0] * i0, o[jd][1] * i0); } if (v1) { u32* dst = reinterpret_cast(P.out + hoff + (size_t)t1 * D) + cc; #pragma unroll for (int jd = 0; jd < D / 8; jd++) dst[4 * jd] = pack_bf16(o[jd][2] * i1, o[jd][3] * i1); } __syncthreads(); } } // --------------------------------------------------------------------------------- // host launchers (prep + select first, so the output tensor can be allocated meanwhile) // --------------------------------------------------------------------------------- #include static int g_prof = 0; static double g_acc[4] = {0, 0, 0, 0}; static int g_n = 0; static cudaEvent_t g_ev[4]; static int g_ev_init = 0; void nsa_set_prof(int p) { if (p == 2) { printf("prof (us): prep %.1f select %.1f attn %.1f (n=%d)\n", g_acc[0] / g_n, g_acc[1] / g_n, g_acc[2] / g_n, g_n); fflush(stdout); return; } g_prof = p; g_n = 0; for (int i = 0; i < 4; i++) g_acc[i] = 0; } #define PROF_MARK(i) if (g_prof) { cudaEventRecord(g_ev[i], st); } #ifndef NSA_USE_DENSE8 #define NSA_USE_DENSE8 1 #endif struct NsaDims { int nb, nbf, nbR, listCap; }; static NsaDims nsa_dims(int S, int CD) { NsaDims d; d.nb = (S + 63) / 64; d.nbf = S / 64; d.nbR = d.nb > CD ? d.nb - 2 : 0; d.listCap = 0; for (int bi = 0; bi < d.nbR; bi++) { const int cmin = bi + 2 > CD ? bi + 2 : CD; d.listCap += S - 64 * cmin > 0 ? S - 64 * cmin : 0; } return d; } template static void launch_pre(const u16* Q, const u16* K, const u16* V, float* ps8, u32* kb_hi, u32* kb_lo, int* cnt, u32* lists, const int* loff, u32* meta, int* ctrl, int NH, int S, int CD, cudaStream_t st) { const NsaDims d = nsa_dims(S, CD); if (g_prof) { if (!g_ev_init) { for (int i = 0; i < 4; i++) cudaEventCreate(&g_ev[i]); g_ev_init = 1; } cudaStreamSynchronize(st); } PROF_MARK(0) { // zero: ctrl[0 .. 16+2*NH) (cursor, flags, per-head counters), cnt[0 .. NH*nbR) (pair counters) const int nZc = 16 + 2 * NH, nZn = NH * d.nbR; int total = NH * d.nb * D; if (total < nZc) total = nZc; if (total < nZn) total = nZn; k_prep<<<(total + 127) / 128, 128, 0, st>>>(K, ps8, kb_hi, kb_lo, cnt, nZn, ctrl, nZc, NH, S, D, d.nb, d.nbf); } PROF_MARK(1) if (d.nb > 8) { const int nSel = d.nb - 8; const int NCAP = (d.nb + 7) & ~7; const int scoreWords = 64 * NCAP > 32 * D ? 64 * NCAP : 32 * D; // also holds one staged key block const size_t smemSel = (size_t)scoreWords * 4 + (size_t)64 * (NCAP / 8) * 4 + (size_t)2 * SEL_CHB * D * 2 + 64 * 4; static int attrSet = 0; if (!attrSet) { cudaFuncSetAttribute(k_select, cudaFuncAttributeMaxDynamicSharedMemorySize, 96 * 1024); attrSet = 1; } k_select<<>>(Q, K, V, (const u16*)kb_hi, (const u16*)kb_lo, ps8, cnt, lists, loff, meta, ctrl, S, d.nb, d.nbf, nSel, d.listCap, d.nbR, NCAP, scoreWords, CD, 16 + 2 * NH); } PROF_MARK(2) } template static void launch_attn(const u16* Q, const u16* K, const u16* V, u16* out, int* cnt, u32* tick, u32* lists, const int* loff, u32* meta, u32* part_o, float* part_lw, int* ctrl, int NH, int S, int CD, int nWorkers, cudaStream_t st) { const NsaDims d = nsa_dims(S, CD); AttnParams P; P.Q = Q; P.K = K; P.V = V; P.out = out; P.lists = lists; P.loff = loff; P.cnt = cnt; P.pos = cnt + NH * d.nbR; P.tick = tick; P.ctrl = ctrl; P.meta = meta; P.part_o = part_o; P.part_lw = part_lw; P.S = S; P.NH = NH; P.nb = d.nb; P.nbR = d.nbR; P.listCap = d.listCap; P.CD = CD; P.scale2 = 1.4426950408889634f / sqrtf((float)D); if (d.nb <= CD && NSA_USE_DENSE8) { // all-dense: one 8-warp worker per SM, tickets = (head, pair of query blocks) const int nT = NH * ((d.nb + 1) / 2); int grid = nWorkers / 2 > 0 ? nWorkers / 2 : 1; if (grid > nT) grid = nT; k_dense8<<>>(P); } else { k_attn<<>>(P); } PROF_MARK(3) if (g_prof) { cudaStreamSynchronize(st); for (int i = 0; i < 3; i++) { float ms = 0; cudaEventElapsedTime(&ms, g_ev[i], g_ev[i + 1]); g_acc[i] += ms * 1000.0; } g_n++; } } void nsa_launch_pre(const void* Q, const void* K, const void* V, void* ps8, void* kb_hi, void* kb_lo, void* cnt, void* lists, const void* loff, void* meta, void* ctrl, int NH, int S, int D, int CD, void* stream) { cudaStream_t st = (cudaStream_t)stream; if (D == 64) { launch_pre<64>((const u16*)Q, (const u16*)K, (const u16*)V, (float*)ps8, (u32*)kb_hi, (u32*)kb_lo, (int*)cnt, (u32*)lists, (const int*)loff, (u32*)meta, (int*)ctrl, NH, S, CD, st); } else { launch_pre<128>((const u16*)Q, (const u16*)K, (const u16*)V, (float*)ps8, (u32*)kb_hi, (u32*)kb_lo, (int*)cnt, (u32*)lists, (const int*)loff, (u32*)meta, (int*)ctrl, NH, S, CD, st); } } void nsa_launch_attn(const void* Q, const void* K, const void* V, void* out, void* cnt, void* tick, void* lists, const void* loff, void* meta, void* part_o, void* part_lw, void* ctrl, int NH, int S, int D, int CD, int nWorkers, void* stream) { cudaStream_t st = (cudaStream_t)stream; if (D == 64) { launch_attn<64>((const u16*)Q, (const u16*)K, (const u16*)V, (u16*)out, (int*)cnt, (u32*)tick, (u32*)lists, (const int*)loff, (u32*)meta, (u32*)part_o, (float*)part_lw, (int*)ctrl, NH, S, CD, nWorkers, st); } else { launch_attn<128>((const u16*)Q, (const u16*)K, (const u16*)V, (u16*)out, (int*)cnt, (u32*)tick, (u32*)lists, (const int*)loff, (u32*)meta, (u32*)part_o, (float*)part_lw, (int*)ctrl, NH, S, CD, nWorkers, st); } } """ _CPP_SRC = r""" #include #include void nsa_launch_pre(const void* Q, const void* K, const void* V, void* ps8, void* kb_hi, void* kb_lo, void* cnt, void* lists, const void* loff, void* meta, void* ctrl, int NH, int S, int D, int CD, void* stream); void nsa_launch_attn(const void* Q, const void* K, const void* V, void* out, void* cnt, void* tick, void* lists, const void* loff, void* meta, void* part_o, void* part_lw, void* ctrl, int NH, int S, int D, int CD, int nWorkers, void* stream); void nsa_set_prof(int p); void set_prof(int64_t p) { nsa_set_prof((int)p); } torch::Tensor nsa_forward(torch::Tensor q, torch::Tensor k, torch::Tensor v, torch::Tensor ps8, torch::Tensor kb_hi, torch::Tensor kb_lo, torch::Tensor cnt, torch::Tensor tick, torch::Tensor lists, torch::Tensor loff, torch::Tensor meta, torch::Tensor part_o, torch::Tensor part_lw, torch::Tensor ctrl, int64_t cDense, int64_t nWorkers) { const int NH = (int)(q.size(0) * q.size(1)), S = (int)q.size(2), D = (int)q.size(3); void* stream = (void*)c10::cuda::getCurrentCUDAStream(q.get_device()).stream(); // block sums + selection do not need the output buffer: get them going before allocating it nsa_launch_pre(q.data_ptr(), k.data_ptr(), v.data_ptr(), ps8.data_ptr(), kb_hi.data_ptr(), kb_lo.data_ptr(), cnt.data_ptr(), lists.data_ptr(), loff.data_ptr(), meta.data_ptr(), ctrl.data_ptr(), NH, S, D, (int)cDense, stream); torch::Tensor out = torch::empty_like(q); nsa_launch_attn(q.data_ptr(), k.data_ptr(), v.data_ptr(), out.data_ptr(), cnt.data_ptr(), tick.data_ptr(), lists.data_ptr(), loff.data_ptr(), meta.data_ptr(), part_o.data_ptr(), part_lw.data_ptr(), ctrl.data_ptr(), NH, S, D, (int)cDense, (int)nWorkers, stream); return out; } """ _EXT = None _EXT_NAME = "nsa_sm120_ext_dd96601b4e" def _get_ext(): global _EXT if _EXT is None: _EXT = load_inline( name=_EXT_NAME, cpp_sources=[_CPP_SRC], cuda_sources=[_CUDA_SRC], functions=["nsa_forward", "set_prof"], with_cuda=True, extra_cuda_cflags=["-O3", "-arch=sm_120"], verbose=False, ) return _EXT C_DENSE = 0 # query blocks below this index use the dense (partial-free) path (8..32); 0 = auto N_WORKERS = 0 # 0 = auto: two resident 4-warp workers per SM class _Plan: """Scratch buffers for one (device, B, H, S, D).""" def __init__(self, device, B, H, S, D, c_dense, n_workers): NH = B * H nb = (S + 63) // 64 nbf = S // 64 self.c_dense = c_dense self.n_workers = n_workers nbR = nb - 2 if nb > c_dense else 0 offs = [0] for bi in range(nbR): offs.append(offs[-1] + max(S - 64 * max(bi + 2, c_dense), 0)) list_cap = offs[-1] i32 = torch.int32 self.ps8 = torch.zeros(NH * nb * 8 * D, dtype=torch.float32, device=device) self.kb_hi = torch.zeros(NH * max(nbf, 1) * D // 2, dtype=i32, device=device) self.kb_lo = torch.zeros(NH * max(nbf, 1) * D // 2, dtype=i32, device=device) self.cnt = torch.zeros(2 * NH * nbR + NH * ((nbR + 7) // 8) + NH + 16, dtype=i32, device=device) self.tick = torch.zeros(2 * (NH * S * 8 // 128 + 2 * NH * nb + 64), dtype=i32, device=device) self.lists = torch.zeros(NH * list_cap + 64, dtype=i32, device=device) self.loff = torch.tensor(offs, dtype=i32, device=device) self.meta = torch.zeros(NH * S, dtype=i32, device=device) n_part = NH * S * 8 if nbR > 0 else 8 self.part_o = torch.zeros(n_part * (D // 2), dtype=i32, device=device) self.part_lw = torch.zeros(n_part, dtype=torch.float32, device=device) self.ctrl = torch.zeros(64 + 3 * NH, dtype=i32, device=device) def _torch_fallback(q, k, v): """Bench semantics with plain torch ops, for inputs the CUDA path does not cover (non-CUDA device, non-bf16 dtype, D not in {64, 128}, very long sequences).""" B, H, S, D = q.shape dev = q.device qd, kd, vd = q.double(), k.double(), v.double() scale = 1.0 / math.sqrt(D) nb = (S + BLOCK_SIZE - 1) // BLOCK_SIZE pad = nb * BLOCK_SIZE - S idx = torch.arange(S, device=dev) out = torch.empty(B, H, S, D, dtype=torch.float64, device=dev) rows = max(1, min(S, (1 << 24) // max(S, 1))) for b in range(B): for h in range(H): for r0 in range(0, S, rows): t = idx[r0:r0 + rows] n = t.numel() sc = (qd[b, h, r0:r0 + rows] @ kd[b, h].T) * scale causal = idx[None, :] <= t[:, None] scm = torch.where(causal, sc, torch.zeros((), dtype=sc.dtype, device=dev)) cnt = torch.nn.functional.pad(causal.to(sc.dtype), (0, pad)).view(n, nb, BLOCK_SIZE).sum(-1) imp = torch.nn.functional.pad(scm, (0, pad)).view(n, nb, BLOCK_SIZE).sum(-1) / cnt.clamp_min(1) # ties go to the higher block index (reference sorts (score, index) descending) order = torch.argsort(imp.flip(1), dim=1, descending=True, stable=True) order = (nb - 1 - order) valid = torch.gather(cnt > 0, 1, order) order_valid_first = torch.argsort((~valid).to(torch.int8), dim=1, stable=True) order = torch.gather(order, 1, order_valid_first)[:, :TOP_N_BLOCKS] selb = torch.zeros(n, nb, dtype=torch.bool, device=dev) selb.scatter_(1, order, True) selb &= cnt > 0 selk = selb[:, :, None].expand(n, nb, BLOCK_SIZE).reshape(n, nb * BLOCK_SIZE)[:, :S] win = idx[None, :] > t[:, None] - SLIDING_WINDOW mask = (selk | win) & causal att = torch.softmax(sc.masked_fill(~mask, float("-inf")), dim=-1) out[b, h, r0:r0 + rows] = att @ vd[b, h] return out.to(torch.bfloat16) _S_MAX = 16384 # limits of the packed work-list / ticket encodings and of the selection smem class Model(nn.Module): def __init__(self, B: int, H: int, S: int, D: int): super().__init__() self.B, self.H, self.S, self.D = B, H, S, D self.register_buffer("_dummy", torch.zeros(1, dtype=torch.bfloat16)) self._plans = {} self._fwd = _get_ext().nsa_forward def forward(self, q: torch.Tensor, k: torch.Tensor, v: torch.Tensor) -> torch.Tensor: bf = torch.bfloat16 if not (q.is_cuda and q.dim() == 4 and q.dtype == bf and k.dtype == bf and v.dtype == bf and k.shape == q.shape and v.shape == q.shape and k.device == q.device and v.device == q.device and q.shape[3] in (64, 128) and 1 <= q.shape[2] <= _S_MAX and q.shape[0] * q.shape[1] > 0): return _torch_fallback(q, k, v) if not (q.is_contiguous() and k.is_contiguous() and v.is_contiguous()): q, k, v = q.contiguous(), k.contiguous(), v.contiguous() key = (q.device, q.shape) plan = self._plans.get(key) if plan is None: B, H, S, D = q.shape # up to 32 blocks everything is dense (8-warp kernel, selection bitmask fits 32 bits); # longer sequences keep only the first 8 blocks dense and pool the sparse far field cd = C_DENSE if C_DENSE else (32 if S <= 2048 else 8) nw = N_WORKERS if N_WORKERS else 2 * torch.cuda.get_device_properties(q.device).multi_processor_count plan = _Plan(q.device, B, H, S, D, cd, nw) self._plans[key] = plan return self._fwd(q, k, v, plan.ps8, plan.kb_hi, plan.kb_lo, plan.cnt, plan.tick, plan.lists, plan.loff, plan.meta, plan.part_o, plan.part_lw, plan.ctrl, plan.c_dense, plan.n_workers)