Qwen3.8-Flash-Next on any consumer hardware: one-click install for Windows / Linux. Strata inference engine, OpenAI/Anthropic API on localhost, optional image input.
C++
// src/kernels/cuda/qsa_select.cu - see include/strata/kernels/qsa_select.hpp.
#include "strata/core/emulate.hpp"
#include "strata/core/sm75_series.hpp"
#include "strata/core/geometry.hpp"
#include <cstdlib>
#include <cstring>
#include "strata/kernels/qsa_select.hpp"
#include "strata/kernels/gfx_arch.hpp"
#include <cuda_runtime.h>
#include <atomic>
#include <cfloat>
#include <cstdio>
#include <cstdlib>
#include <cstring>
namespace strata::kernels {
namespace {
constexpr int IDX_DIM = 128, IDX_HEADS = 4, R = 4;
static_assert(IDX_DIM == strata::core::kCompiledGeometry.idx_key_dim && IDX_HEADS == strata::core::kCompiledGeometry.idx_q_heads && R == strata::core::kCompiledGeometry.idx_block,
"qsa_select is compiled for core/geometry.hpp");
constexpr int SCORE_WARPS = 8;
constexpr int TOPK_T = 256;
__device__ __forceinline__ uint32_t order_key(float s) {
const float v = s + 0.0f;
if (!(v == v)) return 0u;
const uint32_t b = __float_as_uint(v);
return (b & 0x80000000u) ? ~b : (b | 0x80000000u);
}
__global__ void __launch_bounds__(SCORE_WARPS * 32) block_scores_kernel(const float* __restrict__ pooled,
const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps,
int64_t max_blocks, float* __restrict__ out) {
const int64_t qi = blockIdx.y;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid];
const int64_t b = (int64_t) blockIdx.x * SCORE_WARPS + (threadIdx.x >> 5);
if (b > n_bid || b >= max_blocks) return;
const int lane = threadIdx.x & 31;
const float* key = (b == n_bid) ? dead : pooled + b * IDX_DIM;
const float4 k4 = *reinterpret_cast<const float4*>(key + lane * 4);
const float* q = q_idx + qi * IDX_HEADS * IDX_DIM + lane * 4;
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float4 q4 = *reinterpret_cast<const float4*>(q + h * IDX_DIM);
float d = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
#pragma unroll
for (int o = 16; o > 0; o >>= 1) d += __shfl_xor_sync(0xffffffffu, d, o);
score += d > 0.0f ? d : 0.0f;
}
if (lane == 0) {
if (b == n_bid && n_kv % R != 0) score += 1e9f;
out[qi * max_blocks + b] = score;
}
}
__global__ void __launch_bounds__(TOPK_T) block_topk_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
__shared__ int hist[256];
__shared__ int s_a[TOPK_T], s_b[TOPK_T];
__shared__ int s_digit, s_above;
const int64_t qi = blockIdx.x;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + qi * cap;
const int t = threadIdx.x;
if (n_kv <= width) { // everything is selected: the identity, ascending
for (int64_t j = t; j < n_kv; j += TOPK_T) out[j] = (int32_t) j;
return;
}
const float* sc = scores + qi * max_blocks;
const int64_t nb = n_bid + 1; // blocks 0..n_bid, the last possibly empty
const int64_t per = (nb + TOPK_T - 1) / TOPK_T;
const int64_t b0 = (int64_t) t * per, b1 = (b0 + per < nb) ? b0 + per : nb;
auto weight = [&](int64_t b) -> int { return b < n_bid ? R : (int) (n_kv - n_bid * R); };
// ---- radix select: the largest key thr with (cells with key >= thr) >= width, 8 bits at a time
uint32_t prefix = 0;
int above = 0; // cells strictly above the digits fixed so far
for (int shift = 24; shift >= 0; shift -= 8) {
for (int i = t; i < 256; i += TOPK_T) hist[i] = 0;
__syncthreads();
const uint32_t hi_mask = shift == 24 ? 0u : (0xffffffffu << (shift + 8));
for (int64_t b = b0; b < b1; ++b) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if ((k & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[(k >> shift) & 255], w);
}
__syncthreads();
if (t == 0) {
int cum = above, d = 255;
for (; d > 0; --d) {
if (cum + hist[d] >= width) break;
cum += hist[d];
}
s_digit = d;
s_above = cum;
}
__syncthreads();
prefix |= (uint32_t) s_digit << shift;
above = s_above;
__syncthreads();
}
const uint32_t thr = prefix;
const int64_t eq_budget = width - above; // cells equal to thr that fit, lowest index first
// ---- per-thread counts of cells above and at the threshold, then their exclusive prefixes
int gt = 0, eq = 0;
for (int64_t b = b0; b < b1; ++b) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k > thr) gt += w;
else if (k == thr) eq += w;
}
s_a[t] = gt;
s_b[t] = eq;
__syncthreads();
if (t == 0) {
int ag = 0, ae = 0;
for (int i = 0; i < TOPK_T; ++i) {
const int g = s_a[i], e = s_b[i];
s_a[i] = ag; s_b[i] = ae;
ag += g; ae += e;
}
}
__syncthreads();
const int64_t eq_before = s_b[t];
int64_t my_eq = eq_budget - eq_before;
if (my_eq < 0) my_eq = 0;
if (my_eq > eq) my_eq = eq;
const int sel = gt + (int) my_eq;
__syncthreads();
s_a[t] = sel;
__syncthreads();
if (t == 0) {
int a = 0;
for (int i = 0; i < TOPK_T; ++i) { const int c = s_a[i]; s_a[i] = a; a += c; }
}
__syncthreads();
int64_t wpos = s_a[t];
int64_t eq_left = my_eq;
for (int64_t b = b0; b < b1; ++b) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k > thr) {
for (int c = 0; c < w; ++c) out[wpos++] = (int32_t) (b * R + c);
} else if (k == thr) {
for (int c = 0; c < w && eq_left > 0; ++c, --eq_left) out[wpos++] = (int32_t) (b * R + c);
}
}
}
// ---- QSA select on tensor cores (perf-review, after D-1): the block scores of many queries are one GEMM,
// rows (query, indexer head) x columns (blocks), K = 128, with relu per head summed. 3xTF32 (each operand split
// into a TF32 hi and lo part, hi*hi + hi*lo + lo*hi) keeps FP32-level accuracy; the summation order differs from
// the warp kernel, so a score can move in its last bits and a near-tie can select differently (not bitwise).
// Blocks < n_bid only; the tail block n_bid (the `dead` key, +1e9) is scored by the warp kernel's own code.
constexpr int TC_QT = 16; // queries per CTA (one m16 tile per indexer head)
constexpr int TC_NB = 32; // blocks per tile (4 warps x n8)
constexpr int TC_ITER = 4; // tiles per CTA (the query tile is loaded once)
constexpr int TC_QS = IDX_HEADS * IDX_DIM + 4; // query row stride in floats
constexpr int TC_KS = IDX_DIM + 4; // key row stride
// TF32 conversion and MMA need sm_80: below it they compile to a trap and qsa_block_scores_tc refuses the device
#if defined(__HIPCC__) // AMD: no mma.sync / cp.async; the host keeps the warp kernel (below)
#define STRATA_SEL_SM80 0
#elif !defined(__CUDA_ARCH__) || __CUDA_ARCH__ >= 800
#define STRATA_SEL_SM80 1
#else
#define STRATA_SEL_SM80 0
#endif
__device__ __forceinline__ uint32_t tf32_hi(float x) {
#if STRATA_SEL_SM80
uint32_t r;
asm("cvt.rna.tf32.f32 %0, %1;" : "=r"(r) : "f"(x));
return r;
#else
return __float_as_uint(x);
#endif
}
__device__ __forceinline__ void mma_tf32(float* c, const uint32_t* a, const uint32_t* b) {
#if !STRATA_SEL_SM80
__trap();
#else
asm volatile("mma.sync.aligned.m16n8k8.row.col.f32.tf32.tf32.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"(a[0]), "r"(a[1]), "r"(a[2]), "r"(a[3]), "r"(b[0]), "r"(b[1]));
#endif
}
__global__ void __launch_bounds__(128) block_scores_tc_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
extern __shared__ __align__(16) float sm[];
float* sQ = sm; // [TC_QT][TC_QS]
float* sK = sm + TC_QT * TC_QS; // [TC_NB][TC_KS]
__shared__ int s_nbid[TC_QT];
const int t = threadIdx.x, lane = t & 31, warp = t >> 5, gid = lane >> 2, tig = lane & 3;
const int64_t q0 = (int64_t) blockIdx.y * TC_QT;
for (int i = t; i < TC_QT * IDX_HEADS * IDX_DIM / 4; i += 128) {
const int r = i / (IDX_HEADS * IDX_DIM / 4), c = i % (IDX_HEADS * IDX_DIM / 4);
float4 v = make_float4(0.f, 0.f, 0.f, 0.f);
if (q0 + r < nq) v = reinterpret_cast<const float4*>(q_idx + (q0 + r) * IDX_HEADS * IDX_DIM)[c];
*reinterpret_cast<float4*>(sQ + r * TC_QS + c * 4) = v;
}
if (t < TC_QT) s_nbid[t] = q0 + t < nq ? steps[(q0 + t) * kStepCount + kStepNBid] : 0;
int lo_nbid = 0x7fffffff, hi_nbid = 0;
__syncthreads();
for (int i = 0; i < TC_QT; ++i) {
if (q0 + i >= nq) break;
lo_nbid = min(lo_nbid, s_nbid[i]);
hi_nbid = max(hi_nbid, s_nbid[i]);
}
for (int it = 0; it < TC_ITER; ++it) {
const int64_t b0 = ((int64_t) blockIdx.x * TC_ITER + it) * TC_NB;
if (b0 >= reach || b0 >= hi_nbid) break; // blocks >= every query's n_bid: nothing to score
__syncthreads(); // the previous tile's reads are done
for (int i = t; i < TC_NB * IDX_DIM / 4; i += 128) {
const int r = i / (IDX_DIM / 4), c = i % (IDX_DIM / 4);
float4 v = make_float4(0.f, 0.f, 0.f, 0.f);
if (b0 + r < hi_nbid) v = reinterpret_cast<const float4*>(pooled + (b0 + r) * IDX_DIM)[c];
*reinterpret_cast<float4*>(sK + r * TC_KS + c * 4) = v;
}
__syncthreads();
float acc[IDX_HEADS][4];
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) acc[h][0] = acc[h][1] = acc[h][2] = acc[h][3] = 0.f;
const float* kr = sK + (warp * 8 + gid) * TC_KS;
#pragma unroll 4
for (int k0 = 0; k0 < IDX_DIM; k0 += 8) {
const float kx0 = kr[k0 + tig], kx1 = kr[k0 + tig + 4];
uint32_t bh[2], bl[2];
bh[0] = tf32_hi(kx0);
bh[1] = tf32_hi(kx1);
bl[0] = tf32_hi(kx0 - __uint_as_float(bh[0]));
bl[1] = tf32_hi(kx1 - __uint_as_float(bh[1]));
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float* qa = sQ + h * IDX_DIM + k0 + tig;
const float x0 = qa[gid * TC_QS], x1 = qa[(gid + 8) * TC_QS];
const float x2 = qa[gid * TC_QS + 4], x3 = qa[(gid + 8) * TC_QS + 4];
uint32_t ah[4], al[4];
ah[0] = tf32_hi(x0); ah[1] = tf32_hi(x1); ah[2] = tf32_hi(x2); ah[3] = tf32_hi(x3);
al[0] = tf32_hi(x0 - __uint_as_float(ah[0]));
al[1] = tf32_hi(x1 - __uint_as_float(ah[1]));
al[2] = tf32_hi(x2 - __uint_as_float(ah[2]));
al[3] = tf32_hi(x3 - __uint_as_float(ah[3]));
mma_tf32(acc[h], al, bh);
mma_tf32(acc[h], ah, bl);
mma_tf32(acc[h], ah, bh);
}
}
// relu per head, heads added in order (as the warp kernel), written where the block completed for the query
const int64_t bc = b0 + warp * 8 + 2 * tig;
#pragma unroll
for (int half = 0; half < 2; ++half) {
const int qr = gid + half * 8;
const int64_t qi = q0 + qr;
if (qi >= nq) continue;
const int nb = s_nbid[qr];
#pragma unroll
for (int j = 0; j < 2; ++j) {
const int64_t b = bc + j;
if (b >= nb || b >= max_blocks) continue;
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float d = acc[h][half * 2 + j];
score += d > 0.0f ? d : 0.0f;
}
out[qi * max_blocks + b] = score;
}
}
}
}
#if defined(__HIPCC__)
// ---- gfx12 (RDNA4: gfx1200 / gfx1201) scorer on v_wmma_f32_16x16x16_bf16 (wave32). Same GEMM as above: for a tile of 16
// queries, every block's score is sum over the 4 indexer heads of relu(q_h . k), K = 128. FP32-level accuracy from a
// three-way bf16 split of both operands (x = hi + mid + lo EXACTLY - the top 8, next 8 and last 8 bits of the fp32
// mantissa, so bf16's fp32-sized exponent range needs no scaling) and the six products of order <= 2, smallest first;
// like the TF32 kernel it sums in another order than the warp kernel (not bitwise). The tail block n_bid is the warp
// kernel's arithmetic (block_scores_tail_kernel).
// D = A x B with A = 16 key blocks (row l%16 of a lane, k = 8*(l/16)+i), B = 16 queries (column l%16, same k):
// a lane ends up with 8 consecutive blocks of ONE query, written as one run. No LDS for keys: a lane reads its
// 32-byte slice of the key row from global (the 16 query tiles of a launch re-read them from L2); the queries are
// split once per CTA into LDS.
// gfx11 (RDNA3 / RDNA3.5) has the same instruction with another fragment layout: a lane holds all 16 k of its row
// (A) or column (B) - lanes 16..31 repeat lanes 0..15 - and D[2i + l/16][l%16]; SEL_KL is the k per lane, SEL_KOFF(g)
// the first, SEL_ROW(i, g) the D row of element i. Same products, same order per element as on gfx12.
#if defined(__gfx1200__) || defined(__gfx1201__)
#define STRATA_SEL_GFX12 1
#define STRATA_SEL_GFX11 0
#elif defined(__gfx1100__) || defined(__gfx1101__) || defined(__gfx1102__) || defined(__gfx1103__) || defined(__gfx1150__) || \
defined(__gfx1151__)
#define STRATA_SEL_GFX12 0
#define STRATA_SEL_GFX11 1
#else
#define STRATA_SEL_GFX12 0
#define STRATA_SEL_GFX11 0
#endif
#if STRATA_SEL_GFX11
constexpr int SEL_KL = 16;
#define SEL_KOFF(g) 0
#define SEL_ROW(i, g) (2 * (i) + (g))
#else
constexpr int SEL_KL = 8;
#define SEL_KOFF(g) ((g) * 8)
#define SEL_ROW(i, g) ((g) * 8 + (i))
#endif
typedef short sel_s8 __attribute__((ext_vector_type(SEL_KL)));
typedef float sel_f8 __attribute__((ext_vector_type(8)));
typedef uint32_t sel_u4 __attribute__((ext_vector_type(SEL_KL / 2)));
constexpr int WQT = 16; // queries per CTA (the N of one WMMA)
constexpr int WITER = 4; // key tiles per warp (the CTA covers 4 warps * WITER * 16 blocks)
constexpr int WQS = IDX_DIM + 8; // bf16 elements per LDS row: 272 bytes, conflict-free 16-byte reads
__device__ __forceinline__ sel_f8 wmma_bf16(const sel_s8& a, const sel_s8& b, const sel_f8& c) {
#if STRATA_SEL_GFX12
return __builtin_amdgcn_wmma_f32_16x16x16_bf16_w32_gfx12(a, b, c);
#elif STRATA_SEL_GFX11
return __builtin_amdgcn_wmma_f32_16x16x16_bf16_w32(a, b, c);
#else
__trap();
return c;
#endif
}
// the bf16 pieces of x as fp32 bit patterns whose upper 16 bits are the bf16 (lower 16 are zero)
__device__ __forceinline__ void split3(float x, uint32_t& hi, uint32_t& mid, uint32_t& lo) {
hi = __float_as_uint(x) & 0xffff0000u;
const float r1 = x - __uint_as_float(hi); // exact
mid = __float_as_uint(r1) & 0xffff0000u;
lo = __float_as_uint(r1 - __uint_as_float(mid)) & 0xffff0000u; // exact: at most 8 significant bits left
}
__device__ __forceinline__ uint32_t pack_bf16x2(uint32_t a, uint32_t b) { // low half = a's bf16, high half = b's
#if STRATA_SEL_GFX12 || STRATA_SEL_GFX11
return __builtin_amdgcn_perm(b, a, 0x07060302u);
#else
return (a >> 16) | (b & 0xffff0000u);
#endif
}
__global__ void __launch_bounds__(128) block_scores_wmma_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
__shared__ __align__(16) uint16_t sq[3][IDX_HEADS][WQT][WQS]; // hi / mid / lo, [head][query][dim]
__shared__ int s_nbid[WQT];
const int t = threadIdx.x, lane = t & 31, warp = t >> 5, l16 = lane & 15, g = lane >> 4;
const int64_t q0 = (int64_t) blockIdx.y * WQT;
for (int i = t; i < WQT * IDX_HEADS * IDX_DIM / 4; i += 128) {
const int row = i / (IDX_DIM / 4), c = i % (IDX_DIM / 4);
const int qr = row / IDX_HEADS, h = row % IDX_HEADS;
float4 v = make_float4(0.f, 0.f, 0.f, 0.f);
if (q0 + qr < nq) v = reinterpret_cast<const float4*>(q_idx + (q0 + qr) * IDX_HEADS * IDX_DIM)[h * (IDX_DIM / 4) + c];
const float x[4] = {v.x, v.y, v.z, v.w};
uint32_t hb[4], mb[4], lb[4];
#pragma unroll
for (int j = 0; j < 4; ++j) split3(x[j], hb[j], mb[j], lb[j]);
*reinterpret_cast<uint2*>(&sq[0][h][qr][c * 4]) = make_uint2(pack_bf16x2(hb[0], hb[1]), pack_bf16x2(hb[2], hb[3]));
*reinterpret_cast<uint2*>(&sq[1][h][qr][c * 4]) = make_uint2(pack_bf16x2(mb[0], mb[1]), pack_bf16x2(mb[2], mb[3]));
*reinterpret_cast<uint2*>(&sq[2][h][qr][c * 4]) = make_uint2(pack_bf16x2(lb[0], lb[1]), pack_bf16x2(lb[2], lb[3]));
}
if (t < WQT) s_nbid[t] = q0 + t < nq ? steps[(q0 + t) * kStepCount + kStepNBid] : 0;
__syncthreads();
int hi_nbid = 0;
#pragma unroll
for (int i = 0; i < WQT; ++i) hi_nbid = max(hi_nbid, s_nbid[i]);
const int64_t qi = q0 + l16;
const int nb_q = s_nbid[l16];
for (int it = 0; it < WITER; ++it) {
const int64_t b0 = (((int64_t) blockIdx.x * WITER + it) * 4 + warp) * 16;
if (b0 >= reach || b0 >= hi_nbid) break; // warp-uniform; later tiles start higher
const int64_t row = b0 + l16;
const bool rv = row < hi_nbid && row < max_blocks;
const float* kp = pooled + (rv ? row : 0) * IDX_DIM + SEL_KOFF(g);
// acc: the hi*hi products; cor: the five smaller ones (<= 2^-8 of it). Kept apart and added once at the end: a
// correction summed into the big accumulator is rounded to ITS ulp at every one of the 48 steps (measured: 8e-7
// of the score scale; apart, near the warp kernel's)
sel_f8 acc[IDX_HEADS], cor[IDX_HEADS];
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) acc[h] = cor[h] = sel_f8{0.f, 0.f, 0.f, 0.f, 0.f, 0.f, 0.f, 0.f};
#pragma unroll 2
for (int kk = 0; kk < IDX_DIM / 16; ++kk) {
float x[SEL_KL];
#pragma unroll
for (int j = 0; j < SEL_KL / 4; ++j) {
float4 kv = make_float4(0.f, 0.f, 0.f, 0.f);
if (rv) kv = *reinterpret_cast<const float4*>(kp + kk * 16 + 4 * j);
x[4 * j] = kv.x; x[4 * j + 1] = kv.y; x[4 * j + 2] = kv.z; x[4 * j + 3] = kv.w;
}
uint32_t hb[SEL_KL], mb[SEL_KL], lb[SEL_KL];
#pragma unroll
for (int j = 0; j < SEL_KL; ++j) split3(x[j], hb[j], mb[j], lb[j]);
sel_u4 ah, am, al;
#pragma unroll
for (int j = 0; j < SEL_KL / 2; ++j) {
ah[j] = pack_bf16x2(hb[2 * j], hb[2 * j + 1]);
am[j] = pack_bf16x2(mb[2 * j], mb[2 * j + 1]);
al[j] = pack_bf16x2(lb[2 * j], lb[2 * j + 1]);
}
const sel_s8 Ah = __builtin_bit_cast(sel_s8, ah), Am = __builtin_bit_cast(sel_s8, am),
Al = __builtin_bit_cast(sel_s8, al);
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const sel_s8 Bh = *reinterpret_cast<const sel_s8*>(&sq[0][h][l16][kk * 16 + SEL_KOFF(g)]);
const sel_s8 Bm = *reinterpret_cast<const sel_s8*>(&sq[1][h][l16][kk * 16 + SEL_KOFF(g)]);
const sel_s8 Bl = *reinterpret_cast<const sel_s8*>(&sq[2][h][l16][kk * 16 + SEL_KOFF(g)]);
cor[h] = wmma_bf16(Al, Bh, cor[h]);
cor[h] = wmma_bf16(Ah, Bl, cor[h]);
cor[h] = wmma_bf16(Am, Bm, cor[h]);
cor[h] = wmma_bf16(Ah, Bm, cor[h]);
cor[h] = wmma_bf16(Am, Bh, cor[h]);
acc[h] = wmma_bf16(Ah, Bh, acc[h]);
}
}
// relu per head, heads added in order (as the warp kernel); this lane: query qi, blocks b0 + SEL_ROW(i, g)
if (qi < nq) {
#pragma unroll
for (int i = 0; i < 8; ++i) {
const int64_t b = b0 + SEL_ROW(i, g);
if (b >= nb_q || b >= max_blocks) continue;
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float d = acc[h][i] + cor[h][i];
score += d > 0.0f ? d : 0.0f;
}
out[qi * max_blocks + b] = score;
}
}
}
}
// the WMMA kernel needs gfx12 (gfx1200/gfx1201) or gfx11 (gfx110x/gfx115x: the other fragment layout) code objects
bool sel_gfx12_device() {
static int ok[64] = {}; // per device: 0 unknown, 1 yes, 2 no
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
cudaDeviceProp prop;
ok[dev] = (cudaGetDeviceProperties(&prop, dev) == cudaSuccess &&
(std::strncmp(prop.gcnArchName, "gfx1200", 7) == 0 || std::strncmp(prop.gcnArchName, "gfx1201", 7) == 0 ||
strata::kernels::gfx_arch_is_gfx11_wmma(prop.gcnArchName)))
? 1 : 2;
cudaGetLastError();
}
return ok[dev] == 1;
}
// RDNA2 (gfx1030-gfx1036): the FP32 tiled scorer's tiling measured there
bool sel_gfx103_device() {
static int ok[64] = {}; // per device: 0 unknown, 1 yes, 2 no
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
cudaDeviceProp prop;
ok[dev] = (cudaGetDeviceProperties(&prop, dev) == cudaSuccess && std::strncmp(prop.gcnArchName, "gfx103", 6) == 0) ? 1 : 2;
cudaGetLastError();
}
return ok[dev] == 1;
}
#endif // __HIPCC__
// the tail block n_bid of each query: exactly block_scores_kernel's arithmetic for that block
__global__ void __launch_bounds__(32) block_scores_tail_kernel(const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps,
int64_t max_blocks, float* __restrict__ out) {
const int64_t qi = blockIdx.x;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid];
if (n_bid >= max_blocks) return;
const int lane = threadIdx.x & 31;
const float4 k4 = *reinterpret_cast<const float4*>(dead + lane * 4);
const float* q = q_idx + qi * IDX_HEADS * IDX_DIM + lane * 4;
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float4 q4 = *reinterpret_cast<const float4*>(q + h * IDX_DIM);
float d = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
#pragma unroll
for (int o = 16; o > 0; o >>= 1) d += __shfl_xor_sync(0xffffffffu, d, o);
score += d > 0.0f ? d : 0.0f;
}
if (lane == 0) {
if (n_kv % R != 0) score += 1e9f;
out[qi * max_blocks + n_bid] = score;
}
}
// ---- the block scores as an FP32 tiled GEMM for cards without a matrix-core scorer (CUDA below sm_80; HIP, opt-in):
// rows (query, indexer head) x columns (blocks), K = 128 through shared memory, 2 queries x 4 heads x TN blocks per
// thread, relu per head summed in registers. The warp kernel spends 5 shuffles per 4 products and reached ~1 TFLOPS
// on an RTX 2080 Ti; this one ~6.9 (256 queries: 4.5x at 4K, 6.8x at 120K-250K). FP32 like the warp kernel in another
// summation order, so not bitwise (as the tensor-core scorer). Blocks < n_bid only; the tail block is
// block_scores_tail_kernel's.
//
// The tiling (QT queries and NB blocks per CTA, KC of K per shared-memory pass, TN blocks per thread) only decides
// which thread computes which score: every score is still the fmaf chain over k = 0..127 in order and the same relu sum
// over the heads, so every tiling gives the same bytes (an RX 6900 XT, qsa_select_bench at 32K and 128K, 14 tilings,
// also with 60 and 72 of its 80 CUs: all byte-identical). CUDA keeps the tiling it was written with (32/64/32/4);
// gfx103x runs 32/128/16/8, 15% faster there at 128K (0.695 -> 0.587 ms per 256 queries).
template <int QT, int NB, int KC, int TN>
__global__ void __launch_bounds__(256) block_scores_simt_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
constexpr int ROWS = QT * IDX_HEADS, QS = ROWS + 4, KS = NB + 4, CX = NB / TN;
static_assert((ROWS / 8) * CX == 256, "256 threads, 8 rows (2 queries x 4 heads) each");
static_assert(TN % 4 == 0 && KC % 4 == 0 && IDX_DIM % KC == 0, "float4 loads");
__shared__ __align__(16) float Qs[KC][QS];
__shared__ __align__(16) float Ks[KC][KS];
const int64_t q0 = (int64_t) blockIdx.y * QT, b0 = (int64_t) blockIdx.x * NB;
const int64_t qlast = (q0 + QT < nq ? q0 + QT : nq) - 1;
if (b0 >= steps[qlast * kStepCount + kStepNBid]) return; // n_bid rises with the position
const int tid = threadIdx.x, tx = tid % CX, ty = tid / CX;
float acc[8][TN] = {};
for (int kc = 0; kc < IDX_DIM; kc += KC) {
for (int idx = tid; idx < ROWS * (KC / 4); idx += 256) { // the query rows: ROWS x KC/4 float4
const int r = idx / (KC / 4), k4 = idx % (KC / 4);
float4 v = make_float4(0.f, 0.f, 0.f, 0.f);
if (q0 + (r >> 2) < nq)
v = *reinterpret_cast<const float4*>(q_idx + (q0 * IDX_HEADS + r) * IDX_DIM + kc + k4 * 4);
Qs[k4 * 4 + 0][r] = v.x; Qs[k4 * 4 + 1][r] = v.y; Qs[k4 * 4 + 2][r] = v.z; Qs[k4 * 4 + 3][r] = v.w;
}
for (int idx = tid; idx < NB * (KC / 4); idx += 256) { // the pooled keys: NB x KC/4 float4
const int c = idx / (KC / 4), k4 = idx % (KC / 4);
float4 v = make_float4(0.f, 0.f, 0.f, 0.f);
if (b0 + c < reach) v = *reinterpret_cast<const float4*>(pooled + (b0 + c) * IDX_DIM + kc + k4 * 4);
Ks[k4 * 4 + 0][c] = v.x; Ks[k4 * 4 + 1][c] = v.y; Ks[k4 * 4 + 2][c] = v.z; Ks[k4 * 4 + 3][c] = v.w;
}
__syncthreads();
#pragma unroll 8
for (int k = 0; k < KC; ++k) {
float qr[8], kr[TN];
*reinterpret_cast<float4*>(&qr[0]) = *reinterpret_cast<const float4*>(&Qs[k][ty * 8]);
*reinterpret_cast<float4*>(&qr[4]) = *reinterpret_cast<const float4*>(&Qs[k][ty * 8 + 4]);
#pragma unroll
for (int t = 0; t < TN; t += 4)
*reinterpret_cast<float4*>(&kr[t]) = *reinterpret_cast<const float4*>(&Ks[k][tx * TN + t]);
#pragma unroll
for (int i = 0; i < 8; ++i)
#pragma unroll
for (int j = 0; j < TN; ++j) acc[i][j] = fmaf(qr[i], kr[j], acc[i][j]);
}
__syncthreads();
}
#pragma unroll
for (int i = 0; i < 2; ++i) {
const int64_t q = q0 + ty * 2 + i;
if (q >= nq) continue;
const int64_t n_bid = steps[q * kStepCount + kStepNBid];
#pragma unroll
for (int j = 0; j < TN; ++j) {
const int64_t b = b0 + tx * TN + j;
if (b >= n_bid || b >= max_blocks) continue;
float sc = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float d = acc[i * 4 + h][j];
sc += d > 0.0f ? d : 0.0f;
}
out[q * max_blocks + b] = sc;
}
}
}
// The FP32 tiled scores and the tail block; false when the grid does not fit. `rdna2_tiles`: gfx103x's tiling.
static bool block_scores_simt(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps,
int64_t nq, int64_t max_blocks, int64_t reach, float* scores, cudaStream_t stream,
bool rdna2_tiles) {
const int64_t qt = 32, nb = rdna2_tiles ? 128 : 64;
const dim3 grid((unsigned) ((reach + nb - 1) / nb), (unsigned) ((nq + qt - 1) / qt));
if (grid.y > 65535) return false;
if (rdna2_tiles)
block_scores_simt_kernel<32, 128, 16, 8><<<grid, 256, 0, stream>>>(pooled, q_idx, steps, nq, max_blocks, reach, scores);
else
block_scores_simt_kernel<32, 64, 32, 4><<<grid, 256, 0, stream>>>(pooled, q_idx, steps, nq, max_blocks, reach, scores);
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, stream>>>(dead, q_idx, steps, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores (simt): %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
// block_scores_simt_kernel with larger tiles (QT queries x NB blocks, RI x CJ products per thread) and the next K
// chunk's loads in registers while the current one is used. Every (row, block) dot is the same fmaf chain over
// k = 0..127 from 0, and the relu sum over the heads in the same order: the same bits as block_scores_simt_kernel.
// STRATA_SELECT_SIMT=2.
constexpr int S2_KC = 32;
template <int QT, int NB>
__global__ void __launch_bounds__(256, 1) block_scores_simt2_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
constexpr int ROWS = QT * IDX_HEADS, RI = ROWS / 16, CJ = NB / 16, QS = ROWS + 4, KS = NB + 4;
constexpr int QL = ROWS * S2_KC / 4 / 256, KL = NB * S2_KC / 4 / 256; // float4 loads per thread
static_assert(RI % 4 == 0 && CJ % 4 == 0 && QL >= 1 && KL >= 1, "tile");
__shared__ __align__(16) float Qs[S2_KC][QS];
__shared__ __align__(16) float Ks[S2_KC][KS];
const int64_t q0 = (int64_t) blockIdx.y * QT, b0 = (int64_t) blockIdx.x * NB;
const int64_t qlast = (q0 + QT < nq ? q0 + QT : nq) - 1;
if (b0 >= steps[qlast * kStepCount + kStepNBid]) return; // n_bid rises with the position
const int tid = threadIdx.x, tx = tid & 15, ty = tid >> 4;
float acc[RI][CJ];
#pragma unroll
for (int i = 0; i < RI; ++i)
#pragma unroll
for (int j = 0; j < CJ; ++j) acc[i][j] = 0.0f;
float4 qv[QL], kv[KL];
auto load = [&](int kc) {
#pragma unroll
for (int i = 0; i < QL; ++i) {
const int idx = tid + i * 256, r = idx >> 3, k4 = idx & 7;
qv[i] = make_float4(0.f, 0.f, 0.f, 0.f);
if (q0 + (r >> 2) < nq)
qv[i] = *reinterpret_cast<const float4*>(q_idx + (q0 * IDX_HEADS + r) * IDX_DIM + kc + k4 * 4);
}
#pragma unroll
for (int i = 0; i < KL; ++i) {
const int idx = tid + i * 256, c = idx >> 3, k4 = idx & 7;
kv[i] = make_float4(0.f, 0.f, 0.f, 0.f);
if (b0 + c < reach) kv[i] = *reinterpret_cast<const float4*>(pooled + (b0 + c) * IDX_DIM + kc + k4 * 4);
}
};
load(0);
#pragma unroll 1
for (int kc = 0; kc < IDX_DIM; kc += S2_KC) {
#pragma unroll
for (int i = 0; i < QL; ++i) {
const int idx = tid + i * 256, r = idx >> 3, k4 = idx & 7;
Qs[k4 * 4 + 0][r] = qv[i].x; Qs[k4 * 4 + 1][r] = qv[i].y; Qs[k4 * 4 + 2][r] = qv[i].z; Qs[k4 * 4 + 3][r] = qv[i].w;
}
#pragma unroll
for (int i = 0; i < KL; ++i) {
const int idx = tid + i * 256, c = idx >> 3, k4 = idx & 7;
Ks[k4 * 4 + 0][c] = kv[i].x; Ks[k4 * 4 + 1][c] = kv[i].y; Ks[k4 * 4 + 2][c] = kv[i].z; Ks[k4 * 4 + 3][c] = kv[i].w;
}
__syncthreads();
if (kc + S2_KC < IDX_DIM) load(kc + S2_KC); // in flight during this chunk's products
#pragma unroll 4
for (int k = 0; k < S2_KC; ++k) {
float qr[RI], kr[CJ];
#pragma unroll
for (int m = 0; m < RI / 4; ++m) {
const float4 a = *reinterpret_cast<const float4*>(&Qs[k][ty * RI + 4 * m]);
qr[4 * m] = a.x; qr[4 * m + 1] = a.y; qr[4 * m + 2] = a.z; qr[4 * m + 3] = a.w;
}
#pragma unroll
for (int g = 0; g < CJ / 4; ++g) {
const float4 b = *reinterpret_cast<const float4*>(&Ks[k][g * 64 + tx * 4]);
kr[4 * g] = b.x; kr[4 * g + 1] = b.y; kr[4 * g + 2] = b.z; kr[4 * g + 3] = b.w;
}
#pragma unroll
for (int i = 0; i < RI; ++i)
#pragma unroll
for (int j = 0; j < CJ; ++j) acc[i][j] = fmaf(qr[i], kr[j], acc[i][j]);
}
__syncthreads();
}
#pragma unroll
for (int qi = 0; qi < RI / 4; ++qi) {
const int64_t q = q0 + ty * (RI / 4) + qi;
if (q >= nq) continue;
const int64_t n_bid = steps[q * kStepCount + kStepNBid];
#pragma unroll
for (int j = 0; j < CJ; ++j) {
const int64_t b = b0 + (j >> 2) * 64 + tx * 4 + (j & 3);
if (b >= n_bid || b >= max_blocks) continue;
float sc = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float d = acc[qi * 4 + h][j];
sc += d > 0.0f ? d : 0.0f;
}
out[q * max_blocks + b] = sc;
}
}
}
// ---- the same top-k with each query's keys read once: 1,024 threads hold up to TK_PER consecutive blocks' keys in
// registers (contexts up to 4 * 1024 * TK_PER cells), per-warp histograms, block-wide scans. The selection rule is
// block_topk_kernel's (radix threshold, ties to the lowest index, cells ascending): identical ids.
constexpr int TK_T = 1024;
constexpr int TK_PER = 33;
#if defined(__HIPCC__)
// AMD (RDNA, wave32): a 1,024-thread block may use 192 VGPRs per lane, so the keys of 66 blocks per thread fit - contexts
// up to 4 * 1024 * 66 = 270,336 cells (the 262,144 --max-context) keep the register kernel. NVIDIA's 64 registers per
// thread at 1,024 threads allow only TK_PER.
constexpr int TK_PER_MAX = 66;
#else
constexpr int TK_PER_MAX = TK_PER;
#endif
__device__ __forceinline__ int block_excl_scan(int v, int* s_warp, int& total) {
const int lane = threadIdx.x & 31, warp = threadIdx.x >> 5;
int x = v;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, x, o);
if (lane >= o) x += y;
}
if (lane == 31) s_warp[warp] = x;
__syncthreads();
if (warp == 0) {
int w = s_warp[lane];
int z = w;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, z, o);
if (lane >= o) z += y;
}
s_warp[lane] = z - w; // exclusive per warp
if (lane == 31) s_warp[32] = z; // total
}
__syncthreads();
const int r = s_warp[warp] + x - v;
total = s_warp[32];
__syncthreads();
return r;
}
template <int PER>
__global__ void __launch_bounds__(TK_T) block_topk_reg_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
__shared__ int hist[TK_T / 32][256];
__shared__ int s_warp[33];
__shared__ int s_digit, s_above;
const int64_t qi = blockIdx.x;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + qi * cap;
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
if (n_kv <= width) {
for (int64_t j = t; j < n_kv; j += TK_T) out[j] = (int32_t) j;
return;
}
const float* sc = scores + qi * max_blocks;
const int64_t nb = n_bid + 1;
const int64_t per = (nb + TK_T - 1) / TK_T; // <= PER (the caller checks)
const int64_t b0 = (int64_t) t * per, b1 = (b0 + per < nb) ? b0 + per : nb;
uint32_t key[PER];
#pragma unroll
for (int j = 0; j < PER; ++j) key[j] = (b0 + j < b1) ? order_key(sc[b0 + j]) : 0u;
auto weight = [&](int64_t b) -> int { return b < n_bid ? R : (int) (n_kv - n_bid * R); };
uint32_t prefix = 0;
int above = 0;
for (int shift = 24; shift >= 0; shift -= 8) {
for (int i = lane; i < 256; i += 32) hist[warp][i] = 0;
__syncwarp();
const uint32_t hi_mask = shift == 24 ? 0u : (0xffffffffu << (shift + 8));
#pragma unroll
for (int j = 0; j < PER; ++j) {
const int64_t b = b0 + j;
if (b >= b1) break;
const int w = weight(b);
if (w == 0) continue;
if ((key[j] & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[warp][(key[j] >> shift) & 255], w);
}
__syncthreads();
if (t < 256) { // fold the warps' histograms into warp 0's
int s = 0;
for (int w2 = 0; w2 < TK_T / 32; ++w2) s += hist[w2][t];
hist[0][t] = s;
}
__syncthreads();
// the digit: the first bin from the top where the count above reaches `width` (bin 0 when none of 255..1
// does). Threads 0-255 (warps 0-7) prefix-sum the 256 bins in descending order instead of one thread
// walking them: the same digit and count above.
int v = 0, x = 0;
if (t < 256) {
v = hist[0][255 - t];
x = v;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, x, o);
if (lane >= o) x += y;
}
if (lane == 31) s_warp[warp] = x;
}
__syncthreads();
if (t < 256) {
int inc = x;
for (int w2 = 0; w2 < warp; ++w2) inc += s_warp[w2];
const int before = above + inc - v;
if (before < width && (above + inc >= width || t == 255)) {
s_digit = 255 - t;
s_above = before;
}
}
__syncthreads();
prefix |= (uint32_t) s_digit << shift;
above = s_above;
__syncthreads();
}
const uint32_t thr = prefix;
const int64_t eq_budget = width - above;
int gt = 0, eq = 0;
#pragma unroll
for (int j = 0; j < PER; ++j) {
const int64_t b = b0 + j;
if (b >= b1) break;
const int w = weight(b);
if (w == 0) continue;
if (key[j] > thr) gt += w;
else if (key[j] == thr) eq += w;
}
int tot;
const int eq_before = block_excl_scan(eq, s_warp, tot);
int64_t my_eq = eq_budget - eq_before;
if (my_eq < 0) my_eq = 0;
if (my_eq > eq) my_eq = eq;
const int sel = gt + (int) my_eq;
int64_t wpos = block_excl_scan(sel, s_warp, tot);
int64_t eq_left = my_eq;
#pragma unroll
for (int j = 0; j < PER; ++j) {
const int64_t b = b0 + j;
if (b >= b1) break;
const int w = weight(b);
if (w == 0) continue;
if (key[j] > thr) {
for (int c = 0; c < w; ++c) out[wpos++] = (int32_t) (b * R + c);
} else if (key[j] == thr) {
for (int c = 0; c < w && eq_left > 0; ++c, --eq_left) out[wpos++] = (int32_t) (b * R + c);
}
}
}
// ---- a query with more blocks than the register kernel holds (contexts past 4 * 1024 * TK_PER cells): the register
// kernel's threads, per-warp histograms and warp scans, with each key read from memory again on every pass. A
// histogram has no order, so on the four radix passes thread t reads blocks t, t + 1024, ...: a warp reads 32
// neighbours at a time. The cells are emitted ascending in the order (warp, row, lane): warp w holds the `per` rows
// of 32 consecutive blocks from block w * 32 * per. block_topk_kernel's selection rule (radix threshold, ties to the
// lowest index): identical ids.
// campaign3: also compiled on HIP (gfx11: plain shared/atomic code, no sm_90 features; the dispatch still needs
// reach > fit, i.e. the deep contexts where the ref radix was the only option on AMD).
constexpr int TS_MAXQ = 4096;
__device__ int g_tk_fail[TS_MAXQ]; // block_topk_sample_kernel: 1 = the query is block_topk_wide_kernel<true>'s
template <bool ONLY_FAILED = false>
__global__ void __launch_bounds__(TK_T) block_topk_wide_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
if (ONLY_FAILED && !g_tk_fail[blockIdx.x]) return;
__shared__ int hist[TK_T / 32][256];
__shared__ int s_gt[TK_T / 32], s_eq[TK_T / 32];
__shared__ int s_digit, s_above;
const int64_t qi = blockIdx.x;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + qi * cap;
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
if (n_kv <= width) {
for (int64_t j = t; j < n_kv; j += TK_T) out[j] = (int32_t) j;
return;
}
const float* sc = scores + qi * max_blocks;
const int64_t nb = n_bid + 1;
const int64_t per = (nb + TK_T - 1) / TK_T; // rows of 32 blocks per warp
auto weight = [&](int64_t b) -> int { return b < n_bid ? R : (int) (n_kv - n_bid * R); };
uint32_t prefix = 0;
int above = 0;
for (int shift = 24; shift >= 0; shift -= 8) {
for (int i = lane; i < 256; i += 32) hist[warp][i] = 0;
__syncwarp();
const uint32_t hi_mask = shift == 24 ? 0u : (0xffffffffu << (shift + 8));
for (int64_t b = t; b < nb; b += TK_T) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if ((k & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[warp][(k >> shift) & 255], w);
}
__syncthreads();
if (t < 256) { // fold the warps' histograms into warp 0's
int sum = 0;
for (int w2 = 0; w2 < TK_T / 32; ++w2) sum += hist[w2][t];
hist[0][t] = sum;
}
__syncthreads();
if (t == 0) {
int cum = above, d = 255;
for (; d > 0; --d) {
if (cum + hist[0][d] >= width) break;
cum += hist[0][d];
}
s_digit = d;
s_above = cum;
}
__syncthreads();
prefix |= (uint32_t) s_digit << shift;
above = s_above;
__syncthreads();
}
const uint32_t thr = prefix;
const int eq_budget = (int) (width - above); // cells equal to thr that fit, lowest index first
const int64_t w0 = (int64_t) warp * 32 * per;
int gt = 0, eq = 0;
for (int64_t b = w0 + lane; b < nb && b < w0 + 32 * per; b += 32) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k > thr) gt += w;
else if (k == thr) eq += w;
}
#pragma unroll
for (int o = 16; o > 0; o >>= 1) {
gt += __shfl_xor_sync(0xffffffffu, gt, o);
eq += __shfl_xor_sync(0xffffffffu, eq, o);
}
if (lane == 0) { s_gt[warp] = gt; s_eq[warp] = eq; }
__syncthreads();
if (t == 0) { // per warp: the selected cells and the tied cells before it
int eb = 0, sb = 0;
for (int w2 = 0; w2 < TK_T / 32; ++w2) {
const int g2 = s_gt[w2], e2 = s_eq[w2];
const int take = eq_budget - eb < 0 ? 0 : (eq_budget - eb > e2 ? e2 : eq_budget - eb);
s_gt[w2] = sb;
s_eq[w2] = eb;
sb += g2 + take;
eb += e2;
}
}
__syncthreads();
int run_sel = s_gt[warp], run_eq = s_eq[warp];
for (int64_t r0 = w0; r0 < nb && r0 < w0 + 32 * per; r0 += 32) {
const int64_t b = r0 + lane;
const int w = b < nb ? weight(b) : 0;
const uint32_t k = w ? order_key(sc[b]) : 0u;
const int my_gt = (w && k > thr) ? w : 0, my_eq = (w && k == thr) ? w : 0;
if (__ballot_sync(0xffffffffu, (my_gt | my_eq) != 0) == 0u) continue; // a row without a selected block
int pe = my_eq; // tied cells up to and with this lane
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, pe, o);
if (lane >= o) pe += y;
}
const int left = eq_budget - (run_eq + pe - my_eq);
const int take = left < 0 ? 0 : (left > my_eq ? my_eq : left);
const int my_sel = my_gt + take;
int ps = my_sel;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, ps, o);
if (lane >= o) ps += y;
}
int32_t* dst = out + run_sel + ps - my_sel;
for (int c = 0; c < my_sel; ++c) dst[c] = (int32_t) (b * R + c);
run_eq += __shfl_sync(0xffffffffu, pe, 31);
run_sel += __shfl_sync(0xffffffffu, ps, 31);
}
}
// Block scores with every key block read ONCE for all of a call's queries (block_scores_kernel's grid is
// (max_blocks / 8) x nq: ~24,600 mostly-idle blocks per layer at a decode window, each key re-read per query). A fixed
// grid strides over the blocks; per (block, query) the same arithmetic in the same order as block_scores_kernel.
// qsa_block_scores takes it for every call without an active-block count and at most MQ queries: the captured decode
// window, the uncaptured decode, and prefill's pooled16 call.
constexpr int MQ = 8;
__device__ __forceinline__ void block_scores_multi_body(const float* __restrict__ pooled,
const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int nq, int64_t max_blocks,
float* __restrict__ out, bool early_exit,
const QsaScoreRows& srow) {
__shared__ __align__(16) float qs[MQ * IDX_HEADS * IDX_DIM];
__shared__ int64_t s_nkv[MQ], s_nbid[MQ];
if (!early_exit)
for (int i = threadIdx.x; i < nq * IDX_HEADS * IDX_DIM; i += blockDim.x) qs[i] = q_idx[i];
if (threadIdx.x < nq) {
s_nkv[threadIdx.x] = steps[threadIdx.x * kStepCount + kStepNKv];
s_nbid[threadIdx.x] = steps[threadIdx.x * kStepCount + kStepNBid];
}
__syncthreads();
int64_t top = 0;
for (int q = 0; q < nq; ++q) top = s_nbid[q] > top ? s_nbid[q] : top;
if (early_exit) {
// (#783, stuchapin909) a CTA whose first block is past the batch's largest n_bid has no work: the grid is a
// fixed 256 CTAs and a decode window reaches only a few of them, so those return before staging the queries.
// Every thread of the CTA takes the same branch (top and blockIdx are CTA-uniform), so the barrier is safe.
if ((int64_t) blockIdx.x * SCORE_WARPS > top) return;
for (int i = threadIdx.x; i < nq * IDX_HEADS * IDX_DIM; i += blockDim.x) qs[i] = q_idx[i];
__syncthreads();
}
const int lane = threadIdx.x & 31;
const int64_t wstride = (int64_t) gridDim.x * SCORE_WARPS;
for (int64_t b = (int64_t) blockIdx.x * SCORE_WARPS + (threadIdx.x >> 5); b <= top && b < max_blocks; b += wstride) {
// srow.n > 0: each query reads its own sequence's keys; else one set of keys for every query
const bool own = srow.n > 0;
const float4 kp = own ? float4{} : *reinterpret_cast<const float4*>(pooled + b * IDX_DIM + lane * 4);
const float4 kd = own ? float4{} : *reinterpret_cast<const float4*>(dead + lane * 4);
for (int qi = 0; qi < nq; ++qi) {
const int64_t n_bid = s_nbid[qi];
if (b > n_bid) continue;
const float4 k4 = !own ? ((b == n_bid) ? kd : kp)
: (b == n_bid) ? *reinterpret_cast<const float4*>(srow.dead[qi] + lane * 4)
: *reinterpret_cast<const float4*>(srow.pooled[qi] + b * IDX_DIM + lane * 4);
const float* q = qs + qi * IDX_HEADS * IDX_DIM + lane * 4;
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float4 q4 = *reinterpret_cast<const float4*>(q + h * IDX_DIM);
float d = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
#pragma unroll
for (int o = 16; o > 0; o >>= 1) d += __shfl_xor_sync(0xffffffffu, d, o);
score += d > 0.0f ? d : 0.0f;
}
if (lane == 0) {
if (b == n_bid && s_nkv[qi] % R != 0) score += 1e9f;
out[qi * max_blocks + b] = score;
}
}
}
}
__global__ void __launch_bounds__(SCORE_WARPS * 32) block_scores_multi_kernel(const float* __restrict__ pooled,
const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int nq,
int64_t max_blocks, float* __restrict__ out,
bool early_exit, QsaScoreRows srow = {}) {
block_scores_multi_body(pooled, dead, q_idx, steps, nq, max_blocks, out, early_exit, srow);
}
// Queries of different slots, each with its own indexer keys: blockIdx.y is the query, and its CTAs run exactly the
// single-query call of block_scores_multi_kernel (qsa_block_scores_slots).
struct ScoreSlotKeys {
const float* pooled[MQ];
const float* dead[MQ];
};
__global__ void __launch_bounds__(SCORE_WARPS * 32) block_scores_slots_kernel(ScoreSlotKeys keys,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps,
int64_t max_blocks, float* __restrict__ out,
bool early_exit) {
const unsigned z = blockIdx.y;
// the slot's pointers picked by unrolled selects: indexing the argument array by z would copy it to local memory
const float* pooled = keys.pooled[0];
const float* dead = keys.dead[0];
#pragma unroll
for (unsigned i = 1; i < MQ; ++i)
if (z == i) { pooled = keys.pooled[i]; dead = keys.dead[i]; }
block_scores_multi_body(pooled, dead, q_idx + (size_t) z * IDX_HEADS * IDX_DIM,
steps + (size_t) z * kStepCount, 1, max_blocks, out + (size_t) z * max_blocks, early_exit,
QsaScoreRows{});
}
// QSAROWS (docs/QSAROWS.md, STRATA_QSA_ROWS=1): block_scores_multi_kernel's work for NQ <= 4 queries with less issue
// pressure per (block, query). nsys of a 131k decode window (RTX 2080 Ti + RTX 3060): the multi kernel costs ~20 us more a
// call for every row of the window on both cards - per (block, query) it reads the four query slices from shared memory
// (4 x LDS.128) and reduces each head's lane products with its own five shuffles (20 a block and query), and those two
// pipes bound it, not the key reads (the keys are read once for all the queries, as there). Here (1) the lane's slices
// of the NQ queries (4 heads x 4 floats each) live in registers for the whole kernel, (2) the four heads' lane products
// are reduce-scattered with warp_sum's pairing (xor 16, 8, then 4, 2, 1: six shuffles for the four heads) and gathered
// to lane 0 in head order (three more). Every sum adds the same two operands as block_scores_kernel's warp_sum at the
// same level (float add commutes), the dot expression is the same text in the same file, the relu-and-add runs over the
// heads in the same order: the same score bits. The tail block and the +1e9 are as in the multi kernel.
template <int NQ>
__global__ void __launch_bounds__(SCORE_WARPS * 32) block_scores_rows_kernel(const float* __restrict__ pooled,
const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int nq,
int64_t max_blocks, float* __restrict__ out) {
__shared__ int64_t s_nkv[NQ], s_nbid[NQ];
if (threadIdx.x < nq) {
s_nkv[threadIdx.x] = steps[threadIdx.x * kStepCount + kStepNKv];
s_nbid[threadIdx.x] = steps[threadIdx.x * kStepCount + kStepNBid];
}
__syncthreads();
int64_t top = 0;
for (int q = 0; q < nq; ++q) top = s_nbid[q] > top ? s_nbid[q] : top;
if ((int64_t) blockIdx.x * SCORE_WARPS > top) return; // the multi kernel's early exit (CTA-uniform)
const int lane = threadIdx.x & 31;
float4 qr[NQ][IDX_HEADS];
#pragma unroll
for (int qi = 0; qi < NQ; ++qi)
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h)
qr[qi][h] = qi < nq ? *reinterpret_cast<const float4*>(q_idx + qi * IDX_HEADS * IDX_DIM + h * IDX_DIM + lane * 4)
: make_float4(0.f, 0.f, 0.f, 0.f);
const float4 kd = *reinterpret_cast<const float4*>(dead + lane * 4);
const bool hi16 = (lane & 16) != 0, hi8 = (lane & 8) != 0;
const int64_t wstride = (int64_t) gridDim.x * SCORE_WARPS;
for (int64_t b = (int64_t) blockIdx.x * SCORE_WARPS + (threadIdx.x >> 5); b <= top && b < max_blocks; b += wstride) {
const float4 kp = *reinterpret_cast<const float4*>(pooled + b * IDX_DIM + lane * 4);
#pragma unroll
for (int qi = 0; qi < NQ; ++qi) {
if (qi >= nq) break;
const int64_t n_bid = s_nbid[qi];
if (b > n_bid) continue;
const float4 k4 = (b == n_bid) ? kd : kp;
float d[IDX_HEADS];
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float4 q4 = qr[qi][h];
d[h] = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
}
// reduce-scatter: after xor 16 the lane keeps heads {0,1} (bit 4 clear) or {2,3}; after xor 8 one head
float r2[2];
#pragma unroll
for (int i = 0; i < 2; ++i)
r2[i] = (hi16 ? d[i + 2] : d[i]) + __shfl_xor_sync(0xffffffffu, hi16 ? d[i] : d[i + 2], 16);
float r = (hi8 ? r2[1] : r2[0]) + __shfl_xor_sync(0xffffffffu, hi8 ? r2[0] : r2[1], 8);
r += __shfl_xor_sync(0xffffffffu, r, 4);
r += __shfl_xor_sync(0xffffffffu, r, 2);
r += __shfl_xor_sync(0xffffffffu, r, 1);
// lane 8h holds head h's full sum: gather to lane 0 and add the relus in head order, as the warp kernel
const float s1 = __shfl_sync(0xffffffffu, r, 8);
const float s2 = __shfl_sync(0xffffffffu, r, 16);
const float s3 = __shfl_sync(0xffffffffu, r, 24);
if (lane == 0) {
float score = 0.0f;
score += r > 0.0f ? r : 0.0f;
score += s1 > 0.0f ? s1 : 0.0f;
score += s2 > 0.0f ? s2 : 0.0f;
score += s3 > 0.0f ? s3 : 0.0f;
if (b == n_bid && s_nkv[qi] % R != 0) score += 1e9f;
out[qi * max_blocks + b] = score;
}
}
}
}
#if defined(__HIPCC__)
// Optional gfx1100 port of PR1825 (14bf3215): same FP32 expression and reduction tree.
// Decode and the original top-k stay unchanged. No additional persistent weight/state allocation.
constexpr int TS_Q = 64; // queries per CTA (8 per wave, four lanes per query)
constexpr int TS_KB = 32; // key blocks per shared-memory tile
constexpr int TS_BR = 512; // key blocks per CTA
__device__ __forceinline__ float ts_part(const float4 k4, const float4 q4) {
return k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w; // block_scores_kernel's per-lane expression
}
__global__ void __launch_bounds__(256, 1) block_scores_thread_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
__shared__ __align__(16) float4 ks[TS_KB][IDX_DIM / 4];
__shared__ float so[TS_Q][TS_KB + 1];
__shared__ int64_t s_nbid[TS_Q];
// Four lanes per query, lane j (0..3) one quarter of the tree for all four heads: the partials c[j] of lane 0's
// xor-shuffle sum combine groups j, j+16, j+8, j+24, j+4, j+20, j+12, j+28, and only then do the quarters meet
// (c0 + c2, c1 + c3, then their sum) - two shuffles here. A key load now feeds four heads: four times fewer
// shared-memory loads per FMA. The MIO-pipe motivation was measured by PR1825 on NVIDIA.
constexpr int QG[8] = {0, 16, 8, 24, 4, 20, 12, 28};
const int t = threadIdx.x, lane = t & 31;
const int ql = (t >> 5) * 8 + (lane >> 2), j4 = lane & 3; // this lane's query (in the CTA) and quarter
const int64_t q0 = (int64_t) blockIdx.y * TS_Q, qi = q0 + ql;
if (t < TS_Q) s_nbid[t] = q0 + t < nq ? steps[(q0 + t) * kStepCount + kStepNBid] : -1;
float4 qv[IDX_HEADS][8];
{
const float4* src = reinterpret_cast<const float4*>(q_idx + (qi < nq ? qi : 0) * IDX_HEADS * IDX_DIM);
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h)
#pragma unroll
for (int m = 0; m < 8; ++m) qv[h][m] = src[h * (IDX_DIM / 4) + j4 + QG[m]];
}
__syncthreads();
int64_t top = -1; // the largest n_bid of the CTA's queries: blocks at or past it are never written here
for (int i = 0; i < TS_Q; ++i) top = s_nbid[i] > top ? s_nbid[i] : top;
const int64_t b_lo = (int64_t) blockIdx.x * TS_BR;
int64_t b_hi = b_lo + TS_BR;
if (b_hi > reach) b_hi = reach;
if (b_hi > top) b_hi = top;
if (b_hi > max_blocks) b_hi = max_blocks;
for (int64_t b0 = b_lo; b0 < b_hi; b0 += TS_KB) {
const int nb = (int) (b_hi - b0 < TS_KB ? b_hi - b0 : TS_KB);
__syncthreads(); // the previous tile's reads of ks and so are done
for (int i = t; i < nb * (IDX_DIM / 4); i += blockDim.x)
ks[i / (IDX_DIM / 4)][i % (IDX_DIM / 4)] = reinterpret_cast<const float4*>(pooled + (b0 + i / (IDX_DIM / 4)) * IDX_DIM)[i % (IDX_DIM / 4)];
__syncthreads();
for (int j = 0; j < nb; ++j) {
float4 kk[8];
#pragma unroll
for (int m = 0; m < 8; ++m) kk[m] = ks[j][j4 + QG[m]];
float e[IDX_HEADS];
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float c = ((ts_part(kk[0], qv[h][0]) + ts_part(kk[1], qv[h][1])) +
(ts_part(kk[2], qv[h][2]) + ts_part(kk[3], qv[h][3]))) +
((ts_part(kk[4], qv[h][4]) + ts_part(kk[5], qv[h][5])) +
(ts_part(kk[6], qv[h][6]) + ts_part(kk[7], qv[h][7])));
const float d = c + __shfl_xor_sync(0xffffffffu, c, 2); // lane 0: c0 + c2, lane 1: c1 + c3
e[h] = d + __shfl_xor_sync(0xffffffffu, d, 1); // lane 0: (c0 + c2) + (c1 + c3)
}
if (j4 == 0) {
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) score += e[h] > 0.0f ? e[h] : 0.0f;
so[ql][j] = score;
}
}
__syncthreads();
for (int i = t; i < TS_Q * nb; i += blockDim.x) {
const int q = i / nb, j = i % nb;
if (b0 + j < s_nbid[q]) out[(q0 + q) * max_blocks + b0 + j] = so[q][j];
}
}
}
// The exact scorer runs on gfx1100 (the PR's own card) when STRATA_SCORES_THREAD=1, and on gfx12 (RDNA4) unless STRATA_SCORES_THREAD=0:
// there it is bitwise equal to the warp scorer on an R9700 (qsa_scores_gfx1100_parity --full, 35 cases; exact_pp residual dumps at 70K and
// 131K tokens) and 3.6-4.4x faster in the scorer stage, +8% (131K) to +15% (230K) on a prompt read. Other wave32 parts have no measurement.
// Returns 0 (not offered), 1 (gfx1100: only on request), 2 (gfx12: the default).
int scores_thread_arch() {
int device = -1;
if (cudaGetDevice(&device) != cudaSuccess) { cudaGetLastError(); return 0; }
static thread_local int cached_device = -1;
static thread_local int arch = 0;
if (device != cached_device) {
cudaDeviceProp properties{};
arch = 0;
if (cudaGetDeviceProperties(&properties, device) == cudaSuccess)
arch = gfx_arch_is_gfx12(properties.gcnArchName) ? 2 : gfx_arch_is(properties.gcnArchName, "gfx1100") ? 1 : 0;
cached_device = device;
cudaGetLastError();
}
return arch;
}
#endif
#if !defined(__HIPCC__)
// ---- prompt calls on cards without the tensor-core scorer (Turing): block_scores_kernel's scores, BITWISE, with a
// thread per (query, head) instead of a warp per (query, block). There a warp spends 20 shuffles and five 512-byte
// loads per score; here a lane holds its query head (128 floats) in registers, every lane of the warp reads the same
// key from shared memory (a broadcast), and the 4-value partials are added in the tree lane 0 of the xor-shuffle sum
// computes: partial g covers values 4g..4g+3, level o adds g and g + o. Float addition is commutative, so the same
// pairs in the same tree give the same bits. The heads are then summed 0..3 from 0.0f as there. Blocks < n_bid only:
// the tail block n_bid (the `dead` key, +1e9) is block_scores_tail_kernel's.
constexpr int TS_Q = 64; // queries per CTA (8 per warp, a lane per query head)
constexpr int TS_KB = 32; // key blocks per shared-memory tile
constexpr int TS_BR = 512; // key blocks per CTA
__device__ __forceinline__ float ts_part(const float4 k4, const float4 q4) {
return k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w; // block_scores_kernel's per-lane expression
}
__global__ void __launch_bounds__(256, 1) block_scores_thread_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t nq,
int64_t max_blocks, int64_t reach,
float* __restrict__ out) {
__shared__ __align__(16) float4 ks[TS_KB][IDX_DIM / 4];
__shared__ float so[TS_Q][TS_KB + 1];
__shared__ int64_t s_nbid[TS_Q];
// Four lanes per query, lane j (0..3) one quarter of the tree for all four heads: the partials c[j] of lane 0's
// xor-shuffle sum combine groups j, j+16, j+8, j+24, j+4, j+20, j+12, j+28, and only then do the quarters meet
// (c0 + c2, c1 + c3, then their sum) - two shuffles here. A key load now feeds four heads: four times fewer
// shared-memory loads per FMA (the kernel was bound by the MIO pipe, ncu: mio_throttle first).
constexpr int QG[8] = {0, 16, 8, 24, 4, 20, 12, 28};
const int t = threadIdx.x, lane = t & 31;
const int ql = (t >> 5) * 8 + (lane >> 2), j4 = lane & 3; // this lane's query (in the CTA) and quarter
const int64_t q0 = (int64_t) blockIdx.y * TS_Q, qi = q0 + ql;
if (t < TS_Q) s_nbid[t] = q0 + t < nq ? steps[(q0 + t) * kStepCount + kStepNBid] : -1;
float4 qv[IDX_HEADS][8];
{
const float4* src = reinterpret_cast<const float4*>(q_idx + (qi < nq ? qi : 0) * IDX_HEADS * IDX_DIM);
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h)
#pragma unroll
for (int m = 0; m < 8; ++m) qv[h][m] = src[h * (IDX_DIM / 4) + j4 + QG[m]];
}
__syncthreads();
int64_t top = -1; // the largest n_bid of the CTA's queries: blocks at or past it are never written here
for (int i = 0; i < TS_Q; ++i) top = s_nbid[i] > top ? s_nbid[i] : top;
const int64_t b_lo = (int64_t) blockIdx.x * TS_BR;
int64_t b_hi = b_lo + TS_BR;
if (b_hi > reach) b_hi = reach;
if (b_hi > top) b_hi = top;
if (b_hi > max_blocks) b_hi = max_blocks;
for (int64_t b0 = b_lo; b0 < b_hi; b0 += TS_KB) {
const int nb = (int) (b_hi - b0 < TS_KB ? b_hi - b0 : TS_KB);
__syncthreads(); // the previous tile's reads of ks and so are done
for (int i = t; i < nb * (IDX_DIM / 4); i += blockDim.x)
ks[i / (IDX_DIM / 4)][i % (IDX_DIM / 4)] = reinterpret_cast<const float4*>(pooled + (b0 + i / (IDX_DIM / 4)) * IDX_DIM)[i % (IDX_DIM / 4)];
__syncthreads();
for (int j = 0; j < nb; ++j) {
float4 kk[8];
#pragma unroll
for (int m = 0; m < 8; ++m) kk[m] = ks[j][j4 + QG[m]];
float e[IDX_HEADS];
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
const float c = ((ts_part(kk[0], qv[h][0]) + ts_part(kk[1], qv[h][1])) +
(ts_part(kk[2], qv[h][2]) + ts_part(kk[3], qv[h][3]))) +
((ts_part(kk[4], qv[h][4]) + ts_part(kk[5], qv[h][5])) +
(ts_part(kk[6], qv[h][6]) + ts_part(kk[7], qv[h][7])));
const float d = c + __shfl_xor_sync(0xffffffffu, c, 2); // lane 0: c0 + c2, lane 1: c1 + c3
e[h] = d + __shfl_xor_sync(0xffffffffu, d, 1); // lane 0: (c0 + c2) + (c1 + c3)
}
if (j4 == 0) {
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) score += e[h] > 0.0f ? e[h] : 0.0f;
so[ql][j] = score;
}
}
__syncthreads();
for (int i = t; i < TS_Q * nb; i += blockDim.x) {
const int q = i / nb, j = i % nb;
if (b0 + j < s_nbid[q]) out[(q0 + q) * max_blocks + b0 + j] = so[q][j];
}
}
}
#endif
#if !defined(__HIPCC__)
// ---- the decode top-k on a thread-block cluster (sm_90+; S19). One CTA per query (block_topk_reg_kernel, or
// block_topk_kernel above 33,792 blocks: a --max-context over ~135K) makes four radix passes and two scans over up to
// 65,538 blocks on ONE SM while the rest of the GPU idles - a decode window has 1-5 queries. Here a cluster of CL_N
// CTAs shares a query: CTA r holds the keys of blocks [r * per, (r + 1) * per) in shared memory, builds the digit
// histogram of its keys, and PUSHES it into slot r of every CTA's `hin` (distributed shared memory); after one cluster
// barrier each CTA sums the CL_N slots itself, so all of them take the same digit. The emit pass needs each CTA's
// cells above / at the threshold: pushed the same way, then each CTA offsets its own by the ranks before it.
// RTX 5070, per call at capacity = context (decode_cluster_parity --bench): 21.9 -> 15.6 us at 32K, 58 -> 18 at 128K,
// 200 -> 22 at 262K (the one-CTA kernels' digit search was serial, too: one thread over 256 bins per pass).
//
// IDENTICAL IDS, by construction rather than by luck: the threshold thr (the width-th largest key, cells counted with
// their weights) and `above` (cells with a larger key) are pure functions of the multiset of (key, weight) - integer
// histograms, summed in any order - and the digit rule is block_topk_kernel's, written as a scan (the largest digit d
// whose cells at or above it reach `need`; 0 when none). The cells emitted are then fixed: every cell of a block with
// key > thr, and the first eq_budget = width - above cells at thr in ascending order (a block at thr may be cut),
// written in ascending cell order. Position of a thread's first cell = (cells above thr before it) + min(cells at thr
// before it, eq_budget): the telescoped sum of the reference's per-thread clamp. NaN keys are 0 (order_key) as there.
//
// Barriers: barrier.cluster arrive / wait (each CTA's threads all take part; it also orders the CTA's own shared
// memory, so it doubles as __syncthreads). Phase 0 is a relaxed arrive at entry, waited before the first remote store
// (a CTA's shared memory exists once it runs). Pushes go out before the arrive that releases them, and nothing reads
// another CTA's memory after the last wait - so a CTA may exit without a closing barrier (a wait counts the threads
// that have not exited). `hin` alternates by pass parity: CTA x reads slot buffer p&1 in pass p before arriving at
// pass p+1's barrier, and nobody writes buffer p&1 again (pass p+2) before waiting on that barrier.
constexpr int CL_N = 8; // CTAs per query (the portable cluster size)
constexpr int CL_T = 1024; // threads per CTA
constexpr int CL_MAXQ = 16; // larger calls (prefill sub-batches) fill the GPU with one CTA per query already
#if defined(__CUDA_ARCH__) && __CUDA_ARCH__ >= 900
#define STRATA_SEL_CLUSTER 1
#else
#define STRATA_SEL_CLUSTER 0 // an older target's code is a trap; qsa_block_topk_cluster never launches it there
#endif
#if STRATA_SEL_CLUSTER
__device__ __forceinline__ void cl_arrive_relaxed() {
asm volatile("barrier.cluster.arrive.relaxed.aligned;\n" ::: "memory");
}
__device__ __forceinline__ void cl_arrive() { asm volatile("barrier.cluster.arrive.release.aligned;\n" ::: "memory"); }
__device__ __forceinline__ void cl_wait() { asm volatile("barrier.cluster.wait.acquire.aligned;\n" ::: "memory"); }
__device__ __forceinline__ unsigned cl_rank() {
unsigned r;
asm volatile("mov.u32 %0, %%cluster_ctarank;\n" : "=r"(r));
return r;
}
template <typename T> __device__ __forceinline__ T* cl_map(T* p, unsigned rank) { // p in CTA `rank`'s shared memory
uint64_t o;
asm volatile("mapa.u64 %0, %1, %2;\n" : "=l"(o) : "l"((uint64_t) p), "r"(rank));
return reinterpret_cast<T*>(o);
}
// exclusive block scan of a 64-bit value over CL_T threads; `total` = the CTA's sum
__device__ __forceinline__ unsigned long long cl_excl_scan64(unsigned long long v, unsigned long long* s_warp,
unsigned long long& total) {
const int lane = threadIdx.x & 31, warp = threadIdx.x >> 5;
unsigned long long x = v;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const unsigned long long y = __shfl_up_sync(0xffffffffu, x, o);
if (lane >= o) x += y;
}
if (lane == 31) s_warp[warp] = x;
__syncthreads();
if (warp == 0) {
const unsigned long long w = s_warp[lane];
unsigned long long z = w;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const unsigned long long y = __shfl_up_sync(0xffffffffu, z, o);
if (lane >= o) z += y;
}
s_warp[lane] = z - w;
if (lane == 31) s_warp[32] = z;
}
__syncthreads();
total = s_warp[32];
return s_warp[warp] + x - v;
}
#endif
// grid (CL_N, nq), cluster (CL_N, 1, 1), CL_T threads, dynamic shared memory: ceil(max_blocks / CL_N) keys
__global__ void __launch_bounds__(CL_T) block_topk_cluster_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
#if STRATA_SEL_CLUSTER
extern __shared__ uint32_t keys[]; // this CTA's blocks' keys
__shared__ __align__(16) int hin[2][CL_N][256]; // the cluster's histograms, slot = the pushing rank
__shared__ __align__(16) int hloc[2][256]; // this CTA's histogram
__shared__ unsigned long long cnt[CL_N]; // per rank: its cells above thr (low 32 bits) and at it (high)
__shared__ unsigned long long s_warp[33];
__shared__ uint32_t s_prefix;
__shared__ int s_above;
const unsigned rank = cl_rank();
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
cl_arrive_relaxed(); // phase 0: this CTA runs
const int64_t qi = blockIdx.y;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + qi * cap;
if (n_kv <= width) { // the identity, split over the cluster; no remote access
for (int64_t j = (int64_t) rank * CL_T + t; j < n_kv; j += (int64_t) CL_N * CL_T) out[j] = (int32_t) j;
return;
}
// the tail block n_bid weighs its cells (0..3); with none it is not a candidate (the reference skips w == 0)
const int wtail = (int) (n_kv - n_bid * R);
const int64_t nbe = n_bid + (wtail > 0 ? 1 : 0);
const int64_t per = (nbe + CL_N - 1) / CL_N; // <= ceil(max_blocks / CL_N), the keys the host sized
const int64_t lo = (int64_t) rank * per < nbe ? (int64_t) rank * per : nbe;
const int64_t hi = lo + per < nbe ? lo + per : nbe;
const int n = (int) (hi - lo);
const int tail_i = (wtail > 0 && n_bid >= lo && n_bid < hi) ? (int) (n_bid - lo) : -1;
const float* sc = scores + qi * max_blocks + lo;
for (int i = t; i < n; i += CL_T) keys[i] = order_key(sc[i]);
for (int i = t; i < 2 * 256; i += CL_T) (&hloc[0][0])[i] = 0;
__syncthreads();
uint32_t prefix = 0;
int above = 0; // cells strictly above the digits fixed so far
for (int pass = 0; pass < 4; ++pass) {
const int shift = 24 - 8 * pass;
const uint32_t hmask = pass == 0 ? 0u : (0xffffffffu << (shift + 8));
int* hl = hloc[pass & 1];
// warp-aggregated: the scores share their top bits, so plain atomics would queue on a few bins
for (int i0 = 0; i0 < n; i0 += CL_T) {
const int i = i0 + t;
int bin = -1;
if (i < n) {
const uint32_t k = keys[i];
if ((k & hmask) == prefix) bin = (int) ((k >> shift) & 255);
}
const unsigned same = __match_any_sync(0xffffffffu, bin);
if (bin >= 0 && lane == __ffs(same) - 1) atomicAdd(&hl[bin], __popc(same) * R);
if (bin >= 0 && i == tail_i) atomicAdd(&hl[bin], wtail - R);
}
__syncthreads();
if (pass == 0) cl_wait(); // phase 0 done: every CTA's shared memory is there
for (int i = t; i < CL_N * 64; i += CL_T) { // the histogram into slot `rank` of every CTA, as int4
const int dst = i >> 6, c = i & 63;
*cl_map(reinterpret_cast<int4*>(&hin[pass & 1][rank][0]) + c, (unsigned) dst) =
reinterpret_cast<const int4*>(hl)[c];
}
for (int i = t; i < 256; i += CL_T) hloc[(pass + 1) & 1][i] = 0;
cl_arrive();
cl_wait();
if (warp == 0) {
// lane L owns digits 255 - 8L down to 248 - 8L; the digit holding the need-th cell from the top
const int need = (int) width - above;
int tot[8], part = 0;
#pragma unroll
for (int k = 0; k < 8; ++k) {
const int d = 255 - 8 * lane - k;
int v = 0;
#pragma unroll
for (int r = 0; r < CL_N; ++r) v += hin[pass & 1][r][d];
tot[k] = v;
part += v;
}
int incl = part;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, incl, o);
if (lane >= o) incl += y;
}
const int excl = incl - part;
const unsigned hit = __ballot_sync(0xffffffffu, excl < need && incl >= need);
// no hit cannot happen (the cells total n_kv > width); the reference would then take digit 0
const int who = hit ? __ffs(hit) - 1 : 31;
if (lane == who) {
int acc = excl, k = 0;
for (; k < 7; ++k) {
if (acc + tot[k] >= need) break;
acc += tot[k];
}
s_prefix = prefix | ((uint32_t) (255 - 8 * lane - k) << shift);
s_above = above + acc;
}
}
__syncthreads();
prefix = s_prefix;
above = s_above;
}
const uint32_t thr = prefix;
const int64_t eq_budget = width - above; // cells at thr that fit, lowest index first
// each thread a contiguous run of the CTA's keys; an odd run length keeps the shared reads conflict-free
int seg = (n + CL_T - 1) / CL_T;
if ((seg & 1) == 0 && seg > 0) ++seg;
const int s0 = t * seg < n ? t * seg : n, s1 = s0 + seg < n ? s0 + seg : n;
uint32_t gt = 0, eq = 0;
for (int i = s0; i < s1; ++i) {
const uint32_t k = keys[i], w = i == tail_i ? (uint32_t) wtail : (uint32_t) R;
if (k > thr) gt += w;
else if (k == thr) eq += w;
}
unsigned long long cta;
const unsigned long long before =
cl_excl_scan64((unsigned long long) gt | ((unsigned long long) eq << 32), s_warp, cta);
if (t < CL_N) *cl_map(&cnt[rank], (unsigned) t) = cta;
cl_arrive();
cl_wait();
int64_t gt_off = 0, eq_off = 0;
for (unsigned r = 0; r < rank; ++r) {
gt_off += (int64_t) (cnt[r] & 0xffffffffu);
eq_off += (int64_t) (cnt[r] >> 32);
}
const int64_t eq_before = eq_off + (int64_t) (before >> 32);
int64_t wpos = gt_off + (int64_t) (before & 0xffffffffu) + (eq_before < eq_budget ? eq_before : eq_budget);
int64_t eq_left = eq_budget - eq_before;
if (eq_left < 0) eq_left = 0;
for (int i = s0; i < s1; ++i) {
const uint32_t k = keys[i];
const int w = i == tail_i ? wtail : R;
const int64_t b = lo + i;
if (k > thr) {
for (int c = 0; c < w; ++c) out[wpos++] = (int32_t) (b * R + c);
} else if (k == thr) {
for (int c = 0; c < w && eq_left > 0; ++c, --eq_left) out[wpos++] = (int32_t) (b * R + c);
}
}
#else
(void) scores; (void) steps; (void) max_blocks; (void) cap; (void) ids;
__trap();
#endif
}
#endif // !__HIPCC__
bool scores_multi_on() {
static const bool on = [] { const char* v = std::getenv("STRATA_SCORES_MULTI"); return v == nullptr || std::atoi(v) != 0; }();
return on;
}
// STRATA_QSA_EARLY_EXIT=0 keeps the old staging (every CTA loads the queries first); the scores are the same bits
bool scores_early_exit() {
static const bool on = [] { const char* v = std::getenv("STRATA_QSA_EARLY_EXIT"); return v == nullptr || std::atoi(v) != 0; }();
return on;
}
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
// STRATA_SELECT_LONG (verify.cpp): the long-context decode select, qsa_block_scores_long / qsa_block_topk_long.
// ---- decode block scores bit for bit block_scores_multi_kernel's, without its shuffles (STRATA_SCORES_DX, default on
// 6.x, under STRATA_SELECT_LONG). The multi kernel gives a block to a warp and pays 5 shuffles per head per (block, query) for 4 products per
// lane: on GP100 a decode window's call costs ~88 us more per query at 300K cells. Here lane i of warp h builds, for
// block i of a 32-block tile and indexer head h, the same 32-leaf tree as block_scores_multi_kernel's xor butterfly (lanes visited in
// 5-bit-reversed order, depth-first: the xor butterfly's association) for every query of the call at once, the key
// staged once per tile in shared memory and read by all of the queries; the relu sum over the heads then runs in the
// warp kernel's order (0 + r0 + r1 + r2 + r3) from shared memory. Blocks < n_bid; the tail block n_bid is
// block_scores_tail_kernel's (the multi kernel's arithmetic for it). A fixed grid strides over the tiles below the
// call's largest n_bid (capturable).
__device__ __forceinline__ int dx_lane(int j) { return (int) (__brev((unsigned) j) >> 27); } // 5-bit reversal
constexpr int DX_NB = 32; // blocks per tile: one per lane
constexpr int DX_T = 32 * IDX_HEADS; // warp h: indexer head h
constexpr int DX_KS = IDX_DIM + 4; // a key row in shared memory (a quarter warp's 16-byte reads: 32 banks)
template <int NQ>
__global__ void __launch_bounds__(DX_T) block_scores_dx_kernel(const float* __restrict__ pooled,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int64_t max_blocks,
float* __restrict__ out) {
extern __shared__ __align__(16) float dx_smem[];
float* Ks = dx_smem; // [DX_NB][DX_KS]
float* Qs = Ks + DX_NB * DX_KS; // [NQ][IDX_HEADS][IDX_DIM]
float* Ds = Qs + NQ * IDX_HEADS * IDX_DIM; // [NQ][IDX_HEADS][DX_NB]: each head's sum, for the relu pass
__shared__ int64_t s_nbid[NQ];
const int t = threadIdx.x, lane = t & 31, h = t >> 5;
if (t < NQ) s_nbid[t] = steps[t * kStepCount + kStepNBid];
__syncthreads();
int64_t top = 0;
#pragma unroll
for (int q = 0; q < NQ; ++q) top = s_nbid[q] > top ? s_nbid[q] : top;
if (top > max_blocks) top = max_blocks;
if ((int64_t) blockIdx.x * DX_NB >= top) return; // CTA-uniform
for (int i = t; i < NQ * IDX_HEADS * IDX_DIM / 4; i += DX_T)
reinterpret_cast<float4*>(Qs)[i] = reinterpret_cast<const float4*>(q_idx)[i];
const float* krow = Ks + lane * DX_KS;
// the next tile's keys in registers while this one is scored (coalesced: thread t row (t + 128 i) / 32, float4 t % 32)
constexpr int PF = DX_NB * (IDX_DIM / 4) / DX_T;
float4 pre[PF];
const int64_t stride = (int64_t) gridDim.x * DX_NB;
auto fetch = [&](int64_t tb) {
#pragma unroll
for (int i = 0; i < PF; ++i) {
const int idx = t + i * DX_T, row = idx / (IDX_DIM / 4), c4 = idx % (IDX_DIM / 4);
pre[i] = tb + row < top ? __ldg(reinterpret_cast<const float4*>(pooled + (tb + row) * IDX_DIM) + c4)
: make_float4(0.f, 0.f, 0.f, 0.f);
}
};
fetch((int64_t) blockIdx.x * DX_NB);
for (int64_t b0 = (int64_t) blockIdx.x * DX_NB; b0 < top; b0 += stride) {
#pragma unroll
for (int i = 0; i < PF; ++i) {
const int idx = t + i * DX_T, row = idx / (IDX_DIM / 4), c4 = idx % (IDX_DIM / 4);
*reinterpret_cast<float4*>(Ks + row * DX_KS + c4 * 4) = pre[i];
}
__syncthreads();
if (b0 + stride < top) fetch(b0 + stride);
float half0[NQ], half1[NQ];
#pragma unroll 1
for (int c = 0; c < 4; ++c) {
float l0[NQ], l1[NQ], l2[NQ];
#pragma unroll
for (int jj = 0; jj < 8; ++jj) {
const int L = dx_lane(8 * c + jj);
const float4 k4 = *reinterpret_cast<const float4*>(krow + L * 4);
#pragma unroll
for (int q = 0; q < NQ; ++q) {
const float4 q4 = *reinterpret_cast<const float4*>(Qs + (q * IDX_HEADS + h) * IDX_DIM + L * 4);
const float d = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
// the depth-first tree over the slice's 8 leaves (pairs, quads, the octet), then the octets
if (jj == 0 || jj == 2 || jj == 4 || jj == 6) l0[q] = d;
else if (jj == 1 || jj == 5) l1[q] = l0[q] + d;
else if (jj == 3) l2[q] = l1[q] + (l0[q] + d);
else {
const float oct = l2[q] + (l1[q] + (l0[q] + d));
if (c == 0) half0[q] = oct;
else if (c == 1) half0[q] = half0[q] + oct;
else if (c == 2) half1[q] = oct;
else half1[q] = half1[q] + oct;
}
}
}
}
#pragma unroll
for (int q = 0; q < NQ; ++q) Ds[(q * IDX_HEADS + h) * DX_NB + lane] = half0[q] + half1[q];
__syncthreads(); // also: every warp is done reading Ks before the next tile
for (int q = h; q < NQ; q += IDX_HEADS) {
const int64_t b = b0 + lane;
if (b >= s_nbid[q]) continue;
float score = 0.0f;
#pragma unroll
for (int hh = 0; hh < IDX_HEADS; ++hh) {
const float d = Ds[(q * IDX_HEADS + hh) * DX_NB + lane];
score += d > 0.0f ? d : 0.0f;
}
out[q * max_blocks + b] = score;
}
}
}
// ---- the decode top-k over several CTAs per query without clusters (any CUDA card; on sm_6x by default under
// STRATA_SELECT_LONG). A decode
// window's 1-5 queries otherwise run one 1,024-thread CTA each (block_topk_wide_kernel past ~135K cells) on one SM
// apiece: on GP100 0.39 ms per call at 300K cells and 1.15 ms at 1M, x12 QSA layers per window. Here each query gets
// n CTAs (a grid of n x nq), CTA r taking blocks [r * per, (r + 1) * per), and the four radix passes, the count and the
// emit are six kernels in a row on the caller's stream - capturable, no co-residency or spin waits: the kernel boundary
// is the barrier. Exchange goes through the caller's scratch (qsa_topk_multi_scratch_ints): pass 0's histograms one
// row per CTA (plain stores), passes 1-3 summed with atomics into rows the pass-0 kernel zeroes, (prefix, above) after
// each digit, and each warp's cells above / at the threshold. Nothing is carried from one call to the next.
// Warp w of a CTA takes the rows [w * rpw, (w + 1) * rpw) of 32 consecutive blocks (lane l block l of a row: coalesced),
// MT_U rows' loads in flight at a time; the loops stay rolled (GP100's instruction cache: a fully unrolled 33-row body
// doubled every kernel's time).
//
// IDENTICAL IDS, as block_topk_cluster_kernel's: thr (the width-th largest key, cells counted with their weights) and
// `above` are pure functions of the integer histograms whatever order they are summed in, and the digit rule is
// block_topk_kernel's (the largest digit d >= 1 whose cells at or above it reach `need`, else 0), here as a 256-thread
// scan. The emit writes every cell of a block above thr and the first eq_budget = width - above cells at thr, ascending
// (block_topk_wide_kernel's row emit, offset by the cells of the warps and CTAs before).
constexpr int MT_T = 256; // threads per CTA
constexpr int MT_W = MT_T / 32; // warps per CTA
constexpr int MT_U = 4; // rows of loads in flight per warp
constexpr int MT_NMAX = 32; // CTAs per query, at most
constexpr int MT_MAXQ = 16; // more queries per call fill the GPU with one CTA each already
// scratch per query (int32): pass 0's rows [MT_NMAX][256], passes 1-3 [3][256], state [5][2], counts [MT_NMAX][MT_W][2]
constexpr int MT_ACC = MT_NMAX * 256, MT_STATE = MT_ACC + 3 * 256, MT_CNT = MT_STATE + 16;
constexpr int MT_Q_INTS = MT_CNT + 2 * MT_NMAX * MT_W + 64;
static_assert(MT_NMAX * MT_W <= MT_T, "the emit sums the earlier CTAs' warp counts one per thread");
struct MtQuery {
int64_t n_kv, n_bid, width, lo, hi, row0; // row0: the first block of this warp's first row
int rpw, wtail;
bool all; // n_kv <= width: every cell, nothing to select
};
__device__ __forceinline__ MtQuery mt_query(const int32_t* __restrict__ steps) {
const int32_t* st = steps + (int64_t) blockIdx.y * kStepCount;
MtQuery m;
m.n_kv = st[kStepNKv];
m.n_bid = st[kStepNBid];
m.width = st[kStepWidth];
m.all = m.n_kv <= m.width;
// the tail block n_bid weighs its cells (0..3); with none it is not a candidate (the reference skips w == 0)
m.wtail = (int) (m.n_kv - m.n_bid * R);
const int64_t nbe = m.n_bid + (m.wtail > 0 ? 1 : 0);
const int64_t per = (nbe + gridDim.x - 1) / gridDim.x;
m.lo = (int64_t) blockIdx.x * per < nbe ? (int64_t) blockIdx.x * per : nbe;
m.hi = m.lo + per < nbe ? m.lo + per : nbe;
m.rpw = (int) (((m.hi - m.lo + 31) / 32 + MT_W - 1) / MT_W);
m.row0 = m.lo + (int64_t) (threadIdx.x >> 5) * m.rpw * 32;
return m;
}
// rows j0 .. j0 + MT_U - 1 of this warp: key[u] for block row0 + 32 (j0 + u) + lane (0 past hi or the warp's rows)
__device__ __forceinline__ void mt_load(const MtQuery& m, const float* __restrict__ sc, int j0, uint32_t (&key)[MT_U]) {
const int lane = threadIdx.x & 31;
#pragma unroll
for (int u = 0; u < MT_U; ++u) {
const int64_t b = m.row0 + 32 * (j0 + u) + lane;
key[u] = (j0 + u < m.rpw && b < m.hi) ? order_key(__ldg(sc + b)) : 0u;
}
}
// inclusive scan of one value per thread over the MT_T threads
template <typename V> __device__ __forceinline__ V mt_incl_scan(V v, V* s_w) {
const int lane = threadIdx.x & 31, warp = threadIdx.x >> 5;
V x = v;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const V y = __shfl_up_sync(0xffffffffu, x, o);
if (lane >= o) x += y;
}
if (lane == 31) s_w[warp] = x;
__syncthreads();
V off = 0;
for (int w = 0; w < warp; ++w) off += s_w[w];
__syncthreads();
return x + off;
}
// The digit at `shift` from the 256 counts (thread t holds digit 255 - t's): block_topk_kernel's rule.
__device__ __forceinline__ void mt_choose(int v, int64_t width, int shift, uint32_t& prefix, int& above, int* s_w,
int* s_ex, int* s_i) {
const int t = threadIdx.x;
if (t == 0) *s_i = 255; // no digit >= 1 reaches it: 0, all of 1..255 above
const int incl = mt_incl_scan(v, s_w);
s_ex[t] = incl - v;
const int64_t need = width - above;
if (t < 255 && incl >= need && incl - v < need) *s_i = t; // the one t where the running count crosses `need`
__syncthreads();
const int i = *s_i;
prefix |= (uint32_t) (255 - i) << shift;
above += s_ex[i];
__syncthreads();
}
// pass PASS's histogram of the CTA's keys under the prefix so far (PASS >= 1 first takes digit PASS - 1)
template <int PASS>
__global__ void __launch_bounds__(MT_T) block_topk_multi_hist_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps,
int64_t max_blocks, int32_t* __restrict__ scratch) {
__shared__ int h[MT_W][256];
__shared__ int s_w[MT_W], s_ex[256], s_i;
const MtQuery m = mt_query(steps);
if (m.all) return;
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
const float* sc = scores + (int64_t) blockIdx.y * max_blocks;
uint32_t key[MT_U];
mt_load(m, sc, 0, key); // in flight while the digit is taken
for (int i = t; i < MT_W * 256; i += MT_T) (&h[0][0])[i] = 0;
int32_t* qs = scratch + (int64_t) blockIdx.y * MT_Q_INTS;
uint32_t prefix = 0;
int above = 0;
if (PASS == 0) {
if (blockIdx.x == 0) // passes 1-3 sum into these: zero them for this call
for (int i = t; i < 3 * 256; i += MT_T) qs[MT_ACC + i] = 0;
} else {
int v = 0;
if (PASS == 1) { // pass 0: one row per CTA
#pragma unroll 8
for (unsigned r = 0; r < gridDim.x; ++r) v += qs[r * 256 + 255 - t];
} else {
prefix = (uint32_t) qs[MT_STATE + 2 * (PASS - 1)];
above = qs[MT_STATE + 2 * (PASS - 1) + 1];
v = qs[MT_ACC + (PASS - 2) * 256 + 255 - t];
}
mt_choose(v, m.width, 32 - 8 * PASS, prefix, above, s_w, s_ex, &s_i);
if (blockIdx.x == 0 && t == 0) {
qs[MT_STATE + 2 * PASS] = (int) prefix;
qs[MT_STATE + 2 * PASS + 1] = above;
}
}
__syncthreads();
const int shift = 24 - 8 * PASS;
const uint32_t hmask = PASS == 0 ? 0u : (0xffffffffu << (shift + 8));
#pragma unroll 1
for (int j0 = 0; j0 < m.rpw; j0 += MT_U) { // uniform over the warp: the ballots see all its lanes
if (j0 > 0) mt_load(m, sc, j0, key);
#pragma unroll
for (int u = 0; u < MT_U; ++u) {
if (j0 + u >= m.rpw) break;
const int64_t b = m.row0 + 32 * (j0 + u) + lane;
const int bin = (b < m.hi && (key[u] & hmask) == prefix) ? (int) ((key[u] >> shift) & 255) : -1;
// the scores share their top bits: the lanes on the first lane's bin in one atomic (no __match_any_sync on 6.x)
const unsigned pend = __ballot_sync(0xffffffffu, bin >= 0);
if (pend) {
const int leader = __ffs(pend) - 1;
const int lb = __shfl_sync(0xffffffffu, bin, leader);
const unsigned same = __ballot_sync(0xffffffffu, bin == lb);
if (lane == leader) atomicAdd(&h[warp][lb], __popc(same) * R);
else if (bin >= 0 && bin != lb) atomicAdd(&h[warp][bin], R);
}
if (bin >= 0 && b == m.n_bid) atomicAdd(&h[warp][bin], m.wtail - R);
}
}
__syncthreads();
int sum = 0;
#pragma unroll
for (int w = 0; w < MT_W; ++w) sum += h[w][t];
if (PASS == 0) qs[blockIdx.x * 256 + t] = sum;
else if (sum != 0) atomicAdd(&qs[MT_ACC + (PASS - 1) * 256 + t], sum);
}
// digit 3 (the threshold), then each warp's cells above it and at it
__global__ void __launch_bounds__(MT_T) block_topk_multi_count_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps,
int64_t max_blocks, int32_t* __restrict__ scratch) {
__shared__ int s_w[MT_W], s_ex[256], s_i;
const MtQuery m = mt_query(steps);
if (m.all) return;
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
const float* sc = scores + (int64_t) blockIdx.y * max_blocks;
uint32_t key[MT_U];
mt_load(m, sc, 0, key);
int32_t* qs = scratch + (int64_t) blockIdx.y * MT_Q_INTS;
uint32_t prefix = (uint32_t) qs[MT_STATE + 6];
int above = qs[MT_STATE + 7];
mt_choose(qs[MT_ACC + 2 * 256 + 255 - t], m.width, 0, prefix, above, s_w, s_ex, &s_i);
if (blockIdx.x == 0 && t == 0) {
qs[MT_STATE + 8] = (int) prefix;
qs[MT_STATE + 9] = above;
}
const uint32_t thr = prefix;
int gt = 0, eq = 0;
#pragma unroll 1
for (int j0 = 0; j0 < m.rpw; j0 += MT_U) {
if (j0 > 0) mt_load(m, sc, j0, key);
#pragma unroll
for (int u = 0; u < MT_U; ++u) {
const int64_t b = m.row0 + 32 * (j0 + u) + lane;
if (j0 + u >= m.rpw || b >= m.hi) continue;
const int w = b == m.n_bid ? m.wtail : R;
if (key[u] > thr) gt += w;
else if (key[u] == thr) eq += w;
}
}
#pragma unroll
for (int o = 16; o > 0; o >>= 1) {
gt += __shfl_xor_sync(0xffffffffu, gt, o);
eq += __shfl_xor_sync(0xffffffffu, eq, o);
}
if (lane == 0) {
qs[MT_CNT + 2 * (blockIdx.x * MT_W + warp)] = gt;
qs[MT_CNT + 2 * (blockIdx.x * MT_W + warp) + 1] = eq;
}
}
// the cells, ascending: a warp's first cell goes after the cells the CTAs and warps before it selected
__global__ void __launch_bounds__(MT_T) block_topk_multi_emit_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps,
int64_t max_blocks, int64_t cap,
int32_t* __restrict__ ids,
const int32_t* __restrict__ scratch) {
__shared__ unsigned long long s_w[MT_W];
const MtQuery m = mt_query(steps);
const int t = threadIdx.x, lane = t & 31, warp = t >> 5;
int32_t* out = ids + (int64_t) blockIdx.y * cap;
if (m.all) { // the identity, split over the CTAs
for (int64_t j = (int64_t) blockIdx.x * MT_T + t; j < m.n_kv; j += (int64_t) gridDim.x * MT_T) out[j] = (int32_t) j;
return;
}
const float* sc = scores + (int64_t) blockIdx.y * max_blocks;
uint32_t key[MT_U];
mt_load(m, sc, 0, key);
const int32_t* qs = scratch + (int64_t) blockIdx.y * MT_Q_INTS;
const uint32_t thr = (uint32_t) qs[MT_STATE + 8];
const int eq_budget = (int) (m.width - qs[MT_STATE + 9]); // cells at thr that fit, lowest index first
// the cells of the warps before this one: the earlier CTAs' (one warp count per thread), then this CTA's
unsigned long long c = 0;
if (t < (int) blockIdx.x * MT_W)
c = (unsigned long long) (unsigned) qs[MT_CNT + 2 * t] | ((unsigned long long) (unsigned) qs[MT_CNT + 2 * t + 1] << 32);
#pragma unroll
for (int o = 16; o > 0; o >>= 1) c += __shfl_xor_sync(0xffffffffu, c, o);
if (lane == 0) s_w[warp] = c;
__syncthreads();
unsigned long long before = 0;
for (int w = 0; w < MT_W; ++w) before += s_w[w];
for (int w = 0; w < warp; ++w) {
const int i = (int) blockIdx.x * MT_W + w;
before += (unsigned long long) (unsigned) qs[MT_CNT + 2 * i] |
((unsigned long long) (unsigned) qs[MT_CNT + 2 * i + 1] << 32);
}
const int gt_before = (int) (before & 0xffffffffu), eq_before = (int) (before >> 32);
int run_sel = gt_before + (eq_before < eq_budget ? eq_before : eq_budget), run_eq = eq_before;
#pragma unroll 1
for (int j0 = 0; j0 < m.rpw; j0 += MT_U) {
if (j0 > 0) mt_load(m, sc, j0, key);
#pragma unroll
for (int u = 0; u < MT_U; ++u) {
if (j0 + u >= m.rpw) break;
const int64_t b = m.row0 + 32 * (j0 + u) + lane;
const int w = b < m.hi ? (b == m.n_bid ? m.wtail : R) : 0;
const uint32_t k = key[u];
const int my_gt = (w && k > thr) ? w : 0, my_eq = (w && k == thr) ? w : 0;
if (__ballot_sync(0xffffffffu, (my_gt | my_eq) != 0) == 0u) continue; // a row without a selected block
int pe = my_eq; // tied cells up to and with this lane
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, pe, o);
if (lane >= o) pe += y;
}
const int left = eq_budget - (run_eq + pe - my_eq);
const int take = left < 0 ? 0 : (left > my_eq ? my_eq : left);
const int my_sel = my_gt + take;
int ps = my_sel;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, ps, o);
if (lane >= o) ps += y;
}
int32_t* dst = out + run_sel + ps - my_sel;
for (int cc = 0; cc < my_sel; ++cc) dst[cc] = (int32_t) (b * R + cc);
run_eq += __shfl_sync(0xffffffffu, pe, 31);
run_sel += __shfl_sync(0xffffffffu, ps, 31);
}
}
}
#endif // !__HIPCC__ && STRATA_EXPERIMENTAL_SM60
} // namespace
bool qsa_block_scores_slots(const float* const* pooled, const float* const* dead, const float* q_idx,
const int32_t* steps, int64_t nq, int64_t max_blocks, const QsaShapes& s, float* scores,
void* stream) {
if (nq <= 0) return true;
if (s.idx_dim != IDX_DIM || s.idx_n_head != IDX_HEADS || s.idx_block != R) {
std::fprintf(stderr, "qsa_block_scores_slots: unsupported indexer geometry\n");
std::exit(1);
}
if (nq > MQ || !scores_multi_on()) return false; // the single-query call would not run the multi kernel
ScoreSlotKeys keys{};
for (int64_t z = 0; z < nq; ++z) {
keys.pooled[z] = pooled[z];
keys.dead[z] = dead[z];
}
block_scores_slots_kernel<<<dim3(256, (unsigned) nq), SCORE_WARPS * 32, 0, (cudaStream_t) stream>>>(
keys, q_idx, steps, max_blocks, scores, scores_early_exit());
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores_slots: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
// block_scores_multi_kernel with the warp sums as one recursive-halving reduction. A (query, head) dot is a lane's
// 4-term product summed over the 32 lanes by an xor butterfly (offsets 16, 8, 4, 2, 1): 5 shuffles per value, 20 per
// (block, query) - on Turing the decode scorer's time grew with the window's queries (420K cells: 117 / 265 / 509 us
// for 1 / 3 / 6 queries), the shuffles, not the keys. Here the V = 4 x queries values (padded to a power of 2) are
// reduced together: at offset o each lane keeps half of its values and adds its partner's copy of them - the pair
// (lane l, lane l ^ o) the butterfly adds for that value at that offset, so every value's additions are the
// butterfly's, operand for operand (float addition commutes): the same bits, with V - 1 shuffles plus the plain
// butterfly's remaining stages instead of 5 V. Lane l ends with value (l >> (5 - log2 V)); the query's 4 heads are
// then gathered by its head-0 lane and summed in block_scores_multi_kernel's order. STRATA_SCORES_HALVE=0: the old kernel.
template <int V>
__global__ void __launch_bounds__(SCORE_WARPS * 32) block_scores_halve_kernel(const float* __restrict__ pooled,
const float* __restrict__ dead,
const float* __restrict__ q_idx,
const int32_t* __restrict__ steps, int nq,
int64_t max_blocks, float* __restrict__ out) {
constexpr int NQ = V / IDX_HEADS; // query slots (nq <= NQ)
constexpr int LV = V == 4 ? 2 : V == 8 ? 3 : V == 16 ? 4 : 5, SH = 5 - LV;
static_assert(V == 4 || V == 8 || V == 16 || V == 32, "V");
__shared__ __align__(16) float qs[NQ * IDX_HEADS * IDX_DIM];
__shared__ int64_t s_nkv[NQ], s_nbid[NQ];
if (threadIdx.x < NQ) {
s_nkv[threadIdx.x] = threadIdx.x < nq ? steps[threadIdx.x * kStepCount + kStepNKv] : 0;
s_nbid[threadIdx.x] = threadIdx.x < nq ? steps[threadIdx.x * kStepCount + kStepNBid] : -1;
}
__syncthreads();
int64_t top = 0;
for (int q = 0; q < nq; ++q) top = s_nbid[q] > top ? s_nbid[q] : top;
if ((int64_t) blockIdx.x * SCORE_WARPS > top) return; // CTA-uniform (as block_scores_multi_kernel's early exit)
for (int i = threadIdx.x; i < NQ * IDX_HEADS * IDX_DIM; i += blockDim.x)
qs[i] = i < nq * IDX_HEADS * IDX_DIM ? q_idx[i] : 0.0f;
__syncthreads();
const int lane = threadIdx.x & 31;
const int64_t wstride = (int64_t) gridDim.x * SCORE_WARPS;
const float4 kd = *reinterpret_cast<const float4*>(dead + lane * 4);
// up to 4 queries: the lane's query values in registers (read once, not once per block from shared memory: the
// shared-memory reads were the kernel's limit, ncu mio_throttle)
constexpr bool QREG = V <= 16;
float4 qr[QREG ? V : 1];
if constexpr (QREG) {
#pragma unroll
for (int i = 0; i < V; ++i) qr[i] = *reinterpret_cast<const float4*>(qs + (i >> 2) * IDX_HEADS * IDX_DIM + (i & 3) * IDX_DIM + lane * 4);
}
int s_nbid_r[NQ]; // n_bid < 2^31
#pragma unroll
for (int qi = 0; qi < NQ; ++qi) s_nbid_r[qi] = (int) s_nbid[qi];
for (int64_t b = (int64_t) blockIdx.x * SCORE_WARPS + (threadIdx.x >> 5); b <= top && b < max_blocks; b += wstride) {
const float4 kp = *reinterpret_cast<const float4*>(pooled + b * IDX_DIM + lane * 4);
float v[V];
#pragma unroll
for (int qi = 0; qi < NQ; ++qi) {
const float4 k4 = (b == s_nbid_r[qi]) ? kd : kp;
const float* q = qs + qi * IDX_HEADS * IDX_DIM + lane * 4;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) {
float4 q4;
if constexpr (QREG) q4 = qr[qi * IDX_HEADS + h];
else q4 = *reinterpret_cast<const float4*>(q + h * IDX_DIM);
v[qi * IDX_HEADS + h] = k4.x * q4.x + k4.y * q4.y + k4.z * q4.z + k4.w * q4.w;
}
}
// recursive halving over offsets 16, 8, ... while more than one value is left, then the plain butterfly
int cnt = V;
#pragma unroll
for (int o = 16; o > 0; o >>= 1) {
if (cnt > 1) {
const int half = cnt >> 1;
const bool hi = (lane & o) != 0;
#pragma unroll
for (int i = 0; i < V / 2; ++i) {
if (i < half) {
const float send = hi ? v[i] : v[i + half];
const float keep = hi ? v[i + half] : v[i];
const float recv = __shfl_xor_sync(0xffffffffu, send, o);
v[i] = keep + recv;
}
}
cnt = half;
} else {
v[0] += __shfl_xor_sync(0xffffffffu, v[0], o);
}
}
// lane l holds value j = l >> SH = qi * 4 + h; the head-0 lane of each query gathers heads 1-3
const int j = lane >> SH, qi = j >> 2;
const float d1 = __shfl_sync(0xffffffffu, v[0], (lane + (1 << SH)) & 31);
const float d2 = __shfl_sync(0xffffffffu, v[0], (lane + (2 << SH)) & 31);
const float d3 = __shfl_sync(0xffffffffu, v[0], (lane + (3 << SH)) & 31);
if ((j & 3) == 0 && (lane & ((1 << SH) - 1)) == 0 && qi < nq && b <= s_nbid_r[qi & (NQ - 1)]) {
const float d[4] = {v[0], d1, d2, d3};
float score = 0.0f;
#pragma unroll
for (int h = 0; h < IDX_HEADS; ++h) score += d[h] > 0.0f ? d[h] : 0.0f;
if (b == s_nbid_r[qi & (NQ - 1)] && s_nkv[qi] % R != 0) score += 1e9f;
out[qi * max_blocks + b] = score;
}
}
}
// #1825: the prompt path's thread-per-head scorer (bitwise the warp kernel's scores). Default: Turing with
// STRATA_SM75_PERF=1 (the P100 gain measured here is +1..3% at 30-60K tokens, under the 3% bar for a new default);
// STRATA_SCORES_THREAD=1 turns it on, =0 off, on any CUDA card
bool scores_thread_on() {
static const int env = [] { const char* v = std::getenv("STRATA_SCORES_THREAD"); return v ? (std::atoi(v) != 0 ? 1 : 0) : -1; }();
if (env >= 0) return env != 0;
static int ok[64] = {}; // 0 unknown, 1 yes, 2 no
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
int major = 0, minor = 0;
cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev);
cudaDeviceGetAttribute(&minor, cudaDevAttrComputeCapabilityMinor, dev);
ok[dev] = strata::sm75_default(major, minor) ? 1 : 2; // Turing, STRATA_SM75_PERF=1
}
return ok[dev] == 1;
}
bool scores_halve_on() {
static const int env = [] { const char* v = std::getenv("STRATA_SCORES_HALVE"); return v ? (std::atoi(v) != 0 ? 1 : 0) : -1; }();
if (env >= 0) return env != 0;
static int ok[64] = {}; // 0 unknown, 1 yes, 2 no
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
int major = 0, minor = 0;
cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev);
cudaDeviceGetAttribute(&minor, cudaDevAttrComputeCapabilityMinor, dev);
ok[dev] = strata::sm75_default(major, minor) ? 1 : 2; // Turing, STRATA_SM75_PERF=1
}
return ok[dev] == 1;
}
void qsa_block_scores(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps, int64_t nq,
int64_t max_blocks, const QsaShapes& s, float* scores, void* stream, int64_t active_blocks) {
if (nq <= 0) return;
if (s.idx_dim != IDX_DIM || s.idx_n_head != IDX_HEADS || s.idx_block != R || nq > 65535) {
std::fprintf(stderr, "qsa_block_scores: unsupported indexer geometry\n");
std::exit(1);
}
// a block past a query's n_bid returns at once: the grid need only reach the batch's largest n_bid (C-1)
if (scores_multi_on() && nq <= MQ && active_blocks <= 0) { // no active count: decode (captured or not) and prefill's pooled16
// QSAROWS: STRATA_QSA_ROWS=1 (exactly) takes block_scores_rows_kernel for calls of up to 4 queries - the same bits
static const bool rows_env = [] { const char* v = std::getenv("STRATA_QSA_ROWS"); return v != nullptr && v[0] == '1' && v[1] == '\0'; }();
if (rows_env && qsa_block_scores_rows(pooled, dead, q_idx, steps, nq, max_blocks, s, scores, stream)) return;
if (scores_halve_on()) { // Turing: block_scores_halve_kernel, the same bits
const cudaStream_t st = (cudaStream_t) stream;
if (nq <= 1) block_scores_halve_kernel<4><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, (int) nq, max_blocks, scores);
else if (nq <= 2) block_scores_halve_kernel<8><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, (int) nq, max_blocks, scores);
else if (nq <= 4) block_scores_halve_kernel<16><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, (int) nq, max_blocks, scores);
else { // 5-8 queries: two calls of up to 4 (the register form; each query's scores are its own)
block_scores_halve_kernel<16><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, 4, max_blocks, scores);
const int rest = (int) nq - 4;
const float* q2 = q_idx + 4 * IDX_HEADS * IDX_DIM;
const int32_t* st2 = steps + 4 * kStepCount;
float* sc2 = scores + 4 * max_blocks;
if (rest <= 1) block_scores_halve_kernel<4><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q2, st2, rest, max_blocks, sc2);
else if (rest <= 2) block_scores_halve_kernel<8><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q2, st2, rest, max_blocks, sc2);
else block_scores_halve_kernel<16><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q2, st2, rest, max_blocks, sc2);
}
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores halve: %s\n", cudaGetErrorString(e)); std::exit(1); }
return;
}
block_scores_multi_kernel<<<256, SCORE_WARPS * 32, 0, (cudaStream_t) stream>>>(pooled, dead, q_idx, steps, (int) nq,
max_blocks, scores, scores_early_exit());
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores multi: %s\n", cudaGetErrorString(e)); std::exit(1); }
return;
}
const int64_t reach = active_blocks > 0 && active_blocks < max_blocks ? active_blocks : max_blocks;
#if defined(__HIPCC__)
// STRATA_SCORES_THREAD: 1 = on (gfx1100, gfx12), 0 = off, unset = on for gfx12 only (gfx1100: off, nothing measured here)
static const int thread_env = [] {
const char* value = std::getenv("STRATA_SCORES_THREAD");
return value == nullptr ? -1 : (std::atoi(value) == 1 ? 1 : 0);
}();
// The bound is the ACTUAL live extent. A reserved 256K context never enables this by itself.
if (thread_env != 0 && active_blocks >= 16385 && active_blocks <= max_blocks && nq >= 64 &&
(scores_thread_arch() == 2 || (thread_env == 1 && scores_thread_arch() == 1))) {
static thread_local bool logged = false;
if (!logged && (thread_env == -1 || std::getenv("STRATA_SCORES_THREAD_TRACE"))) {
std::fprintf(stderr, "qsa exact thread: the prompt's block scorer runs as the four-lanes-per-query kernel (nq=%lld active_blocks=%lld "
"capacity=%lld; the same scores bit for bit; STRATA_SCORES_THREAD=0 turns it off)\n",
(long long)nq, (long long)active_blocks, (long long)max_blocks);
logged = true;
}
const dim3 tgrid((unsigned)((reach + TS_BR - 1) / TS_BR), (unsigned)((nq + TS_Q - 1) / TS_Q));
block_scores_thread_kernel<<<tgrid, 256, 0, (cudaStream_t)stream>>>(pooled, q_idx, steps, nq,
max_blocks, reach, scores);
block_scores_tail_kernel<<<(unsigned)nq, 32, 0, (cudaStream_t)stream>>>(dead, q_idx, steps,
max_blocks, scores);
const cudaError_t error = cudaGetLastError();
if (error != cudaSuccess) {
std::fprintf(stderr, "qsa exact thread: %s\n", cudaGetErrorString(error));
std::exit(1);
}
return;
}
#else
// prompt calls (an active-block count): the thread-per-head kernel, the same bits (opt-in: scores_thread_on); else the
// warp kernel below
if (active_blocks > 0 && scores_thread_on()) {
const dim3 tgrid((unsigned) ((reach + TS_BR - 1) / TS_BR), (unsigned) ((nq + TS_Q - 1) / TS_Q));
block_scores_thread_kernel<<<tgrid, 256, 0, (cudaStream_t) stream>>>(pooled, q_idx, steps, nq, max_blocks, reach,
scores);
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, (cudaStream_t) stream>>>(dead, q_idx, steps, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores thread: %s\n", cudaGetErrorString(e)); std::exit(1); }
return;
}
#endif
const dim3 grid((unsigned) ((reach + SCORE_WARPS - 1) / SCORE_WARPS), (unsigned) nq);
block_scores_kernel<<<grid, SCORE_WARPS * 32, 0, (cudaStream_t) stream>>>(pooled, dead, q_idx, steps, max_blocks,
scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores: %s\n", cudaGetErrorString(e)); std::exit(1); }
}
bool qsa_block_scores_rows(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps, int64_t nq,
int64_t max_blocks, const QsaShapes& s, float* scores, void* stream) {
if (nq <= 0) return true;
if (nq > 4 || s.idx_dim != IDX_DIM || s.idx_n_head != IDX_HEADS || s.idx_block != R) return false;
cudaStream_t st = (cudaStream_t) stream;
const int n = (int) nq;
if (n == 1) block_scores_rows_kernel<1><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, n, max_blocks, scores);
else if (n == 2) block_scores_rows_kernel<2><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, n, max_blocks, scores);
else if (n == 3) block_scores_rows_kernel<3><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, n, max_blocks, scores);
else block_scores_rows_kernel<4><<<256, SCORE_WARPS * 32, 0, st>>>(pooled, dead, q_idx, steps, n, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores rows: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
void qsa_block_scores_rows(const QsaScoreRows& rows, const float* q_idx, const int32_t* steps, int64_t nq,
int64_t max_blocks, const QsaShapes& s, float* scores, void* stream) {
if (nq <= 0) return;
if (s.idx_dim != IDX_DIM || s.idx_n_head != IDX_HEADS || s.idx_block != R || nq > MQ || rows.n != nq) {
std::fprintf(stderr, "qsa_block_scores_rows: unsupported geometry\n");
std::exit(1);
}
static const bool early = [] { const char* v = std::getenv("STRATA_QSA_EARLY_EXIT"); return v == nullptr || std::atoi(v) != 0; }();
block_scores_multi_kernel<<<256, SCORE_WARPS * 32, 0, (cudaStream_t) stream>>>(nullptr, nullptr, q_idx, steps, (int) nq,
max_blocks, scores, early, rows);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores_rows: %s\n", cudaGetErrorString(e)); std::exit(1); }
}
bool qsa_block_scores_tc(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps, int64_t nq,
int64_t max_blocks, const QsaShapes& s, float* scores, void* stream, int64_t active_blocks) {
if (nq <= 0) return true;
if (s.idx_dim != IDX_DIM || s.idx_n_head != IDX_HEADS || s.idx_block != R || nq > 65535 * TC_QT) return false;
#if defined(__HIPCC__)
// AMD: the gfx12 (RDNA4) WMMA scorer, opt-in (STRATA_SELECT_WMMA=1): it selects slightly differently from the warp
// kernel (254/256 queries the same), so the default keeps the warp kernel; every other target keeps it too (false)
static const bool wmma_on = [] {
const char* v = std::getenv("STRATA_SELECT_WMMA");
return v != nullptr && v[0] != '\0' && v[0] != '0';
}();
// any HIP card: the FP32 tiled scorer, opt-in as on CUDA (STRATA_SELECT_SIMT=1; another summation order than the
// warp kernel, so the default keeps the warp kernel). RX 6900 XT, 256 queries at 128K: 2.71 -> 0.587 ms
static const bool simt_on = [] {
const char* v = std::getenv("STRATA_SELECT_SIMT");
return v != nullptr && v[0] == '1';
}();
if (simt_on && !(wmma_on && sel_gfx12_device())) {
const int64_t reach = active_blocks > 0 && active_blocks < max_blocks ? active_blocks : max_blocks;
const bool rdna2 = sel_gfx103_device();
static std::atomic<bool> said{false};
if (!said.exchange(true))
std::fprintf(stderr, "qsa select: FP32 tiled scorer (STRATA_SELECT_SIMT=1), tiles %s\n",
rdna2 ? "32/128/16/8 (gfx103x)" : "32/64/32/4");
return block_scores_simt(pooled, dead, q_idx, steps, nq, max_blocks, reach, scores, (cudaStream_t) stream, rdna2);
}
if (!wmma_on || !sel_gfx12_device()) return false;
{
const int64_t reach = active_blocks > 0 && active_blocks < max_blocks ? active_blocks : max_blocks;
const int64_t per = (int64_t) 4 * WITER * 16;
const dim3 grid((unsigned) ((reach + per - 1) / per), (unsigned) ((nq + WQT - 1) / WQT));
block_scores_wmma_kernel<<<grid, 128, 0, (cudaStream_t) stream>>>(pooled, q_idx, steps, nq, max_blocks, reach, scores);
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, (cudaStream_t) stream>>>(dead, q_idx, steps, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores_tc: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
#else
{ // sm_80 or newer (TF32 MMA); an older card keeps the warp kernel
static int cc_major[64] = {};
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (cc_major[dev] == 0) {
int major = 0;
if (cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev) != cudaSuccess) {
cudaGetLastError();
return false;
}
// STRATA_QSA_WARP=1|select (an A/B arm): the pre-sm_80 kernels on any card, as RTX 20 runs them
const char* w = std::getenv("STRATA_QSA_WARP");
cc_major[dev] = w && (!std::strcmp(w, "1") || !std::strcmp(w, "select")) ? 7 : strata::cc_major_of(major);
}
if (cc_major[dev] < 8) {
// no TF32 tensor cores: the FP32 tiled kernel, opt-in (STRATA_SELECT_SIMT=1): its sum order differs from the
// warp kernel's, so the default stays the caller's warp kernel and the output bytes stay the same
// STRATA_SELECT_SIMT=2: block_scores_simt2_kernel (the same bits as =1, larger tiles)
static const int simt = [] {
const char* v = std::getenv("STRATA_SELECT_SIMT");
return v == nullptr ? 0 : v[0] == '1' ? 1 : v[0] == '2' ? 2 : 0;
}();
if (!simt) return false;
const int64_t reach = active_blocks > 0 && active_blocks < max_blocks ? active_blocks : max_blocks;
if (simt == 2) {
// STRATA_SIMT2_TILE=2: 64 x 64 tiles (measured slower: 400K 3.00 vs 2.82 ms)
static const int tile = [] { const char* v = std::getenv("STRATA_SIMT2_TILE"); return v ? std::atoi(v) : 1; }();
if (tile != 2) {
const dim3 grid((unsigned) ((reach + 127) / 128), (unsigned) ((nq + 31) / 32));
if (grid.y > 65535) return false;
block_scores_simt2_kernel<32, 128><<<grid, 256, 0, (cudaStream_t) stream>>>(pooled, q_idx, steps, nq,
max_blocks, reach, scores);
} else {
const dim3 grid((unsigned) ((reach + 63) / 64), (unsigned) ((nq + 63) / 64));
if (grid.y > 65535) return false;
block_scores_simt2_kernel<64, 64><<<grid, 256, 0, (cudaStream_t) stream>>>(pooled, q_idx, steps, nq,
max_blocks, reach, scores);
}
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, (cudaStream_t) stream>>>(dead, q_idx, steps, max_blocks,
scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores (simt): %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
return block_scores_simt(pooled, dead, q_idx, steps, nq, max_blocks, reach, scores, (cudaStream_t) stream,
false);
}
}
static bool attr[64] = {}; // the shared-memory opt-in is per device (a layer split runs it on several)
int adev = 0;
cudaGetDevice(&adev);
const int bytes = (TC_QT * TC_QS + TC_NB * TC_KS) * (int) sizeof(float);
if (!attr[adev]) {
if (cudaFuncSetAttribute(block_scores_tc_kernel, cudaFuncAttributeMaxDynamicSharedMemorySize, bytes) !=
cudaSuccess) {
cudaGetLastError();
return false;
}
attr[adev] = true;
}
const int64_t reach = active_blocks > 0 && active_blocks < max_blocks ? active_blocks : max_blocks;
const int64_t per = (int64_t) TC_NB * TC_ITER;
const dim3 grid((unsigned) ((reach + per - 1) / per), (unsigned) ((nq + TC_QT - 1) / TC_QT));
block_scores_tc_kernel<<<grid, 128, bytes, (cudaStream_t) stream>>>(pooled, q_idx, steps, nq, max_blocks, reach,
scores);
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, (cudaStream_t) stream>>>(dead, q_idx, steps, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores_tc: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
#endif
}
void qsa_block_topk_ref(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
const QsaShapes& s, int32_t* ids, void* stream) {
if (nq <= 0) return;
if (s.idx_block != R || cap < qsa_selection_width(kTopkMaxCells, s)) {
std::fprintf(stderr, "qsa_block_topk: unsupported geometry or cap\n");
std::exit(1);
}
block_topk_kernel<<<(unsigned) nq, TOPK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_topk: %s\n", cudaGetErrorString(e)); std::exit(1); }
}
#if !defined(__HIPCC__)
// Only Turing has a retained model measurement for this CUDA dispatch. Other CUDA devices keep the capacity rule
// (the RTX 5070 regression below). Cache the properties per calling thread; layer-split device switches are checked.
static bool topk_active_turing_device() {
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess) return false;
static thread_local int cached_device = -1;
static thread_local bool turing = false;
if (dev != cached_device) {
cudaDeviceProp prop{};
if (cudaGetDeviceProperties(&prop, dev) != cudaSuccess) return false;
turing = prop.major == 7 && prop.minor == 5;
cached_device = dev;
}
return turing;
}
#endif
bool qsa_block_topk_cluster(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
const QsaShapes& s, int32_t* ids, void* stream) {
#if defined(__HIPCC__)
(void) scores; (void) steps; (void) nq; (void) max_blocks; (void) cap; (void) s; (void) ids; (void) stream;
return false;
#else
if (nq <= 0) return true;
if (s.idx_block != R || cap < qsa_selection_width(kTopkMaxCells, s) || nq > 65535 || max_blocks <= 0) return false;
const size_t smem = (size_t) ((max_blocks + CL_N - 1) / CL_N) * sizeof(uint32_t);
// Per device (a layer split runs on several): 1 the cluster kernel runs here, 2 it does not. It needs sm_90+ (the
// card's, or STRATA_EMULATE_CC's) AND code built for it: a build with only older code JIT-compiles their PTX, whose
// copy of this kernel is a trap - the function's PTX version says which. `opt`: the dynamic shared memory opted in.
static int ok[64] = {};
static size_t opt[64] = {};
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
int major = 0;
cudaFuncAttributes fa{};
const bool code = cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev) == cudaSuccess &&
strata::cc_major_of(major) >= 9 &&
cudaFuncGetAttributes(&fa, block_topk_cluster_kernel) == cudaSuccess && fa.ptxVersion >= 90 &&
fa.binaryVersion >= 90;
cudaGetLastError();
ok[dev] = code ? 1 : 2;
}
if (ok[dev] != 1) return false;
if (smem > opt[dev]) { // a larger capacity: opt in, and check that a cluster of CL_N such CTAs can be resident
int clusters = 0;
cudaLaunchConfig_t q{};
cudaLaunchAttribute qa[1];
qa[0].id = cudaLaunchAttributeClusterDimension;
qa[0].val.clusterDim.x = CL_N;
qa[0].val.clusterDim.y = 1;
qa[0].val.clusterDim.z = 1;
q.gridDim = dim3(CL_N, 1, 1);
q.blockDim = dim3(CL_T, 1, 1);
q.dynamicSmemBytes = smem;
q.attrs = qa;
q.numAttrs = 1;
if (cudaFuncSetAttribute(block_topk_cluster_kernel, cudaFuncAttributeMaxDynamicSharedMemorySize, (int) smem) !=
cudaSuccess ||
cudaOccupancyMaxActiveClusters(&clusters, block_topk_cluster_kernel, &q) != cudaSuccess || clusters < 1) {
cudaGetLastError();
return false; // this capacity takes the one-CTA kernels; a smaller one may still fit
}
opt[dev] = smem;
}
cudaLaunchConfig_t cfg{};
cudaLaunchAttribute at[1];
at[0].id = cudaLaunchAttributeClusterDimension;
at[0].val.clusterDim.x = CL_N;
at[0].val.clusterDim.y = 1;
at[0].val.clusterDim.z = 1;
cfg.gridDim = dim3(CL_N, (unsigned) nq, 1);
cfg.blockDim = dim3(CL_T, 1, 1);
cfg.dynamicSmemBytes = smem;
cfg.stream = (cudaStream_t) stream;
cfg.attrs = at;
cfg.numAttrs = 1;
const cudaError_t e = cudaLaunchKernelEx(&cfg, block_topk_cluster_kernel, scores, steps, max_blocks, cap, ids);
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_topk cluster: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
#endif
}
#if !defined(__HIPCC__)
// ---- the decode top-k split over many CTAs, for cards without thread-block clusters (Turing: a decode window's 1-6
// queries ran block_topk_wide_kernel on 1-6 SMs, ~230 us a call at 420K cells, RTX 2080 Ti). A query's blocks are
// cut into chunks of SP_CH; six launches: four radix passes (each chunk adds its 8-bit histogram to the query's global
// one), a count of each chunk's cells above / at the threshold, and the emit. Each pass's CTAs take the previous
// digit from the complete histogram with block_topk_kernel's rule (the largest digit whose cells at or above it reach
// the width; 0 when none) - pure functions of integer counts, so every CTA finds the same digit, and the threshold,
// `above` and the emitted cells are block_topk_kernel's: identical ids. STRATA_TOPK_SPLIT=0 keeps the wide kernel.
constexpr int SP_T = 256, SP_W = SP_T / 32, SP_CH = 2048, SP_MAXQ = 16, SP_MAXCH = 512;
__device__ int g_sp_hist[SP_MAXQ][4][256];
__device__ int g_sp_state[5][SP_MAXQ][2]; // after p digits: prefix, above
__device__ int g_sp_cnt[SP_MAXQ][SP_MAXCH][2]; // per chunk: cells above the threshold, cells at it
// the digit of pass `p` from its complete histogram: block_topk_kernel's scan as a parallel suffix sum
__device__ void sp_digit(const int* __restrict__ h, int width, int above, int& digit, int& above_out, int* s_buf) {
const int t = threadIdx.x;
// s_buf[d] = sum of h[d'] for d' > d (exclusive suffix), d in 0..255
const int v = h[t];
int x = v; // inclusive suffix scan over t = 255..0: reverse index r = 255 - t
const int lane = t & 31, w = t >> 5;
__shared__ int s_w[SP_W];
// scan in reverse order: thread t holds element r = 255 - t
int e = h[255 - t];
for (int o = 1; o < 32; o <<= 1) { const int y = __shfl_up_sync(0xffffffffu, e, o); if (lane >= o) e += y; }
if (lane == 31) s_w[w] = e;
__syncthreads();
int add = 0;
for (int i = 0; i < w; ++i) add += s_w[i];
e += add; // inclusive suffix sum of h from 255 down to r = 255 - t
(void) x; (void) v;
s_buf[255 - t] = e; // s_buf[r] = sum_{d >= r} h[d]
__syncthreads();
// the scan picks the largest d in 1..255 with above + sum_{d' >= d} h >= width, else 0
__shared__ int s_best;
if (t == 0) s_best = 0;
__syncthreads();
if (t >= 1 && above + s_buf[t] >= width) atomicMax(&s_best, t);
__syncthreads();
const int d = s_best;
digit = d;
above_out = above + (d == 255 ? 0 : s_buf[d + 1]); // cells strictly above digit d (the scan's cum)
if (d == 0) above_out = above + s_buf[1];
__syncthreads();
}
template <int P>
__global__ void __launch_bounds__(SP_T) topk_split_hist_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks) {
__shared__ int hist[SP_W][256];
__shared__ int s_buf[256];
const int q = blockIdx.y, t = threadIdx.x, lane = t & 31, warp = t >> 5;
const int32_t* st = steps + (int64_t) q * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
if (n_kv <= width) return;
const int64_t nb = n_bid + 1, b0 = (int64_t) blockIdx.x * SP_CH;
uint32_t prefix = 0;
int above = 0;
if (P > 0) {
const int pa = g_sp_state[P - 1][q][0], ab = g_sp_state[P - 1][q][1];
int d, ab2;
sp_digit(g_sp_hist[q][P - 1], (int) width, ab, d, ab2, s_buf);
prefix = (uint32_t) pa | ((uint32_t) d << (24 - 8 * (P - 1)));
above = ab2;
if (blockIdx.x == 0 && t == 0) { g_sp_state[P][q][0] = (int) prefix; g_sp_state[P][q][1] = above; }
} else if (blockIdx.x == 0 && t == 0) {
g_sp_state[0][q][0] = 0; g_sp_state[0][q][1] = 0;
}
if (P == 4 || b0 >= nb) return;
constexpr int shift = 24 - 8 * (P < 4 ? P : 0);
const uint32_t hi_mask = P == 0 ? 0u : (0xffffffffu << (shift + 8));
for (int i = lane; i < 256; i += 32) hist[warp][i] = 0;
__syncwarp();
const float* sc = scores + (int64_t) q * max_blocks;
const int64_t b1 = b0 + SP_CH < nb ? b0 + SP_CH : nb;
for (int64_t b = b0 + t; b < b1; b += SP_T) {
const int w = b < n_bid ? R : (int) (n_kv - n_bid * R);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if ((k & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[warp][(k >> shift) & 255], w);
}
__syncthreads();
int s = 0;
for (int w2 = 0; w2 < SP_W; ++w2) s += hist[w2][t];
if (s) atomicAdd(&g_sp_hist[q][P][t], s);
}
// the threshold from pass 3's histogram, then each chunk's cells above / at it
__global__ void __launch_bounds__(SP_T) topk_split_count_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks) {
__shared__ int s_buf[256];
__shared__ int s_r[2][SP_W];
const int q = blockIdx.y, t = threadIdx.x, lane = t & 31, warp = t >> 5;
const int32_t* st = steps + (int64_t) q * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
if (n_kv <= width) return;
const int pa = g_sp_state[3][q][0], ab = g_sp_state[3][q][1];
int d, ab2;
sp_digit(g_sp_hist[q][3], (int) width, ab, d, ab2, s_buf);
const uint32_t thr = (uint32_t) pa | (uint32_t) d;
if (blockIdx.x == 0 && t == 0) { g_sp_state[4][q][0] = (int) thr; g_sp_state[4][q][1] = ab2; }
const int64_t nb = n_bid + 1, b0 = (int64_t) blockIdx.x * SP_CH;
const int64_t b1 = b0 + SP_CH < nb ? b0 + SP_CH : nb;
const float* sc = scores + (int64_t) q * max_blocks;
int gt = 0, eq = 0;
for (int64_t b = b0 + t; b < b1; b += SP_T) {
const int w = b < n_bid ? R : (int) (n_kv - n_bid * R);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k > thr) gt += w;
else if (k == thr) eq += w;
}
for (int o = 16; o > 0; o >>= 1) {
gt += __shfl_xor_sync(0xffffffffu, gt, o);
eq += __shfl_xor_sync(0xffffffffu, eq, o);
}
if (lane == 0) { s_r[0][warp] = gt; s_r[1][warp] = eq; }
__syncthreads();
if (t == 0) {
int g2 = 0, e2 = 0;
for (int w2 = 0; w2 < SP_W; ++w2) { g2 += s_r[0][w2]; e2 += s_r[1][w2]; }
g_sp_cnt[q][blockIdx.x][0] = g2;
g_sp_cnt[q][blockIdx.x][1] = e2;
}
}
// the emit: block_topk_wide_kernel's within a chunk, offset by the chunks before it
__global__ void __launch_bounds__(SP_T) topk_split_emit_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
__shared__ int s_gt[SP_W], s_eq[SP_W];
__shared__ int s_sel0, s_eqb0;
const int q = blockIdx.y, t = threadIdx.x, lane = t & 31, warp = t >> 5;
const int32_t* st = steps + (int64_t) q * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + (int64_t) q * cap;
const int64_t nb = n_bid + 1, b0 = (int64_t) blockIdx.x * SP_CH;
if (n_kv <= width) { // everything is selected: the identity, ascending
const int64_t c0 = b0 * R, c1 = (b0 + SP_CH) * R < n_kv ? (b0 + SP_CH) * R : n_kv;
for (int64_t j = c0 + t; j < c1; j += SP_T) out[j] = (int32_t) j;
return;
}
if (b0 >= nb) return;
const uint32_t thr = (uint32_t) g_sp_state[4][q][0];
const int eq_budget = (int) (width - g_sp_state[4][q][1]);
if (t == 0) { // the cells the chunks before this one select / hold at thr
int sel = 0, eqb = 0;
for (int c = 0; c < (int) blockIdx.x; ++c) {
const int g2 = g_sp_cnt[q][c][0], e2 = g_sp_cnt[q][c][1];
const int take = eq_budget - eqb < 0 ? 0 : (eq_budget - eqb > e2 ? e2 : eq_budget - eqb);
sel += g2 + take;
eqb += e2;
}
s_sel0 = sel;
s_eqb0 = eqb;
}
const int64_t b1 = b0 + SP_CH < nb ? b0 + SP_CH : nb;
const int64_t per = (SP_CH / 32) / SP_W; // rows of 32 blocks per warp
const int64_t w0 = b0 + (int64_t) warp * 32 * per, w1 = w0 + 32 * per < b1 ? w0 + 32 * per : b1;
const float* sc = scores + (int64_t) q * max_blocks;
auto weight = [&](int64_t b) -> int { return b < n_bid ? R : (int) (n_kv - n_bid * R); };
int gt = 0, eq = 0;
for (int64_t b = w0 + lane; b < w1; b += 32) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k > thr) gt += w;
else if (k == thr) eq += w;
}
#pragma unroll
for (int o = 16; o > 0; o >>= 1) {
gt += __shfl_xor_sync(0xffffffffu, gt, o);
eq += __shfl_xor_sync(0xffffffffu, eq, o);
}
if (lane == 0) { s_gt[warp] = gt; s_eq[warp] = eq; }
__syncthreads();
if (t == 0) {
int eb = s_eqb0, sb = s_sel0;
for (int w2 = 0; w2 < SP_W; ++w2) {
const int g2 = s_gt[w2], e2 = s_eq[w2];
const int take = eq_budget - eb < 0 ? 0 : (eq_budget - eb > e2 ? e2 : eq_budget - eb);
s_gt[w2] = sb;
s_eq[w2] = eb;
sb += g2 + take;
eb += e2;
}
}
__syncthreads();
int run_sel = s_gt[warp], run_eq = s_eq[warp];
for (int64_t r0 = w0; r0 < w1; r0 += 32) {
const int64_t b = r0 + lane;
const int w = b < w1 ? weight(b) : 0;
const uint32_t k = w ? order_key(sc[b]) : 0u;
const int my_gt = (w && k > thr) ? w : 0, my_eq = (w && k == thr) ? w : 0;
if (__ballot_sync(0xffffffffu, (my_gt | my_eq) != 0) == 0u) continue;
int pe = my_eq;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, pe, o);
if (lane >= o) pe += y;
}
const int left = eq_budget - (run_eq + pe - my_eq);
const int take = left < 0 ? 0 : (left > my_eq ? my_eq : left);
const int my_sel = my_gt + take;
int ps = my_sel;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) {
const int y = __shfl_up_sync(0xffffffffu, ps, o);
if (lane >= o) ps += y;
}
int32_t* dst = out + run_sel + ps - my_sel;
for (int c = 0; c < my_sel; ++c) dst[c] = (int32_t) (b * R + c);
run_eq += __shfl_sync(0xffffffffu, pe, 31);
run_sel += __shfl_sync(0xffffffffu, ps, 31);
}
}
bool topk_split_device() {
static int ok[64] = {}; // 0 unknown, 1 yes, 2 no
static const int env = [] { const char* v = std::getenv("STRATA_TOPK_SPLIT"); return v ? (std::atoi(v) != 0 ? 1 : 0) : -1; }();
if (env == 0) return false;
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
int major = 0, minor = 0;
cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev);
cudaDeviceGetAttribute(&minor, cudaDevAttrComputeCapabilityMinor, dev);
ok[dev] = (env == 1 || strata::sm75_default(major, minor)) ? 1 : 2; // Turing, STRATA_SM75_PERF=1
}
return ok[dev] == 1;
}
bool qsa_block_topk_split(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
int32_t* ids, cudaStream_t s) {
const int64_t nch = (max_blocks + SP_CH - 1) / SP_CH;
if (nq < 1 || nq > SP_MAXQ || nch > SP_MAXCH) return false;
static void* hist_ptr[64] = {};
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (hist_ptr[dev] == nullptr && cudaGetSymbolAddress(&hist_ptr[dev], g_sp_hist) != cudaSuccess) {
cudaGetLastError();
hist_ptr[dev] = nullptr;
return false;
}
if (cudaMemsetAsync(hist_ptr[dev], 0, (size_t) nq * 4 * 256 * sizeof(int), s) != cudaSuccess) return false;
const dim3 grid((unsigned) nch, (unsigned) nq);
topk_split_hist_kernel<0><<<grid, SP_T, 0, s>>>(scores, steps, max_blocks);
topk_split_hist_kernel<1><<<grid, SP_T, 0, s>>>(scores, steps, max_blocks);
topk_split_hist_kernel<2><<<grid, SP_T, 0, s>>>(scores, steps, max_blocks);
topk_split_hist_kernel<3><<<grid, SP_T, 0, s>>>(scores, steps, max_blocks);
topk_split_count_kernel<<<grid, SP_T, 0, s>>>(scores, steps, max_blocks);
topk_split_emit_kernel<<<grid, SP_T, 0, s>>>(scores, steps, max_blocks, cap, ids);
return true;
}
#endif
#if !defined(__HIPCC__)
// ---- the prompt path's top-k with one full read of the scores (Turing). block_topk_wide_kernel reads a query's scores
// six times (four radix passes, a count, the emit); past ~90K cells that is DRAM traffic (256 queries at 400K: 0.6 GB a
// layer, ~1.5 ms on an RTX 2080 Ti). Here a CTA first reads every 32nd block and takes the KS-th largest of those keys
// as a bound LB, then reads all blocks once and keeps the ones with key >= LB in shared memory. When those hold at
// least `width` cells, the width-th largest cell key (block_topk_kernel's threshold) is >= LB, so every block at or
// above the threshold is a candidate: the threshold, `above` and the tie budget computed over the candidates with
// block_topk_kernel's rule are the reference's, and the candidates sorted by block emit the reference's cells in its
// order. Otherwise (too few cells above LB, or more than SM_CAP candidates) the query is flagged and
// block_topk_wide_kernel<true> runs it. STRATA_TOPK_SAMPLE=0 keeps the wide kernel alone.
constexpr int TS_STRIDE = 32, TS_CAP = 4096;
__device__ __forceinline__ int ts_block_scan(int v, int* s_w) { // exclusive scan over the CTA's TK_T threads
const int t = threadIdx.x, lane = t & 31, w = t >> 5;
int x = v;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) { const int y = __shfl_up_sync(0xffffffffu, x, o); if (lane >= o) x += y; }
if (lane == 31) s_w[w] = x;
__syncthreads();
if (w == 0) {
int y = lane < TK_T / 32 ? s_w[lane] : 0;
#pragma unroll
for (int o = 1; o < 32; o <<= 1) { const int z = __shfl_up_sync(0xffffffffu, y, o); if (lane >= o) y += z; }
if (lane < TK_T / 32) s_w[lane] = y; // inclusive warp totals
}
__syncthreads();
const int base = w > 0 ? s_w[w - 1] : 0;
const int r = base + x - v;
__syncthreads();
return r;
}
__global__ void __launch_bounds__(TK_T) block_topk_sample_kernel(const float* __restrict__ scores,
const int32_t* __restrict__ steps, int64_t max_blocks,
int64_t cap, int32_t* __restrict__ ids) {
__shared__ uint32_t s_key[TS_CAP];
__shared__ int32_t s_idx[TS_CAP];
__shared__ int hist[256];
__shared__ int s_w[TK_T / 32];
__shared__ int s_cnt, s_cells, s_digit, s_above;
const int64_t qi = blockIdx.x;
const int32_t* st = steps + qi * kStepCount;
const int64_t n_kv = st[kStepNKv], n_bid = st[kStepNBid], width = st[kStepWidth];
int32_t* out = ids + qi * cap;
const int t = threadIdx.x;
if (n_kv <= width) {
if (t == 0) g_tk_fail[qi] = 0;
for (int64_t j = t; j < n_kv; j += TK_T) out[j] = (int32_t) j;
return;
}
const float* sc = scores + qi * max_blocks;
const int64_t nb = n_bid + 1;
auto weight = [&](int64_t b) -> int { return b < n_bid ? R : (int) (n_kv - n_bid * R); };
const int ns = (int) ((nb + TS_STRIDE - 1) / TS_STRIDE);
if (ns > TS_CAP) { if (t == 0) g_tk_fail[qi] = 1; return; }
// 1. the bound: the KS-th largest of every 32nd block's key (a block without cells counts as the smallest key)
for (int i = t; i < ns; i += TK_T) {
const int64_t b = (int64_t) i * TS_STRIDE;
s_key[i] = weight(b) ? order_key(sc[b]) : 0u;
}
const int ks_want = (int) (2 * ((width + R * TS_STRIDE - 1) / (R * TS_STRIDE)) + 16);
int need = ks_want < ns ? ks_want : ns;
uint32_t prefix = 0;
for (int shift = 24; shift >= 0; shift -= 8) {
for (int i = t; i < 256; i += TK_T) hist[i] = 0;
__syncthreads();
const uint32_t hi_mask = shift == 24 ? 0u : (0xffffffffu << (shift + 8));
for (int i = t; i < ns; i += TK_T) {
const uint32_t k = s_key[i];
if ((k & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[(k >> shift) & 255], 1);
}
__syncthreads();
if (t == 0) {
int cum = 0, d = 255;
for (; d > 0; --d) {
if (cum + hist[d] >= need) break;
cum += hist[d];
}
s_digit = d;
s_above = need - cum;
}
__syncthreads();
prefix |= (uint32_t) s_digit << shift;
need = s_above;
__syncthreads();
}
const uint32_t lb = prefix;
// 2. one read of every block: the candidates (key >= LB) and their cells
if (t == 0) { s_cnt = 0; s_cells = 0; }
__syncthreads();
for (int64_t b = t; b < nb; b += TK_T) {
const int w = weight(b);
if (w == 0) continue;
const uint32_t k = order_key(sc[b]);
if (k >= lb) {
const int pos = atomicAdd(&s_cnt, 1);
if (pos < TS_CAP) { s_key[pos] = k; s_idx[pos] = (int32_t) b; }
atomicAdd(&s_cells, w);
}
}
__syncthreads();
const int n = s_cnt;
if (n > TS_CAP || s_cells < width) { // the bound was too low or too high: the wide kernel takes this query
if (t == 0) g_tk_fail[qi] = 1;
return;
}
if (t == 0) g_tk_fail[qi] = 0;
// 3. block_topk_kernel's threshold over the candidates (weighted)
prefix = 0;
int above = 0;
for (int shift = 24; shift >= 0; shift -= 8) {
for (int i = t; i < 256; i += TK_T) hist[i] = 0;
__syncthreads();
const uint32_t hi_mask = shift == 24 ? 0u : (0xffffffffu << (shift + 8));
for (int i = t; i < n; i += TK_T) {
const uint32_t k = s_key[i];
if ((k & hi_mask) == (prefix & hi_mask)) atomicAdd(&hist[(k >> shift) & 255], weight(s_idx[i]));
}
__syncthreads();
if (t == 0) {
int cum = above, d = 255;
for (; d > 0; --d) {
if (cum + hist[d] >= width) break;
cum += hist[d];
}
s_digit = d;
s_above = cum;
}
__syncthreads();
prefix |= (uint32_t) s_digit << shift;
above = s_above;
__syncthreads();
}
const uint32_t thr = prefix;
const int eq_budget = (int) (width - above);
// 4. the candidates in block order (bitonic sort; padding sorts last)
int n2 = 1;
while (n2 < n) n2 <<= 1;
for (int i = n + t; i < n2; i += TK_T) { s_idx[i] = 0x7fffffff; s_key[i] = 0u; }
__syncthreads();
for (int kk = 2; kk <= n2; kk <<= 1) {
for (int j = kk >> 1; j > 0; j >>= 1) {
for (int i = t; i < n2; i += TK_T) {
const int p = i ^ j;
if (p > i) {
const bool up = (i & kk) == 0;
const int a = s_idx[i], b = s_idx[p];
if ((a > b) == up) {
s_idx[i] = b; s_idx[p] = a;
const uint32_t ka = s_key[i]; s_key[i] = s_key[p]; s_key[p] = ka;
}
}
}
__syncthreads();
}
}
// 5. the emit: cells above thr, and the first eq_budget cells at thr, in block order
constexpr int PER = TS_CAP / TK_T; // candidates per thread, consecutive
int eqc[PER], gtc[PER];
int my_eq = 0;
#pragma unroll
for (int r = 0; r < PER; ++r) {
const int i = t * PER + r;
const int w = i < n ? weight(s_idx[i]) : 0;
const uint32_t k = s_key[i < n ? i : 0];
gtc[r] = (i < n && k > thr) ? w : 0;
eqc[r] = (i < n && k == thr) ? w : 0;
my_eq += eqc[r];
}
int eq_before = ts_block_scan(my_eq, s_w);
int sel[PER], my_sel = 0;
#pragma unroll
for (int r = 0; r < PER; ++r) {
const int left = eq_budget - eq_before;
const int take = left < 0 ? 0 : (left > eqc[r] ? eqc[r] : left);
sel[r] = gtc[r] + take;
my_sel += sel[r];
eq_before += eqc[r];
}
int pos = ts_block_scan(my_sel, s_w);
#pragma unroll
for (int r = 0; r < PER; ++r) {
const int i = t * PER + r;
if (sel[r] > 0) {
const int64_t b = s_idx[i];
for (int c = 0; c < sel[r]; ++c) out[pos + c] = (int32_t) (b * R + c);
}
pos += sel[r];
}
}
// The prompt path's one-read top-k: STRATA_TOPK_SAMPLE=0 / 1 forces it off / on for any card; unset it is a Turing kernel
// of the series (STRATA_SM75_PERF=1). (As submitted in #2093 it was on for every CUDA card; same ids, but only measured
// on an RTX 2080 Ti, so the other cards keep the wide kernel.)
bool topk_sample_on() {
static const int env = [] { const char* v = std::getenv("STRATA_TOPK_SAMPLE"); return v ? (std::atoi(v) != 0 ? 1 : 0) : -1; }();
if (env >= 0) return env != 0;
static int ok[64] = {}; // 0 unknown, 1 yes, 2 no
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess || dev < 0 || dev >= 64) { cudaGetLastError(); return false; }
if (ok[dev] == 0) {
int major = 0, minor = 0;
cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev);
cudaDeviceGetAttribute(&minor, cudaDevAttrComputeCapabilityMinor, dev);
ok[dev] = strata::sm75_default(major, minor) ? 1 : 2;
}
return ok[dev] == 1;
}
#endif
void qsa_block_topk(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
const QsaShapes& s, int32_t* ids, void* stream, int64_t active_blocks) {
// keys in registers when every query's blocks fit (contexts up to ~135K cells), else (CUDA) the same threads
// reading them from memory; the same ids. STRATA_TOPK_OLD=1: the original kernel
static const bool old = std::getenv("STRATA_TOPK_OLD") != nullptr;
if (nq <= 0) return;
#if !defined(__HIPCC__)
// sm_90+: a cluster of CL_N CTAs per query for the calls of a few queries (decode windows); the same ids.
// STRATA_QSA_CLUSTER=0: the one-CTA kernels below
static const bool cluster = [] {
const char* v = std::getenv("STRATA_QSA_CLUSTER");
return !v || std::atoi(v) != 0;
}();
if (cluster && !old && nq <= CL_MAXQ && qsa_block_topk_cluster(scores, steps, nq, max_blocks, cap, s, ids, stream))
return;
#endif
#if !defined(__HIPCC__)
// Turing decode (a window's few queries, no block count): the split kernels above; the same ids
if (!old && active_blocks <= 0 && max_blocks >= 16384 && s.idx_block == R &&
cap >= qsa_selection_width(kTopkMaxCells, s) && topk_split_device() &&
qsa_block_topk_split(scores, steps, nq, max_blocks, cap, ids, (cudaStream_t) stream)) {
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_topk (split): %s\n", cudaGetErrorString(e)); std::exit(1); }
return;
}
#endif
// the blocks a query can have: the call's active count when the caller knows it (the prompt path), else the capacity.
// Decode (no count) keeps the capacity rule and the original register width: nothing changes there.
#if defined(__HIPCC__)
const bool counted = active_blocks > 0;
#else
// Turing: --max-context 262144 makes the stride 65538, even while a 131K prompt's active blocks fit in
// TK_T * TK_PER registers. Use the prefill bound on sm_75, keeping max_blocks as the score-row stride.
// Other CUDA devices keep 0.1.32's capacity rule: #337 was measured on RDNA4, and RTX 5070 64K prompts were
// 1-3% slower. Decode/captured graphs omit the bound and never query the device here.
static const bool capacity_guard = std::getenv("STRATA_TOPK_CAPACITY_GUARD") != nullptr;
// STRATA_TOPK_ACTIVE_ANY=1 (tests): the Turing dispatch on any CUDA card, so qsa_topk_active_parity checks it
// on whatever card runs the tests (the kernels are the same on every architecture)
static const bool any_card = [] { const char* v = std::getenv("STRATA_TOPK_ACTIVE_ANY"); return v && v[0] == '1'; }();
const bool counted = !capacity_guard && active_blocks > 0 && active_blocks <= max_blocks &&
(any_card || topk_active_turing_device());
#endif
const int64_t reach = counted && active_blocks < max_blocks ? active_blocks : max_blocks;
const int64_t fit = (int64_t) TK_T * (counted ? TK_PER_MAX : TK_PER);
#if defined(__HIPCC__)
// gfx1201: below ~28K cells (7,168 blocks) the 1,024-thread kernel's fixed cost loses to the ref. STRATA_TOPK_REG_MIN_BLOCKS
// moves the line (0: the register kernel always); gfx1151's table sets 4096, the crossover with the cooperative scan
static const int64_t kRegMinBlocks = [] {
const char* v = std::getenv("STRATA_TOPK_REG_MIN_BLOCKS");
return v != nullptr ? (int64_t) std::atoll(v) : (int64_t) 7168;
}();
const bool too_small = counted && reach < kRegMinBlocks;
// campaign3: `reach > fit` no longer forces the ref radix - the wide kernel below takes it (same ids).
if (old || too_small) {
#else
constexpr int64_t kWideMinBlocks = 4608; // RTX 3060: a prompt batch below ~18K cells is faster on the ref
const bool too_small = reach > fit && active_blocks > 0 && active_blocks < kWideMinBlocks;
if (old || too_small) {
#endif
qsa_block_topk_ref(scores, steps, nq, max_blocks, cap, s, ids, stream);
return;
}
if (s.idx_block != R || cap < qsa_selection_width(kTopkMaxCells, s)) {
std::fprintf(stderr, "qsa_block_topk: unsupported geometry or cap\n");
std::exit(1);
}
// Turing prefill (the `counted` bound) above ~90K cells (22,528 blocks): the wide kernel, which reads the keys
// coalesced, instead of the register kernel's uncoalesced per-thread runs (PR #743: 131K, 1.03 -> 0.75 ms); the
// same ids. STRATA_TOPK_STREAM=0 restores the register kernel there.
// campaign3: on HIP too (was CUDA-only; gfx11 has no sm_90 cluster path and fell to the ref radix past the
// register kernel's reach - the deep-decode top-k cost). Same ids as the ref kernel.
static const bool turing_wide = [] {
const char* v = std::getenv("STRATA_TOPK_STREAM");
return v == nullptr || v[0] != '0';
}();
if (reach > fit || (turing_wide && counted && reach > 22528)) { // past the register kernel's reach, or Turing's band
#if !defined(__HIPCC__)
if (counted && nq <= TS_MAXQ && reach > 28672 && topk_sample_on()) { // one read of the scores (below ~115K cells the wide kernel is as fast)
block_topk_sample_kernel<<<(unsigned) nq, TK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
block_topk_wide_kernel<true><<<(unsigned) nq, TK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
} else
#endif
block_topk_wide_kernel<false><<<(unsigned) nq, TK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
} else
if (reach <= (int64_t) TK_T * TK_PER)
block_topk_reg_kernel<TK_PER><<<(unsigned) nq, TK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
else
block_topk_reg_kernel<TK_PER_MAX><<<(unsigned) nq, TK_T, 0, (cudaStream_t) stream>>>(scores, steps, max_blocks, cap, ids);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_topk: %s\n", cudaGetErrorString(e)); std::exit(1); }
}
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
// STRATA_SCORES_DX: 0 off, 1 on for any CUDA card; unset: on for compute capability 6.x (block_scores_dx_kernel).
// `sms`: the device's multiprocessors (the grid: as many CTAs as fit on each).
static bool scores_dx_device(int& sms) {
static const int env = [] {
const char* v = std::getenv("STRATA_SCORES_DX");
return v == nullptr || *v == '\0' ? -1 : std::atoi(v);
}();
if (env == 0) return false;
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess) { cudaGetLastError(); return false; }
static thread_local int cached_device = -1, cached_sms = 0;
static thread_local bool pascal = false;
if (dev != cached_device) {
int major = 0;
pascal = cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev) == cudaSuccess &&
strata::cc_major_of(major) == 6;
if (cudaDeviceGetAttribute(&cached_sms, cudaDevAttrMultiProcessorCount, dev) != cudaSuccess) cached_sms = 0;
cudaGetLastError();
cached_device = dev;
}
sms = cached_sms;
return sms > 0 && (env > 0 || pascal);
}
template <int NQ>
static void scores_dx_launch(const float* pooled, const float* q_idx, const int32_t* steps, int64_t max_blocks,
float* scores, int sms, cudaStream_t st) {
const size_t smem = (size_t) (DX_NB * DX_KS + NQ * IDX_HEADS * IDX_DIM + NQ * IDX_HEADS * DX_NB) * sizeof(float);
static thread_local int per_sm[64][9] = {}; // CTAs per multiprocessor, by device and NQ
int dev = 0;
cudaGetDevice(&dev);
int& occ = per_sm[dev & 63][NQ];
if (occ == 0 && (cudaOccupancyMaxActiveBlocksPerMultiprocessor(&occ, block_scores_dx_kernel<NQ>, DX_T, smem) !=
cudaSuccess || occ < 1)) {
cudaGetLastError();
occ = 2;
}
const int64_t tiles = (max_blocks + DX_NB - 1) / DX_NB, want = (int64_t) occ * sms;
const unsigned grid = (unsigned) (want < tiles ? want : tiles);
block_scores_dx_kernel<NQ><<<grid, DX_T, smem, st>>>(pooled, q_idx, steps, max_blocks, scores);
}
static bool qsa_block_scores_dx(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps,
int64_t nq, int64_t max_blocks, float* scores, void* stream) {
int sms = 0;
if (nq < 1 || nq > MQ || !scores_dx_device(sms)) return false;
const cudaStream_t st = (cudaStream_t) stream;
switch (nq) {
case 1: scores_dx_launch<1>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 2: scores_dx_launch<2>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 3: scores_dx_launch<3>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 4: scores_dx_launch<4>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 5: scores_dx_launch<5>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 6: scores_dx_launch<6>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
case 7: scores_dx_launch<7>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
default: scores_dx_launch<8>(pooled, q_idx, steps, max_blocks, scores, sms, st); break;
}
block_scores_tail_kernel<<<(unsigned) nq, 32, 0, st>>>(dead, q_idx, steps, max_blocks, scores);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_scores (dx): %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
#endif
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
// STRATA_TOPK_MULTI: 0 off, 1 on for any CUDA card and capacity; unset: on for compute capability 6.x past the register
// kernel's reach (GP100: 0.39 -> 0.04 ms per call at 300K cells; see block_topk_multi_hist_kernel)
static int topk_multi_mode() {
static const int env = [] {
const char* v = std::getenv("STRATA_TOPK_MULTI");
return v == nullptr || *v == '\0' ? -1 : std::atoi(v);
}();
if (env >= 0) return env != 0 ? 1 : 0;
int dev = 0;
if (cudaGetDevice(&dev) != cudaSuccess) { cudaGetLastError(); return 0; }
static thread_local int cached_device = -1;
static thread_local int mode = 0;
if (dev != cached_device) {
int major = 0;
mode = cudaDeviceGetAttribute(&major, cudaDevAttrComputeCapabilityMajor, dev) == cudaSuccess &&
strata::cc_major_of(major) == 6 ? 2 : 0;
cudaGetLastError();
cached_device = dev;
}
return mode;
}
static bool qsa_block_topk_multi(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
int32_t* ids, void* stream, int32_t* scratch) {
// CTAs per query from the capacity (the grid is fixed in a captured graph; each CTA's share follows n_bid): one per
// 2,048 blocks, at most MT_NMAX. STRATA_TOPK_MULTI_N: a fixed count (tests)
static const int n_env = [] { const char* v = std::getenv("STRATA_TOPK_MULTI_N"); return v ? std::atoi(v) : 0; }();
int64_t n = n_env > 0 ? n_env : (max_blocks + 2047) / 2048;
n = n < 1 ? 1 : n > MT_NMAX ? MT_NMAX : n;
const dim3 grid((unsigned) n, (unsigned) nq);
const cudaStream_t st = (cudaStream_t) stream;
block_topk_multi_hist_kernel<0><<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, scratch);
block_topk_multi_hist_kernel<1><<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, scratch);
block_topk_multi_hist_kernel<2><<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, scratch);
block_topk_multi_hist_kernel<3><<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, scratch);
block_topk_multi_count_kernel<<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, scratch);
block_topk_multi_emit_kernel<<<grid, MT_T, 0, st>>>(scores, steps, max_blocks, cap, ids, scratch);
const cudaError_t e = cudaGetLastError();
if (e != cudaSuccess) { std::fprintf(stderr, "qsa_block_topk multi: %s\n", cudaGetErrorString(e)); std::exit(1); }
return true;
}
#endif
// ---- STRATA_SELECT_LONG (verify.cpp, opt-in): the decode select past ~64K cells. Outside the SM60 build (and on HIP)
// these are the plain calls; the scratch is never asked for.
int64_t qsa_topk_multi_scratch_ints(int64_t nq) {
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
return (nq < MT_MAXQ ? nq : MT_MAXQ) * (int64_t) MT_Q_INTS;
#else
(void) nq;
return 0;
#endif
}
void qsa_block_topk_long(const float* scores, const int32_t* steps, int64_t nq, int64_t max_blocks, int64_t cap,
const QsaShapes& s, int32_t* ids, void* stream, int64_t active_blocks, int32_t* multi_scratch) {
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
// several CTAs per query through the caller's scratch (decode calls: no active count, a few queries)
static const bool old = std::getenv("STRATA_TOPK_OLD") != nullptr;
if (nq > 0 && multi_scratch != nullptr && !old && active_blocks <= 0 && nq <= MT_MAXQ && s.idx_block == R &&
cap >= qsa_selection_width(kTopkMaxCells, s)) {
const int mode = topk_multi_mode();
if ((mode == 1 || (mode == 2 && max_blocks > (int64_t) TK_T * TK_PER)) &&
qsa_block_topk_multi(scores, steps, nq, max_blocks, cap, ids, stream, multi_scratch))
return;
}
#else
(void) multi_scratch;
#endif
qsa_block_topk(scores, steps, nq, max_blocks, cap, s, ids, stream, active_blocks);
}
void qsa_block_scores_long(const float* pooled, const float* dead, const float* q_idx, const int32_t* steps, int64_t nq,
int64_t max_blocks, const QsaShapes& s, float* scores, void* stream, int64_t active_blocks) {
#if !defined(__HIPCC__) && defined(STRATA_EXPERIMENTAL_SM60)
if (nq > 0 && s.idx_dim == IDX_DIM && s.idx_n_head == IDX_HEADS && s.idx_block == R && scores_multi_on() &&
nq <= MQ && active_blocks <= 0 &&
qsa_block_scores_dx(pooled, dead, q_idx, steps, nq, max_blocks, scores, stream))
return;
#endif
qsa_block_scores(pooled, dead, q_idx, steps, nq, max_blocks, s, scores, stream, active_blocks);
}
} // namespace strata::kernels