"""Lesson 20 check: prefill and decode as separate pools; expert and data parallelism.

What is computed here:
  0. the published facts the chapter quotes (paraphrased, printed so the chapter can be compared line by line);
  1. the opening count: the weights of DeepSeek-V4.1-Flash in bytes against the memory of one accelerator;
  2. the toy layer (attention with 4 heads, 8 routed experts, 8 token positions) on one GPU, and the same layer
     spread over 4 GPUs in four ways: data parallelism alone, tensor parallelism, expert parallelism with
     data-parallel attention, and context parallelism. Each is checked against the one-GPU output, with a count of
     the weights each GPU holds and the numbers that cross between GPUs in one layer;
  3. dispatch and combine on the toy, pair by pair;
  4. the real sizes: experts and gigabytes per GPU at each EP size, against two chosen memory sizes;
  5. our toy cost model: tokens per expert, expert weights read per token and operations per byte, for decode and
     for prefill, and the bytes that dispatch and combine put on the interconnect;
  6. the toy timeline: one long prefill and a stream of decode steps on one GPU, then on separate pools;
  7. the availability arithmetic for EP4 against EP64 with a chosen failure probability;
  8. the listing's function on a second, random batch.

Sources: the DeepInfer deployment document (doc/inference_deployment_qa.md): the introduction, "Inference system
overview", "Cluster & storage", "Autoscaling & fault tolerance", the speculative-decoding answer that states the
production operating point, and the two Mega MoE answers under "Kernel implementation"; the DeepInfer README; the
DeepSeek-V4 report (arXiv 2606.19348), sections 2.1 and 3.1; the DeepEP README; the DeepSeek-V4.1-Flash report
(arXiv 2609.19969), sections 2.1, 2.4.2 and 4.2.1; lessons 6, 10 and 12 for the expert count and bytes per number.

Chosen for easy arithmetic, not taken from any source: the toy layer and all its weights, the 4 GPUs and the split
of the 8 positions, the way numbers that cross are counted, the two accelerator memory sizes (80 GB and 180 GB),
the one byte per number for the weights outside the routed experts, the 4,096 prompt tokens per prefill rank, the
uniform routing of the cost model, every time unit of the timeline, the failure probability of 0.001 per GPU and
day and the 10 minutes of restart. The cost model, the timeline and the availability arithmetic are ours.
Every number in lesson-20-prefill-decode-pools.md is printed here.
Run:  /Users/rajat/.pyenv/shims/python3 lesson20_check.py
"""
import numpy as np
import torch
import torch.nn.functional as F

torch.set_printoptions(precision=4, sci_mode=False, linewidth=170)
np.set_printoptions(precision=4, suppress=True, linewidth=170)

