Skip to content

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

19.6 KB
Raw Blame
from __future__ import annotations

import os
from typing import NamedTuple

import torch
import triton
import triton.language as tl
from flashlib.kernels.slot_cache import lru_ensure

# Hybrid backend: which of a step's missing experts to fetch (when capped below the miss
# count). "recency" (default) fetches the experts most-recently active before this step
# (LRU on the expert -> prioritizes recurring misses, lowering the steady miss rate);
# "lowest_id" fetches the smallest expert ids (the original, routing-blind heuristic).
_HYBRID_FETCH_BY_RECENCY = (
    os.getenv("FREETOKEN_HYBRID_FETCH", "recency").strip().lower() != "lowest_id"
)
# How fetch_fraction * misses becomes a fetch count: "min-wait" (default) picks the integer
# that makes the PCIe fetch and the CPU compute finish closest together, "stochastic" rounds
# up with probability equal to the fractional part, "prefer-fetch" always rounds up.
_HYBRID_FETCH_ROUNDING = {"min-wait": 0, "stochastic": 1, "prefer-fetch": 2}
_hybrid_fetch_round = (os.getenv("FREETOKEN_HYBRID_FETCH_ROUND") or "min-wait").strip().lower()
if _hybrid_fetch_round not in _HYBRID_FETCH_ROUNDING:
    raise ValueError(f"FREETOKEN_HYBRID_FETCH_ROUND={_hybrid_fetch_round!r}: expected one of {sorted(_HYBRID_FETCH_ROUNDING)}")
_HYBRID_FETCH_ROUND = _HYBRID_FETCH_ROUNDING[_hybrid_fetch_round]
_HYBRID_FETCH_SEED = 0
# Phase 2 of the hybrid ensure kernel scans a pool wider than this in tiles of this width.
_HYBRID_EVICT_CHUNK = 8192


def ensure_experts(cache, layer_id: int, expert_ids: torch.Tensor) -> None:
    """Make this layer's routed experts resident; rewrite ``expert_ids`` to slot ids.

    Delegates to flashlib's slot cache. ``id_base`` maps this layer's expert ids into the
    flat ``layer * num_experts + expert`` space the cache indexes by, and maps
    ``src_indices`` back, so ``copy_missing`` still resolves against this layer's own host
    tensor. ``out_indices`` aliases the input, preserving the in-place rewrite every
    downstream GEMM depends on.
    """
    id_of_slot, usage = cache.pool_state(layer_id)
    lru_ensure(
        expert_ids,
        cache.slot_for_id.view(-1),
        id_of_slot,
        usage,
        cache.step,
        expert_ids,
        cache.src_indices,
        cache.evict_slots,
        cache.num_indices,
        stats=cache.lru_stats[layer_id] if cache.collect_stats else None,
        id_base=layer_id * cache.num_experts,
    )


class HybridRoutes(NamedTuple):
    """One layer's routes split between the GPU and the CPU, each [bs, top_k]."""

    gpu_slots: torch.Tensor  # cache slot of each route; a CPU route is -1, or 0 with clamp
    gpu_w: torch.Tensor  # router weights, 0 for a CPU route
    cpu_ids: torch.Tensor  # expert ids, -1 for a GPU route


