summaryrefslogtreecommitdiff
path: root/volta_kernels/attn.cu
diff options
context:
space:
mode:
Diffstat (limited to 'volta_kernels/attn.cu')
-rw-r--r--volta_kernels/attn.cu761
1 files changed, 761 insertions, 0 deletions
diff --git a/volta_kernels/attn.cu b/volta_kernels/attn.cu
new file mode 100644
index 0000000..1725723
--- /dev/null
+++ b/volta_kernels/attn.cu
@@ -0,0 +1,761 @@
+// swarm/integ_attn: merged attention kernel = live attn.cu +
+// attn_softmax padded smem (row stride 84 halves), fwd software pipelining (double-buffered K,
+// next QK^T overlapping softmax), unrolled full-tile dQ atomic loop;
+// bwd ILP kept as a knob, default off (see BWD_ILP) (polynomial exp NOT included)
+// attn_long 1-D grid, heads interleaved in the global longest-first launch order
+// attn_bwd mode 6: next query tile's Q, dO, lse, D prefetched into registers (BWD_PF)
+// o, lse, dk, dv bitwise identical to the live kernel; dq differs only by fp32 atomic order.
+// Varlen causal FlashAttention for sm_70 (V100), head_dim 64, fp16 in/out.
+//
+// Why this exists: PyTorch's only SDPA backend that trains on sm_70 is the
+// CUTLASS memory-efficient kernel, whose backward measured ~4x its own forward
+// on Boris-2's shapes (FlashAttention-2 does ~2.5x). Triton cannot help here:
+// on sm_70 tl.dot lowers to plain FMA (no tensor cores), so this is CUDA with
+// raw mma.sync.m8n8k4 -- the same HMMA.884 instruction CUTLASS's sm70 path uses.
+//
+// Precision is the memory-efficient kernel's precision class, deliberately:
+// * every GEMM takes fp16 operands and accumulates in fp32
+// * softmax statistics (max, sum, logsumexp) are fp32
+// * P and dS are rounded to fp16 only as GEMM operands, as in any fp16 kernel
+// * dQ is accumulated in an fp32 buffer across key tiles and rounded once
+//
+// Fragment layouts of m8n8k4 (verified empirically on this card, see
+// volta_kernels/README.md). j = lane%4, hi = lane>=16, quad-pair qp = (lane>>2)&3:
+// A.row : row = j + 4hi, k = 0..3 A.col : k = j, row = 4hi + 0..3
+// B.col : n = j + 4hi, k = 0..3 B.row : k = j, n = 4hi + 0..3
+// D f32 : row = (lane&1) + (i&2) + 4hi, col = (i&4) + (lane&2) + (i&1)
+// Each quad-pair computes its own 8x8 tile; the four are arranged 2x2 into a
+// 16x16 warp tile: m offset 8*(qp&1), n offset 8*(qp>>1).
+#include <torch/extension.h>
+#include <ATen/cuda/CUDAContext.h>
+#include <cuda_fp16.h>
+#include <stdint.h>
+
+namespace {
+
+constexpr int HD = 64; // head dim
+constexpr int TL = 64; // tile edge (queries or keys)
+constexpr int NT = 128; // 4 warps, 16 tile rows each
+
+// 64x64 fp16 tiles live unpadded in shared memory with the 8-byte segments of
+// each row XOR-swizzled. The mapping makes every fragment access pattern used
+// below (A.row, B.col: 8 rows x one segment; B.row, A.col: 4 rows x two
+// segments) hit distinct banks within each half-warp.
+__device__ __forceinline__ int swz(int r) { return ((r & 3) << 2) | ((r >> 2) & 3); }
+__device__ __forceinline__ int so(int r, int c) {
+ return r * 64 + ((((c >> 2) ^ swz(r))) << 2) + (c & 3);
+}
+
+// Compile-time knobs (defaults = the adopted combination).
+// BWD_ILP (attn_softmax) and BWD_PF (attn_bwd mode 6) combine without spills (255 regs, 2 CTAs/SM),
+// but with the prefetch on, ILP adds nothing measurable (bwd vs live: PF only 0.944/0.945 at
+// 16x2048, 0.900 at 4x8192; PF+ILP 0.946/0.947 and 0.897). PF alone wins at stage 1 and leaves
+// 17 registers of headroom (238), so ILP is off by default; set -DBWD_ILP=1 to re-test.
+#ifndef BWD_ILP
+#define BWD_ILP 0 // bwd: S^T MMAs first, then exp(S^T) and the dP^T MMAs in one basic block
+#endif
+#ifndef BWD_PF
+#define BWD_PF 1 // bwd: next query tile's Q/dO/lse/D prefetched into registers
+#endif
+
+// Padded layout: row stride 84 halves = 42 words. Every fragment pattern used
+// here (8 rows {0..3,8..11} x 8B; 4 rows x 2 segments 16B apart; P's 32-bit
+// stores; commit's 2 rows x 8 segments) hits distinct banks per half-warp, and
+// all per-ks / per-nb offsets become compile-time immediates.
+constexpr int LDP = 84;
+template <bool P> __device__ __forceinline__ int lo(int r, int c) {
+ if constexpr (P) return r * LDP + c; else return so(r, c);
+}
+
+__device__ __forceinline__ uint2 lds2(const half* t, int off) {
+ return *reinterpret_cast<const uint2*>(t + off);
+}
+
+#define DEF_MMA(LA, LB) \
+ __device__ __forceinline__ void mma_##LA##_##LB(float* d, uint2 a, uint2 b) { \
+ asm("mma.sync.aligned.m8n8k4." #LA "." #LB ".f32.f16.f16.f32 " \
+ "{%0,%1,%2,%3,%4,%5,%6,%7}, {%8,%9}, {%10,%11}, {%0,%1,%2,%3,%4,%5,%6,%7};" \
+ : "+f"(d[0]), "+f"(d[1]), "+f"(d[2]), "+f"(d[3]), \
+ "+f"(d[4]), "+f"(d[5]), "+f"(d[6]), "+f"(d[7]) \
+ : "r"(a.x), "r"(a.y), "r"(b.x), "r"(b.y)); \
+ }
+DEF_MMA(row, col)
+DEF_MMA(row, row)
+DEF_MMA(col, row)
+
+__device__ __forceinline__ float ex2(float x) {
+ float y;
+ asm("ex2.approx.ftz.f32 %0, %1;" : "=f"(y) : "f"(x));
+ return y;
+}
+
+__device__ __forceinline__ unsigned pack_h2(float a, float b) {
+ __half2 h = __floats2half2_rn(a, b);
+ return *reinterpret_cast<unsigned*>(&h);
+}
+
+// Copy rows [row0, row0+64) of one head (64 contiguous halves at token stride
+// `ts`) into a swizzled tile. Rows at or past `nrows` are zero-filled.
+template <bool PD = false>
+__device__ __forceinline__ void load_tile(half* t, const half* g, int ts, int row0,
+ int nrows, int tid) {
+#pragma unroll
+ for (int it = 0; it < (TL * 8) / NT; ++it) {
+ int idx = tid + it * NT;
+ int r = idx >> 3, c = (idx & 7) * 8;
+ uint4 v = make_uint4(0, 0, 0, 0);
+ if (row0 + r < nrows)
+ v = *reinterpret_cast<const uint4*>(g + (long)(row0 + r) * ts + c);
+ *reinterpret_cast<uint2*>(t + lo<PD>(r, c)) = make_uint2(v.x, v.y);
+ *reinterpret_cast<uint2*>(t + lo<PD>(r, c + 4)) = make_uint2(v.z, v.w);
+ }
+}
+
+// Register-staged copy of one 64x64 tile: global loads issued early, the
+// swizzled shared-memory stores later, so the load latency overlaps compute.
+struct TileRegs { uint4 v[(TL * 8) / NT]; };
+__device__ __forceinline__ void fetch_tile(TileRegs& R, const half* g, int ts, int row0, int nrows, int tid) {
+#pragma unroll
+ for (int it = 0; it < (TL * 8) / NT; ++it) {
+ int idx = tid + it * NT, r = idx >> 3, c = (idx & 7) * 8;
+ R.v[it] = (row0 + r < nrows) ? *reinterpret_cast<const uint4*>(g + (long)(row0 + r) * ts + c)
+ : make_uint4(0, 0, 0, 0);
+ }
+}
+template <bool PD = false>
+__device__ __forceinline__ void commit_tile(half* t, const TileRegs& R, int tid) {
+#pragma unroll
+ for (int it = 0; it < (TL * 8) / NT; ++it) {
+ int idx = tid + it * NT, r = idx >> 3, c = (idx & 7) * 8;
+ *reinterpret_cast<uint2*>(t + lo<PD>(r, c)) = make_uint2(R.v[it].x, R.v[it].y);
+ *reinterpret_cast<uint2*>(t + lo<PD>(r, c + 4)) = make_uint2(R.v[it].z, R.v[it].w);
+ }
+}
+
+// Map a flat block index onto (document, tile). tcum[d] is the number of tiles
+// in documents before d; tcum[ndocs] the total.
+__device__ __forceinline__ bool find_tile(const int* tcum, const int* perm, int ndocs, int b,
+ int& doc, int& local, int& ntiles) {
+ if (b >= tcum[ndocs]) return false;
+ int lo = 0, hi = ndocs - 1;
+ while (lo < hi) {
+ int mid = (lo + hi + 1) >> 1;
+ if (tcum[mid] <= b) lo = mid; else hi = mid - 1;
+ }
+ doc = perm[lo]; // tcum is over documents sorted longest-first
+ local = b - tcum[lo];
+ ntiles = tcum[lo + 1] - tcum[lo];
+ return true;
+}
+
+// --------------------------------------------------------------------------
+// Forward. One CTA = one 64-query tile of one document, one head.
+// --------------------------------------------------------------------------
+__global__ void __launch_bounds__(NT) fwd_kernel(
+ const half* __restrict__ Q, const half* __restrict__ K, const half* __restrict__ V,
+ half* __restrict__ O, float* __restrict__ LSE, const int* __restrict__ cu,
+ const int* __restrict__ tcum, const int* __restrict__ perm, int ndocs, int N, int H,
+ int sq, int sk, int sv, int s_o, float scale_log2) {
+ // Padded tiles (row stride LDP); K double-buffered for the software pipeline.
+ __shared__ __align__(16) half Ks2[2][TL * LDP];
+ __shared__ __align__(16) half Vs[TL * LDP];
+ __shared__ __align__(16) half Ps[4][16 * LDP];
+
+ // 1-D grid, heads interleaved: the longest-first order holds across heads.
+ const int h = blockIdx.x % H;
+ int doc, local, ntiles;
+ if (!find_tile(tcum, perm, ndocs, blockIdx.x / H, doc, local, ntiles)) return;
+ const int t = ntiles - 1 - local; // longest-running tiles launch first
+ const int s0 = cu[doc], L = cu[doc + 1] - s0;
+
+ const int tid = threadIdx.x, w = tid >> 5, lane = tid & 31;
+ const int j = lane & 3, hi = lane >> 4, qp = (lane >> 2) & 3;
+ const int mo = 8 * (qp & 1), no = 8 * (qp >> 1);
+
+ uint2 qf[16];
+ {
+ int qrow = t * TL + 16 * w + mo + j + 4 * hi;
+ const half* g = Q + (long)(s0 + qrow) * sq + h * HD;
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks)
+ qf[ks] = qrow < L ? *reinterpret_cast<const uint2*>(g + 4 * ks) : make_uint2(0, 0);
+ }
+ const int qr0 = t * TL + 16 * w + mo + (lane & 1) + 4 * hi; // i&2 == 0
+ float m[2] = {-INFINITY, -INFINITY}, l[2] = {0.f, 0.f};
+ float o[4][8];
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) o[a][i] = 0.f;
+
+ half* P = Ps[w];
+ const half* Kg = K + (long)s0 * sk + h * HD;
+ const half* Vg = V + (long)s0 * sv + h * HD;
+
+ float s[4][8];
+ TileRegs kr, vr;
+ // Prologue: K_0 committed, S_0 computed; the loop body computes S_{kt+1}
+ // while doing softmax(S_kt). Ks2[kt&1] holds K_kt.
+ fetch_tile(kr, Kg, sk, 0, L, tid);
+ fetch_tile(vr, Vg, sv, 0, L, tid);
+ commit_tile<true>(Ks2[0], kr, tid);
+ if (t > 0) fetch_tile(kr, Kg, sk, TL, L, tid);
+ __syncthreads();
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) s[a][i] = 0.f;
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks)
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_col(s[nb], qf[ks], lds2(Ks2[0], lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
+
+ for (int kt = 0; kt <= t; ++kt) {
+ __syncthreads(); // everyone done with Vs (PV of kt-1) and Ks2[(kt+1)&1] (S_kt's MMAs)
+ commit_tile<true>(Vs, vr, tid);
+ if (kt < t) commit_tile<true>(Ks2[(kt + 1) & 1], kr, tid);
+ if (kt < t) {
+ fetch_tile(vr, Vg, sv, (kt + 1) * TL, L, tid);
+ if (kt + 1 < t) fetch_tile(kr, Kg, sk, (kt + 2) * TL, L, tid);
+ }
+ __syncthreads();
+
+ const bool diag = (kt == t);
+ const bool masked = diag || kt * TL + TL > L;
+ float mx[2] = {m[0], m[1]};
+ // Mask by select only; the max, the next tile's MMAs and the exp share one
+ // basic block so ptxas can interleave HMMA with the softmax FP work.
+ if (masked) {
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) {
+ int key = kt * TL + nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
+ int qr = qr0 + (i & 2);
+ bool ok = key < L && (!diag || key <= qr);
+ s[nb][i] = ok ? s[nb][i] : -INFINITY;
+ }
+ }
+ float sn[4][8];
+ {
+ const half* Kn = Ks2[(kt + 1) & 1]; // stale on the last tile; result unused
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) sn[a][i] = 0.f;
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks)
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_col(sn[nb], qf[ks], lds2(Kn, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
+ }
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) mx[(i >> 1) & 1] = fmaxf(mx[(i >> 1) & 1], s[nb][i]);
+#pragma unroll
+ for (int r = 0; r < 2; ++r) {
+ mx[r] = fmaxf(mx[r], __shfl_xor_sync(0xffffffff, mx[r], 2));
+ mx[r] = fmaxf(mx[r], __shfl_xor_sync(0xffffffff, mx[r], 8));
+ }
+ float alpha[2];
+#pragma unroll
+ for (int r = 0; r < 2; ++r) {
+ alpha[r] = ex2((m[r] - mx[r]) * scale_log2); // exp2(-inf) = 0 on the first tile
+ m[r] = mx[r];
+ l[r] *= alpha[r];
+ }
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) {
+ int r = (i >> 1) & 1;
+ float p = ex2(fmaf(s[nb][i], scale_log2, -m[r] * scale_log2));
+ s[nb][i] = p;
+ l[r] += p;
+ o[nb][i] *= alpha[r];
+ }
+
+ __syncwarp();
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; i += 2) {
+ int row = mo + (lane & 1) + (i & 2) + 4 * hi;
+ int col = nb * 16 + no + (i & 4) + (lane & 2);
+ *reinterpret_cast<unsigned*>(P + lo<true>(row, col)) = pack_h2(s[nb][i], s[nb][i + 1]);
+ }
+ __syncwarp();
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 a = lds2(P, lo<true>(mo + j + 4 * hi, 4 * ks));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_row(o[nb], a, lds2(Vs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
+ }
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) s[a][i] = sn[a][i];
+ }
+
+#pragma unroll
+ for (int r = 0; r < 2; ++r) {
+ l[r] += __shfl_xor_sync(0xffffffff, l[r], 2);
+ l[r] += __shfl_xor_sync(0xffffffff, l[r], 8);
+ }
+#pragma unroll
+ for (int r = 0; r < 2; ++r) {
+ int qr = qr0 + 2 * r;
+ if (qr >= L) continue;
+ float inv = 1.f / l[r];
+ half* og = O + (long)(s0 + qr) * s_o + h * HD;
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 2 * r; i < 8; i += 4) {
+ int col = nb * 16 + no + (i & 4) + (lane & 2);
+ *reinterpret_cast<unsigned*>(og + col) = pack_h2(o[nb][i] * inv, o[nb][i + 1] * inv);
+ }
+ if ((lane & 2) == 0 && no == 0) LSE[(long)h * N + s0 + qr] = m[r] * scale_log2 + __log2f(l[r]);
+ }
+}
+
+// --------------------------------------------------------------------------
+// Backward. One CTA = one 64-key tile of one document, one head; it walks the
+// query tiles at and after it. dK/dV stay in registers; dQ is accumulated in
+// an fp32 buffer with atomics (same as FlashAttention-2).
+// --------------------------------------------------------------------------
+__global__ void __launch_bounds__(NT) bwd_kernel(
+ const half* __restrict__ Q, const half* __restrict__ K, const half* __restrict__ V,
+ const half* __restrict__ dO, const float* __restrict__ LSE,
+ const float* __restrict__ Dv, float* __restrict__ dQacc, half* __restrict__ dK,
+ half* __restrict__ dV, const int* __restrict__ cu, const int* __restrict__ tcum,
+ const int* __restrict__ perm,
+ int ndocs, int N, int H, int sq, int sk, int sv, int sdo, int sdk, int sdv,
+ float scale_log2, float scale) {
+ __shared__ __align__(16) half Ks[TL * HD];
+ __shared__ __align__(16) half Vs[TL * HD];
+ // Q and dO for the current query tile (padded, row stride LDP). Once dK/dV
+ // are done with them they are dead for the iteration, and the same bytes
+ // stage dQ in fp32.
+ __shared__ __align__(16) half QdOs[2 * TL * LDP];
+ half* Qs = QdOs;
+ half* dOs = QdOs + TL * LDP;
+ float* dQs = reinterpret_cast<float*>(QdOs);
+ __shared__ __align__(16) half St[TL * TL]; // P^T, then dS^T (key rows, query cols)
+ __shared__ float lse_s[TL], d_s[TL];
+
+ // 1-D grid, heads interleaved: the longest-first order holds across heads.
+ const int h = blockIdx.x % H;
+ int doc, kt, ntiles;
+ if (!find_tile(tcum, perm, ndocs, blockIdx.x / H, doc, kt, ntiles)) return;
+ const int s0 = cu[doc], L = cu[doc + 1] - s0;
+
+ const int tid = threadIdx.x, w = tid >> 5, lane = tid & 31;
+ const int j = lane & 3, hi = lane >> 4, qp = (lane >> 2) & 3;
+ const int mo = 8 * (qp & 1), no = 8 * (qp >> 1);
+
+ load_tile(Ks, K + (long)s0 * sk + h * HD, sk, kt * TL, L, tid);
+ load_tile(Vs, V + (long)s0 * sv + h * HD, sv, kt * TL, L, tid);
+
+ float dk[4][8], dv[4][8];
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) dk[a][i] = dv[a][i] = 0.f;
+
+ const int kr0 = kt * TL + 16 * w + mo + (lane & 1) + 4 * hi; // this lane's key rows (i&2==0)
+ half* Sw = St + 16 * w * 64; // this warp's 16 key rows
+ const half* Qg = Q + (long)s0 * sq + h * HD;
+ const half* dOg = dO + (long)s0 * sdo + h * HD;
+#if BWD_PF
+ // The next query tile's Q/dO (and lse/D) are fetched into registers while
+ // the current tile computes, like the forward's K/V prefetch.
+ TileRegs qreg, dreg;
+ float lse_n = 0.f, d_n = 0.f;
+ fetch_tile(qreg, Qg, sq, kt * TL, L, tid);
+ fetch_tile(dreg, dOg, sdo, kt * TL, L, tid);
+ if (tid < TL) {
+ int qr = kt * TL + tid;
+ if (qr < L) { lse_n = LSE[(long)h * N + s0 + qr]; d_n = Dv[(long)h * N + s0 + qr]; }
+ }
+#endif
+
+ for (int qt = kt; qt < ntiles; ++qt) {
+ __syncthreads();
+#if BWD_PF
+ commit_tile<true>(Qs, qreg, tid);
+ commit_tile<true>(dOs, dreg, tid);
+ if (tid < TL) { lse_s[tid] = lse_n; d_s[tid] = d_n; }
+ if (qt + 1 < ntiles) {
+ fetch_tile(qreg, Qg, sq, (qt + 1) * TL, L, tid);
+ fetch_tile(dreg, dOg, sdo, (qt + 1) * TL, L, tid);
+ if (tid < TL) {
+ int qr = (qt + 1) * TL + tid;
+ bool ok = qr < L;
+ lse_n = ok ? LSE[(long)h * N + s0 + qr] : 0.f;
+ d_n = ok ? Dv[(long)h * N + s0 + qr] : 0.f;
+ }
+ }
+#else
+ load_tile<true>(Qs, Qg, sq, qt * TL, L, tid);
+ load_tile<true>(dOs, dOg, sdo, qt * TL, L, tid);
+ if (tid < TL) {
+ int qr = qt * TL + tid;
+ bool ok = qr < L;
+ lse_s[tid] = ok ? LSE[(long)h * N + s0 + qr] : 0.f;
+ d_s[tid] = ok ? Dv[(long)h * N + s0 + qr] : 0.f;
+ }
+#endif
+ __syncthreads();
+
+ // S^T = K_w Q^T and dP^T = V_w dO^T, both (16 keys x 64 queries).
+ float st[4][8], dp[4][8];
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) st[a][i] = dp[a][i] = 0.f;
+#if BWD_ILP
+ // S^T first; the dP^T MMAs are issued in the same basic block as exp(S^T)
+ // so ptxas interleaves HMMA with the MUFU/FFMA work.
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 ak = lds2(Ks, so(16 * w + mo + j + 4 * hi, 4 * ks));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_col(st[nb], ak, lds2(Qs, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks)));
+ }
+#define DP_MMAS \
+ _Pragma("unroll") for (int ks = 0; ks < 16; ++ks) { \
+ uint2 av = lds2(Vs, so(16 * w + mo + j + 4 * hi, 4 * ks)); \
+ _Pragma("unroll") for (int nb = 0; nb < 4; ++nb) \
+ mma_row_col(dp[nb], av, lds2(dOs, lo<true>(nb * 16 + no + j + 4 * hi, 4 * ks))); \
+ }
+#define DS_FROM_P \
+ _Pragma("unroll") for (int nb = 0; nb < 4; ++nb) \
+ _Pragma("unroll") for (int i = 0; i < 8; ++i) { \
+ int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1); \
+ dp[nb][i] = st[nb][i] * (dp[nb][i] - d_s[c]); \
+ }
+#else
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 ak = lds2(Ks, so(16 * w + mo + j + 4 * hi, 4 * ks));
+ uint2 av = lds2(Vs, so(16 * w + mo + j + 4 * hi, 4 * ks));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb) {
+ int n = nb * 16 + no + j + 4 * hi;
+ mma_row_col(st[nb], ak, lds2(Qs, lo<true>(n, 4 * ks)));
+ mma_row_col(dp[nb], av, lds2(dOs, lo<true>(n, 4 * ks)));
+ }
+ }
+#endif
+
+ const bool diag = (qt == kt);
+ // Masks are needed only on the diagonal tile and a document's last query
+ // tile (a partial key tile is always diagonal); uniform across the CTA.
+ if (diag || qt * TL + TL > L) {
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) {
+ int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
+ int qr = qt * TL + c;
+ int kr = kr0 + (i & 2);
+ bool ok = qr < L && kr < L && (!diag || kr <= qr);
+ float p = ok ? ex2(fmaf(st[nb][i], scale_log2, -lse_s[c])) : 0.f;
+ st[nb][i] = p;
+#if !BWD_ILP
+ dp[nb][i] = p * (dp[nb][i] - d_s[c]);
+#endif
+ }
+#if BWD_ILP
+ DP_MMAS
+ DS_FROM_P
+#endif
+ } else {
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) {
+ int c = nb * 16 + no + (i & 4) + (lane & 2) + (i & 1);
+ float p = ex2(fmaf(st[nb][i], scale_log2, -lse_s[c]));
+ st[nb][i] = p;
+#if !BWD_ILP
+ dp[nb][i] = p * (dp[nb][i] - d_s[c]);
+#endif
+ }
+#if BWD_ILP
+ DP_MMAS
+ DS_FROM_P
+#endif
+ }
+#undef DP_MMAS
+#undef DS_FROM_P
+
+ // dV_w += P^T_w dO
+ __syncwarp();
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; i += 2) {
+ int row = mo + (lane & 1) + (i & 2) + 4 * hi;
+ int col = nb * 16 + no + (i & 4) + (lane & 2);
+ *reinterpret_cast<unsigned*>(Sw + so(row, col)) = pack_h2(st[nb][i], st[nb][i + 1]);
+ }
+ __syncwarp();
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 a = lds2(Sw, so(mo + j + 4 * hi, 4 * ks));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_row(dv[nb], a, lds2(dOs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
+ }
+
+ // dK_w += dS^T_w Q
+ __syncwarp();
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; i += 2) {
+ int row = mo + (lane & 1) + (i & 2) + 4 * hi;
+ int col = nb * 16 + no + (i & 4) + (lane & 2);
+ *reinterpret_cast<unsigned*>(Sw + so(row, col)) = pack_h2(dp[nb][i], dp[nb][i + 1]);
+ }
+ __syncwarp();
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 a = lds2(Sw, so(mo + j + 4 * hi, 4 * ks));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_row_row(dk[nb], a, lds2(Qs, lo<true>(4 * ks + j, nb * 16 + no + 4 * hi)));
+ }
+
+ // dQ (64 queries x 64 dims) += dS K; warp w takes queries 16w..16w+15.
+ // Its A operand is dS = (dS^T)^T, read straight from St as A.col.
+ __syncthreads();
+ float dq[4][8];
+#pragma unroll
+ for (int a = 0; a < 4; ++a)
+#pragma unroll
+ for (int i = 0; i < 8; ++i) dq[a][i] = 0.f;
+#pragma unroll
+ for (int ks = 0; ks < 16; ++ks) {
+ uint2 a = lds2(St, so(4 * ks + j, 16 * w + mo + 4 * hi));
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+ mma_col_row(dq[nb], a, lds2(Ks, so(4 * ks + j, nb * 16 + no + 4 * hi)));
+ }
+ // Stage the warp's 16x64 dQ slice in shared memory and issue the atomics
+ // row-contiguous: each warp-wide RED then covers 128 consecutive bytes
+ // (4 sectors) instead of scattering over 8 rows 2KB apart. Row stride is
+ // 64 floats; float2 slots are XOR-swizzled by row so both the fragment-
+ // layout writes and the row reads are bank-conflict free.
+ float* dQw = dQs + 16 * w * 64;
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 0; i < 8; i += 2) {
+ int row = mo + (lane & 1) + (i & 2) + 4 * hi;
+ int c2 = (nb * 16 + no + (i & 4) + (lane & 2)) >> 1;
+ int f = ((row & 1) << 1) | (row & 8);
+ *reinterpret_cast<float2*>(dQw + row * 64 + 2 * (c2 ^ f)) =
+ make_float2(dq[nb][i], dq[nb][i + 1]);
+ }
+ __syncwarp();
+ {
+ const int qbase = qt * TL + 16 * w;
+ const int nrow = min(16, L - qbase);
+ if (nrow == 16) {
+ // full 16-row slice: unrolled, smem offsets are 4 lane bases + immediates,
+ // global offsets one 64-bit pointer + row * (H*HD) increments.
+ float* gp = dQacc + ((long)(s0 + qbase) * H + h) * HD + lane;
+ const long rs = (long)H * HD;
+ const int x0 = lane >> 1, b0 = lane & 1;
+#pragma unroll
+ for (int row = 0; row < 16; ++row) {
+ const int f = ((row & 1) << 1) | (row & 8);
+ const float* sr = dQw + row * 64 + 2 * (x0 ^ f) + b0;
+ atomicAdd(gp, sr[0]);
+ atomicAdd(gp + 32, sr[32]);
+ gp += rs;
+ }
+ } else
+ for (int it = 0; it < 2 * nrow; ++it) {
+ int row = it >> 1, col = (it & 1) * 32 + lane;
+ int f = ((row & 1) << 1) | (row & 8);
+ float v = dQw[row * 64 + 2 * ((col >> 1) ^ f) + (col & 1)];
+ atomicAdd(dQacc + ((long)(s0 + qbase + row) * H + h) * HD + col, v);
+ }
+ }
+ }
+
+#pragma unroll
+ for (int r = 0; r < 2; ++r) {
+ int kr = kr0 + 2 * r;
+ if (kr >= L) continue;
+ half* gk = dK + (long)(s0 + kr) * sdk + h * HD;
+ half* gv = dV + (long)(s0 + kr) * sdv + h * HD;
+#pragma unroll
+ for (int nb = 0; nb < 4; ++nb)
+#pragma unroll
+ for (int i = 2 * r; i < 8; i += 4) {
+ int col = nb * 16 + no + (i & 4) + (lane & 2);
+ *reinterpret_cast<unsigned*>(gk + col) = pack_h2(dk[nb][i] * scale, dk[nb][i + 1] * scale);
+ *reinterpret_cast<unsigned*>(gv + col) = pack_h2(dv[nb][i], dv[nb][i + 1]);
+ }
+ }
+}
+
+// D[h][n] = sum_d dO[n,h,d] * O[n,h,d] in fp32. One warp per (n, h) row pair.
+__global__ void bwd_pre_kernel(const half* __restrict__ dO, const half* __restrict__ O,
+ float* __restrict__ Dv, int N, int H, int sdo, int s_o) {
+ int gw = (blockIdx.x * blockDim.x + threadIdx.x) >> 5, lane = threadIdx.x & 31;
+ if (gw >= N * H) return;
+ int n = gw / H, h = gw % H;
+ __half2 a = reinterpret_cast<const __half2*>(dO + (long)n * sdo + h * HD)[lane];
+ __half2 b = reinterpret_cast<const __half2*>(O + (long)n * s_o + h * HD)[lane];
+ float2 fa = __half22float2(a), fb = __half22float2(b);
+ float acc = fa.x * fb.x + fa.y * fb.y;
+#pragma unroll
+ for (int o = 16; o; o >>= 1) acc += __shfl_xor_sync(0xffffffff, acc, o);
+ if (lane == 0) Dv[(long)h * N + n] = acc;
+}
+
+// dq = fp16(dQacc * scale), four elements per thread.
+__global__ void bwd_post_kernel(const float4* __restrict__ acc, uint2* __restrict__ dq,
+ long n4, float scale) {
+ long i = blockIdx.x * (long)blockDim.x + threadIdx.x;
+ if (i >= n4) return;
+ float4 v = acc[i];
+ dq[i] = make_uint2(pack_h2(v.x * scale, v.y * scale), pack_h2(v.z * scale, v.w * scale));
+}
+
+void check_qkv(const torch::Tensor& t, const char* name) {
+ TORCH_CHECK(t.is_cuda() && t.scalar_type() == at::kHalf, name, " must be cuda fp16");
+ TORCH_CHECK(t.dim() == 3 && t.size(2) == HD && t.stride(2) == 1 && t.stride(1) == HD,
+ name, " must be (N, H, 64) with contiguous heads");
+ TORCH_CHECK(t.stride(0) % 8 == 0, name, " token stride must be a multiple of 8");
+}
+
+void check_meta(const torch::Tensor& q, const torch::Tensor& k, const torch::Tensor& v,
+ const torch::Tensor& cu, const torch::Tensor& tcum) {
+ TORCH_CHECK(k.sizes() == q.sizes() && v.sizes() == q.sizes(),
+ "q, k, v must have the same (N, H, 64) shape");
+ TORCH_CHECK(k.device() == q.device() && v.device() == q.device() &&
+ cu.device() == q.device() && tcum.device() == q.device(),
+ "q, k, v, cu, tcum must be on one device");
+ TORCH_CHECK(cu.scalar_type() == at::kInt && tcum.scalar_type() == at::kInt &&
+ cu.dim() == 1 && tcum.dim() == 1 && cu.is_contiguous() && tcum.is_contiguous(),
+ "cu and tcum must be contiguous 1-D int32");
+ TORCH_CHECK(cu.numel() >= 2 && tcum.numel() == cu.numel(),
+ "cu and tcum must both have ndocs+1 entries");
+}
+
+} // namespace
+
+// q, k, v: (N, H, 64) fp16. cu: (ndocs+1,) int32 offsets. tcum: (ndocs+1,) int32
+// cumulative 64-tile counts. Returns (o, lse) with lse (H, N) fp32 in log2 units.
+std::vector<torch::Tensor> fwd(torch::Tensor q, torch::Tensor k, torch::Tensor v,
+ torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
+ check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
+ check_meta(q, k, v, cu, tcum);
+ const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
+ auto o = torch::empty({N, H, HD}, q.options());
+ auto lse = torch::empty({H, N}, q.options().dtype(torch::kFloat));
+ // 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
+ dim3 grid(((N + TL - 1) / TL + ndocs) * H);
+ fwd_kernel<<<grid, NT, 0, at::cuda::getCurrentCUDAStream()>>>(
+ (const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
+ (half*)o.data_ptr(), lse.data_ptr<float>(), cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(),
+ ndocs, N, H, q.stride(0), k.stride(0), v.stride(0), o.stride(0),
+ (float)(scale * 1.4426950408889634));
+ C10_CUDA_KERNEL_LAUNCH_CHECK();
+ return {o, lse};
+}
+
+// Returns (dq, dk, dv), each (N, H, 64) fp16.
+std::vector<torch::Tensor> bwd_raw(torch::Tensor dout, torch::Tensor q, torch::Tensor k,
+ torch::Tensor v, torch::Tensor o, torch::Tensor lse,
+ torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
+ check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
+ check_meta(q, k, v, cu, tcum);
+ dout = dout.contiguous();
+ check_qkv(dout, "dout");
+ TORCH_CHECK(dout.sizes() == q.sizes() && o.sizes() == q.sizes() && o.stride(2) == 1 &&
+ o.stride(1) == HD && dout.device() == q.device() && o.device() == q.device(),
+ "dout and o must match q");
+ TORCH_CHECK(lse.scalar_type() == at::kFloat && lse.is_contiguous() && lse.dim() == 2 &&
+ lse.size(0) == q.size(1) && lse.size(1) == q.size(0), "lse must be (H, N) fp32");
+ const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
+ // D_i = rowsum(dO * O), fp32, laid out (H, N) like lse.
+ auto stream = at::cuda::getCurrentCUDAStream();
+ auto Dv = torch::empty({H, N}, q.options().dtype(torch::kFloat));
+ bwd_pre_kernel<<<(N * H * 32 + 255) / 256, 256, 0, stream>>>(
+ (const half*)dout.data_ptr(), (const half*)o.data_ptr(), Dv.data_ptr<float>(), N, H,
+ dout.stride(0), o.stride(0));
+ auto dqacc = torch::zeros({N, H, HD}, q.options().dtype(torch::kFloat));
+ auto dk = torch::empty({N, H, HD}, q.options());
+ auto dv = torch::empty({N, H, HD}, q.options());
+ // 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
+ dim3 grid(((N + TL - 1) / TL + ndocs) * H);
+ bwd_kernel<<<grid, NT, 0, stream>>>(
+ (const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
+ (const half*)dout.data_ptr(), lse.data_ptr<float>(), Dv.data_ptr<float>(),
+ dqacc.data_ptr<float>(), (half*)dk.data_ptr(), (half*)dv.data_ptr(),
+ cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(), ndocs, N, H, q.stride(0), k.stride(0),
+ v.stride(0), dout.stride(0), dk.stride(0), dv.stride(0),
+ (float)(scale * 1.4426950408889634), (float)scale);
+ C10_CUDA_KERNEL_LAUNCH_CHECK();
+ // raw fp32 dQ accumulator, NOT yet multiplied by the softmax scale
+ return {dqacc, dk, dv};
+}
+
+std::vector<torch::Tensor> bwd(torch::Tensor dout, torch::Tensor q, torch::Tensor k,
+ torch::Tensor v, torch::Tensor o, torch::Tensor lse,
+ torch::Tensor cu, torch::Tensor tcum, torch::Tensor perm, double scale) {
+ check_qkv(q, "q"); check_qkv(k, "k"); check_qkv(v, "v");
+ check_meta(q, k, v, cu, tcum);
+ dout = dout.contiguous();
+ check_qkv(dout, "dout");
+ TORCH_CHECK(dout.sizes() == q.sizes() && o.sizes() == q.sizes() && o.stride(2) == 1 &&
+ o.stride(1) == HD && dout.device() == q.device() && o.device() == q.device(),
+ "dout and o must match q");
+ TORCH_CHECK(lse.scalar_type() == at::kFloat && lse.is_contiguous() && lse.dim() == 2 &&
+ lse.size(0) == q.size(1) && lse.size(1) == q.size(0), "lse must be (H, N) fp32");
+ const int N = q.size(0), H = q.size(1), ndocs = cu.numel() - 1;
+ // D_i = rowsum(dO * O), fp32, laid out (H, N) like lse.
+ auto stream = at::cuda::getCurrentCUDAStream();
+ auto Dv = torch::empty({H, N}, q.options().dtype(torch::kFloat));
+ bwd_pre_kernel<<<(N * H * 32 + 255) / 256, 256, 0, stream>>>(
+ (const half*)dout.data_ptr(), (const half*)o.data_ptr(), Dv.data_ptr<float>(), N, H,
+ dout.stride(0), o.stride(0));
+ auto dqacc = torch::zeros({N, H, HD}, q.options().dtype(torch::kFloat));
+ auto dk = torch::empty({N, H, HD}, q.options());
+ auto dv = torch::empty({N, H, HD}, q.options());
+ // 1-D grid, heads interleaved (b = blockIdx.x / H); >= H * sum of ceil(len/64)
+ dim3 grid(((N + TL - 1) / TL + ndocs) * H);
+ bwd_kernel<<<grid, NT, 0, stream>>>(
+ (const half*)q.data_ptr(), (const half*)k.data_ptr(), (const half*)v.data_ptr(),
+ (const half*)dout.data_ptr(), lse.data_ptr<float>(), Dv.data_ptr<float>(),
+ dqacc.data_ptr<float>(), (half*)dk.data_ptr(), (half*)dv.data_ptr(),
+ cu.data_ptr<int>(), tcum.data_ptr<int>(), perm.data_ptr<int>(), ndocs, N, H, q.stride(0), k.stride(0),
+ v.stride(0), dout.stride(0), dk.stride(0), dv.stride(0),
+ (float)(scale * 1.4426950408889634), (float)scale);
+ C10_CUDA_KERNEL_LAUNCH_CHECK();
+ auto dq = torch::empty({N, H, HD}, q.options());
+ long n4 = (long)N * H * HD / 4;
+ bwd_post_kernel<<<(n4 + 255) / 256, 256, 0, stream>>>(
+ reinterpret_cast<const float4*>(dqacc.data_ptr<float>()),
+ reinterpret_cast<uint2*>(dq.data_ptr()), n4, (float)scale);
+ C10_CUDA_KERNEL_LAUNCH_CHECK();
+ return {dq, dk, dv};
+}
+
+PYBIND11_MODULE(TORCH_EXTENSION_NAME, m) {
+ m.def("fwd", &fwd);
+ m.def("bwd", &bwd);
+ m.def("bwd_raw", &bwd_raw);
+}