mirror of
https://github.com/FlashML-org/FreeToken.git
synced 2026-11-21 01:52:30 +08:00
* refactor: add engine and scheduler seams for multi-row decode steps * refactor: rename the graph steps argument to rows_per_req * refactor: drop VerifyInfo and require rows_per_req on verify batches * refactor: fix stale seam comments and read decode_rows_per_req directly * refactor: reword two GraphRunner comments for multi-row graphs * fix(engine): scale the GPU-decode MoE pool limits by decode_rows_per_req * refactor: drop the unread Context.moe_offload_cache field * test: trim the multi-row seam tests
441 lines
24 KiB
Python
441 lines
24 KiB
Python
"""DeepSeek-V4.1 sparse-attention backend.
|
|
|
|
Same contract and division of labour as ``dsv4_sparse``: the backend owns the per-forward KV
|
|
ADDRESSING over the shared page table (window ring slots, compressed rows, compress-state carry,
|
|
the decode snapshot and the CUDA-graph staging buffers) plus the selection helpers that are pure
|
|
index arithmetic (causal top-k, the hierarchical candidate pool); the model computes projections
|
|
and hands the picks back to be resolved into pool rows.
|
|
|
|
What DSV41 adds on top of DSV4's vocabulary:
|
|
|
|
* **cross-layer sharing** -- the compressed tiers belong to the kv-source layer; a consumer layer
|
|
addresses ``source_of(layer)``'s pools. The Top-K rows and the candidate pool the Full / Reindex
|
|
layers produce ride on the per-forward ``SharedSelection`` for the Reuse layers to read.
|
|
* **packed rows** -- writes quantize into the pool (``pool.store_*``), reads dequantize in-kernel.
|
|
* **prefill passes with a window floor** -- a ``PrefillSegment`` carries ``window_floor``: the
|
|
absolute position a query's sliding window may not reach below (Decoder SWA Bounded Replay
|
|
truncates the decoder's window at ``L - W``, the start of the prompt's last window). The metadata
|
|
carries the encoder pass (every new token) and the decoder pass (the new tokens inside the
|
|
prompt's last window, or every new token in exact mode).
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
from dataclasses import dataclass, field
|
|
from typing import TYPE_CHECKING, List
|
|
|
|
import torch
|
|
from freetoken.core import Batch, get_global_ctx
|
|
|
|
from .base import AttentionSpec, BaseAttnBackend, BaseAttnMetadata
|
|
|
|
if TYPE_CHECKING:
|
|
from freetoken.models import ModelConfig
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class PrefillSegment:
|
|
"""One request's slice of a flat prefill token stream.
|
|
|
|
``offset``/``n`` tile the stream; ``start_pos`` is the absolute position of the first token;
|
|
``window_floor`` bounds every query's sliding window from below (0 = the exact window; bounded
|
|
replay sets it to the start of the prompt's last window).
|
|
"""
|
|
|
|
offset: int
|
|
n: int
|
|
table_idx: int
|
|
start_pos: int
|
|
window_floor: int = 0
|
|
|
|
@property
|
|
def end(self) -> int:
|
|
return self.start_pos + self.n
|
|
|
|
|
|
@dataclass
|
|
class SharedSelection:
|
|
"""What the index-producing layers hand down the stack within ONE forward.
|
|
|
|
``topk_rows`` are GLOBAL main-pool rows (``-1`` masked) for the current kv source, laid out
|
|
exactly as the attention kernel consumes them; ``cmp_counts`` is the decode-only per-row live
|
|
count that bounds the kernel's loop; ``candidates`` is the Hierarchical Sparse Indexer's
|
|
compressed-position pool (``-1`` = empty slot). Layers run in order and every producer writes
|
|
before its consumers read, so one slot each suffices.
|
|
"""
|
|
|
|
source: int | None = None
|
|
topk_rows: torch.Tensor | None = None
|
|
cmp_counts: torch.Tensor | None = None
|
|
candidates: torch.Tensor | None = None
|
|
|
|
|
|
@dataclass
|
|
class DSV41AttnMetadata(BaseAttnMetadata):
|
|
last_indices: torch.Tensor
|
|
# Prefill: the encoder pass tiles the batch's new tokens; the decoder pass tiles the tokens the
|
|
# decoder layers process (``decoder_rows`` gathers them out of the encoder stream; None = all of
|
|
# it). ``decoder_pad``: some request has no decoder row this chunk, and its ``last_indices`` entry
|
|
# points at one placeholder row the model appends after the decoder stream (its logits are unused).
|
|
segments: List[PrefillSegment] | None = None
|
|
decoder_segments: List[PrefillSegment] | None = None
|
|
decoder_rows: torch.Tensor | None = None
|
|
decoder_pad: bool = False
|
|
# Decode: the whole-history full-loc snapshot (captured buffer under a replay, lazy eager copy).
|
|
full_snap: torch.Tensor | None = None
|
|
table_rows: torch.Tensor | None = None
|
|
window_ar: torch.Tensor | None = None
|
|
selection: SharedSelection = field(default_factory=SharedSelection)
|
|
|
|
def get_last_indices(self, bs: int) -> torch.Tensor:
|
|
return self.last_indices[:bs]
|
|
|
|
@property
|
|
def stage_width(self) -> int:
|
|
assert self.full_snap is not None, "stage_width is capture/replay-only"
|
|
return self.full_snap.shape[1]
|
|
|
|
def full_snapshot(self) -> torch.Tensor:
|
|
if self.full_snap is None:
|
|
assert self.table_rows is not None, "snapshot is decode-only"
|
|
pool = get_global_ctx().kv_cache
|
|
self.full_snap = pool.full_loc_map.index_select(0, self.table_rows).to(torch.int64)
|
|
return self.full_snap
|
|
|
|
def window_ctx(self, pos: torch.Tensor, rows: torch.Tensor):
|
|
"""Layer-invariant decode ring context ``(window_slots, prev_window_slots,
|
|
window_slots_topk [B, 1, win])``; computed fresh on every call (never cached -- a capture
|
|
must record these gathers), off the snapshot so a concurrent allocation cannot redirect
|
|
an in-flight replay."""
|
|
snap = self.full_snapshot()
|
|
translate = get_global_ctx().kv_cache.translate_full_to_window
|
|
bs = pos.shape[0]
|
|
j = self.window_ar
|
|
assert j is not None, "window_ctx is decode-only"
|
|
win = j.shape[0]
|
|
window_slots = translate(snap[rows, pos])
|
|
prev_window_slots = translate(snap[rows, (pos - 1).clamp_min(0)])
|
|
p = pos[:, None] - ((pos[:, None] - j[None, :]) % win)
|
|
ws = translate(snap[rows[:, None], p.clamp(min=0)])
|
|
window_slots_topk = torch.where((p >= 0) & (j[None, :] <= pos[:, None]), ws, -1).view(bs, 1, win)
|
|
return window_slots, prev_window_slots, window_slots_topk
|
|
|
|
def private_window_ctx(self, pos: torch.Tensor, rows: torch.Tensor):
|
|
"""The private-ring counterpart of ``window_ctx`` for request-private window layers:
|
|
``(window_slots [B], window_slots_topk [B, 1, win])`` in the layer's ring, where a request's
|
|
row holds positions by ``pos % win`` (candidate ``j`` is the position congruent to ``j``)."""
|
|
assert self.table_rows is not None and self.window_ar is not None, "private_window_ctx is decode-only"
|
|
pool = get_global_ctx().kv_cache
|
|
bs = pos.shape[0]
|
|
j = self.window_ar
|
|
win = j.shape[0]
|
|
table = self.table_rows[rows]
|
|
window_slots = pool.ring_slots(table, pos)
|
|
p = pos[:, None] - ((pos[:, None] - j[None, :]) % win) # the position at ring index j (< 0: none yet)
|
|
window_slots_topk = pool.ring_slots(table[:, None], p).view(bs, 1, win)
|
|
return window_slots, window_slots_topk
|
|
|
|
|
|
@dataclass
|
|
class DSV41CaptureData:
|
|
full_snap: torch.Tensor
|
|
last_indices: torch.Tensor
|
|
table_rows: torch.Tensor # each batch row's page-table row (the private window rings key on it)
|
|
|
|
@classmethod
|
|
def create(cls, max_bs: int, width: int, device: torch.device) -> "DSV41CaptureData":
|
|
return cls(
|
|
full_snap=torch.full((max_bs, width), -1, dtype=torch.int64, device=device),
|
|
last_indices=torch.arange(max_bs, dtype=torch.int32, device=device),
|
|
table_rows=torch.zeros(max_bs, dtype=torch.int64, device=device),
|
|
)
|
|
|
|
|
|
class DSV41SparseAttnBackend(BaseAttnBackend):
|
|
def __init__(self, config: ModelConfig):
|
|
self.config = config
|
|
self.device = get_global_ctx().kv_cache.device
|
|
args = config.dsv41_args
|
|
self.window_size = args.window_size
|
|
self.swa_decoder_replay: str = args.swa_decoder_replay
|
|
self.capture: DSV41CaptureData | None = None
|
|
self.capture_bs: List[int] = []
|
|
self.max_graph_bs = 0
|
|
self._window_ar = torch.arange(self.window_size, device=self.device)
|
|
|
|
@property
|
|
def pool(self):
|
|
return get_global_ctx().kv_cache
|
|
|
|
# ----- generic contract -------------------------------------------------------------
|
|
def forward(self, q, k, v, layer_id, batch, attn_spec: AttentionSpec | None = None):
|
|
raise NotImplementedError("DSV41 attention is driven per-tier from the model module; use DSV41SparseAttnBackend.attend().")
|
|
|
|
def prepare_metadata(self, batch: Batch) -> None:
|
|
if not batch.is_decode:
|
|
batch.attn_metadata = self._prefill_metadata(batch)
|
|
return
|
|
last = torch.tensor([r.extend_len for r in batch.padded_reqs], dtype=torch.int32, device=self.device).cumsum_(0) - 1
|
|
batch.attn_metadata = DSV41AttnMetadata(last_indices=last, table_rows=self._table_rows(batch), window_ar=self._window_ar)
|
|
|
|
def _prefill_metadata(self, batch: Batch) -> DSV41AttnMetadata:
|
|
"""The encoder pass runs every request's new tokens ``[cached_len, device_len)``. Exact mode runs
|
|
the decoder on the same stream. Decoder SWA Bounded Replay runs it on the new tokens inside the
|
|
prompt's last window ``[L - W, L)`` (``L = prompt_len``) with every query's window floored at
|
|
``L - W``: the chunks of a chunked prefill each take their part of that window (earlier rows
|
|
come from the request's private ring), and a chunk that ends before it runs no decoder row."""
|
|
segments: List[PrefillSegment] = []
|
|
off = 0
|
|
for r in batch.reqs:
|
|
segments.append(PrefillSegment(off, r.extend_len, r.table_idx, r.cached_len))
|
|
off += r.extend_len
|
|
if self.swa_decoder_replay == "exact":
|
|
last = torch.tensor([s.n for s in segments], dtype=torch.int32, device=self.device).cumsum_(0) - 1
|
|
return DSV41AttnMetadata(last_indices=last, segments=segments, decoder_segments=segments)
|
|
win = self.window_size
|
|
dec: List[PrefillSegment] = []
|
|
rows: list[torch.Tensor] = []
|
|
last: list[int] = []
|
|
doff = 0
|
|
for r, s in zip(batch.reqs, segments):
|
|
floor = max(0, r.prompt_len - win)
|
|
lo = max(s.start_pos, floor)
|
|
n = max(0, s.end - lo)
|
|
if n:
|
|
# the decoder's window KV goes to the request's private rings, never to radix-shared pages
|
|
dec.append(PrefillSegment(doff, n, s.table_idx, lo, window_floor=floor))
|
|
rows.append(torch.arange(s.offset + lo - s.start_pos, s.offset + s.n))
|
|
doff += n
|
|
last.append(doff - 1 if n else -1)
|
|
pad = -1 in last
|
|
last_indices = torch.tensor([doff if i < 0 else i for i in last], dtype=torch.int32, device=self.device)
|
|
decoder_rows = torch.cat(rows).to(self.device, non_blocking=True) if rows else torch.empty(0, dtype=torch.int64, device=self.device)
|
|
return DSV41AttnMetadata(last_indices=last_indices, segments=segments, decoder_segments=dec, decoder_rows=decoder_rows, decoder_pad=pad)
|
|
|
|
def init_capture_graph(self, max_seq_len: int, bs_list: List[int], rows_per_req: int = 1) -> None:
|
|
if rows_per_req != 1:
|
|
raise NotImplementedError("dsv41_sparse captures decode graphs only")
|
|
assert self.capture is None, "Capture already initialized."
|
|
self.max_graph_bs = max(bs_list)
|
|
self.capture = DSV41CaptureData.create(self.max_graph_bs, max_seq_len, self.device)
|
|
self.capture_bs = sorted(bs_list)
|
|
|
|
def prepare_for_capture(self, batch: Batch) -> None:
|
|
bs = batch.size
|
|
rows = torch.full((bs,), batch.padded_reqs[0].table_idx, dtype=torch.int64, device=self.device)
|
|
self._point_to_capture(batch, bs, rows)
|
|
|
|
def prepare_for_replay(self, batch: Batch) -> None:
|
|
self._point_to_capture(batch, batch.padded_size, self._table_rows(batch))
|
|
|
|
def _table_rows(self, batch: Batch) -> torch.Tensor:
|
|
assert batch.active_table_idx is not None, "decode batch is missing its page-table rows"
|
|
return batch.active_table_idx.to(torch.int64)
|
|
|
|
def _point_to_capture(self, batch: Batch, bs: int, rows_ti: torch.Tensor) -> None:
|
|
assert self.capture is not None and bs <= self.max_graph_bs
|
|
cap = self.capture
|
|
src = self.pool.full_loc_map.index_select(0, rows_ti)
|
|
w = min(src.shape[1], cap.full_snap.shape[1])
|
|
cap.full_snap[:bs, :w].copy_(src[:bs, :w])
|
|
cap.table_rows[:bs].copy_(rows_ti[:bs])
|
|
batch.attn_metadata = DSV41AttnMetadata(
|
|
last_indices=cap.last_indices[:bs], full_snap=cap.full_snap[:bs], table_rows=cap.table_rows[:bs], window_ar=self._window_ar,
|
|
)
|
|
|
|
# ----- metadata / selection access -------------------------------------------------
|
|
@property
|
|
def metadata(self) -> DSV41AttnMetadata:
|
|
md = get_global_ctx().batch.attn_metadata
|
|
assert isinstance(md, DSV41AttnMetadata)
|
|
return md
|
|
|
|
@property
|
|
def selection(self) -> SharedSelection:
|
|
return self.metadata.selection
|
|
|
|
def snapshot(self) -> torch.Tensor:
|
|
return self.metadata.full_snapshot()
|
|
|
|
# ----- window tier -------------------------------------------------------------------
|
|
def window_slots_of(self, ti: int, lo: int, hi: int) -> torch.Tensor:
|
|
"""SHARED window slots of positions ``[lo, hi)`` off the request's LIVE full locs (slid-out -> -1)."""
|
|
return self.pool.translate_full_to_window(self.pool.full_loc_map[ti, lo:hi])
|
|
|
|
def ring_slots_of(self, ti: int, lo: int, hi: int) -> torch.Tensor:
|
|
"""PRIVATE-ring slots of positions ``[lo, hi)`` of page-table row ``ti`` (``hi - lo <= win``)."""
|
|
assert hi - lo <= self.window_size, f"a private ring holds one window, not {hi - lo} positions"
|
|
return self.pool.ring_slots(torch.tensor(ti, device=self.device), torch.arange(lo, hi, device=self.device))
|
|
|
|
def layer_window_slots_of(self, layer_id: int, ti: int, lo: int, hi: int) -> torch.Tensor:
|
|
"""Where ``layer_id`` keeps the window KV of positions ``[lo, hi)``: its private ring or the shared pool."""
|
|
if self.pool.is_private_window(layer_id):
|
|
return self.ring_slots_of(ti, lo, hi)
|
|
return self.window_slots_of(ti, lo, hi)
|
|
|
|
def store_window(self, kv: torch.Tensor, layer_id: int, window_slots: torch.Tensor) -> None:
|
|
self.pool.store_window(kv, layer_id, window_slots)
|
|
|
|
def window_topk_prefill(self, seg: PrefillSegment, layer_id: int | None = None) -> torch.Tensor:
|
|
"""Per-query window candidates for a prefill segment as GLOBAL window slots ``[1, n, win]``
|
|
(``-1`` where empty) in the tier ``layer_id`` reads (shared pool by default). Query at
|
|
absolute ``p`` sees ``[max(floor, first_retained, p - win + 1), p]``."""
|
|
win, device = self.window_size, self.device
|
|
lo = max(0, seg.start_pos - win + 1, seg.window_floor)
|
|
private = layer_id is not None and self.pool.is_private_window(layer_id)
|
|
ws_pool = (self.ring_slots_of if private else self.window_slots_of)(seg.table_idx, lo, seg.end) # [end - lo]
|
|
abs_p = seg.start_pos + torch.arange(seg.n, device=device).unsqueeze(1)
|
|
cand = (abs_p - win + 1).clamp(min=lo) + torch.arange(win, device=device)
|
|
cols = torch.where(cand > abs_p, -1, cand - lo)
|
|
g = ws_pool[cols.clamp_min(0)]
|
|
return torch.where(cols < 0, -1, g).unsqueeze(0)
|
|
|
|
# ----- compressed tiers (per kv source) ----------------------------------------------
|
|
def source_of(self, layer_id: int) -> int:
|
|
return self.pool.source_of(layer_id)
|
|
|
|
def compressed_rows_of(self, ti: int, group_starts: torch.Tensor, ratio: int) -> torch.Tensor:
|
|
"""Main / index rows of the compressed groups whose ABSOLUTE first positions are
|
|
``group_starts``, off the request's LIVE full locs (a page is ratio-divisible, so every
|
|
position of a group shares one row)."""
|
|
return self.pool.cmp_rows(self.pool.full_loc_map[ti, group_starts], ratio)
|
|
|
|
def locs_prefill(self, ti: int, end: int) -> torch.Tensor:
|
|
"""``[1, end]`` int32: the request's live full locs for positions ``[0, end)`` -- what the indexer
|
|
derives compressed rows from (``loc // ratio``) for the positions its queries may see."""
|
|
return self.pool.full_loc_map[ti : ti + 1, :end]
|
|
|
|
def store_main(self, latent: torch.Tensor, source: int, rows: torch.Tensor) -> None:
|
|
self.pool.store_main(latent, source, rows)
|
|
|
|
def store_index(self, k: torch.Tensor, source: int, rows: torch.Tensor) -> None:
|
|
self.pool.store_index(k, source, rows)
|
|
|
|
def decode_store_rows(self, rows: torch.Tensor, pos: torch.Tensor, ratio: int, source: int, completed: torch.Tensor) -> torch.Tensor:
|
|
"""Per-row decode destination: the completed group's arithmetic row, or the row's OWN scratch
|
|
row when this step did not complete a group (graph-safe, collision-free masked store)."""
|
|
row_of_group = self.pool.cmp_rows(self.snapshot()[rows, pos], ratio)
|
|
scratch = rows + self.pool.scratch_base[source]
|
|
return torch.where(completed, row_of_group, scratch)
|
|
|
|
# ----- compress-state ring (ratio > 1 sources) ---------------------------------------
|
|
def ring_page_base(self, window_slots: torch.Tensor, ring_size: int) -> torch.Tensor:
|
|
return torch.div(window_slots, self.window_size, rounding_mode="floor") * ring_size
|
|
|
|
def carry_state_loc(self, window_slot: int, ring_size: int) -> torch.Tensor:
|
|
base = (window_slot // self.window_size) * ring_size
|
|
return torch.arange(base, base + ring_size, device=self.device, dtype=torch.int64)
|
|
|
|
def read_carry(self, source: int, window_slot: int) -> torch.Tensor:
|
|
"""The ``[ring_size, 2 * head_dim]`` carry block at ``window_slot``'s page (kv | score)."""
|
|
ring = self.pool.state_ring[source]
|
|
return ring.get(self.carry_state_loc(window_slot, ring.ring_size))
|
|
|
|
def write_carry(self, source: int, window_slot: int, kv_score: torch.Tensor) -> None:
|
|
ring = self.pool.state_ring[source]
|
|
ring.set(self.carry_state_loc(window_slot, ring.ring_size), kv_score)
|
|
|
|
def read_carry_blocks(self, source: int, window_slots: torch.Tensor) -> torch.Tensor:
|
|
ring = self.pool.state_ring[source]
|
|
return ring.get_blocks(self.ring_page_base(window_slots, ring.ring_size))
|
|
|
|
def write_carry_blocks(self, source: int, window_slots: torch.Tensor, blocks: torch.Tensor) -> None:
|
|
ring = self.pool.state_ring[source]
|
|
ring.set_blocks(self.ring_page_base(window_slots, ring.ring_size), blocks)
|
|
|
|
def write_boundary_carries(self, source: int, *, lo: int, hi: int, window_slots: torch.Tensor) -> None:
|
|
"""Persist the compressor carry at every window-page boundary ``B`` in ``(lo, hi]`` so a
|
|
page-aligned radix match can resume by value. A page holds whole groups (``P % ratio == 0``),
|
|
so the carry at a boundary is the empty group -- the reset block is written so a resume never
|
|
reads a stale one. ``window_slots`` is indexed by ``pos - lo``. One batched ring write, no host syncs."""
|
|
ring = self.pool.state_ring.get(source)
|
|
if ring is None:
|
|
return
|
|
P = self.window_size
|
|
first = (lo // P + 1) * P
|
|
if first > hi:
|
|
return
|
|
bounds = torch.arange(first, hi + 1, P, device=self.device)
|
|
page_slots = window_slots[bounds - 1 - lo].to(torch.int64) # the last slot of each page
|
|
locs = (torch.div(page_slots, P, rounding_mode="floor") * ring.ring_size)[:, None] + torch.arange(ring.ring_size, device=self.device)
|
|
empty = torch.cat([
|
|
torch.zeros(ring.ring_size, ring.item_size, dtype=torch.float32, device=self.device),
|
|
torch.full((ring.ring_size, ring.item_size), float("-inf"), dtype=torch.float32, device=self.device),
|
|
], dim=-1)
|
|
ring.set(locs.flatten(), empty.repeat(bounds.numel(), 1))
|
|
|
|
# ----- indexer ----------------------------------------------------------------------
|
|
def indexer_logits(
|
|
self, q: torch.Tensor, weights: torch.Tensor, source: int, locs: torch.Tensor, ratio: int, live: torch.Tensor,
|
|
T: int | None = None, candidates: torch.Tensor | None = None,
|
|
) -> torch.Tensor:
|
|
"""``[B, S, T]`` full-range scores (live columns written) or ``[B, S, NC]`` candidate scores; the
|
|
row of compressed position ``t`` is ``locs[b, t * ratio] // ratio``."""
|
|
from freetoken.kernel.triton.dsv41.indexer import indexer_logits_packed
|
|
|
|
return indexer_logits_packed(q, weights, self.pool.idx_pool[source], self.pool.idx_fmt, locs, ratio, live, T=T, candidates=candidates)
|
|
|
|
@staticmethod
|
|
def select_topk(scores: torch.Tensor, live: torch.Tensor, topk: int) -> torch.Tensor:
|
|
"""Exact causal top-k over ``[B, S, T]`` full-range scores (columns at or past ``live`` unread):
|
|
compressed positions ``[B, S, topk]`` int32 in ascending order, ``-1`` in the tail for picks
|
|
that do not exist (fewer live or finite positions than ``topk``). Ties: lowest position wins."""
|
|
from freetoken.kernel.triton.dsv41.topk import dsv41_topk
|
|
|
|
b, s, t = scores.shape
|
|
return dsv41_topk(scores.reshape(b * s, t), live.reshape(b * s), topk).view(b, s, topk)
|
|
|
|
@staticmethod
|
|
def select_topk_in_candidates(scores: torch.Tensor, candidates: torch.Tensor, topk: int) -> torch.Tensor:
|
|
"""Top-k over ``[B, S, NC]`` candidate-aligned scores -> the picked compressed positions
|
|
``[B, S, topk]`` int32. The candidate list is a sorted valid prefix (``-1`` tail) and empty /
|
|
unreachable slots score ``-inf``, so the ascending winning slots map to ascending positions."""
|
|
from freetoken.kernel.triton.dsv41.topk import dsv41_topk
|
|
|
|
b, s, nc = scores.shape
|
|
live = torch.full((b * s,), nc, dtype=torch.int32, device=scores.device)
|
|
slots = dsv41_topk(scores.reshape(b * s, nc), live, topk).view(b, s, topk)
|
|
pos = candidates.gather(-1, slots.clamp_min(0).to(torch.int64)).to(torch.int32)
|
|
return torch.where(slots < 0, -1, pos)
|
|
|
|
@staticmethod
|
|
def select_candidate_blocks(scores: torch.Tensor, live: torch.Tensor, topk_blocks: int, block_size: int) -> torch.Tensor:
|
|
"""Level one of the Hierarchical Sparse Indexer: the ``topk_blocks`` best live ``block_size``
|
|
blocks by their best position, the block holding the newest live position always kept,
|
|
expanded to the compact candidate list ``[B, S, topk_blocks * block_size]`` int32 of
|
|
compressed positions (ascending, ``-1`` tail). Mirrors the reference ``select_candidate_blocks``
|
|
(which returns the equivalent boolean mask)."""
|
|
from freetoken.kernel.triton.dsv41.topk import dsv41_candidate_blocks
|
|
|
|
b, s, t = scores.shape
|
|
return dsv41_candidate_blocks(scores.reshape(b * s, t), live.reshape(b * s), topk_blocks, block_size).view(b, s, -1)
|
|
|
|
@staticmethod
|
|
def positions_to_rows(positions: torch.Tensor, locs: torch.Tensor, ratio: int) -> torch.Tensor:
|
|
"""Compressed positions ``[B, S, K]`` (``-1`` masked) -> GLOBAL main rows ``locs[b, p * ratio] // ratio``."""
|
|
b = positions.shape[0]
|
|
idx = (positions.to(torch.int64) * ratio).clamp_min(0).flatten(1)
|
|
full = locs.to(torch.int64).gather(1, idx.clamp(max=locs.shape[1] - 1)).view_as(positions)
|
|
rows = torch.div(full, ratio, rounding_mode="floor")
|
|
return torch.where((positions < 0) | (full < 0), -1, rows)
|
|
|
|
# ----- attention -----------------------------------------------------------------------
|
|
def attend(
|
|
self, q: torch.Tensor, layer_id: int, topk_idxs: torch.Tensor, n_window: int, attn_sink: torch.Tensor,
|
|
softmax_scale: float, cmp_counts: torch.Tensor | None = None,
|
|
) -> torch.Tensor:
|
|
"""Paged sparse attention over ``[window | compressed]`` global rows; the compressed half reads
|
|
the layer's kv source (window-only layers pass ``n_window == topk``)."""
|
|
from freetoken.kernel.triton.dsv41.sparse_attn import sparse_attn_packed
|
|
|
|
pool, args = self.pool, self.config.dsv41_args
|
|
src = args.roles[layer_id].kv_source
|
|
cmp = pool.main_pool[src] if src is not None else pool.main_pool[args.backbone_kv_sources[0]]
|
|
return sparse_attn_packed(
|
|
q, pool.window_pool[layer_id], pool.win_fmt, cmp, pool.main_fmt, attn_sink,
|
|
topk_idxs, n_window, softmax_scale, cmp_counts=cmp_counts,
|
|
)
|
|
|
|
|
|
__all__ = ["DSV41SparseAttnBackend", "DSV41AttnMetadata", "PrefillSegment", "SharedSelection"]
|