def ensure_experts_hybrid(
    cache,
    layer_id: int,
    expert_ids: torch.Tensor,
    weights: torch.Tensor,
    max_fetch: int,
    fetch_fraction: float = 0.0,
    clamp: bool = False,
    fetch_cap: int | None = None,
) -> HybridRoutes:
    """Capped-fetch variant of ``ensure_experts`` (hybrid backend).

    Identical LRU bookkeeping, but only the first ``max_fetch`` of this step's missing
    experts are given a slot and scheduled for copy; the overflow misses stay
    non-resident and their ``expert_ids`` positions are rewritten to ``-1`` (compute on
    the CPU). ``fetch_fraction`` > 0 replaces the fixed cap with the bandwidth-matched
    split (fraction = pcie_bw / cpu_bw): fetch ~fraction of the step's misses, rounded as
    ``FREETOKEN_HYBRID_FETCH_ROUND`` says (default: the integer that makes the PCIe fetch and the CPU overflow compute finish closest together).
    ``num_indices`` = capped fetch count (copy_missing); ``num_missing_full`` =
    pre-cap miss count (stats).

    The same launch splits the routes: ``expert_ids`` becomes the GPU slots in place, and
    ``clamp`` gives CPU routes slot 0 instead of -1 for GEMM kernels that read every slot.
    ``fetch_cap`` bounds the fetch count after ``max_fetch`` / ``fetch_fraction`` (a fixed-size staging buffer)."""
    assert expert_ids.is_cuda, "the hybrid ensure kernel runs on the GPU"
    # Q16 fixed point: the kernel caps in integers.
    frac_q16 = min(1 << 16, max(0, round(fetch_fraction * (1 << 16))))
    weights = weights.contiguous()
    routes = HybridRoutes(expert_ids, torch.empty_like(weights), torch.empty_like(expert_ids))
    cap = cache.num_experts if fetch_cap is None else fetch_cap
    _ensure_experts_hybrid_gpu(cache, layer_id, expert_ids, weights, routes, clamp, max_fetch, frac_q16, cap)
    return routes


def prefill_hit_compact(cache, layer_id: int) -> None:
    """Compact this layer's cache-resident experts into gather indices, device-side.

    hit = slot_for_id[layer_id][e] >= the pool's staging threshold (the double buffer owns the
    slots below, so those bytes are volatile within a prefill chunk and classify
    as miss). Writes fixed-shape ``_prefill_hit_dst``/``_prefill_hit_src`` (buffer
    row / pool-local slot) and the count into ``_prefill_hit_num``; one launch on the
    current stream, no host sync. Safe against the concurrent buffer invalidation
    on the copy stream: that only rewrites entries already below the threshold."""
    num_experts = cache.num_experts
    _prefill_hit_compact_kernel[(1,)](
        cache.slot_for_id[layer_id],
        cache._prefill_hit_dst,
        cache._prefill_hit_src,
        cache._prefill_hit_num,
        cache._pool_stable_from[cache.pool_of_layer[layer_id]],
        num_experts,
        BLOCK=triton.next_power_of_2(num_experts),
    )


def materialize_layer(cache, layer_id: int) -> None:
    if len(cache.pool_sizes) == 1:
        _materialize_layer_gpu(cache, layer_id)
        return
    # staging buffer 0 may overlap several pools, so it only holds the layer for this forward and registers nothing
    E = cache.num_experts
    cache._invalidate_prefill_buffer(0, layer_id)
    rows = torch.arange(E, dtype=torch.int32, device=cache.device)
    cache.evict_slots[:E].copy_(rows)
    cache.src_indices[:E].copy_(rows)
    cache.num_indices.fill_(E)


def reset_cache(cache) -> None:
    _reset_cache_gpu(cache)






