Skip to content

FreeToken brings datacenter-scale model serving to your desktop. Run massive models locally, fast and efficiently.

13.7 KB
Raw Blame
"""Sparse gathered-KV flash attention over PACKED pools (DeepSeek-V4.1).

Same contract as ``kernel/triton/dsv4/sparse_attn.py`` -- each query attends to a per-query list of
GLOBAL slots laid out ``[window part | compressed part]`` plus a per-head attention sink, K == V is one
shared latent head -- but the two pools are byte pools in (possibly different) ``RowFormat``s: the
window ring holds fp8 rows, the compressed KV holds fp4 rows, and every gathered row is dequantized
in-kernel (``row_format.load_rows``) to the bf16 value the reference cache would have held.

Because the two pools dequantize differently, a tile never mixes them: the window part is
``n_window`` columns with ``n_window % BLOCK_T == 0`` (the caller pads it with ``-1``), so the kernel
walks the window tiles and then the compressed tiles in two loops, each with a single load site.
Both dots take bf16 operands with fp32 accumulation, like the reference ``sparse_attn`` kernel.

Two implementations, picked from the launch shape (no knob):
  * prefill (``m`` > 1): one program per (query, request, head block)
  * decode (``m`` == 1): flash-decoding split over the candidate axis, merged through log-sum-exp
    (the sink joins in the merge). Not bit-identical to the single-program path.

``cmp_counts`` (device ``[b, m]`` int32) bounds the compressed columns a CUDA-graph replay visits;
without it the full ``topk_idxs`` width is walked.
"""

from __future__ import annotations

import torch
import triton
import triton.language as tl

from freetoken.kvcache.dsv4.v41_row_format import RowFormat

from .row_format import load_rows

BLOCK_H = 16
BLOCK_T = 32
MAX_SPLITS = 32
# Decode splits at tile boundaries, bounded by the device's SM count below.
MIN_TILES_PER_SPLIT = 1


@triton.jit
def _attend_tile(q, kv, valid, scale, m_i, l_i, acc):
    """One online-softmax step over a ``[BLOCK_T, D]`` fp32 KV tile (bf16-exact values)."""
    kv16 = kv.to(tl.bfloat16)
    scores = tl.dot(q, tl.trans(kv16)) * scale  # [BLOCK_H, BLOCK_T] fp32
    scores = tl.where(valid[None, :], scores, -float("inf"))
    m_new = tl.maximum(m_i, tl.max(scores, axis=1))
    # an all-masked tile keeps m_new at -inf; short-circuit so -inf - -inf never forms
    alpha = tl.where(m_new == -float("inf"), 1.0, tl.exp(m_i - m_new))
    p = tl.where(valid[None, :], tl.exp(scores - m_new[:, None]), 0.0)
    l_i = l_i * alpha + tl.sum(p, axis=1)
    acc = acc * alpha[:, None] + tl.dot(p.to(tl.bfloat16), kv16)
    return m_new, l_i, acc