# ---------------------------------------------------------------- 0. published facts
print("0. Published facts used in the chapter (paraphrased)")
facts = [
    "DeepInfer document, title: 'DeepSeek V4.1 Flash Inference Deployment Q&A'.",
    "DeepInfer document, introduction: three goals: support accelerators from multiple vendors; organize prefill and",
    "      decode around commodity hardware, 'ordinary 8-GPU machines for prefill, ordinary 64-128-GPU supernodes for",
    "      decode'; retain KV cache for more than 72 hours. 'A single cluster currently serves 155 trillion tokens per",
    "      day', with 'overall revenue of US$38 per GPU-hour (at the off-peak price)'. For throughput and latency it",
    "      uses (a) 'Expert parallelism (EP) for the MoE part within a (super)node', which 'increases batch size and GPU",
    "      matrix-multiplication efficiency', and (b) disaggregated Vision Encoder / Prefill / Decode deployment, which",
    "      'decouples resource allocation per stage', so TTFT and TBT can be controlled and optimized independently.",
    "      'attention uses data parallelism (#DP = #EP)', as in the DeepSeek-V3/R1 inference system. Four load",
    "      balancers: prefill, decode, vision encoder, expert-parallel. A KVCache Storage component.",
    "DeepInfer document, overall shape: 'A disaggregated E/P/D architecture plus dedicated storage nodes.'",
    "DeepInfer document, parallelism: VE: a single GPU per instance is generally enough, cheaper GPUs recommended.",
    "      Prefill: 'EP2-8 / DP2-8; use the smallest EP/DP that HBM allows.' Decode: 'EP64-128 / DP64-128 (Wide-EP); use",
    "      the largest EP/DP that the available GPUs allow.' 'TP and CP are not used for now.'",
    "DeepInfer document, smallest size for prefill: 'Unlike decode, prefill already has a sufficiently large batch size",
    "      per expert.' 'Smaller DP/EP groups improve both data-parallel and expert-parallel load balance and reduce",
    "      NVLink traffic.'",
    "DeepInfer document, Wide-EP for decode: it 'substantially reduces per-step memory traffic in the MoE expert part'",
    "      and, with good expert-parallel load balancing, raises TPS. One chart, 'EP8 vs. EP64 decode throughput',",
    "      offline benchmark data; no number is in the text.",
    "DeepInfer document, CP and TP: CP 'splits long sequences across multiple GPUs, reducing tail TTFT'; 'up to 5%",
    "      slower than DP end to end'; it removes the need for the DP load-balancing scheme; not used mainly because",
    "      V4.1 is fast enough to keep tail TTFT acceptable even on a complete cache miss; CP improves data-parallel",
    "      load balance and tends to worsen expert-parallel load balance; it adds kernel, communication and CPU",
    "      overhead. 'Tensor parallelism (TP) has high communication overhead'; not used when the model fits in memory",
    "      and the latency SLA can be met without it.",
    "DeepInfer document, choosing a strategy: maximize utilization while meeting reasonable TTFT and TPS targets;",
    "      analyze kernel performance and load balance; validate with offline benchmarks. No target is given in numbers.",
    "DeepInfer document, multimodal: 'EPD disaggregation, with the vision encoder deployed on a single GPU.' VE load",
    "      balancer: images routed at machine granularity; within a machine to the GPU processing the fewest patches.",
    "DeepInfer document, Engram: 'a separate parallel group (ENP), sharded along the vocabulary dimension'; prefill uses",
    "      ENP8, decode an ENP size equal to the DP/EP size; on GPUs the vocabulary is in local host memory, each rank",
    "      holding a 1/ENP shard, registered for RDMA reads issued at the start of the forward pass.",
    "DeepInfer document, smallest unit: '1P + 1D is deployable'; 'In practice the GPU ratio between P and D is roughly",
    "      1:1'; with decode at EP64 or above 'the smallest efficient deployment unit is 64 GPUs of prefill plus 64",
    "      GPUs of decode'.",
    "DeepInfer document, cluster and storage: P and D can be split across data centers because V4.1 Flash compresses",
    "      the KV cache; 'roughly 400 Gbps of interconnect bandwidth per 8 GPUs'; a KV storage server: 20 x 30.73 TB",
    "      SSDs, at least 40 GB/s read and 5 GB/s write; 'about 14.4 TB per GPU measured as logical size'; training",
    "      and inference clusters are managed together and resources move between them.",
    "DeepInfer document, KV cache: 'the prefill side also uses a paged KV cache'; 'Decode is not bound by cache",
    "      capacity'; 'The SWA KV cache and the block KV cache share the same P-to-D transfer path.' Prefill computes",
    "      only in the encoder layers and recomputes the last 128 prompt tokens in the decoder layers.",
    "DeepInfer document, autoscaling: prefill scales with 'the number of non-cached tokens', decode with 'the number of",
    "      running requests', rate-limited and bounded. A decode engine (CE) 'enters a grace period (1 min) after",
    "      receiving a shutdown notice'; requests still unfinished, 'along with their KV cache, are forwarded in one",
    "      shot to other CEs', to address the waste long-tail requests cause in large-EP deployments. Redundant quota:",
    "      idle ready machines, and more instances online than computed demand; no scale-in 'whenever quota",
    "      utilization is above 0.8'. 'Restarts are on the order of minutes.' Fault tolerance comes from PE / CE quota",
    "      redundancy plus request-level rerouting.",
    "DeepInfer document, EP failover: 'a single failed GPU makes the whole instance unusable', since all GPUs of an",
    "      instance form a single communication domain; on restart 'the platform re-determines the EP size from all",
    "      currently healthy GPUs'. What happens to the requests that were running is not stated.",
    "DeepInfer document, speculative decoding: benchmark data at EP64/DP64; 'the production operating point (~60",
    "      concurrent sequences per rank)'.",
    "DeepInfer document, kernels: Mega MoE is 'the general solution within a scale-up domain' and faster than unfused",
    "      MoE at any EP or batch size. Beyond EP32 in decode: 'Increasing EP raises arithmetic intensity to avoid",
    "      being memory-bound. Once memory bandwidth is no longer the bottleneck, a larger EP size introduces",
    "      additional communication and synchronization overhead.' Jobs sharing NVLink in a supernode can interfere.",
    "DeepInfer README: 'Parallelism: Attention DP / balanced CP, MoE EP + EPLB' ('balanced CP' is not explained).",
    "      Not included in the release: a KV cache system, VE/Prefill/Decode disaggregation, load balancing across",
    "      data-parallel replicas. Benchmarks 'on 4 SM100 GPUs for prefill and 64 for decode - each within one scale-up",
    "      domain'; results are two charts without numbers in the text. Supports NVIDIA SM100 GPUs and Huawei Ascend",
    "      950 NPUs. No GPU memory size and no weight size are stated.",
    "V4 report, section 2.1: 'we remove the constraint on the number of routing target nodes'.",
    "V4 report, section 3.1: EP 'requires complex inter-node communication and imposes substantial demands on",
    "      interconnect bandwidth and latency'. An MoE layer has four stages: Dispatch and Combine (communication",
    "      bound), Linear-1 and Linear-2 (computation bound). Within one layer 'the total time of communication is",
    "      less than that of the computation'. For V4-Pro 'each token-expert pair requires 6hd FLOPs' and 'only 3h",
    "      bytes of communication (FP8 Dispatch + BF16 Combine)', so C/B <= 2d = 6144 FLOPs/Byte, and 'each GBps of",
    "      interconnect bandwidth suffices to hide the communication for 6.1 TFLOP/s of compute'. Dispatch is pull",
    "      based: each GPU reads activations from remote GPUs. Fused EP: 1.50 to 1.73x for general inference, up to",
    "      1.96x for latency-sensitive workloads. Validated on NVIDIA GPUs and Huawei Ascend NPUs.",
    "DeepEP README: 'expert-parallel (EP) all-to-all GPU kernels for MoE dispatch and combine'. 'MoE dispatch: route",
    "      tokens to the corresponding experts across all ranks.' 'MoE combine: reduce expert outputs back to their",
    "      original ranks.' NVLink for intranode and RDMA for internode communication.",
    "V4.1-Flash report: 552B backbone parameters and 196B Engram parameters; 40 layers, hidden size 5120; 1 shared and",
    "      384 routed experts per layer, 6 routed experts per token, intermediate size 2304; vision encoder with 32",
    "      layers, hidden size 1024, 16 heads, patch size 14 (no parameter count); Engram tables in FP8.",
]
for f in facts:
    print("   " + f)