def _ensure_experts_hybrid_gpu(
    cache,
    layer_id: int,
    expert_ids: torch.Tensor,
    weights: torch.Tensor,
    routes: HybridRoutes,
    clamp: bool,
    max_fetch: int,
    frac_q16: int,
    fetch_cap: int,
) -> None:
    id_of_slot, usage = cache.pool_state(layer_id)
    num_slots = id_of_slot.numel()
    block_e = triton.next_power_of_2(cache.num_experts)
    chunk = min(_HYBRID_EVICT_CHUNK, triton.next_power_of_2(num_slots))
    # with 4 warps a 4096+ chunk spills on sm80-sm89
    num_warps = 8 if chunk >= 4096 else 4
    _ensure_experts_hybrid_kernel[(1,)](
        expert_ids,
        cache.slot_for_id,
        id_of_slot,
        usage,
        cache.step,
        cache.active_mask,
        cache.evict_slots,
        cache.src_indices,
        cache.num_indices,
        cache.num_missing_full,
        cache.expert_recency,
        weights,
        routes.cpu_ids,
        routes.gpu_w,
        *(cache.hybrid_stats if cache.collect_stats else (expert_ids,) * 2),
        layer_id,
        expert_ids.numel(),
        int(max_fetch),
        int(frac_q16),
        int(fetch_cap),
        cache.num_experts,
        num_slots,
        _HYBRID_FETCH_SEED,
        BLOCK_E=block_e,
        CHUNK=chunk,
        SMALL=num_slots <= chunk,
        BY_RECENCY=_HYBRID_FETCH_BY_RECENCY,
        ROUND=_HYBRID_FETCH_ROUND,
        CLAMP=clamp,
        STATS=cache.collect_stats,
        num_warps=num_warps,
    )


def _materialize_layer_gpu(cache, layer_id: int) -> None:
    block = triton.next_power_of_2(max(cache.num_experts, cache.cache_size))
    _materialize_layer_kernel[(1,)](
        cache.slot_for_id,
        cache.id_of_slot,
        cache.usage,
        cache.step,
        cache.evict_slots,
        cache.src_indices,
        cache.num_indices,
        layer_id,
        cache.num_experts,
        cache.cache_size,
        BLOCK=block,
    )


def _reset_cache_gpu(cache) -> None:
    block = 256
    total_ids = cache.num_layers * cache.num_experts
    grid = (triton.cdiv(max(total_ids, cache.cache_size), block),)
    _reset_cache_kernel[grid](
        cache.slot_for_id,
        cache.id_of_slot,
        cache.usage,
        cache.step,
        cache.active_mask,
        cache.num_indices,
        total_ids,
        cache.num_experts,
        cache.cache_size,
        BLOCK=block,
    )


@triton.jit
def _reset_cache_kernel(
    slot_for_id_ptr,
    id_of_slot_ptr,
    usage_ptr,
    step_ptr,
    active_mask_ptr,
    num_indices_ptr,
    total_ids: tl.constexpr,
    num_experts: tl.constexpr,
    cache_size: tl.constexpr,
    BLOCK: tl.constexpr,
):
    off = tl.program_id(0) * BLOCK + tl.arange(0, BLOCK)
    tl.store(slot_for_id_ptr + off, -1, mask=off < total_ids)
    tl.store(id_of_slot_ptr + off, -1, mask=off < cache_size)
    tl.store(usage_ptr + off, 0, mask=off < cache_size)
    tl.store(active_mask_ptr + off, 0, mask=off < num_experts)
    if tl.program_id(0) == 0:
        tl.store(step_ptr, 0)
        tl.store(num_indices_ptr, 0)


@triton.jit
def _materialize_layer_kernel(
    slot_for_id_ptr,
    id_of_slot_ptr,
    usage_ptr,
    step_ptr,
    evict_slots_ptr,
    src_indices_ptr,
    num_indices_ptr,
    layer_id: tl.constexpr,
    num_experts: tl.constexpr,
    cache_size: tl.constexpr,
    BLOCK: tl.constexpr,
):
    off = tl.arange(0, BLOCK)
    expert_mask = off < num_experts
    slot_mask = off < cache_size
    slot = off

    base = layer_id * num_experts
    old_id = tl.load(id_of_slot_ptr + slot, mask=slot_mask, other=-1)
    # Flat ids make "belongs to this layer" a range check instead of a field compare.
    same_layer = slot_mask & (old_id >= base) & (old_id < base + num_experts)
    tl.store(id_of_slot_ptr + slot, -1, mask=same_layer)
    tl.store(usage_ptr + slot, 0, mask=same_layer)

    old_valid = expert_mask & (old_id >= 0) & (~same_layer)
    tl.store(slot_for_id_ptr + old_id, -1, mask=old_valid)

    step = tl.load(step_ptr) + 1
    tl.store(step_ptr, step)
    tl.store(id_of_slot_ptr + slot, base + off, mask=expert_mask)
    tl.store(slot_for_id_ptr + base + off, slot, mask=expert_mask)
    tl.store(usage_ptr + slot, step, mask=expert_mask)
    tl.store(evict_slots_ptr + off, slot, mask=expert_mask)
    tl.store(src_indices_ptr + off, off, mask=expert_mask)  # layer-local row
    tl.store(num_indices_ptr, num_experts)