@triton.jit
def _sparse_attn_packed_kernel(
    q_ptr, win_ptr, cmp_ptr, o_ptr, sink_ptr, idx_ptr, cnt_ptr,
    scale,
    H, TOPK, N_WINDOW,
    stride_qb, stride_qm, stride_qh, stride_qd,
    stride_ob, stride_om, stride_oh, stride_od,
    stride_ib, stride_im, stride_it,
    stride_nb, stride_nm,
    D: tl.constexpr,
    WIN_FMT: tl.constexpr, WIN_ROW_BYTES: tl.constexpr,
    CMP_FMT: tl.constexpr, CMP_ROW_BYTES: tl.constexpr,
    BLOCK_H: tl.constexpr,
    BLOCK_T: tl.constexpr,
    HAS_COUNTS: tl.constexpr,
):
    pid_m = tl.program_id(0)
    pid_b = tl.program_id(1)
    pid_h = tl.program_id(2)

    offs_h = pid_h * BLOCK_H + tl.arange(0, BLOCK_H)
    h_mask = offs_h < H
    offs_d = tl.arange(0, D)

    q_ptrs = q_ptr + pid_b * stride_qb + pid_m * stride_qm + offs_h[:, None] * stride_qh + offs_d[None, :] * stride_qd
    q = tl.load(q_ptrs, mask=h_mask[:, None], other=0.0).to(tl.bfloat16)  # [BLOCK_H, D]

    m_i = tl.full((BLOCK_H,), -float("inf"), dtype=tl.float32)
    l_i = tl.zeros((BLOCK_H,), dtype=tl.float32)
    acc = tl.zeros((BLOCK_H, D), dtype=tl.float32)

    n_active = TOPK
    if HAS_COUNTS:
        n_active = N_WINDOW + tl.load(cnt_ptr + pid_b * stride_nb + pid_m * stride_nm)

    idx_base = idx_ptr + pid_b * stride_ib + pid_m * stride_im
    for start in range(0, N_WINDOW, BLOCK_T):
        offs_t = start + tl.arange(0, BLOCK_T)
        idxs = tl.load(idx_base + offs_t * stride_it)
        valid = idxs >= 0
        kv = load_rows(win_ptr, idxs, valid, offs_d, D, WIN_ROW_BYTES, WIN_FMT)
        m_i, l_i, acc = _attend_tile(q, kv, valid, scale, m_i, l_i, acc)
    for start in range(N_WINDOW, n_active, BLOCK_T):
        offs_t = start + tl.arange(0, BLOCK_T)
        t_mask = offs_t < n_active
        idxs = tl.load(idx_base + offs_t * stride_it, mask=t_mask, other=-1)
        valid = idxs >= 0
        kv = load_rows(cmp_ptr, idxs, valid, offs_d, D, CMP_ROW_BYTES, CMP_FMT)
        m_i, l_i, acc = _attend_tile(q, kv, valid, scale, m_i, l_i, acc)

    sink = tl.load(sink_ptr + offs_h, mask=h_mask, other=0.0).to(tl.float32)
    l_i = l_i + tl.exp(sink - m_i)
    o = acc / l_i[:, None]

    o_ptrs = o_ptr + pid_b * stride_ob + pid_m * stride_om + offs_h[:, None] * stride_oh + offs_d[None, :] * stride_od
    tl.store(o_ptrs, o.to(o_ptr.dtype.element_ty), mask=h_mask[:, None])


@triton.jit
def _sparse_attn_packed_splitk_kernel(
    q_ptr, win_ptr, cmp_ptr, mid_o_ptr, mid_lse_ptr, idx_ptr, cnt_ptr,
    scale,
    H, TOPK, N_WINDOW,
    stride_qb, stride_qm, stride_qh, stride_qd,
    stride_mb, stride_mm, stride_mh, stride_ms, stride_md,
    stride_lb, stride_lm, stride_lh, stride_ls,
    stride_ib, stride_im, stride_it,
    stride_nb, stride_nm,
    D: tl.constexpr,
    WIN_FMT: tl.constexpr, WIN_ROW_BYTES: tl.constexpr,
    CMP_FMT: tl.constexpr, CMP_ROW_BYTES: tl.constexpr,
    BLOCK_H: tl.constexpr,
    BLOCK_T: tl.constexpr,
    HAS_COUNTS: tl.constexpr,
    NUM_SPLITS: tl.constexpr,
):
    """Stage 1: each program reduces one BLOCK_T-aligned slice of the candidate list and writes
    its normalized partial output + log-sum-exp. A slice may straddle the window / compressed
    boundary; it is walked as (window tiles, compressed tiles) since N_WINDOW is tile-aligned."""
    pid_ms = tl.program_id(0)
    pid_m = pid_ms // NUM_SPLITS
    split_id = pid_ms % NUM_SPLITS
    pid_b = tl.program_id(1)
    pid_h = tl.program_id(2)

    offs_h = pid_h * BLOCK_H + tl.arange(0, BLOCK_H)
    h_mask = offs_h < H
    offs_d = tl.arange(0, D)

    n_active = TOPK
    if HAS_COUNTS:
        n_active = N_WINDOW + tl.load(cnt_ptr + pid_b * stride_nb + pid_m * stride_nm)

    per_split = tl.cdiv(tl.cdiv(n_active, NUM_SPLITS), BLOCK_T) * BLOCK_T
    split_start = per_split * split_id
    split_end = tl.minimum(split_start + per_split, n_active)

    m_i = tl.full((BLOCK_H,), -float("inf"), dtype=tl.float32)
    l_i = tl.zeros((BLOCK_H,), dtype=tl.float32)
    acc = tl.zeros((BLOCK_H, D), dtype=tl.float32)

    if split_end > split_start:
        q_ptrs = (
            q_ptr + pid_b * stride_qb + pid_m * stride_qm
            + offs_h[:, None] * stride_qh + offs_d[None, :] * stride_qd
        )
        q = tl.load(q_ptrs, mask=h_mask[:, None], other=0.0).to(tl.bfloat16)
        idx_base = idx_ptr + pid_b * stride_ib + pid_m * stride_im

        win_end = tl.minimum(split_end, N_WINDOW)
        for start in range(split_start, win_end, BLOCK_T):
            offs_t = start + tl.arange(0, BLOCK_T)
            idxs = tl.load(idx_base + offs_t * stride_it)
            valid = idxs >= 0
            kv = load_rows(win_ptr, idxs, valid, offs_d, D, WIN_ROW_BYTES, WIN_FMT)
            m_i, l_i, acc = _attend_tile(q, kv, valid, scale, m_i, l_i, acc)
        cmp_start = tl.maximum(split_start, N_WINDOW)
        for start in range(cmp_start, split_end, BLOCK_T):
            offs_t = start + tl.arange(0, BLOCK_T)
            t_mask = offs_t < split_end
            idxs = tl.load(idx_base + offs_t * stride_it, mask=t_mask, other=-1)
            valid = idxs >= 0
            kv = load_rows(cmp_ptr, idxs, valid, offs_d, D, CMP_ROW_BYTES, CMP_FMT)
            m_i, l_i, acc = _attend_tile(q, kv, valid, scale, m_i, l_i, acc)

    out = tl.where(l_i[:, None] == 0.0, 0.0, acc / l_i[:, None])
    lse = tl.where(l_i == 0.0, -float("inf"), m_i + tl.log(l_i))

    mid_base = (
        mid_o_ptr + pid_b * stride_mb + pid_m * stride_mm
        + offs_h[:, None] * stride_mh + split_id * stride_ms + offs_d[None, :] * stride_md
    )
    tl.store(mid_base, out, mask=h_mask[:, None])
    lse_base = (
        mid_lse_ptr + pid_b * stride_lb + pid_m * stride_lm
        + offs_h * stride_lh + split_id * stride_ls
    )
    tl.store(lse_base, lse, mask=h_mask)


