mirror of
https://github.com/FlashML-org/FreeToken.git
synced 2026-11-21 01:52:30 +08:00
* feat(spec): add the MTP proposer for the qwen3_5 family * test(models): read the qwen3_5 MTP head of bf16 and block-fp8 checkpoints * feat(spec): verify qwen4_exp targets on qsa_sparse graphs with PLE verify handlers * feat(spec): add the qwen4_exp MTP draft from the checkpoint or a Strata pack * docs(cli): document the speculative decoding flags * fix(spec): refuse MTP draft sources the draft cannot read before the target loads * docs(qwen4_exp): describe the verify path in the PLE docstrings * fix(spec): refuse a missing relative MTP draft path before the target loads * fix(moe): read MTP head experts on the host and require both stacked tensors * refactor(spec): tell the final prefill chunk from prompt_len instead of the scheduler's ChunkedReq * refactor(spec): let each MTP draft family check its own weight source * fix(qwen4_exp): size the disk PLE eager staging for decode and verify rows * perf(kernel): read the KV-index gather's chunk count from the grid, not a constexpr * refactor(moe): let each family name its MTP expert tensors * refactor(spec): force the MTP draft's MoE resident in the proposer and check it after load * fix(spec): refuse MTP with dummy weights * refactor(spec): move HiddenRelay under spec/mtp, its only user * refactor(spec): drop MTPDraft.config, fold its embed hooks into embed_tokens * refactor(models): note FeatureSink's graph binding, drop its runtime_checkable * fix(models): read quantized MTP fc projections under the quant config
1101 lines
39 KiB
Python
1101 lines
39 KiB
Python
from __future__ import annotations
|
|
|
|
import functools
|
|
|
|
import torch
|
|
import triton
|
|
import triton.language as tl
|
|
|
|
|
|
_MIN_BLOCK_KV = 32
|
|
|
|
|
|
# a long decode request takes splits of at least this many keys, so the partial result each one writes stays small next to the keys it reads
|
|
_MIN_SPLIT_LEN = 128
|
|
# a short request still takes up to this many splits of _MIN_BLOCK_KV keys, so tiny requests stay parallel
|
|
_MIN_SPLITS = 8
|
|
_MAX_KV_SPLITS = 64
|
|
# stage 2 merges at most this many fp32 partial elements per step
|
|
_STAGE2_TILE_ELEMS = 8192
|
|
|
|
|
|
def _stage2_launch(max_kv_splits: int, block_dv: int) -> tuple[int, int]:
|
|
"""(splits merged per step, num_warps) for stage 2; the tile is at most the split cap rounded up to a power of two."""
|
|
tile = min(triton.next_power_of_2(max_kv_splits), max(4, _STAGE2_TILE_ELEMS // block_dv), 64)
|
|
return tile, max(1, min(8, tile * block_dv // 2048))
|
|
|
|
|
|
def _max_request_splits(keys: int) -> int:
|
|
return max(triton.cdiv(keys, _MIN_SPLIT_LEN), min(_MIN_SPLITS, triton.cdiv(keys, _MIN_BLOCK_KV)), 1)
|
|
|
|
|
|
@functools.lru_cache(maxsize=None)
|
|
def _optin_smem_bytes(device_index: int) -> int:
|
|
"""Per-block opt-in shared-memory budget for a CUDA device (0 if unavailable)."""
|
|
props = torch.cuda.get_device_properties(device_index)
|
|
return int(getattr(props, "shared_memory_per_block_optin", 0))
|
|
|
|
|
|
@functools.lru_cache(maxsize=None)
|
|
def _num_sms(device_index: int) -> int:
|
|
return int(torch.cuda.get_device_properties(device_index).multi_processor_count)
|
|
|
|
|
|
def decode_kv_split_cap(batch: int, num_q_heads: int, num_kv_heads: int, device_index: int) -> int:
|
|
"""Most KV splits per request for a decode batch: about four programs per SM, within [_MIN_SPLITS, _MAX_KV_SPLITS]."""
|
|
head_blocks = triton.cdiv(num_q_heads, min(16, max(1, num_q_heads // num_kv_heads)))
|
|
return max(_MIN_SPLITS, min(_MAX_KV_SPLITS, triton.cdiv(4 * _num_sms(device_index), batch * head_blocks)))
|
|
|
|
|
|
def _select_extend_tile(head_dim: int, block_d: int, smem_optin: int) -> tuple[int, int]:
|
|
"""Pick ``(BLOCK_M, BLOCK_N)`` for the extend/prefill kernel, shared-memory aware.
|
|
|
|
Larger tiles run materially faster (~2x for head_dim 512 on H100) but their bf16
|
|
q/k/v tiles need about ``(BLOCK_M + 2 * BLOCK_N) * BLOCK_D * 2`` bytes of shared
|
|
memory, which overflows consumer GPUs (sm_89 ~99KB opt-in) once head_dim >= 256.
|
|
Keep the fast tiles where the device's opt-in shared memory fits them (datacenter
|
|
A100/H100); shrink only where it does not. ``smem_optin == 0`` (unknown) conservatively
|
|
selects the small tiles, i.e. the prior consumer-safe behavior.
|
|
"""
|
|
budget = smem_optin * 0.8 # headroom for scores/acc/alignment/triton scratch
|
|
|
|
def fits(block_m: int, block_n: int) -> bool:
|
|
return (block_m + 2 * block_n) * block_d * 2 <= budget
|
|
|
|
if head_dim <= 128:
|
|
return 128, 64
|
|
if head_dim <= 256:
|
|
return (128, 64) if fits(128, 64) else (64, 32)
|
|
if head_dim <= 384:
|
|
return (32, 64) if fits(32, 64) else (32, 32)
|
|
return (32, 64) if fits(32, 64) else (16, 16)
|
|
|
|
|
|
@triton.jit
|
|
def _paged_attention_kernel(
|
|
q_ptr,
|
|
k_ptr,
|
|
v_ptr,
|
|
o_ptr,
|
|
indptr_ptr,
|
|
indices_ptr,
|
|
q_to_req_ptr,
|
|
q_pos_ptr,
|
|
sm_scale,
|
|
sinks_ptr,
|
|
stride_qt,
|
|
stride_qh,
|
|
stride_ks,
|
|
stride_kh,
|
|
stride_vs,
|
|
stride_vh,
|
|
stride_ot,
|
|
stride_oh,
|
|
GROUP: tl.constexpr,
|
|
D: tl.constexpr,
|
|
BLOCK_D: tl.constexpr,
|
|
BLOCK_N: tl.constexpr,
|
|
SLIDING_WINDOW: tl.constexpr,
|
|
HAS_SINKS: tl.constexpr,
|
|
):
|
|
q_tok = tl.program_id(0)
|
|
q_head = tl.program_id(1)
|
|
kv_head = q_head // GROUP
|
|
|
|
req = tl.load(q_to_req_ptr + q_tok)
|
|
kv_start = tl.load(indptr_ptr + req)
|
|
kv_end = tl.load(indptr_ptr + req + 1)
|
|
kv_len = kv_end - kv_start
|
|
q_pos = tl.load(q_pos_ptr + q_tok)
|
|
|
|
offs_d = tl.arange(0, BLOCK_D)
|
|
mask_d = offs_d < D
|
|
q = tl.load(
|
|
q_ptr + q_tok * stride_qt + q_head * stride_qh + offs_d,
|
|
mask=mask_d,
|
|
other=0.0,
|
|
).to(tl.float32)
|
|
|
|
if HAS_SINKS:
|
|
m_i = tl.load(sinks_ptr + q_head).to(tl.float32)
|
|
l_i = 1.0
|
|
else:
|
|
m_i = -float("inf")
|
|
l_i = 0.0
|
|
acc = tl.zeros((BLOCK_D,), dtype=tl.float32)
|
|
|
|
for start in range(0, kv_len, BLOCK_N):
|
|
offs_n = start + tl.arange(0, BLOCK_N)
|
|
mask_n = offs_n < kv_len
|
|
k_pos = offs_n
|
|
causal_mask = k_pos <= q_pos
|
|
if SLIDING_WINDOW > 0:
|
|
causal_mask = causal_mask & ((k_pos + SLIDING_WINDOW) > q_pos)
|
|
mask_n = mask_n & causal_mask
|
|
|
|
skip_tile = tl.max(mask_n.to(tl.int32), axis=0) == 0
|
|
if not skip_tile:
|
|
slots = tl.load(indices_ptr + kv_start + offs_n, mask=offs_n < kv_len, other=0)
|
|
k = tl.load(
|
|
k_ptr
|
|
+ slots[:, None] * stride_ks
|
|
+ kv_head * stride_kh
|
|
+ offs_d[None, :],
|
|
mask=(offs_n[:, None] < kv_len) & mask_d[None, :],
|
|
other=0.0,
|
|
).to(tl.float32)
|
|
scores = tl.sum(q[None, :] * k, axis=1) * sm_scale
|
|
scores = tl.where(mask_n, scores, -float("inf"))
|
|
|
|
row_max = tl.max(scores, axis=0)
|
|
row_max_fixed = tl.where(row_max == -float("inf"), -1e20, row_max)
|
|
m_new = tl.maximum(row_max_fixed, m_i)
|
|
alpha = tl.exp(m_i - m_new)
|
|
p = tl.exp(scores - m_new)
|
|
|
|
v = tl.load(
|
|
v_ptr
|
|
+ slots[:, None] * stride_vs
|
|
+ kv_head * stride_vh
|
|
+ offs_d[None, :],
|
|
mask=(offs_n[:, None] < kv_len) & mask_d[None, :],
|
|
other=0.0,
|
|
).to(tl.float32)
|
|
acc = acc * alpha + tl.sum(p[:, None] * v, axis=0)
|
|
l_i = l_i * alpha + tl.sum(p, axis=0)
|
|
m_i = m_new
|
|
|
|
out = tl.where(l_i == 0.0, 0.0, acc / l_i)
|
|
tl.store(
|
|
o_ptr + q_tok * stride_ot + q_head * stride_oh + offs_d,
|
|
out.to(o_ptr.dtype.element_ty),
|
|
mask=mask_d,
|
|
)
|
|
|
|
|
|
@triton.jit
|
|
def _decode_num_splits(effective_len, max_kv_splits, MIN_SPLIT_LEN: tl.constexpr, MIN_SPLITS: tl.constexpr, MIN_BLOCK_KV: tl.constexpr):
|
|
# same rule as _max_request_splits: long requests split by length, short ones still take up to MIN_SPLITS small splits
|
|
by_len = tl.maximum(tl.cdiv(effective_len, MIN_SPLIT_LEN), tl.minimum(MIN_SPLITS, tl.cdiv(effective_len, MIN_BLOCK_KV)))
|
|
return tl.minimum(tl.maximum(by_len, 1), max_kv_splits)
|
|
|
|
|
|
@triton.jit(do_not_specialize=["max_kv_splits"])
|
|
def _decode_grouped_stage1_kernel(
|
|
q_ptr,
|
|
k_ptr,
|
|
v_ptr,
|
|
sm_scale,
|
|
indptr_ptr,
|
|
indices_ptr,
|
|
q_pos_ptr,
|
|
mid_o_ptr,
|
|
mid_lse_ptr,
|
|
max_kv_splits,
|
|
stride_qt,
|
|
stride_qh,
|
|
stride_ks,
|
|
stride_kh,
|
|
stride_vs,
|
|
stride_vh,
|
|
stride_mid_ob,
|
|
stride_mid_oh,
|
|
stride_mid_os,
|
|
stride_lse_b,
|
|
stride_lse_h,
|
|
stride_lse_s,
|
|
GROUP: tl.constexpr,
|
|
NUM_Q_HEADS: tl.constexpr,
|
|
BLOCK_D: tl.constexpr,
|
|
BLOCK_DV: tl.constexpr,
|
|
BLOCK_N: tl.constexpr,
|
|
BLOCK_H: tl.constexpr,
|
|
VALID_BLOCK_H: tl.constexpr,
|
|
MIN_BLOCK_KV: tl.constexpr,
|
|
MIN_SPLIT_LEN: tl.constexpr,
|
|
MIN_SPLITS: tl.constexpr,
|
|
D: tl.constexpr,
|
|
DV: tl.constexpr,
|
|
SLIDING_WINDOW: tl.constexpr,
|
|
):
|
|
batch_id = tl.program_id(0)
|
|
head_block_id = tl.program_id(1)
|
|
split_id = tl.program_id(2)
|
|
|
|
# VALID_BLOCK_H == min(cap, GROUP) is the number of query heads actually handled per program;
|
|
# BLOCK_H is the power-of-two tile size for the head axis (tl.arange requires a power of two),
|
|
# so a non-power-of-two GQA group (e.g. 24/4 == 6) rounds the tile up and masks the extra
|
|
# lanes. Each kv head spans cdiv(GROUP, VALID_BLOCK_H) head blocks.
|
|
kv_head = head_block_id // tl.cdiv(GROUP, VALID_BLOCK_H)
|
|
q_heads = head_block_id * VALID_BLOCK_H + tl.arange(0, BLOCK_H)
|
|
mask_h = q_heads < (head_block_id + 1) * VALID_BLOCK_H
|
|
mask_h = mask_h & (q_heads < NUM_Q_HEADS)
|
|
|
|
offs_d = tl.arange(0, BLOCK_D)
|
|
offs_dv = tl.arange(0, BLOCK_DV)
|
|
mask_d = offs_d < D
|
|
mask_dv = offs_dv < DV
|
|
|
|
kv_start = tl.load(indptr_ptr + batch_id)
|
|
kv_len = tl.load(indptr_ptr + batch_id + 1) - kv_start
|
|
q_pos = tl.load(q_pos_ptr + batch_id)
|
|
effective_end = tl.minimum(kv_len, q_pos + 1)
|
|
effective_start = 0
|
|
if SLIDING_WINDOW > 0:
|
|
effective_start = tl.maximum(0, q_pos - SLIDING_WINDOW + 1)
|
|
effective_len = tl.maximum(0, effective_end - effective_start)
|
|
|
|
kv_splits = _decode_num_splits(effective_len, max_kv_splits, MIN_SPLIT_LEN, MIN_SPLITS, MIN_BLOCK_KV)
|
|
kv_len_per_split = (
|
|
tl.cdiv(tl.cdiv(effective_len, kv_splits), MIN_BLOCK_KV) * MIN_BLOCK_KV
|
|
)
|
|
split_start = kv_len_per_split * split_id
|
|
split_end = tl.minimum(split_start + kv_len_per_split, effective_len)
|
|
|
|
m_i = tl.zeros((BLOCK_H,), dtype=tl.float32) - float("inf")
|
|
l_i = tl.zeros((BLOCK_H,), dtype=tl.float32)
|
|
acc = tl.zeros((BLOCK_H, BLOCK_DV), dtype=tl.float32)
|
|
|
|
q_offsets = batch_id * stride_qt + q_heads[:, None] * stride_qh + offs_d[None, :]
|
|
k_base_offsets = kv_head * stride_kh + offs_d[:, None]
|
|
v_base_offsets = kv_head * stride_vh + offs_dv[None, :]
|
|
|
|
if split_end > split_start:
|
|
q = tl.load(q_ptr + q_offsets, mask=mask_h[:, None] & mask_d[None, :], other=0.0)
|
|
q = q.to(k_ptr.dtype.element_ty)
|
|
|
|
for rel_start in tl.range(split_start, split_end, BLOCK_N):
|
|
rel_offs = rel_start + tl.arange(0, BLOCK_N)
|
|
mask_n = rel_offs < split_end
|
|
logical_offs = effective_start + rel_offs
|
|
slots = tl.load(indices_ptr + kv_start + logical_offs, mask=mask_n, other=0)
|
|
|
|
k = tl.load(
|
|
k_ptr + slots[None, :] * stride_ks + k_base_offsets,
|
|
mask=mask_n[None, :] & mask_d[:, None],
|
|
other=0.0,
|
|
)
|
|
scores = tl.dot(q, k) * sm_scale
|
|
scores = tl.where(mask_h[:, None] & mask_n[None, :], scores, -float("inf"))
|
|
|
|
v = tl.load(
|
|
v_ptr + slots[:, None] * stride_vs + v_base_offsets,
|
|
mask=mask_n[:, None] & mask_dv[None, :],
|
|
other=0.0,
|
|
)
|
|
|
|
m_new = tl.maximum(tl.max(scores, axis=1), m_i)
|
|
alpha = tl.exp(m_i - m_new)
|
|
p = tl.exp(scores - m_new[:, None])
|
|
acc = acc * alpha[:, None] + tl.dot(p.to(v.dtype), v)
|
|
l_i = l_i * alpha + tl.sum(p, axis=1)
|
|
m_i = m_new
|
|
|
|
out = acc / l_i[:, None]
|
|
mid_offsets = (
|
|
batch_id * stride_mid_ob
|
|
+ q_heads[:, None] * stride_mid_oh
|
|
+ split_id * stride_mid_os
|
|
+ offs_dv[None, :]
|
|
)
|
|
tl.store(mid_o_ptr + mid_offsets, out, mask=mask_h[:, None] & mask_dv[None, :])
|
|
|
|
lse_offsets = (
|
|
batch_id * stride_lse_b
|
|
+ q_heads * stride_lse_h
|
|
+ split_id * stride_lse_s
|
|
)
|
|
tl.store(mid_lse_ptr + lse_offsets, m_i + tl.log(l_i), mask=mask_h)
|
|
|
|
|
|
@triton.jit(do_not_specialize=["max_kv_splits"])
|
|
def _decode_stage2_kernel(
|
|
mid_o_ptr,
|
|
mid_lse_ptr,
|
|
o_ptr,
|
|
indptr_ptr,
|
|
q_pos_ptr,
|
|
max_kv_splits,
|
|
sinks_ptr,
|
|
stride_mid_ob,
|
|
stride_mid_oh,
|
|
stride_mid_os,
|
|
stride_lse_b,
|
|
stride_lse_h,
|
|
stride_lse_s,
|
|
stride_ot,
|
|
stride_oh,
|
|
MIN_BLOCK_KV: tl.constexpr,
|
|
MIN_SPLIT_LEN: tl.constexpr,
|
|
MIN_SPLITS: tl.constexpr,
|
|
BLOCK_DV: tl.constexpr,
|
|
DV: tl.constexpr,
|
|
SLIDING_WINDOW: tl.constexpr,
|
|
HAS_SINKS: tl.constexpr,
|
|
SPLIT_TILE: tl.constexpr,
|
|
):
|
|
batch_id = tl.program_id(0)
|
|
q_head = tl.program_id(1)
|
|
|
|
kv_len = tl.load(indptr_ptr + batch_id + 1) - tl.load(indptr_ptr + batch_id)
|
|
q_pos = tl.load(q_pos_ptr + batch_id)
|
|
effective_end = tl.minimum(kv_len, q_pos + 1)
|
|
effective_start = 0
|
|
if SLIDING_WINDOW > 0:
|
|
effective_start = tl.maximum(0, q_pos - SLIDING_WINDOW + 1)
|
|
effective_len = tl.maximum(0, effective_end - effective_start)
|
|
|
|
kv_splits = _decode_num_splits(effective_len, max_kv_splits, MIN_SPLIT_LEN, MIN_SPLITS, MIN_BLOCK_KV)
|
|
kv_len_per_split = (
|
|
tl.cdiv(tl.cdiv(effective_len, kv_splits), MIN_BLOCK_KV) * MIN_BLOCK_KV
|
|
)
|
|
|
|
offs_d = tl.arange(0, BLOCK_DV)
|
|
mask_d = offs_d < DV
|
|
offs_s = tl.arange(0, SPLIT_TILE)
|
|
if HAS_SINKS:
|
|
m_i = tl.load(sinks_ptr + q_head).to(tl.float32)
|
|
l_i = 1.0
|
|
else:
|
|
m_i = -float("inf")
|
|
l_i = 0.0
|
|
acc = tl.zeros((BLOCK_DV,), dtype=tl.float32)
|
|
|
|
mid_base = batch_id * stride_mid_ob + q_head * stride_mid_oh
|
|
lse_base = batch_id * stride_lse_b + q_head * stride_lse_h
|
|
|
|
# one load round trip per SPLIT_TILE splits
|
|
for s0 in range(0, kv_splits, SPLIT_TILE):
|
|
split_id = s0 + offs_s
|
|
valid = (split_id < kv_splits) & (kv_len_per_split * split_id < effective_len)
|
|
partial_lse = tl.load(mid_lse_ptr + lse_base + split_id * stride_lse_s, mask=valid, other=-float("inf"))
|
|
partial = tl.load(
|
|
mid_o_ptr + mid_base + split_id[:, None] * stride_mid_os + offs_d[None, :],
|
|
mask=valid[:, None] & mask_d[None, :],
|
|
other=0.0,
|
|
)
|
|
m_new = tl.maximum(m_i, tl.max(partial_lse, axis=0))
|
|
# a tile of empty splits with no sink leaves m at -inf, where exp(-inf - -inf) is nan
|
|
m_safe = tl.where(m_new == -float("inf"), 0.0, m_new)
|
|
alpha = tl.exp(m_i - m_safe)
|
|
beta = tl.exp(partial_lse - m_safe)
|
|
acc = acc * alpha + tl.sum(partial * beta[:, None], axis=0)
|
|
l_i = l_i * alpha + tl.sum(beta, axis=0)
|
|
m_i = m_new
|
|
|
|
out = tl.where(l_i == 0.0, 0.0, acc / l_i)
|
|
tl.store(
|
|
o_ptr + batch_id * stride_ot + q_head * stride_oh + offs_d,
|
|
out.to(o_ptr.dtype.element_ty),
|
|
mask=mask_d,
|
|
)
|
|
|
|
|
|
def decode_paged_attention(
|
|
q: torch.Tensor,
|
|
k_cache: torch.Tensor,
|
|
v_cache: torch.Tensor,
|
|
indptr: torch.Tensor,
|
|
indices: torch.Tensor,
|
|
q_positions: torch.Tensor,
|
|
attn_logits: torch.Tensor,
|
|
attn_lse: torch.Tensor,
|
|
sm_scale: float,
|
|
sliding_window: int | None = None,
|
|
sinks: torch.Tensor | None = None,
|
|
out: torch.Tensor | None = None,
|
|
max_kv_splits: int | None = None,
|
|
) -> torch.Tensor:
|
|
"""SGLang-style split-k grouped decode attention for one query per request.
|
|
|
|
Each request takes ``max(ceil(keys / 128), min(8, ceil(keys / 32)))`` splits, capped by ``max_kv_splits`` (default :func:`decode_kv_split_cap`) and by the split dim of ``attn_logits`` / ``attn_lse``.
|
|
The kernels compute the split count on the device, so a captured graph serves any context length.
|
|
"""
|
|
|
|
assert q.is_cuda and k_cache.is_cuda and v_cache.is_cuda
|
|
assert q.dim() == 3 and k_cache.dim() == 3 and v_cache.dim() == 3
|
|
batch, num_q_heads, head_dim = q.shape
|
|
num_kv_heads = k_cache.shape[1]
|
|
assert batch == indptr.numel() - 1
|
|
assert v_cache.shape[1] == num_kv_heads
|
|
assert k_cache.shape[-1] == head_dim and v_cache.shape[-1] == head_dim
|
|
assert num_q_heads % num_kv_heads == 0
|
|
assert attn_logits.shape[0] >= batch
|
|
assert attn_logits.shape[1] >= num_q_heads
|
|
assert attn_logits.shape[3] >= head_dim
|
|
assert attn_lse.shape[0] >= batch
|
|
assert attn_lse.shape[1] >= num_q_heads
|
|
if sliding_window is not None and sliding_window <= 0:
|
|
# the kernels treat a window <= 0 as no window
|
|
sliding_window = None
|
|
if max_kv_splits is None:
|
|
max_kv_splits = decode_kv_split_cap(batch, num_q_heads, num_kv_heads, q.device.index)
|
|
if sliding_window:
|
|
# no request attends more than the window, so programs past its splits would only exit
|
|
max_kv_splits = min(max_kv_splits, _max_request_splits(sliding_window))
|
|
max_kv_splits = min(max_kv_splits, attn_logits.shape[2], attn_lse.shape[2])
|
|
if sinks is not None:
|
|
assert sinks.is_cuda
|
|
assert sinks.dim() == 1
|
|
assert sinks.numel() >= num_q_heads
|
|
sinks = sinks.contiguous()
|
|
|
|
o = out if out is not None else torch.empty_like(q)
|
|
sinks_arg = sinks if sinks is not None else q
|
|
group = num_q_heads // num_kv_heads
|
|
# valid_block_h = heads computed per program (drives the grid + head indexing); block_h =
|
|
# power-of-two tile size for tl.arange. They differ only for non-power-of-two GQA groups
|
|
# (e.g. 6), where block_h rounds up and the kernel masks the extra lanes.
|
|
valid_block_h = min(16, group)
|
|
block_h = triton.next_power_of_2(valid_block_h)
|
|
block_d = triton.next_power_of_2(head_dim)
|
|
block_dv = triton.next_power_of_2(head_dim)
|
|
grid = (batch, triton.cdiv(num_q_heads, valid_block_h), max_kv_splits)
|
|
# a grid that fits in one wave runs about one program per SM, which then needs wider tiles to keep enough loads in flight
|
|
block_n = 64 if grid[0] * grid[1] * grid[2] <= _num_sms(q.device.index) else _MIN_BLOCK_KV
|
|
num_stages = 3
|
|
# stage 1 keeps the Q tile and one K and one V tile in shared memory
|
|
smem = _optin_smem_bytes(q.device.index)
|
|
elem = k_cache.element_size()
|
|
if 2 * block_n * block_d * elem > 0.8 * smem:
|
|
block_n = _MIN_BLOCK_KV
|
|
# 64 KiB parts (sm_75) cannot fit a head_dim 512 Q tile next to 32-row K/V tiles:
|
|
# halve the KV tile down to tl.dot's 16-row minimum until the three tiles fit.
|
|
while smem and block_n > 16 and (block_h * block_d + 2 * block_n * block_d) * elem > smem:
|
|
block_n //= 2
|
|
if sliding_window:
|
|
split_len = triton.cdiv(triton.cdiv(sliding_window, max_kv_splits), _MIN_BLOCK_KV) * _MIN_BLOCK_KV
|
|
if split_len <= block_n:
|
|
# a full window's split fits in one tile, where a deeper pipeline only adds overhead
|
|
block_n, num_stages = split_len, 2
|
|
|
|
_decode_grouped_stage1_kernel[grid](
|
|
q,
|
|
k_cache,
|
|
v_cache,
|
|
sm_scale,
|
|
indptr,
|
|
indices,
|
|
q_positions,
|
|
attn_logits,
|
|
attn_lse,
|
|
max_kv_splits,
|
|
q.stride(0),
|
|
q.stride(1),
|
|
k_cache.stride(0),
|
|
k_cache.stride(1),
|
|
v_cache.stride(0),
|
|
v_cache.stride(1),
|
|
attn_logits.stride(0),
|
|
attn_logits.stride(1),
|
|
attn_logits.stride(2),
|
|
attn_lse.stride(0),
|
|
attn_lse.stride(1),
|
|
attn_lse.stride(2),
|
|
GROUP=group,
|
|
NUM_Q_HEADS=num_q_heads,
|
|
BLOCK_D=block_d,
|
|
BLOCK_DV=block_dv,
|
|
BLOCK_N=block_n,
|
|
BLOCK_H=block_h,
|
|
VALID_BLOCK_H=valid_block_h,
|
|
MIN_BLOCK_KV=_MIN_BLOCK_KV,
|
|
MIN_SPLIT_LEN=_MIN_SPLIT_LEN,
|
|
MIN_SPLITS=_MIN_SPLITS,
|
|
D=head_dim,
|
|
DV=head_dim,
|
|
SLIDING_WINDOW=sliding_window or 0,
|
|
num_warps=4,
|
|
num_stages=num_stages,
|
|
)
|
|
split_tile, stage2_warps = _stage2_launch(max_kv_splits, block_dv)
|
|
_decode_stage2_kernel[(batch, num_q_heads)](
|
|
attn_logits,
|
|
attn_lse,
|
|
o,
|
|
indptr,
|
|
q_positions,
|
|
max_kv_splits,
|
|
sinks_arg,
|
|
attn_logits.stride(0),
|
|
attn_logits.stride(1),
|
|
attn_logits.stride(2),
|
|
attn_lse.stride(0),
|
|
attn_lse.stride(1),
|
|
attn_lse.stride(2),
|
|
o.stride(0),
|
|
o.stride(1),
|
|
MIN_BLOCK_KV=_MIN_BLOCK_KV,
|
|
MIN_SPLIT_LEN=_MIN_SPLIT_LEN,
|
|
MIN_SPLITS=_MIN_SPLITS,
|
|
BLOCK_DV=block_dv,
|
|
DV=head_dim,
|
|
SLIDING_WINDOW=sliding_window or 0,
|
|
HAS_SINKS=sinks is not None,
|
|
SPLIT_TILE=split_tile,
|
|
num_warps=stage2_warps,
|
|
)
|
|
return o
|
|
|
|
|
|
@triton.jit
|
|
def _extend_attention_kernel(
|
|
q_ptr,
|
|
k_ptr,
|
|
v_ptr,
|
|
o_ptr,
|
|
qo_indptr_ptr,
|
|
kv_indptr_ptr,
|
|
kv_indices_ptr,
|
|
prefix_lens_ptr,
|
|
block_ends_ptr,
|
|
sm_scale,
|
|
sinks_ptr,
|
|
stride_qt,
|
|
stride_qh,
|
|
stride_ks,
|
|
stride_kh,
|
|
stride_vs,
|
|
stride_vh,
|
|
stride_ot,
|
|
stride_oh,
|
|
GROUP: tl.constexpr,
|
|
D: tl.constexpr,
|
|
BLOCK_D: tl.constexpr,
|
|
BLOCK_DV: tl.constexpr,
|
|
BLOCK_M: tl.constexpr,
|
|
BLOCK_N: tl.constexpr,
|
|
SLIDING_WINDOW: tl.constexpr,
|
|
HAS_SINKS: tl.constexpr,
|
|
HAS_BLOCKS: tl.constexpr,
|
|
):
|
|
seq_id = tl.program_id(0)
|
|
q_head = tl.program_id(1)
|
|
block_m_id = tl.program_id(2)
|
|
kv_head = q_head // GROUP
|
|
|
|
q_start = tl.load(qo_indptr_ptr + seq_id)
|
|
q_end = tl.load(qo_indptr_ptr + seq_id + 1)
|
|
q_len = q_end - q_start
|
|
kv_start = tl.load(kv_indptr_ptr + seq_id)
|
|
kv_len = tl.load(kv_indptr_ptr + seq_id + 1) - kv_start
|
|
prefix_len = tl.load(prefix_lens_ptr + seq_id)
|
|
|
|
offs_m = block_m_id * BLOCK_M + tl.arange(0, BLOCK_M)
|
|
offs_n = tl.arange(0, BLOCK_N)
|
|
offs_d = tl.arange(0, BLOCK_D)
|
|
offs_dv = tl.arange(0, BLOCK_DV)
|
|
mask_m = offs_m < q_len
|
|
mask_d = offs_d < D
|
|
mask_dv = offs_dv < D
|
|
q_abs_pos = prefix_len + offs_m
|
|
block_q_end = tl.minimum(q_len, (block_m_id + 1) * BLOCK_M)
|
|
kv_loop_end = tl.minimum(kv_len, prefix_len + block_q_end)
|
|
if HAS_BLOCKS:
|
|
# rows inside a multimodal span also attend forward to the span's later keys: the tile loop must reach them
|
|
block_end = tl.load(block_ends_ptr + q_start + offs_m, mask=mask_m, other=0)
|
|
kv_loop_end = tl.minimum(kv_len, tl.maximum(kv_loop_end, tl.max(block_end, axis=0)))
|
|
else:
|
|
block_end = tl.zeros((BLOCK_M,), dtype=tl.int32)
|
|
|
|
q = tl.load(
|
|
q_ptr + (q_start + offs_m[:, None]) * stride_qt + q_head * stride_qh + offs_d[None, :],
|
|
mask=mask_m[:, None] & mask_d[None, :],
|
|
other=0.0,
|
|
)
|
|
|
|
if HAS_SINKS:
|
|
sink = tl.load(sinks_ptr + q_head).to(tl.float32)
|
|
m_i = tl.full((BLOCK_M,), sink, dtype=tl.float32)
|
|
l_i = tl.full((BLOCK_M,), 1.0, dtype=tl.float32)
|
|
else:
|
|
m_i = tl.zeros((BLOCK_M,), dtype=tl.float32) - float("inf")
|
|
l_i = tl.zeros((BLOCK_M,), dtype=tl.float32)
|
|
acc = tl.zeros((BLOCK_M, BLOCK_DV), dtype=tl.float32)
|
|
|
|
for start_n in tl.range(0, kv_loop_end, BLOCK_N):
|
|
kv_offsets = start_n + offs_n
|
|
mask_n = kv_offsets < kv_len
|
|
key_pos = kv_offsets
|
|
causal_mask = key_pos[None, :] <= q_abs_pos[:, None]
|
|
if HAS_BLOCKS:
|
|
causal_mask = causal_mask | (key_pos[None, :] < block_end[:, None])
|
|
if SLIDING_WINDOW > 0:
|
|
causal_mask = causal_mask & ((key_pos[None, :] + SLIDING_WINDOW) > q_abs_pos[:, None])
|
|
final_mask = mask_m[:, None] & mask_n[None, :] & causal_mask
|
|
|
|
skip_tile = tl.max(tl.max(final_mask.to(tl.int32), axis=1), axis=0) == 0
|
|
if not skip_tile:
|
|
slots = tl.load(kv_indices_ptr + kv_start + kv_offsets, mask=mask_n, other=0)
|
|
k = tl.load(
|
|
k_ptr
|
|
+ slots[None, :] * stride_ks
|
|
+ kv_head * stride_kh
|
|
+ offs_d[:, None],
|
|
mask=mask_n[None, :] & mask_d[:, None],
|
|
other=0.0,
|
|
)
|
|
scores = tl.dot(q.to(k.dtype), k) * sm_scale
|
|
scores = tl.where(final_mask, scores, -float("inf"))
|
|
|
|
row_max = tl.max(scores, axis=1)
|
|
row_max_fixed = tl.where(row_max == -float("inf"), -1e20, row_max)
|
|
m_new = tl.maximum(row_max_fixed, m_i)
|
|
alpha = tl.exp(m_i - m_new)
|
|
p = tl.exp(scores - m_new[:, None])
|
|
|
|
v = tl.load(
|
|
v_ptr
|
|
+ slots[:, None] * stride_vs
|
|
+ kv_head * stride_vh
|
|
+ offs_dv[None, :],
|
|
mask=mask_n[:, None] & mask_dv[None, :],
|
|
other=0.0,
|
|
)
|
|
acc = acc * alpha[:, None] + tl.dot(p.to(v.dtype), v)
|
|
l_i = l_i * alpha + tl.sum(p, axis=1)
|
|
m_i = m_new
|
|
|
|
out = tl.where(l_i[:, None] == 0.0, 0.0, acc / l_i[:, None])
|
|
tl.store(
|
|
o_ptr
|
|
+ (q_start + offs_m[:, None]) * stride_ot
|
|
+ q_head * stride_oh
|
|
+ offs_dv[None, :],
|
|
out.to(o_ptr.dtype.element_ty),
|
|
mask=mask_m[:, None] & mask_dv[None, :],
|
|
)
|
|
|
|
|
|
@triton.jit
|
|
def _extend_attend_tile(
|
|
q, m_i, l_i, acc, qk_scale, k_base, v_base, k_rows, v_rows, offs_d, offs_dv, mask_d, mask_dv, mask_n, mask,
|
|
MASKED: tl.constexpr,
|
|
):
|
|
if MASKED:
|
|
k_mask = mask_n[None, :] & mask_d[:, None]
|
|
v_mask = mask_n[:, None] & mask_dv[None, :]
|
|
else:
|
|
k_mask = mask_d[:, None]
|
|
v_mask = mask_dv[None, :]
|
|
k = tl.load(k_base + k_rows[None, :] + offs_d[:, None], mask=k_mask, other=0.0)
|
|
scores = tl.dot(q.to(k.dtype), k)
|
|
if MASKED:
|
|
scores = tl.where(mask, scores, -float("inf"))
|
|
m_new = tl.maximum(m_i, tl.max(scores, axis=1) * qk_scale)
|
|
if MASKED:
|
|
m_new = tl.where(m_new == -float("inf"), -1e20, m_new)
|
|
alpha = tl.math.exp2(m_i - m_new)
|
|
p = tl.math.exp2(scores * qk_scale - m_new[:, None])
|
|
v = tl.load(v_base + v_rows[:, None] + offs_dv[None, :], mask=v_mask, other=0.0)
|
|
acc = acc * alpha[:, None] + tl.dot(p.to(v.dtype), v)
|
|
l_i = l_i * alpha + tl.sum(p, axis=1)
|
|
return m_new, l_i, acc
|
|
|
|
|
|
@triton.jit
|
|
def _extend_tile_ranges(
|
|
first_row, diag, end, BLOCK_M: tl.constexpr, BLOCK_N: tl.constexpr, SLIDING_WINDOW: tl.constexpr
|
|
):
|
|
"""Split keys [0, end) seen by rows first_row + [0, BLOCK_M) into skipped [0, lo), masked [lo, u0), unmasked [u0, u1) and masked [u1, end); keys below diag are causal for every row."""
|
|
if SLIDING_WINDOW > 0:
|
|
lo = tl.minimum(tl.maximum(first_row - SLIDING_WINDOW + 1, 0) // BLOCK_N * BLOCK_N, end)
|
|
full = tl.cdiv(tl.maximum(first_row + BLOCK_M - SLIDING_WINDOW, 0), BLOCK_N) * BLOCK_N
|
|
else:
|
|
lo = 0
|
|
full = 0
|
|
u1 = tl.maximum(diag, lo)
|
|
u0 = tl.minimum(tl.maximum(full, lo), u1)
|
|
return lo, u0, u1
|
|
|
|
|
|
@triton.jit
|
|
def _extend_attention_split_kernel(
|
|
q_ptr,
|
|
k_extend_ptr,
|
|
v_extend_ptr,
|
|
k_cache_ptr,
|
|
v_cache_ptr,
|
|
o_ptr,
|
|
qo_indptr_ptr,
|
|
kv_indptr_ptr,
|
|
kv_indices_ptr,
|
|
prefix_lens_ptr,
|
|
block_ends_ptr,
|
|
sm_scale,
|
|
sinks_ptr,
|
|
stride_qt,
|
|
stride_qh,
|
|
stride_ket,
|
|
stride_keh,
|
|
stride_vet,
|
|
stride_veh,
|
|
stride_kcs,
|
|
stride_kch,
|
|
stride_vcs,
|
|
stride_vch,
|
|
stride_ot,
|
|
stride_oh,
|
|
GROUP: tl.constexpr,
|
|
D: tl.constexpr,
|
|
BLOCK_D: tl.constexpr,
|
|
BLOCK_DV: tl.constexpr,
|
|
BLOCK_M: tl.constexpr,
|
|
BLOCK_N: tl.constexpr,
|
|
SLIDING_WINDOW: tl.constexpr,
|
|
HAS_SINKS: tl.constexpr,
|
|
HAS_BLOCKS: tl.constexpr,
|
|
):
|
|
seq_id = tl.program_id(0)
|
|
q_head = tl.program_id(1)
|
|
block_m_id = tl.program_id(2)
|
|
kv_head = q_head // GROUP
|
|
|
|
q_start = tl.load(qo_indptr_ptr + seq_id)
|
|
q_len = tl.load(qo_indptr_ptr + seq_id + 1) - q_start
|
|
kv_start = tl.load(kv_indptr_ptr + seq_id)
|
|
prefix_len = tl.load(prefix_lens_ptr + seq_id)
|
|
|
|
block_start = block_m_id * BLOCK_M
|
|
offs_m = block_start + tl.arange(0, BLOCK_M)
|
|
offs_n = tl.arange(0, BLOCK_N)
|
|
offs_d = tl.arange(0, BLOCK_D)
|
|
offs_dv = tl.arange(0, BLOCK_DV)
|
|
mask_m = offs_m < q_len
|
|
mask_d = offs_d < D
|
|
mask_dv = offs_dv < D
|
|
q_abs_pos = prefix_len + offs_m
|
|
# Scores live in the log2 domain: exp2 lowers to ex2.approx.ftz, while tl.exp adds a denormal fixup per element.
|
|
qk_scale = sm_scale * 1.4426950408889634
|
|
|
|
q = tl.load(
|
|
q_ptr
|
|
+ (q_start + offs_m[:, None]) * stride_qt
|
|
+ q_head * stride_qh
|
|
+ offs_d[None, :],
|
|
mask=mask_m[:, None] & mask_d[None, :],
|
|
other=0.0,
|
|
)
|
|
|
|
if HAS_SINKS:
|
|
sink = tl.load(sinks_ptr + q_head).to(tl.float32) * 1.4426950408889634
|
|
m_i = tl.full((BLOCK_M,), sink, dtype=tl.float32)
|
|
l_i = tl.full((BLOCK_M,), 1.0, dtype=tl.float32)
|
|
else:
|
|
m_i = tl.zeros((BLOCK_M,), dtype=tl.float32) - float("inf")
|
|
l_i = tl.zeros((BLOCK_M,), dtype=tl.float32)
|
|
acc = tl.zeros((BLOCK_M, BLOCK_DV), dtype=tl.float32)
|
|
|
|
kc_base = k_cache_ptr + kv_head * stride_kch
|
|
vc_base = v_cache_ptr + kv_head * stride_vch
|
|
prefix_end = tl.where(block_start < q_len, prefix_len, 0)
|
|
lo, u0, u1 = _extend_tile_ranges(
|
|
prefix_len + block_start, prefix_end // BLOCK_N * BLOCK_N, prefix_end, BLOCK_M, BLOCK_N, SLIDING_WINDOW
|
|
)
|
|
for start_n in tl.range(u0, u1, BLOCK_N):
|
|
slots = tl.load(kv_indices_ptr + kv_start + start_n + offs_n)
|
|
m_i, l_i, acc = _extend_attend_tile(
|
|
q, m_i, l_i, acc, qk_scale, kc_base, vc_base, slots * stride_kcs, slots * stride_vcs,
|
|
offs_d, offs_dv, mask_d, mask_dv, None, None, False,
|
|
)
|
|
n_left = (u0 - lo) // BLOCK_N
|
|
for i in tl.range(0, n_left + tl.cdiv(prefix_end - u1, BLOCK_N)):
|
|
kv_offsets = tl.where(i < n_left, lo + i * BLOCK_N, u1 + (i - n_left) * BLOCK_N) + offs_n
|
|
mask_n = kv_offsets < prefix_end
|
|
final_mask = mask_n[None, :]
|
|
if SLIDING_WINDOW > 0:
|
|
final_mask = final_mask & ((kv_offsets[None, :] + SLIDING_WINDOW) > q_abs_pos[:, None])
|
|
slots = tl.load(kv_indices_ptr + kv_start + kv_offsets, mask=mask_n, other=0)
|
|
m_i, l_i, acc = _extend_attend_tile(
|
|
q, m_i, l_i, acc, qk_scale, kc_base, vc_base, slots * stride_kcs, slots * stride_vcs,
|
|
offs_d, offs_dv, mask_d, mask_dv, mask_n, final_mask, True,
|
|
)
|
|
|
|
ke_base = k_extend_ptr + kv_head * stride_keh
|
|
ve_base = v_extend_ptr + kv_head * stride_veh
|
|
current_end = tl.minimum(q_len, block_start + BLOCK_M)
|
|
if HAS_BLOCKS:
|
|
# rows inside a multimodal span also attend forward to the span's later keys: the tile loop must reach them
|
|
block_end = tl.load(block_ends_ptr + q_start + offs_m, mask=mask_m, other=0) - prefix_len
|
|
current_end = tl.minimum(q_len, tl.maximum(current_end, tl.max(block_end, axis=0)))
|
|
else:
|
|
block_end = tl.zeros((BLOCK_M,), dtype=tl.int32)
|
|
current_end = tl.where(block_start < q_len, current_end, 0)
|
|
lo, u0, u1 = _extend_tile_ranges(
|
|
block_start, tl.minimum(block_start // BLOCK_N * BLOCK_N, current_end), current_end, BLOCK_M, BLOCK_N,
|
|
SLIDING_WINDOW,
|
|
)
|
|
for start_n in tl.range(u0, u1, BLOCK_N):
|
|
rows = q_start + start_n + offs_n
|
|
m_i, l_i, acc = _extend_attend_tile(
|
|
q, m_i, l_i, acc, qk_scale, ke_base, ve_base, rows * stride_ket, rows * stride_vet,
|
|
offs_d, offs_dv, mask_d, mask_dv, None, None, False,
|
|
)
|
|
n_left = (u0 - lo) // BLOCK_N
|
|
for i in tl.range(0, n_left + tl.cdiv(current_end - u1, BLOCK_N)):
|
|
local_kv_offsets = tl.where(i < n_left, lo + i * BLOCK_N, u1 + (i - n_left) * BLOCK_N) + offs_n
|
|
mask_n = local_kv_offsets < current_end
|
|
local_q_pos = offs_m
|
|
causal_mask = local_kv_offsets[None, :] <= local_q_pos[:, None]
|
|
if HAS_BLOCKS:
|
|
causal_mask = causal_mask | (local_kv_offsets[None, :] < block_end[:, None])
|
|
if SLIDING_WINDOW > 0:
|
|
causal_mask = causal_mask & (
|
|
(local_kv_offsets[None, :] + SLIDING_WINDOW) > local_q_pos[:, None]
|
|
)
|
|
final_mask = mask_n[None, :] & causal_mask
|
|
rows = q_start + local_kv_offsets
|
|
m_i, l_i, acc = _extend_attend_tile(
|
|
q, m_i, l_i, acc, qk_scale, ke_base, ve_base, rows * stride_ket, rows * stride_vet,
|
|
offs_d, offs_dv, mask_d, mask_dv, mask_n, final_mask, True,
|
|
)
|
|
|
|
out = tl.where(l_i[:, None] == 0.0, 0.0, acc / l_i[:, None])
|
|
tl.store(
|
|
o_ptr
|
|
+ (q_start + offs_m[:, None]) * stride_ot
|
|
+ q_head * stride_oh
|
|
+ offs_dv[None, :],
|
|
out.to(o_ptr.dtype.element_ty),
|
|
mask=mask_m[:, None] & mask_dv[None, :],
|
|
)
|
|
|
|
|
|
def extend_paged_attention(
|
|
q: torch.Tensor,
|
|
k_cache: torch.Tensor,
|
|
v_cache: torch.Tensor,
|
|
qo_indptr: torch.Tensor,
|
|
kv_indptr: torch.Tensor,
|
|
kv_indices: torch.Tensor,
|
|
prefix_lens: torch.Tensor,
|
|
max_q_len: int,
|
|
sm_scale: float,
|
|
sliding_window: int | None = None,
|
|
sinks: torch.Tensor | None = None,
|
|
out: torch.Tensor | None = None,
|
|
k_extend: torch.Tensor | None = None,
|
|
v_extend: torch.Tensor | None = None,
|
|
block_ends: torch.Tensor | None = None,
|
|
) -> torch.Tensor:
|
|
"""Block-tiled causal prefill/extend attention over paged KV cache; block_ends holds per query token the end of the multimodal span it sits in (0 for none), whose later keys the row also attends."""
|
|
|
|
assert q.is_cuda and k_cache.is_cuda and v_cache.is_cuda
|
|
assert q.dim() == 3 and k_cache.dim() == 3 and v_cache.dim() == 3
|
|
num_q_tokens, num_q_heads, head_dim = q.shape
|
|
num_kv_heads = k_cache.shape[1]
|
|
assert qo_indptr.numel() == kv_indptr.numel()
|
|
assert prefix_lens.numel() == qo_indptr.numel() - 1
|
|
assert v_cache.shape[1] == num_kv_heads
|
|
assert k_cache.shape[-1] == head_dim and v_cache.shape[-1] == head_dim
|
|
assert num_q_heads % num_kv_heads == 0
|
|
if sinks is not None:
|
|
assert sinks.is_cuda
|
|
assert sinks.dim() == 1
|
|
assert sinks.numel() >= num_q_heads
|
|
sinks = sinks.contiguous()
|
|
|
|
if block_ends is not None:
|
|
assert block_ends.is_cuda and block_ends.dtype == torch.int32 and block_ends.numel() == num_q_tokens
|
|
o = out if out is not None else torch.empty_like(q)
|
|
sinks_arg = sinks if sinks is not None else q
|
|
block_ends_arg = block_ends if block_ends is not None else qo_indptr
|
|
block_d = triton.next_power_of_2(head_dim)
|
|
block_dv = triton.next_power_of_2(head_dim)
|
|
# Tile size is shared-memory bound: keep the fast (large) tiles on GPUs whose opt-in
|
|
# shared memory fits them, shrink on consumer GPUs (sm_89 ~99KB) where the default
|
|
# 128x64 overflows once head_dim >= 256 (e.g. gemma4: SWA 256, full-attention 512).
|
|
block_m, block_n = _select_extend_tile(
|
|
head_dim, block_d, _optin_smem_bytes(q.device.index)
|
|
)
|
|
grid = (qo_indptr.numel() - 1, num_q_heads, triton.cdiv(max_q_len, block_m))
|
|
if k_extend is not None or v_extend is not None:
|
|
assert k_extend is not None and v_extend is not None
|
|
assert k_extend.is_cuda and v_extend.is_cuda
|
|
assert k_extend.dim() == 3 and v_extend.dim() == 3
|
|
assert k_extend.shape[0] == num_q_tokens and v_extend.shape[0] == num_q_tokens
|
|
assert k_extend.shape[1] == num_kv_heads and v_extend.shape[1] == num_kv_heads
|
|
assert k_extend.shape[-1] == head_dim and v_extend.shape[-1] == head_dim
|
|
_extend_attention_split_kernel[grid](
|
|
q,
|
|
k_extend,
|
|
v_extend,
|
|
k_cache,
|
|
v_cache,
|
|
o,
|
|
qo_indptr,
|
|
kv_indptr,
|
|
kv_indices,
|
|
prefix_lens,
|
|
block_ends_arg,
|
|
sm_scale,
|
|
sinks_arg,
|
|
q.stride(0),
|
|
q.stride(1),
|
|
k_extend.stride(0),
|
|
k_extend.stride(1),
|
|
v_extend.stride(0),
|
|
v_extend.stride(1),
|
|
k_cache.stride(0),
|
|
k_cache.stride(1),
|
|
v_cache.stride(0),
|
|
v_cache.stride(1),
|
|
o.stride(0),
|
|
o.stride(1),
|
|
GROUP=num_q_heads // num_kv_heads,
|
|
D=head_dim,
|
|
BLOCK_D=block_d,
|
|
BLOCK_DV=block_dv,
|
|
BLOCK_M=block_m,
|
|
BLOCK_N=block_n,
|
|
SLIDING_WINDOW=sliding_window or 0,
|
|
HAS_SINKS=sinks is not None,
|
|
HAS_BLOCKS=block_ends is not None,
|
|
num_warps=8,
|
|
num_stages=1,
|
|
)
|
|
return o
|
|
|
|
_extend_attention_kernel[grid](
|
|
q,
|
|
k_cache,
|
|
v_cache,
|
|
o,
|
|
qo_indptr,
|
|
kv_indptr,
|
|
kv_indices,
|
|
prefix_lens,
|
|
block_ends_arg,
|
|
sm_scale,
|
|
sinks_arg,
|
|
q.stride(0),
|
|
q.stride(1),
|
|
k_cache.stride(0),
|
|
k_cache.stride(1),
|
|
v_cache.stride(0),
|
|
v_cache.stride(1),
|
|
o.stride(0),
|
|
o.stride(1),
|
|
GROUP=num_q_heads // num_kv_heads,
|
|
D=head_dim,
|
|
BLOCK_D=block_d,
|
|
BLOCK_DV=block_dv,
|
|
BLOCK_M=block_m,
|
|
BLOCK_N=block_n,
|
|
SLIDING_WINDOW=sliding_window or 0,
|
|
HAS_SINKS=sinks is not None,
|
|
HAS_BLOCKS=block_ends is not None,
|
|
num_warps=8,
|
|
num_stages=1,
|
|
)
|
|
return o
|
|
|
|
|
|
def paged_attention(
|
|
q: torch.Tensor,
|
|
k_cache: torch.Tensor,
|
|
v_cache: torch.Tensor,
|
|
indptr: torch.Tensor,
|
|
indices: torch.Tensor,
|
|
q_to_req: torch.Tensor,
|
|
q_positions: torch.Tensor,
|
|
sm_scale: float,
|
|
sliding_window: int | None = None,
|
|
sinks: torch.Tensor | None = None,
|
|
out: torch.Tensor | None = None,
|
|
block_n: int = 32,
|
|
) -> torch.Tensor:
|
|
"""Paged causal attention for one layer.
|
|
|
|
``q`` is ``[num_query_tokens, num_q_heads, head_dim]``. KV cache tensors are
|
|
flattened to ``[num_slots, num_kv_heads, head_dim]``. ``indptr`` and
|
|
``indices`` describe each request's logical KV slots in order.
|
|
"""
|
|
|
|
assert q.is_cuda and k_cache.is_cuda and v_cache.is_cuda
|
|
assert q.dim() == 3 and k_cache.dim() == 3 and v_cache.dim() == 3
|
|
num_tokens, num_q_heads, head_dim = q.shape
|
|
num_kv_heads = k_cache.shape[1]
|
|
assert v_cache.shape[1] == num_kv_heads
|
|
assert k_cache.shape[-1] == head_dim and v_cache.shape[-1] == head_dim
|
|
assert num_q_heads % num_kv_heads == 0
|
|
if sinks is not None:
|
|
assert sinks.is_cuda
|
|
assert sinks.dim() == 1
|
|
assert sinks.numel() >= num_q_heads
|
|
sinks = sinks.contiguous()
|
|
|
|
o = out if out is not None else torch.empty_like(q)
|
|
sinks_arg = sinks if sinks is not None else q
|
|
block_d = triton.next_power_of_2(head_dim)
|
|
grid = (num_tokens, num_q_heads)
|
|
_paged_attention_kernel[grid](
|
|
q,
|
|
k_cache,
|
|
v_cache,
|
|
o,
|
|
indptr,
|
|
indices,
|
|
q_to_req,
|
|
q_positions,
|
|
sm_scale,
|
|
sinks_arg,
|
|
q.stride(0),
|
|
q.stride(1),
|
|
k_cache.stride(0),
|
|
k_cache.stride(1),
|
|
v_cache.stride(0),
|
|
v_cache.stride(1),
|
|
o.stride(0),
|
|
o.stride(1),
|
|
GROUP=num_q_heads // num_kv_heads,
|
|
D=head_dim,
|
|
BLOCK_D=block_d,
|
|
BLOCK_N=block_n,
|
|
SLIDING_WINDOW=sliding_window or 0,
|
|
HAS_SINKS=sinks is not None,
|
|
num_warps=8 if head_dim >= 256 else 4,
|
|
num_stages=2,
|
|
)
|
|
return o
|
|
|
|
|
|
@triton.jit
|
|
def _gather_kv_indices_kernel(
|
|
page_table,
|
|
rows,
|
|
indptr,
|
|
out,
|
|
pt_stride,
|
|
indptr_stride,
|
|
out_stride,
|
|
BLOCK: tl.constexpr,
|
|
):
|
|
batch_id = tl.program_id(1)
|
|
indptr_row = indptr + tl.program_id(0) * indptr_stride
|
|
start = tl.load(indptr_row + batch_id)
|
|
n = tl.load(indptr_row + batch_id + 1) - start
|
|
src = page_table + tl.load(rows + batch_id).to(tl.int64) * pt_stride
|
|
dst = out + tl.program_id(0).to(tl.int64) * out_stride + start
|
|
for off in range(tl.program_id(2) * BLOCK, n, tl.num_programs(2) * BLOCK):
|
|
cols = off + tl.arange(0, BLOCK)
|
|
mask = cols < n
|
|
tl.store(dst + cols, tl.load(src + cols, mask=mask), mask=mask)
|
|
|
|
|
|
def gather_kv_indices(page_table: torch.Tensor, rows: torch.Tensor, indptr: torch.Tensor, out: torch.Tensor) -> None:
|
|
"""Flat KV slot lists of several decode batches, built on the device: ``out[s, indptr[s, i] + j] = page_table[rows[i], j]`` for ``j < indptr[s, i + 1] - indptr[s, i]``."""
|
|
steps, batch = indptr.shape[0], indptr.shape[1] - 1
|
|
# a fixed grid keeps the launch graph-capturable; long rows loop over it
|
|
chunks = max(1, triton.cdiv(2 * _num_sms(page_table.device.index), steps * batch))
|
|
_gather_kv_indices_kernel[(steps, batch, chunks)](
|
|
page_table,
|
|
rows,
|
|
indptr,
|
|
out,
|
|
page_table.stride(0),
|
|
indptr.stride(0),
|
|
out.stride(0),
|
|
BLOCK=1024,
|
|
)
|