# ---------------------------------------------------------------- 1. the opening count
print("\n1. The weights of V4.1-Flash against one accelerator")
LAYERS, HID, MID, ROUTED, TOPK = 40, 5120, 2304, 384, 6
BACKBONE, ENGRAM = 552e9, 196e9
FP4 = 0.53125                         # bytes per number: MXFP4, one UE8M0 scale per 32 numbers (lesson 12)
per_expert = 3 * HID * MID            # three matrices, as in lessons 6 and 10 (our assumption)
routed = LAYERS * ROUTED * per_expert
rest = BACKBONE - routed
routed_gb = routed * FP4 / 1e9
rest_gb = rest * 1.0 / 1e9            # one byte per number, chosen: the format of these weights is not stated
engram_gb = ENGRAM * 1.0 / 1e9        # FP8 (V4.1 report, section 2.4.2), scales not counted
backbone_gb = routed_gb + rest_gb
print(f"   one expert: 3 x {HID} x {MID} = {per_expert:,} numbers, {per_expert * FP4:,.0f} bytes = {per_expert * FP4 / 1e6:.2f} MB in MXFP4")
print(f"   routed experts: {LAYERS} x {ROUTED} x {per_expert:,} = {routed:,} numbers = {routed / 1e9:.2f}B "
      f"({routed / BACKBONE * 100:.1f} percent of the 552B backbone)")
print(f"      x {FP4} bytes = {routed * FP4:,.0f} bytes = {routed_gb:.1f} GB")
print(f"   the rest of the backbone: 552B - {routed / 1e9:.2f}B = {rest / 1e9:.2f}B numbers, at one byte each (chosen) {rest_gb:.1f} GB")
print(f"   backbone: {routed_gb:.1f} + {rest_gb:.1f} = {backbone_gb:.1f} GB;  Engram: 196B numbers in FP8 = {engram_gb:.0f} GB;  "
      f"together {backbone_gb + engram_gb:.1f} GB")
MEMS = (80, 180)                      # GB of accelerator memory, chosen
for m in MEMS:
    print(f"   an accelerator with {m} GB (chosen): the backbone is {backbone_gb / m:.2f} times its memory, "
          f"at least {int(np.ceil(backbone_gb / m))} of them for the weights alone")
print(f"   all experts of one layer: {ROUTED} x {per_expert * FP4 / 1e6:.2f} MB = {ROUTED * per_expert * FP4 / 1e9:.3f} GB")