@triton.jit
def _sparse_attn_splitk_merge_kernel(
    mid_o_ptr, mid_lse_ptr, o_ptr, sink_ptr,
    stride_mb, stride_mm, stride_mh, stride_ms, stride_md,
    stride_lb, stride_lm, stride_lh, stride_ls,
    stride_ob, stride_om, stride_oh, stride_od,
    D: tl.constexpr,
    NUM_SPLITS: tl.constexpr,
):
    """Stage 2: log-sum-exp merge over the splits; the attention sink joins here once, as a null
    key with logit ``attn_sink[h]`` and zero value. One program per (query, request, head)."""
    pid_m = tl.program_id(0)
    pid_b = tl.program_id(1)
    pid_h = tl.program_id(2)
    offs_d = tl.arange(0, D)

    m_i = tl.load(sink_ptr + pid_h).to(tl.float32)
    l_i = 1.0
    acc = tl.zeros((D,), dtype=tl.float32)

    mid_base = mid_o_ptr + pid_b * stride_mb + pid_m * stride_mm + pid_h * stride_mh + offs_d * stride_md
    lse_base = mid_lse_ptr + pid_b * stride_lb + pid_m * stride_lm + pid_h * stride_lh

    for split_id in tl.range(0, NUM_SPLITS, num_stages=2):
        partial = tl.load(mid_base + split_id * stride_ms)
        lse = tl.load(lse_base + split_id * stride_ls)
        m_new = tl.maximum(m_i, lse)
        alpha = tl.exp(m_i - m_new)
        beta = tl.where(lse == -float("inf"), 0.0, tl.exp(lse - m_new))
        acc = acc * alpha + partial * beta
        l_i = l_i * alpha + beta
        m_i = m_new

    o = acc / l_i
    o_ptrs = o_ptr + pid_b * stride_ob + pid_m * stride_om + pid_h * stride_oh + offs_d * stride_od
    tl.store(o_ptrs, o.to(o_ptr.dtype.element_ty))


