KernelBench cuda · RTX PRO 6000
DeepSeek NSA Claude Fable 5.2
manually audited: clean
Fable 5.2 wrote three launches per forward in raw CUDA with inline-PTX bf16 mma. k_prep builds compensated 8-key prefix sums of K with a hi + lo bf16 split for tensor-core block scoring; k_select picks top-9 by tournament and re-evaluates every candidate near the 8th/9th boundary in error-free fp32, so the selected set equals the exact top-8 with the reference's tie rule. Long sequences use persistent workers with an in-kernel ticket scheduler (dense, remote far-field pooled per key block, local window plus LSE merge); S <= 2048 uses a fully dense masked kernel driven by the selection bitmask.
Per-shape latencymilliseconds are the measured result; the dense-equivalent roofline is not a useful ceiling
geomean(0.080 ms · 0.138 ms · 0.148 ms · 0.260 ms · 0.054 ms · 0.109 ms) = 0.117 ms
Kernel source (redacted)
"""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 <cuda_runtime.h>
#include <cstdint>
#include <cstddef>
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<const uint4*>(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<float4*>(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<uint4*>(kb_hi + o) = h;
*reinterpret_cast<uint4*>(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 <int D>
__device__ __forceinline__ void load_q_frags(u32 (*a)[4], const u16* row0, const u16* row1, int cc) {
const uint4* q0 = reinterpret_cast<const uint4*>(row0) + cc * (D / 32);
const uint4* q1 = reinterpret_cast<const uint4*>(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 <int D, int NT = 128>
struct StageRegs {
uint4 k[8 * D / NT];
uint4 v0[4 * D / NT], v1[4 * D / NT];
};
template <int D, int NT = 128>
__device__ __forceinline__ void stage_load(StageRegs<D, NT>& R, const u16* Kb, const u16* Vb, int nkeys, int tid) {
const uint4* k4 = reinterpret_cast<const uint4*>(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<const uint4*>(Vb + (size_t)ka * D);
const uint4* v1 = reinterpret_cast<const uint4*>(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 <int D, int NT = 128>
__device__ __forceinline__ void stage_store(u32* sK, u32* sV, const StageRegs<D, NT>& R, int tid) {
uint4* s4 = reinterpret_cast<uint4*>(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 <int D>
__device__ __forceinline__ void stage_kv(u32* sK, u32* sV, const u16* Kb, const u16* Vb, int nkeys, int tid) {
StageRegs<D> R;
stage_load<D>(R, Kb, Vb, nkeys, tid);
stage_store<D>(sK, sV, R, tid);
}
// scores[j][0..3] for key tiles j=0..7 (keys 8j+2cc+{0,1}; rows g, g+8)
template <int D>
__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<const uint2*>(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 <int D, int S0 = 0, int S1 = 4>
__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<const uint2*>(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 <int D>
__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 <int D>
__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 <int D>
__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<D>(s, cc, qv, reinterpret_cast<const float4*>(ps8h + ((size_t)id * 8 + 7) * D));
} else {
const int sfull = (i + 1) >> 3;
if (sfull > 0) dot_qf<D>(s, cc, qv, reinterpret_cast<const float4*>(ps8h + ((size_t)c * 8 + sfull - 1) * D));
for (int j = sfull * 8; j <= i; j++) dot_qk<D>(s, cc, qv, reinterpret_cast<const uint4*>(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<const float4*>(rs + 8 * bg);
const float4 y = *reinterpret_cast<const float4*>(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 <int D>
__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<const uint4*>(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<D>(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<D>(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 <int D>
__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<u32*>(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<D>(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<const volatile u32*>(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<const uint4*>((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<const uint4*>(Kc);
uint4* s4 = reinterpret_cast<uint4*>(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<D>(sc, a, reinterpret_cast<const u32*>(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<uint4*>(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<const uint4*>((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<const uint2*>(bh + x * 8 * (D / 2) + 2 * sx);
const uint2 vl = *reinterpret_cast<const uint2*>(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<float2*>(sS + rl0 * NCAP + i0) = make_float2(chh[x][0] + cll[x][0], chh[x][1] + cll[x][1]);
*reinterpret_cast<float2*>(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<const float4*>(rs + 8 * g2);
const float4 y = *reinterpret_cast<const float4*>(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<const float4*>(rs + 8 * bg);
const float4 y = *reinterpret_cast<const float4*>(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<const float4*>(rs + 8 * g2);
const float4 y = *reinterpret_cast<const float4*>(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<const uint4*>(qrow)[u];
for (int id = 0; id <= c; id++) {
if (rs[id] <= 0.5f * NEGV) continue;
const double ex = exact_imp<D>(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<D>(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<const float4*>(rsL + 8 * lane);
const float4 y = *reinterpret_cast<const float4*>(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<D>(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<const u32*>(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<const u32*>(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<const uint4*>(P.part_o + (q0 + (K_)) * (D / 2) + cc * (D / 8)); \
const uint4* s1_ = reinterpret_cast<const uint4*>(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 <int D>
__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<D>(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<D>(a, Qh + (size_t)t0 * D, Qh + (size_t)t1 * D, cc);
for (int eb = eb0;; eb += 64) {
float sc[8][4];
qk_tile<D>(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<D>(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<D>(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<uint4*>(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<uint4*>(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 <int D>
__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<const float4*>(P.part_lw + q0);
const float4* p1 = reinterpret_cast<const float4*>(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<D>(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<D>(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<D>(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<D>(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<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
__syncthreads();
stage_kv<D>(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<D>(sc, a, sK, g, cc);
LOCAL_SOFTMAX()
SLOT_LOAD(6, ta0, ta1)
SLOT_LOAD(7, tb0, tb1)
pv_tile<D>(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<u32*>(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<u32*>(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 <int D>
__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<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
StageRegs<D> R;
stage_load<D>(R, P.K + hoff, P.V + hoff, min(64, S), tid);
stage_store<D>(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<D>(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<D>(sc, a, sK, g, cc);
LOCAL_SOFTMAX()
pv_tile<D>(o, pa, sV, g, cc);
}
if (bi < c) {
__syncthreads();
stage_store<D>(sK, sV, R, tid);
__syncthreads();
}
}
const float i0 = 1.0f / l0, i1 = 1.0f / l1;
if (v0) {
u32* dst = reinterpret_cast<u32*>(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<u32*>(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 <int D>
__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<int*>(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<D>(P, sK, sV, li / P.nb, li % P.nb);
staged = -1;
} else if (w0 & TK_LOCAL) {
local_task<D>(P, sK, sV, w0);
staged = -1;
} else {
remote_task<D>(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 <int D>
__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<D>(a, P.Q + hoff + (size_t)tq0 * D, P.Q + hoff + (size_t)tq1 * D, cc);
StageRegs<D, 256> R;
stage_load<D, 256>(R, P.K + hoff, P.V + hoff, min(64, S), tid);
stage_store<D, 256>(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<D, 256>(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<D>(sc, a, sK, g, cc);
LOCAL_SOFTMAX()
pv_tile<D>(o, pa, sV, g, cc);
}
if (bi < cmax) {
__syncthreads();
stage_store<D, 256>(sK, sV, R, tid);
__syncthreads();
}
}
const float i0 = 1.0f / l0, i1 = 1.0f / l1;
if (v0) {
u32* dst = reinterpret_cast<u32*>(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<u32*>(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 <cstdio>
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 <int D>
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<D>, cudaFuncAttributeMaxDynamicSharedMemorySize, 96 * 1024);
attrSet = 1;
}
k_select<D><<<NH * nSel, 128, smemSel, st>>>(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 <int D>
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<D><<<grid, 256, 0, st>>>(P);
} else {
k_attn<D><<<nWorkers, 128, 0, st>>>(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 <torch/extension.h>
#include <c10/cuda/CUDAStream.h>
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)
20261109_143748_claude_claude-fable-5-2_02_deepseek_nsa