# ---------------------------------------------------------------- 2. the toy layer, on one GPU and four ways on 4 GPUs
print("\n2. The toy layer: 8 positions, attention with 4 heads of one number, 8 routed experts, 2 per position")
TOKENS = ["The", "next", "day", "is", "bright", "and", "sunny", "and"]
X = torch.tensor([
    [ 1., 0., 0., 1.],   # The      rows 0 to 5 are lesson 1's H; rows 6 and 7 are lesson 3's
    [ 0., 1., 1., 0.],   # next
    [ 2., 1., 0., 0.],   # day
    [-1., 0., 1., 1.],   # is
    [ 1., 2., 1., 0.],   # bright
    [ 1., 1., 0., 1.],   # and
    [ 1., 2., 0., 1.],   # sunny
    [ 1., 1., 0., 1.],   # and
])
D, NPOS, NEXP, K, NGPU, MIDT = 4, 8, 8, 2, 4, 4
W_Q = torch.eye(4)                                   # head g reads coordinate g, chosen
W_K = torch.eye(4)
W_V = torch.eye(4)
W_O = 0.5 * torch.eye(4)
E = torch.tensor([[1., 0.5, 0., 0.],                 # router rows of experts 1 to 4: lesson 10's
                  [0., 0., 1., 0.5],
                  [-1., 0., 0., 1.],
                  [0., 0.25, 0., 1.],
                  [0., 0.75, 0., -1.],               # experts 5 to 8: chosen, so that no two scores of a position tie
                  [1., -1., 0., 1.],
                  [0., 0.5, 1.25, -0.5],
                  [0.5, -0.25, 0., 0.75]])
gen = torch.Generator().manual_seed(20)
EXPERTS = []                                         # each expert: W_gate (4, 4), W_lin (4, 4), W_down (4, 4)
for e in range(NEXP):
    EXPERTS.append(tuple(torch.randint(-2, 3, (4, 4), generator=gen).float() / 2 for _ in range(3)))
n_attn, n_router, n_expert = 4 * 16, E.numel(), 3 * 16
n_all = n_attn + n_router + NEXP * n_expert
print(f"   weights: attention 4 x (4, 4) = {n_attn}; router (8, 4) = {n_router}; one expert 3 x (4, 4) = {n_expert}, "
      f"eight experts {NEXP * n_expert}; the layer {n_all}")
print("   expert weights are multiples of 0.5 drawn once with seed 20; everything is chosen")


def attention(Xs, lo=0, K_all=None, V_all=None):
    """Causal attention with 4 heads of one number each. Xs: the positions to compute; they sit at lo.. in their
    sequence. K_all, V_all: keys and values of the whole sequence up to the last of these positions."""
    Q = Xs @ W_Q
    Kk = Xs @ W_K if K_all is None else K_all
    Vv = Xs @ W_V if V_all is None else V_all
    out = torch.zeros_like(Xs)
    for h in range(4):
        s = Q[:, h:h + 1] * Kk[:, h][None, :]                                    # (rows, entries)
        for i in range(Xs.shape[0]):
            s[i, lo + i + 1:] = float("-inf")
        a = torch.softmax(s, dim=-1)
        out += (a @ Vv[:, h:h + 1]) @ W_O[h:h + 1, :]
    return out


def swiglu(x, W_gate, W_lin, W_down):
    return (F.silu(x @ W_gate) * (x @ W_lin)) @ W_down


def route(Y, k=K):
    s = F.softplus(Y @ E.T).sqrt()                   # the V4 affinity of lesson 10
    idx = s.topk(k, dim=-1).indices
    g = s.gather(-1, idx)
    return idx, g / g.sum(-1, keepdim=True)


def moe(Y):
    idx, gate = route(Y)
    out = torch.zeros_like(Y)
    for i in range(Y.shape[0]):
        for j in range(K):
            out[i] += gate[i, j] * swiglu(Y[i:i + 1], *EXPERTS[int(idx[i, j])])[0]
    return out


def layer_batch(Xb):
    """Four requests of two positions each, on one GPU."""
    A = torch.cat([attention(Xb[r:r + 2]) for r in range(0, NPOS, 2)])
    Y = Xb + A
    return Y, Y + moe(Y)


def layer_seq(Xs):
    """One sequence of eight positions, on one GPU."""
    Y = Xs + attention(Xs)
    return Y, Y + moe(Y)


Y_REF, Z_REF = layer_batch(X)
YS_REF, ZS_REF = layer_seq(X)
print("   one GPU, four requests of two positions: output Z (8, 4) =")
print("   " + str(Z_REF).replace("\n", "\n   "))