def split_count(b: int, m: int, h: int, topk: int, device) -> int:
    """How many ways to split the candidate axis; 0 means run the single-program kernel. Decode
    splits until every SM has a program or every split is down to one tile."""
    if m != 1:
        return 0
    sm_count = torch.cuda.get_device_properties(device).multi_processor_count
    n_splits = min(
        MAX_SPLITS,
        triton.cdiv(topk, MIN_TILES_PER_SPLIT * BLOCK_T),
        max(1, sm_count // (b * triton.cdiv(h, BLOCK_H))),
    )
    return n_splits if n_splits > 1 else 0


def sparse_attn_packed(
    q: torch.Tensor,             # [b, m, h, d] bf16
    window_pool: torch.Tensor,   # [n_win_slots, win_fmt.row_bytes(d)] uint8
    win_fmt: RowFormat,
    cmp_pool: torch.Tensor,      # [n_cmp, cmp_fmt.row_bytes(d)] uint8
    cmp_fmt: RowFormat,
    attn_sink: torch.Tensor,     # [h]
    topk_idxs: torch.Tensor,     # [b, m, topk] int32, GLOBAL rows, layout [window | compressed]
    n_window: int,               # window columns (a multiple of BLOCK_T; pad with -1)
    softmax_scale: float,
    cmp_counts: torch.Tensor | None = None,  # [b, m] int32 live compressed columns per query
) -> torch.Tensor:
    """Paged sparse MLA attention over packed KV pools; see the module docstring for the contract."""
    b, m, h, d = q.shape
    topk = topk_idxs.shape[-1]
    assert n_window % BLOCK_T == 0 and 0 <= n_window <= topk, (n_window, topk)
    assert window_pool.dtype == torch.uint8 and window_pool.shape[1] == win_fmt.row_bytes(d), (window_pool.shape, win_fmt)
    assert cmp_pool.dtype == torch.uint8 and cmp_pool.shape[1] == cmp_fmt.row_bytes(d), (cmp_pool.shape, cmp_fmt)
    assert window_pool.is_contiguous() and cmp_pool.is_contiguous()
    q = q.contiguous()
    idx = topk_idxs.contiguous().to(torch.int32)
    sink = attn_sink.contiguous().to(torch.float32)
    o = torch.empty_like(q)

    has_counts = cmp_counts is not None
    if has_counts:
        cnt = cmp_counts.contiguous().to(torch.int32).view(b, m)
        stride_nb, stride_nm = cnt.stride()
    else:
        cnt, stride_nb, stride_nm = idx, 0, 0

    fmt_args = dict(
        WIN_FMT=win_fmt.code, WIN_ROW_BYTES=win_fmt.row_bytes(d),
        CMP_FMT=cmp_fmt.code, CMP_ROW_BYTES=cmp_fmt.row_bytes(d),
    )
    n_splits = split_count(b, m, h, topk, q.device)
    if n_splits:
        head_blocks = triton.cdiv(h, BLOCK_H)
        mid_o = torch.empty((b, m, h, n_splits, d), dtype=torch.float32, device=q.device)
        mid_lse = torch.empty((b, m, h, n_splits), dtype=torch.float32, device=q.device)
        _sparse_attn_packed_splitk_kernel[(m * n_splits, b, head_blocks)](
            q, window_pool, cmp_pool, mid_o, mid_lse, idx, cnt,
            float(softmax_scale),
            h, topk, int(n_window),
            q.stride(0), q.stride(1), q.stride(2), q.stride(3),
            mid_o.stride(0), mid_o.stride(1), mid_o.stride(2), mid_o.stride(3), mid_o.stride(4),
            mid_lse.stride(0), mid_lse.stride(1), mid_lse.stride(2), mid_lse.stride(3),
            idx.stride(0), idx.stride(1), idx.stride(2),
            stride_nb, stride_nm,
            D=d, BLOCK_H=BLOCK_H, BLOCK_T=BLOCK_T, HAS_COUNTS=has_counts, NUM_SPLITS=n_splits,
            **fmt_args, num_warps=8, num_stages=2,
        )
        _sparse_attn_splitk_merge_kernel[(m, b, h)](
            mid_o, mid_lse, o, sink,
            mid_o.stride(0), mid_o.stride(1), mid_o.stride(2), mid_o.stride(3), mid_o.stride(4),
            mid_lse.stride(0), mid_lse.stride(1), mid_lse.stride(2), mid_lse.stride(3),
            o.stride(0), o.stride(1), o.stride(2), o.stride(3),
            D=d, NUM_SPLITS=n_splits, num_warps=4,
        )
        return o

    grid = (m, b, triton.cdiv(h, BLOCK_H))
    _sparse_attn_packed_kernel[grid](
        q, window_pool, cmp_pool, o, sink, idx, cnt,
        float(softmax_scale),
        h, topk, int(n_window),
        q.stride(0), q.stride(1), q.stride(2), q.stride(3),
        o.stride(0), o.stride(1), o.stride(2), o.stride(3),
        idx.stride(0), idx.stride(1), idx.stride(2),
        stride_nb, stride_nm,
        D=d, BLOCK_H=BLOCK_H, BLOCK_T=BLOCK_T, HAS_COUNTS=has_counts,
        **fmt_args, num_warps=8, num_stages=2,
    )
    return o


__all__ = ["sparse_attn_packed", "split_count", "BLOCK_T"]