FreeToken brings datacenter-scale model serving to your desktop. Run massive models locally, fast and efficiently.
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)))