HOME = torch.tensor([p // 2 for p in range(NPOS)])   # the GPU that holds each position
OWNER = torch.tensor([e // 2 for e in range(NEXP)])  # the GPU that holds each expert under EP

# (a) data parallelism alone
Z_dp = torch.cat([layer_batch_part for layer_batch_part in
                  [(lambda Xr: (Xr + attention(Xr)) + moe(Xr + attention(Xr)))(X[r:r + 2]) for r in range(0, NPOS, 2)]])
print(f"\n   (a) data parallelism alone: each GPU holds all {n_all} weights and one request of 2 positions; "
      f"nothing crosses; equal to one GPU: {torch.allclose(Z_dp, Z_REF, atol=1e-5)}")

# (b) tensor parallelism: GPU g holds head g of attention and hidden unit g of every expert
A_parts = []
for g in range(NGPU):
    part = torch.zeros(NPOS, D)
    for r in range(0, NPOS, 2):
        Xr = X[r:r + 2]
        q, kk, v = Xr @ W_Q[:, g], Xr @ W_K[:, g], Xr @ W_V[:, g]            # column g of each matrix
        s = q[:, None] * kk[None, :]
        s[0, 1] = float("-inf")
        part[r:r + 2] = (torch.softmax(s, -1) @ v[:, None]) @ W_O[g:g + 1, :]  # row g of W_O
    A_parts.append(part)
Y_tp = X + sum(A_parts)                              # all-reduce 1: four partial sums of (8, 4)
idx_tp, gate_tp = route(Y_tp)
M_parts = []
for g in range(NGPU):
    part = torch.zeros(NPOS, D)
    for i in range(NPOS):
        for j in range(K):
            Wg, Wl, Wd = EXPERTS[int(idx_tp[i, j])]
            hid = F.silu(Y_tp[i] @ Wg[:, g]) * (Y_tp[i] @ Wl[:, g])           # hidden unit g
            part[i] += gate_tp[i, j] * hid * Wd[g, :]
    M_parts.append(part)
Z_tp = Y_tp + sum(M_parts)                           # all-reduce 2
tp_w = n_attn // 4 + n_router + NEXP * n_expert // 4
tp_cross = 2 * 2 * (NGPU - 1) * NPOS * D             # two all-reduces; a ring all-reduce moves 2 (N - 1) x size
print(f"   (b) tensor parallelism: each GPU holds {n_attn // 4} of attention + {n_router} router + "
      f"{NEXP * n_expert // 4} of the experts = {tp_w} weights and works on all 8 positions;")
print(f"       two all-reduces of (8, 4) partial sums per layer, each moving at least 2 x (4 - 1) x 32 = "
      f"{2 * (NGPU - 1) * NPOS * D} numbers: {tp_cross} cross; equal: {torch.allclose(Z_tp, Z_REF, atol=1e-5)}")

# (c) expert parallelism for the experts, data parallelism for attention
Y_ep = torch.cat([X[r:r + 2] + attention(X[r:r + 2]) for r in range(0, NPOS, 2)])   # attention stays on the home GPU
idx, gate = route(Y_ep)                                                             # so does the router
out = torch.zeros(NPOS, D)
pairs = []
for g in range(NGPU):
    for e in [e for e in range(NEXP) if OWNER[e] == g]:
        tok, slot = (idx == e).nonzero(as_tuple=True)                               # dispatch: who goes to expert e
        if len(tok) == 0:
            continue
        y_e = swiglu(Y_ep[tok], *EXPERTS[e])                                        # one product for the expert's batch
        out.index_add_(0, tok, gate[tok, slot][:, None] * y_e)                      # combine at the home GPU
        pairs += [(int(t), e, int(HOME[t]), g) for t in tok]
Z_ep = Y_ep + out
remote = [p for p in pairs if p[2] != p[3]]
ep_w = n_attn + n_router + 2 * n_expert
ep_cross = 2 * D * len(remote)
print(f"   (c) expert parallelism, attention data-parallel: each GPU holds {n_attn} + {n_router} + 2 x {n_expert} = {ep_w} "
      f"weights and 2 positions;")
print(f"       {len(pairs)} position-expert pairs, {len(pairs) - len(remote)} local and {len(remote)} remote; each remote pair sends 4 numbers "
      f"out and 4 back: {ep_cross} cross; equal: {torch.allclose(Z_ep, Z_REF, atol=1e-5)}")

# (d) context parallelism: one sequence of 8, two positions per GPU, every GPU a full copy
K_seq, V_seq = X @ W_K, X @ W_V
parts, cp_entries, cp_work = [], [], []
for g in range(NGPU):
    lo, hi = 2 * g, 2 * g + 2
    parts.append(attention(X[lo:hi], lo=lo, K_all=K_seq[:hi], V_all=V_seq[:hi]))     # needs entries 0 .. hi - 1
    cp_entries.append(lo)                                                            # entries that come from other GPUs
    cp_work.append(sum(p + 1 for p in range(lo, hi)))                                # entries read by its two positions
Y_cp = X + torch.cat(parts)
Z_cp = Y_cp + moe(Y_cp)
cp_cross = sum(cp_entries) * 2 * D
print(f"   (d) context parallelism: each GPU holds all {n_all} weights and 2 positions of one sequence; GPUs 0 to 3 need "
      f"{cp_entries} earlier entries from other GPUs,")
print(f"       {sum(cp_entries)} entries x (4 key + 4 value numbers) = {cp_cross} cross; entries read per GPU {cp_work}, last / first = {cp_work[-1] / cp_work[0]:g}; "
      f"equal to the one-GPU sequence: {torch.allclose(Z_cp, ZS_REF, atol=1e-5)}")

print("\n   summary                     weights per GPU   positions per GPU     numbers that cross in one layer")
print(f"   one GPU                     {n_all:<17d} 8                     0")
print(f"   data parallelism alone      {n_all:<17d} 2                     0")
print(f"   tensor parallelism          {tp_w:<17d} 8                     {tp_cross}")
print(f"   expert + data parallelism   {ep_w:<17d} 2, then by expert     {ep_cross}")
print(f"   context parallelism         {n_all:<17d} 2 of one sequence     {cp_cross}")

# ---------------------------------------------------------------- 3. dispatch and combine, pair by pair
print("\n3. Dispatch and combine on the toy (experts 1, 2 on GPU 0; 3, 4 on GPU 1; 5, 6 on GPU 2; 7, 8 on GPU 3)")
print("   position   token    home   experts (gate)                 on GPUs    remote pairs")
for p in range(NPOS):
    es = [int(idx[p, j]) for j in range(K)]
    gs = [int(OWNER[e]) for e in es]
    rm = sum(1 for g in gs if g != int(HOME[p]))
    print(f"   p{p + 1}         {TOKENS[p]:8s} G{int(HOME[p])}     E{es[0] + 1} ({gate[p, 0]:.4f})  E{es[1] + 1} ({gate[p, 1]:.4f})      "
          f"G{gs[0]}, G{gs[1]}     {rm}")
per_exp = [int((idx == e).sum()) for e in range(NEXP)]
per_gpu = [sum(per_exp[e] for e in range(NEXP) if OWNER[e] == g) for g in range(NGPU)]
M = np.zeros((NGPU, NGPU), dtype=int)
for t, e, h, g in pairs:
    M[h, g] += 1
zs = (Y_ep @ E.T).sort(dim=-1, descending=True).values
print(f"   smallest gap between the second and third router score of a position: {float((zs[:, 1] - zs[:, 2]).min()):.4f} (no ties)")
print(f"   positions per expert, E1 to E8: {per_exp}")
print(f"   pairs computed on each GPU, G0 to G3: {per_gpu}   (an even share would be {len(pairs) / NGPU:g})")
print("   pairs from home GPU (row) to expert GPU (column):")
print("   " + str(M).replace("\n", "\n   "))
print(f"   on the diagonal {int(np.trace(M))} local pairs; off it {int(M.sum() - np.trace(M))} remote pairs; "
      f"dispatch {D * len(remote)} numbers, combine {D * len(remote)} numbers")
p5 = 4
print(f"   the position 'bright' (p5, GPU 2): hidden state after attention {Y_ep[p5].tolist()}")
for j in range(K):
    e = int(idx[p5, j])
    print(f"      expert E{e + 1} on GPU {int(OWNER[e])}: output {[round(v, 4) for v in swiglu(Y_ep[p5:p5 + 1], *EXPERTS[e])[0].tolist()]}, "
          f"gate {gate[p5, j]:.4f}")
print(f"      combined: {[round(v, 4) for v in out[p5].tolist()]};  layer output {[round(v, 4) for v in Z_ep[p5].tolist()]}")

# ---------------------------------------------------------------- 4. real sizes per GPU
print("\n4. V4.1-Flash under expert parallelism: what one GPU holds (our count; EPLB's redundant experts not counted)")
print("   EP size   routed experts per layer   expert weights   + shared parts   fits in 80 GB   fits in 180 GB   Engram shard in host memory")
for N in (1, 2, 4, 8, 16, 32, 64, 128):
    ex = routed_gb / N
    tot = ex + rest_gb
    enp = 8 if N <= 8 else N
    print(f"   {N:<9d} {ROUTED / N:<26g} {ex:8.2f} GB      {tot:8.2f} GB      {'yes' if tot <= 80 else 'no':15s} "
          f"{'yes' if tot <= 180 else 'no':16s} {engram_gb / enp:6.2f} GB (ENP{enp})")
print("   prefill uses ENP8 and decode an ENP equal to its EP size (published); the shard sizes are our division")
for m, N in ((180, 2), (80, 4), (80, 8)):
    need = routed_gb / N + rest_gb
    print(f"   EP{N} on {m} GB: the weights need {need:.1f} GB, " + (f"which leaves {m - need:.1f} GB for caches and activations" if need <= m else "which does not fit"))

# ---------------------------------------------------------------- 5. the toy cost model (ours)
print("\n5. Our cost model for one MoE layer (uniform routing assumed)")
EXP_MB = per_expert * FP4 / 1e6
PAIR_FLOP = 6 * HID * MID
PAIR_NET = 3 * HID                     # bytes: FP8 dispatch + BF16 combine, the V4 report's formats applied to h = 5120


def cost(N, b):
    T = N * b
    n = TOPK * T / ROUTED
    touched = ROUTED * (1 - (1 - TOPK / ROUTED) ** T)
    read_mb = touched * EXP_MB
    return dict(T=T, n=n, touched=touched, read_gb=read_mb / 1e3, per_tok=read_mb / T, per_gpu=read_mb / N / 1e3,
                flop_byte=PAIR_FLOP * TOPK * T / (read_mb * 1e6), net_tok=TOPK * (1 - 1 / N) * PAIR_NET)


print(f"   one expert {EXP_MB:.2f} MB; a token-expert pair costs 6 x {HID} x {MID} = {PAIR_FLOP:,} operations (the V4 report's 6hd)")
print(f"   and, when remote, 3 x {HID} = {PAIR_NET:,} bytes on the interconnect")
B_DEC, B_PRE = 60, 4096
print(f"   decode, b = {B_DEC} sequences per GPU (the published operating point), one token each per step:")
print("   EP size   tokens T   tokens per expert   experts touched   weights read   per GPU     per token    operations per byte   network per token")
for N in (1, 4, 8, 16, 32, 64, 128):
    c = cost(N, B_DEC)
    print(f"   {N:<9d} {c['T']:<10d} {c['n']:<19.2f} {c['touched']:<17.1f} {c['read_gb']:6.3f} GB      {c['per_gpu'] * 1e3:8.1f} MB {c['per_tok']:8.2f} MB  "
          f"{c['flop_byte']:<21.1f} {c['net_tok']:,.0f} B")
print(f"   prefill, b = {B_PRE} prompt tokens per GPU in one forward pass (chosen):")
for N in (1, 2, 4, 8):
    c = cost(N, B_PRE)
    print(f"   {N:<9d} {c['T']:<10d} {c['n']:<19.2f} {c['touched']:<17.1f} {c['read_gb']:6.3f} GB      {c['per_gpu'] * 1e3:8.1f} MB {c['per_tok']:8.2f} MB  "
          f"{c['flop_byte']:<21.1f} {c['net_tok']:,.0f} B")
c8, c64, c128, p2, p4, p8 = cost(8, B_DEC), cost(64, B_DEC), cost(128, B_DEC), cost(2, B_PRE), cost(4, B_PRE), cost(8, B_PRE)
print(f"   decode EP8 -> EP64: tokens per expert {c8['n']:g} -> {c64['n']:g}; weights read per token {c8['per_tok']:.2f} -> {c64['per_tok']:.2f} MB, "
      f"a factor of {c8['per_tok'] / c64['per_tok']:.2f}; tokens per GB of weights read {1e3 / c8['per_tok']:.1f} -> {1e3 / c64['per_tok']:.1f}")
print(f"   prefill at EP2 has {p2['n']:g} tokens per expert, more than decode at EP128 ({c128['n']:g}); EP4 {p4['n']:g}, EP8 {p8['n']:g}")
print(f"   one decode step over {LAYERS} layers, per GPU: EP8 reads {c8['per_gpu'] * LAYERS:.2f} GB of expert weights, EP64 {c64['per_gpu'] * LAYERS:.2f} GB;")
print(f"      EP64 puts {B_DEC} x {c64['net_tok']:,.0f} x {LAYERS} = {B_DEC * c64['net_tok'] * LAYERS / 1e6:.1f} MB per GPU on the interconnect")
print(f"   share of pairs that are remote, 1 - 1/N: EP2 {1 - 1 / 2:.3f}, EP4 {1 - 1 / 4:.3f}, EP8 {1 - 1 / 8:.3f}, EP64 {1 - 1 / 64:.3f}")
print(f"   network bytes per prompt token and layer: EP2 {p2['net_tok']:,.0f}, EP8 {p8['net_tok']:,.0f}: EP2 sends {p2['net_tok'] / p8['net_tok'] * 100:.0f} percent of EP8")
print(f"   the V4 report's ratio for V4-Pro, 6hd / 3h = 2d: 2 x 3072 = {2 * 3072}; the same count for V4.1-Flash: 2 x {MID} = {2 * MID} operations per byte sent")
rng = np.random.default_rng(20)
hits = []
for _ in range(2000):
    seen = np.zeros(ROUTED, dtype=bool)
    for _t in range(B_DEC):
        seen[rng.choice(ROUTED, TOPK, replace=False)] = True
    hits.append(seen.sum())
print(f"   check of the 'experts touched' formula by sampling, T = 60: formula {cost(1, B_DEC)['touched']:.1f}, mean of 2,000 draws {np.mean(hits):.1f}")

# ---------------------------------------------------------------- 6. the toy timeline
print("\n6. Toy timeline (all units chosen): decode step 1 unit, the prefill of one long prompt 12 units, arriving at t = 4")
STEP, PRE, ARR, CHUNK, HAND = 1, 12, 4, 3, 1


def shared_whole():
    toks = [t for t in range(1, ARR + 1)]
    first = ARR + PRE + STEP
    toks += list(range(first, first + 4))
    return toks, first


def shared_chunked():
    toks = [t for t in range(1, ARR + 1)]
    t = ARR
    done = 0
    while done < PRE:
        t += CHUNK
        done += CHUNK
        t += STEP
        toks.append(t)
    return toks, t          # the last decode step of the loop is the first that includes the new request


def separate():
    first = ARR + PRE + HAND + STEP
    return list(range(1, first + 4)), first


for name, fn in (("one GPU, prefill runs whole", shared_whole), ("one GPU, prefill in chunks of 3", shared_chunked),
                 ("separate pools, hand-off 1", separate)):
    toks, first = fn()
    gaps = [b - a for a, b in zip([0] + toks[:-1], toks)]
    print(f"   {name:34s} running requests receive tokens at {toks[:10]}{' ...' if len(toks) > 10 else ''}")
    print(f"   {'':34s} longest wait between two tokens {max(gaps)};  new request: first token at {first}, {first - ARR} after it arrived")
print(f"   chunking delays the new request by {shared_chunked()[1] - shared_whole()[1]} units against running the prefill whole; "
      f"separate pools by {separate()[1] - shared_whole()[1]}, the hand-off")

# ---------------------------------------------------------------- 7. availability
print("\n7. Availability (chosen: each GPU fails on a given day with probability 0.001; a restart takes 10 minutes)")
PF, RESTART = 0.001, 10
for N in (2, 4, 8, 16, 32, 64, 128):
    ok = (1 - PF) ** N
    print(f"   EP{N:<4d} no GPU of the instance fails in a day: 0.999^{N} = {ok:.5f};  at least one fails: {1 - ok:.5f};  "
          f"mean days between failures 1 / ({N} x 0.001) = {1 / (N * PF):.1f};  sequences stopped at 60 per GPU: {N * 60:,}")
fails = 64 * PF
for name, size in (("16 instances of EP4", 4), ("1 instance of EP64", 64)):
    lost = fails * size * RESTART
    print(f"   64 GPUs as {name:20s}: {fails:.3f} failures a day, each stops {size} GPUs for 10 minutes: {lost:.2f} GPU-minutes a day, "
          f"{lost / (64 * 1440) * 100:.4f} percent of capacity")
print(f"   ratio of GPUs stopped per failure: {64 // 4}")
print(f"   smallest efficient unit (published): 64 + 64 = {64 + 64} GPUs; at about 14.4 TB of KV storage per GPU (published) "
      f"that is {128 * 14.4:,.1f} TB, {128 * 14.4 / (20 * 30.73):.1f} storage servers of 20 x 30.73 TB before redundancy (our division)")

# ---------------------------------------------------------------- 8. the listing on a second batch
print("\n8. The listing's function on a random batch of 16 positions")


def moe_expert_parallel(Y, experts, home, owner, k=2):
    idx, gate = route(Y, k)                                        # A
    out, crossed = torch.zeros_like(Y), 0
    for e, weights in enumerate(experts):                          # B
        tok, slot = (idx == e).nonzero(as_tuple=True)              # C
        if len(tok) == 0:
            continue
        y_e = swiglu(Y[tok], *weights)                             # D
        out.index_add_(0, tok, gate[tok, slot][:, None] * y_e)     # E
        crossed += 2 * Y.shape[1] * int((home[tok] != owner[e]).sum())   # F
    return out, crossed


o1, c1 = moe_expert_parallel(Y_ep, EXPERTS, HOME, OWNER)
print(f"   on the toy: equal to section 2: {torch.allclose(o1, out, atol=1e-6)}, numbers crossed {c1}")
g2 = torch.Generator().manual_seed(7)
Y2 = torch.randint(-2, 3, (16, 4), generator=g2).float()
home2 = torch.arange(16) // 4
o2, c2 = moe_expert_parallel(Y2, EXPERTS, home2, OWNER)
print(f"   16 random positions, 4 per GPU: equal to the one-GPU MoE: {torch.allclose(o2, moe(Y2), atol=1e-5)}, numbers crossed {c2} "
      f"of at most {2 * 4 * 16 * K}")