@triton.jit(do_not_specialize=["layer_id", "num_active", "max_fetch", "fetch_frac_q16", "fetch_cap", "cache_size", "id_of_slot_ptr", "usage_ptr"])
def _ensure_experts_hybrid_kernel(
    expert_ids_ptr,
    slot_for_id_ptr,
    id_of_slot_ptr,
    usage_ptr,
    step_ptr,
    active_mask_ptr,
    evict_slots_ptr,
    src_indices_ptr,
    num_indices_ptr,
    num_missing_full_ptr,
    expert_recency_ptr,
    weights_ptr,
    cpu_ids_ptr,
    gpu_w_ptr,
    stats_ptr,
    stats_layer_ptr,
    layer_id,
    num_active,
    max_fetch,
    fetch_frac_q16,
    fetch_cap,
    num_experts: tl.constexpr,
    cache_size,
    seed,
    BLOCK_E: tl.constexpr,
    CHUNK: tl.constexpr,
    SMALL: tl.constexpr,
    BY_RECENCY: tl.constexpr,
    ROUND: tl.constexpr,
    CLAMP: tl.constexpr,
    STATS: tl.constexpr,
):
    """Capped-fetch timestamp-LRU (hybrid backend).

    Same as ``_ensure_experts_lru_v2_kernel`` but only ``min(num_missing, max_fetch)``
    missing experts are evicted-into / scheduled for copy; the overflow misses stay
    non-resident, so Phase 3 rewrites their positions to -1 (the layer computes those on
    the CPU). ``fetch_frac_q16`` > 0 (Q16 fixed point) replaces the fixed cap with the
    bandwidth-matched split ``~frac * num_missing`` (see the Phase-1 comment), computed
    in-kernel because ``num_missing`` only exists device-side (CUDA graph). ``num_indices``
    = the capped fetch count (copy_missing), ``num_missing_full`` = the pre-cap miss count
    (stats).

    Which misses to fetch is the cap policy. ``BY_RECENCY`` (default) fetches the experts
    most-recently active before this step (LRU on the expert, via ``expert_recency``),
    breaking ties toward the lower expert id -- this prioritizes *recurring* misses for
    caching, lowering the steady miss rate. Otherwise the lowest expert ids are fetched
    (``missing_rank``), the original routing-blind heuristic.

    Victims are the least-used slots, ties to the lowest slot. Every usage is at most the
    step before this launch, so the hit slots stamped with ``step`` in Phase 1 are never
    picked. A pool of at most CHUNK slots stays in registers (SMALL); a larger one is scanned
    from memory in CHUNK tiles per victim."""
    step = tl.load(step_ptr) + 1
    tl.store(step_ptr, step)
    base = layer_id * num_experts

    # ---- Phase 1: active + missing over experts ----
    off_e = tl.arange(0, BLOCK_E)
    e_mask = off_e < num_experts
    is_active = tl.zeros((BLOCK_E,), dtype=tl.int1)
    for i in tl.range(num_active):
        e = tl.load(expert_ids_ptr + i)
        is_active = is_active | (off_e == e)
    tl.store(active_mask_ptr + off_e, is_active.to(tl.int32), mask=e_mask)
    slot = tl.load(slot_for_id_ptr + base + off_e, mask=e_mask, other=-1)
    is_missing = is_active & (slot == -1) & e_mask
    num_missing = tl.sum(is_missing.to(tl.int32))
    # Cap the fetches; the overflow misses are computed on the CPU (left non-resident).
    if fetch_frac_q16 > 0:
        # Bandwidth-matched split (fetch_frac = pcie_bw / cpu_bw): fetch time scales with
        # F * (1 - frac), CPU time with (M - F) * frac; they balance at F = frac * M. Pick
        # the integer neighbor that minimizes the slower (max) side of the overlap.
        lo = (num_missing * fetch_frac_q16) >> 16
        if ROUND == 1:
            # step is unique per launch, so each (layer, step) draws its own number
            rem = (num_missing * fetch_frac_q16) & 0xFFFF
            u = tl.rand(seed, (step & 0x7FFFFFFF).to(tl.int32))
            max_fetch = lo + ((u * 65536.0) < rem.to(tl.float32)).to(tl.int32)
        elif ROUND == 2:
            max_fetch = (num_missing * fetch_frac_q16 + 0xFFFF) >> 16
        else:
            cost_lo = tl.maximum(lo * ((1 << 16) - fetch_frac_q16), (num_missing - lo) * fetch_frac_q16)
            cost_hi = tl.maximum(
                (lo + 1) * ((1 << 16) - fetch_frac_q16), (num_missing - lo - 1) * fetch_frac_q16
            )
            max_fetch = tl.where(cost_lo <= cost_hi, lo, lo + 1)
    is_hit = is_active & (slot >= 0)
    # a pool smaller than num_experts may hold fewer free slots than misses
    num_fetch = tl.minimum(tl.minimum(num_missing, tl.minimum(max_fetch, fetch_cap)), cache_size - tl.sum(is_hit.to(tl.int32)))
    tl.store(num_missing_full_ptr, num_missing.to(tl.int64))
    tl.store(num_indices_ptr, num_fetch.to(tl.int64))
    tl.store(usage_ptr + slot, step, mask=is_hit)

    # Fetch-selection priority: encode (recency desc, id asc) into one strictly-ordered
    # score so argmax has no ties (rec deltas are multiples of num_experts; the id term
    # spans only [0, num_experts), so it can only break exact-recency ties).
    if BY_RECENCY:
        rec = tl.load(expert_recency_ptr + base + off_e, mask=e_mask, other=-1).to(tl.int64)
        score = tl.where(
            is_missing, rec * num_experts + (num_experts - 1 - off_e), -1152921504606846976
        ).to(tl.int64)
    else:
        missing_rank = tl.cumsum(is_missing.to(tl.int32)) - 1

    # ---- Phase 2: evict victims by argmin(usage), only for the capped fetches ----
    if num_fetch > 0:
        off_k = tl.arange(0, CHUNK)
        tl.debug_barrier()  # the scan below must see the hit stamps
        if SMALL:
            u_reg = tl.load(usage_ptr + off_k, mask=off_k < cache_size, other=9223372036854775807).to(tl.int64)
        for i in tl.range(num_fetch):
            if SMALL:
                victim = tl.argmin(u_reg, axis=0).to(tl.int32)
                u_reg = tl.where(off_k == victim, step, u_reg)
            else:
                best_u = tl.full((), 9223372036854775807, tl.int64)
                best_s = tl.full((), 0, tl.int32)
                for c0 in tl.range(0, cache_size, CHUNK):
                    offs = c0 + off_k
                    uu = tl.load(usage_ptr + offs, mask=offs < cache_size, other=9223372036854775807).to(tl.int64)
                    cmin = tl.min(uu, axis=0)
                    carg = (tl.argmin(uu, axis=0) + c0).to(tl.int32)
                    take = cmin < best_u
                    best_s = tl.where(take, carg, best_s)
                    best_u = tl.where(take, cmin, best_u)
                victim = best_s
            old_id = tl.load(id_of_slot_ptr + victim)
            if old_id >= 0:
                tl.store(slot_for_id_ptr + old_id, -1)
            if BY_RECENCY:
                e = tl.argmax(score, axis=0).to(tl.int32)
                score = tl.where(off_e == e, -1152921504606846976, score)
            else:
                e = tl.sum(tl.where((missing_rank == i) & is_missing, off_e, 0))
            tl.store(id_of_slot_ptr + victim, base + e)
            tl.store(slot_for_id_ptr + base + e, victim)
            tl.store(usage_ptr + victim, step)
            tl.store(evict_slots_ptr + i, victim)
            tl.store(src_indices_ptr + i, e)  # layer-local row
            tl.debug_barrier()  # the next scan must see this victim's stamp
    tl.debug_barrier()  # Phase 3 reads slot_for_id entries written above

    # ---- Phase 3: rewrite expert_ids -> slot id (hit/fetched) or -1 (overflow -> CPU) ----
    for i in tl.range(num_active):
        e = tl.load(expert_ids_ptr + i)
        s = tl.load(slot_for_id_ptr + base + e)
        # every warp loads e, one thread stores below; a warp that loads after that store indexes with a slot id
        tl.debug_barrier()
        on_gpu = s >= 0
        tl.store(cpu_ids_ptr + i, tl.where(on_gpu, -1, e))
        tl.store(gpu_w_ptr + i, tl.where(on_gpu, tl.load(weights_ptr + i), 0.0))
        if CLAMP:
            s = tl.maximum(s, 0)
        tl.store(expert_ids_ptr + i, s)

    # stats_ptr: (missing, fetched, active, calls); stats_layer_ptr: the same per layer, [num_layers, 4]
    if STATS:
        n_active = tl.sum((is_active & e_mask).to(tl.int64))
        tl.store(stats_ptr + 0, tl.load(stats_ptr + 0) + num_missing)
        tl.store(stats_ptr + 1, tl.load(stats_ptr + 1) + num_fetch)
        tl.store(stats_ptr + 2, tl.load(stats_ptr + 2) + n_active)
        tl.store(stats_ptr + 3, tl.load(stats_ptr + 3) + 1)
        row = stats_layer_ptr + layer_id * 4
        tl.store(row + 0, tl.load(row + 0) + num_missing)
        tl.store(row + 1, tl.load(row + 1) + num_fetch)
        tl.store(row + 2, tl.load(row + 2) + n_active)
        tl.store(row + 3, tl.load(row + 3) + 1)

    # Bump every active expert's recency to this step (LRU on the expert): an overflow miss
    # computed on the CPU now ranks high if it recurs, so it gets fetched next time.
    if BY_RECENCY:
        step_vec = tl.zeros((BLOCK_E,), dtype=tl.int64) + step
        tl.store(expert_recency_ptr + base + off_e, step_vec, mask=is_active & e_mask)


@triton.jit(do_not_specialize=["threshold"])
def _prefill_hit_compact_kernel(
    slot_ptr,     # [num_experts] int32: this layer's slot_for_id row
    dst_ptr,      # [num_experts] int32 out: buffer rows (expert ids), compacted
    src_ptr,      # [num_experts] int32 out: pool-local slots, compacted
    num_ptr,      # [1] int64 out: hit count
    threshold,    # first pool-local slot outside the staging buffers
    num_experts,
    BLOCK: tl.constexpr,
):
    offs = tl.arange(0, BLOCK)
    lane = offs < num_experts
    slots = tl.load(slot_ptr + offs, mask=lane, other=-1)
    is_hit = lane & (slots >= threshold)
    pos = tl.cumsum(is_hit.to(tl.int32)) - 1
    tl.store(dst_ptr + pos, offs.to(tl.int32), mask=is_hit)
    tl.store(src_ptr + pos, slots, mask=is_hit)
    tl.store(num_ptr, tl.sum(is_hit.to(tl.int64)))