"""Lesson 27 check: the fused MoE kernel, overlapping communication with computation.

What is computed here:
  0. the published facts the chapter quotes (paraphrased, printed so the chapter can be compared line by line);
  1. lesson 20's toy (8 positions, 8 routed experts on 4 GPUs) as counts: pairs and remote pairs per expert and GPU;
  2. a toy clock (all durations chosen) and four schedules of one MoE layer on that toy:
        unfused (three kernels in a row), attempt 1 (work that needs no message runs under dispatch),
        attempt 2 (one expert at a time, three kernels per expert), waves (one kernel, a pipeline over waves);
  3. the pipeline by hand: one GPU with 4 experts in 2 waves, slot by slot; the closed form
        T = r + c + s + (W - 1) x max(r, c, s); the same GPU on a link three times slower;
  4. the number of waves: a GPU with 48 experts, with and without a chosen cost per wave;
  5. the bound 1 / (1 - f), and the f that corresponds to 1.50, 1.73 and 1.96;
  6. the published benchmark (DeepGEMM pull request 316) and what follows from its columns by arithmetic;
  7. kernels started per layer and rows per product at toy and real sizes;
  8. lesson 20's cost model again, with a memory term that falls as 1/N and a chosen term that grows with N;
  9. the listing: the wave pipeline run on lesson 20's real toy matrices (PyTorch; only when this file is executed).

Sources read for section 0, all through narrow questions to a summarizing fetch tool (no file was read line by line):
the DeepSeek-V4 report (arXiv 2606.19348), section 3.1 and the caption of figure 5; the DeepGEMM README, pull request
316, tests/test_mega_moe.py, impls/sm100_fp8_fp4_mega_moe.cuh and scheduler/mega_moe.cuh; the DeepEP README; the
DeepInfer deployment document (doc/inference_deployment_qa.md), section "Kernel implementation"; lessons 20 and 23.

Chosen for easy arithmetic, not taken from any source: the clock (1 tick to read a remote pair, 2 to write one back,
4 to compute a pair, 1 to start a kernel); the by-hand GPU (4 experts, 2 remote pairs each); the link that is three
times slower; the 48-expert GPU's 8 pairs per expert and its cost of 4 ticks per wave; the rates and the cost per
rank of section 8.
Every number in lesson-27-fused-moe-kernel.md is printed here.
Run:  /Users/rajat/.pyenv/shims/python3 lesson27_check.py
"""
import math

# ---------------------------------------------------------------- 0. published facts
FACTS = [
    "V4 REPORT, SECTION 3.1 (arXiv 2606.19348)",
    "Stages: an MoE layer has four stages. Dispatch and Combine are communication bound, Linear-1 and Linear-2 are",
    "      computation bound.",
    "'Our profiling reveals that within a single MoE layer, the total time of communication is less than that of the",
    "      computation.' No ratio and no time is printed. After fusion computation remains the bottleneck, so the",
    "      scheme can 'tolerate lower interconnect bandwidth without degrading end-to-end performance'.",
    "The scheme 'fuses communication and computation into a single pipelined kernel'. 'we split and schedule the",
    "      experts into waves. Each wave consists of a small portion of experts.' 'As soon as all experts within the",
    "      wave have completed their communication, computation can commence immediately without waiting for other",
    "      experts.' 'In steady state, computation of current wave, token transfer for the next wave, and result",
    "      sending of completed experts all proceed concurrently.' It calls this a fine-grained pipeline among experts.",
    "NOT stated in the report: how many experts a wave holds, how many waves there are, how waves are formed, which",
    "      threads do what, how arrival is detected.",
    "Figure 5 caption: Comet (Zhang et al., 2025b) 'overlaps Dispatch with Linear-1, and Linear-2 with Combine,",
    "      separately'; 'Our EP scheme achieves a finer-grained overlapping by splitting and scheduling experts into",
    "      waves'; 'The theoretical speedup is evaluated in the configuration of the DeepSeek-V4-Flash architecture.'",
    "      The values in the figure are not in the text.",
    "Performance: 'Compared against strong non-fused baselines, it achieves 1.50~1.73x speedup for general inference",
    "      workloads, and up to 1.96x for latency-sensitive scenarios' such as RL rollouts and high-speed agent",
    "      serving. Validated on NVIDIA GPUs and Huawei Ascend NPUs. The report gives no EP size, batch size or model",
    "      for these numbers and does not name the baselines. Open-sourced as a CUDA mega-kernel, MegaMoE, in DeepGEMM.",
    "Observations and proposals, four bullets:",
    "   Computation-Communication Ratio: communication is fully hidden when C/B <= V_comp/V_comm (C peak compute, B",
    "      interconnect bandwidth, V the volumes). For V4-Pro a token-expert pair needs 6hd FLOPs (SwiGLU gate, up and",
    "      down projections) and 3h bytes (FP8 Dispatch + BF16 Combine): C/B <= 2d = 6144 FLOPs/Byte; 'each GBps of",
    "      interconnect bandwidth suffices to hide the communication for 6.1 TFLOP/s of compute'. Beyond the threshold",
    "      more bandwidth has diminishing returns. 'We encourage future hardware designs to target such balance",
    "      points rather than scale bandwidth unconditionally.'",
    "   Power Budget: 'Extreme kernel fusion drives compute, memory, and network to high load simultaneously', 'making",
    "      power throttling a key performance limiter'. Proposal: sufficient power headroom for such fully concurrent",
    "      workloads.",
    "   Communication Primitives: 'we adopt a pull-based approach where each GPU actively reads activations from",
    "      remote GPUs', which avoids 'the high notification latency that fine-grained push entails'. 'lower-latency",
    "      cross-GPU signaling would make push viable' and allow more natural communication patterns. Whether Combine",
    "      is pull or push is not stated in the report.",
    "   Activation Function: 'We propose replacing SwiGLU with a low-cost element-wise activation' with no exponential",
    "      or division, to reduce post-GEMM overhead, 'preventing the GEMM pipeline from being stalled by activation",
    "      function computation'. Nothing about removing a projection or changing the intermediate size.",
    "Section 3.1 does not use the words NVLink, symmetric memory, scale-up, RDMA or tensor core.",
    "",
    "DEEPGEMM (README, pull request 316, test and source files)",
    "README: 'Mega MoE fuses and overlaps EP dispatch, linear 1 and linear 2 (FP8xFP4 or FP8xFP8), SwiGLU, and EP",
    "      combine into a single mega-kernel, overlapping NVLink communication and tensor core computation.' 'It",
    "      requires multi-process launch with symmetric memory.' PyTorch 2.9 or later.",
    "Interface: get_symm_buffer_for_mega_moe(group, num_experts, num_max_tokens_per_rank, num_topk, hidden,",
    "      intermediate_hidden, mma_type='fp8xfp4'); transform_weights_for_mega_moe(l1_weights, l2_weights); the caller",
    "      copies x, x_sf, topk_idx and topk_weights into the buffer ('You may fuse these into previous kernels');",
    "      fp8_fp4_mega_moe(y, transformed_l1, transformed_l2, buffer) writes a BF16 output y.",
    "Hardware: the library requires an SM90 or SM100 GPU; the mega MoE source files are sm100_fp8_fp4_mega_moe.cuh and",
    "      sm100_bf16_mega_moe.cuh. We saw no SM90 mega MoE file. The README gives no benchmark number and points to",
    "      pull request 316. Released 2026.04.16.",
    "Pull request 316: 'We benchmarked Mega MoE on DeepSeek-V4-Flash and DeepSeek-V4-Pro under 8-way expert parallelism",
    "      (EP8)', at batch sizes that are 'the number of tokens per rank'; 'All values are averaged across 8 ranks.'",
    "      V4-Flash: 256 experts, top-6, hidden 4096, intermediate 2048. V4-Pro: 384 experts, top-6, hidden 7168,",
    "      intermediate 3072. Two tables (section 6 below). 'legacy' is not defined on the page; the GPU model is not",
    "      named.",
    "tests/test_mega_moe.py: the baseline it times is DeepEP dispatch, an L1 grouped GEMM, SwiGLU, an L2 grouped GEMM",
    "      and DeepEP combine, five steps. Defaults: 8 processes, 8192 tokens per rank, 384 experts, top-6, hidden",
    "      7168, intermediate 3072, 1 shared expert. Comment: '# NVLink bytes: dispatch pull + combine write-back',",
    "      num_nvlink_bytes = num_recv_tokens * hidden * 3. FLOPs: 2 * tokens * hidden * intermediate * 3 for the",
    "      routed experts. Comment: '# Combine reduction (serial) time approximation'.",
    "impls/sm100_fp8_fp4_mega_moe.cuh (comments): 'Dispatch warps'; 'Barrier before pulling'; 'Pull token data and SF",
    "      from remote ranks into local L1 buffer'; 'GEMM TMA load warp for tokens with SFA'; 'GEMM TMA load warp for",
    "      weights with SF'; 'GEMM MMA issue warp (only the leader CTA will run)'; 'GEMM epilogue warps'; 'Unified L1",
    "      epilogue: SwiGLU in-place'; 'L2 BF16 epilogue: write GEMM output to remote combine buffer via NVLink';",
    "      'Combine: reduce top-k results and write back', which first waits 'for the ranks of the selected experts",
    "      to finish their L2 writes'. A compute task waits for 'the entire token arrival' of its block by reading a",
    "      counter that the dispatch warps increment. The word wave does not appear in this file.",
    "scheduler/mega_moe.cuh: tasks are blocks of token rows (phases Linear1, Linear2, SharedLinear1, SharedLinear2),",
    "      laid out in expert-index order. 'all CTA-pair schedulers together form one global wave'; the number of L1",
    "      waves is ceil(L1 tasks / (kNumSMs / 2)). The scheduler issues some warm-up waves of L1 tasks ('to ensure no",
    "      L1 -> L2 deadlock'), then about one L1 task per L2 task. No constant for experts per wave exists.",
    "",
    "DEEPEP README",
    "'high-throughput and low-latency expert-parallel (EP) all-to-all GPU kernels for MoE dispatch and combine'; one",
    "      EPBuffer interface for training, prefill and decode. NVLink inside a node, RDMA between nodes. 'For",
    "      communication-computation overlap, launch communication first and wait at the point where the expert",
    "      computation needs its results'; the example marks 'independent computation' between the launch and the",
    "      wait, and the expert GEMMs run between the dispatch wait and the combine launch. 'EP dispatch and combine",
    "      require GPU SMs'. The current README has no 'normal' and 'low-latency' kernels, no receive hook, and no",
    "      mention of Mega MoE.",
    "",
    "DEEPINFER DEPLOYMENT DOCUMENT, 'Kernel implementation'",
    "'Mega MoE is the general solution within a scale-up domain: regardless of EP size or batch size, Mega MoE is",
    "      significantly faster than unfused MoE.' No number.",
    "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.' 'Different jobs sharing NVLink within a supernode can interfere with one another",
    "      and slow down. Using the whole supernode for a single EP group avoids that interference.'",
    "Internal and public kernel libraries are 'broadly the same; the indexer and mega series differ somewhat';",
    "      end to end 'at most 5% apart'. Scale-up domain and supernode are not defined.",
]

# ---------------------------------------------------------------- 1. lesson 20's toy, as counts
ROUTE = [(6, 8), (7, 2), (1, 6), (3, 2), (7, 1), (1, 4), (1, 4), (1, 4)]   # experts of p1 .. p8 (lesson 20, section 5)
TOKENS = ["The", "next", "day", "is", "bright", "and", "sunny", "and"]
NGPU, NEXP = 4, 8
HOME = [p // 2 for p in range(8)]                                          # two positions per GPU
OWNER = {e: (e - 1) // 2 for e in range(1, NEXP + 1)}                      # E1, E2 on G0; E3, E4 on G1; ...
TOK = {e: [p for p in range(8) if e in ROUTE[p]] for e in range(1, NEXP + 1)}
PAIRS = {e: len(TOK[e]) for e in TOK}
REMOTE = {e: sum(HOME[p] != OWNER[e] for p in TOK[e]) for e in TOK}
ON_GPU = {g: [e for e in range(1, NEXP + 1) if OWNER[e] == g] for g in range(NGPU)}
GPU_PAIRS = [sum(PAIRS[e] for e in ON_GPU[g]) for g in range(NGPU)]
GPU_REMOTE = [sum(REMOTE[e] for e in ON_GPU[g]) for g in range(NGPU)]

# ---------------------------------------------------------------- 2. the clock and the four schedules
A_READ, B_WRITE, C_PAIR, L_START = 1, 2, 4, 1                              # ticks; all chosen


def staged(groups, a=A_READ, b=B_WRITE, c=C_PAIR, start=L_START):
    """Separate kernels on one GPU. groups: (label, pairs, remote pairs), handled in order. Every group has its
    own read kernel, product kernel and write kernel, and each kernel pays `start` before it works. Reads queue on
    the incoming link, products on the cores, writes on the outgoing link. Returns (events, end time)."""
    t_in = t_core = t_out = 0
    ev = []
    for label, n, rem in groups:
        if n == 0:
            continue
        arrived = 0
        if rem:
            ev += [("in", t_in, t_in + start, "start", label), ("in", t_in + start, t_in + start + a * rem, "read", label)]
            t_in += start + a * rem
            arrived = t_in
        s0 = max(arrived, t_core)
        ev += [("core", s0, s0 + start, "start", label), ("core", s0 + start, s0 + start + c * n, "compute", label)]
        t_core = s0 + start + c * n
        if rem:
            s1 = max(t_core, t_out)
            ev += [("out", s1, s1 + start, "start", label), ("out", s1 + start, s1 + start + b * rem, "write", label)]
            t_out = s1 + start + b * rem
    return ev, max(t_core, t_out)


class ToyGPU:
    """One GPU with an incoming link, cores and an outgoing link, each doing one thing at a time. The methods are
    the ones the listing calls. Without `payload` only the clock moves; with it, real toy tensors are computed."""

    def __init__(self, experts, a=A_READ, b=B_WRITE, c=C_PAIR, start=L_START, sync=0, payload=None):
        self.experts = experts                      # {expert: (pairs, remote pairs)}
        self.a, self.b, self.c, self.sync = a, b, c, sync
        self.now = self.t_in = self.t_out = start
        self.arrive, self.payload = {}, payload
        self.ev = [("core", 0, start, "start", "kernel")] if start else []

    def _cnt(self, wave, k):
        return sum(self.experts[e][k] for e in wave)

    def pull(self, wave):                           # start reading the wave's remote tokens; does not wait
        rem = self._cnt(wave, 1)
        t0 = max(self.now, self.t_in)
        self.t_in = t0 + self.a * rem
        self.arrive[tuple(wave)] = self.t_in
        if rem:
            self.ev.append(("in", t0, self.t_in, "read", wave))

    def wait_arrived(self, wave):                   # the cores wait here until every token of the wave is local
        self.now = max(self.now, self.arrive[tuple(wave)]) + self.sync
        return self.payload.fetch(wave) if self.payload else None

    def run_experts(self, wave, x):                 # the two products and SwiGLU for every expert of the wave
        n = self._cnt(wave, 0)
        self.ev.append(("core", self.now, self.now + self.c * n, "compute", wave))
        self.now += self.c * n
        return self.payload.compute(wave, x) if self.payload else None

    def write_back(self, wave, y):                  # start writing the outputs to the home GPUs; does not wait
        rem = self._cnt(wave, 1)
        t0 = max(self.now, self.t_out)
        self.t_out = t0 + self.b * rem
        if rem:
            self.ev.append(("out", t0, self.t_out, "write", wave))
        if self.payload:
            self.payload.deliver(wave, y)

    def wait_written(self):
        self.now = max(self.now, self.t_out)
        return self.now


def fused_moe_layer(gpu, waves):
    """The wave pipeline on one GPU. A sketch of the idea, not DeepGEMM's code."""
    gpu.pull(waves[0])                                                    #A
    for w, wave in enumerate(waves):
        x = gpu.wait_arrived(wave)                                        #B
        if w + 1 < len(waves):
            gpu.pull(waves[w + 1])                                        #C
        y = gpu.run_experts(wave, x)                                      #D
        gpu.write_back(wave, y)                                           #E
    return gpu.wait_written()                                             #F


def toy_experts(g):
    return {e: (PAIRS[e], REMOTE[e]) for e in ON_GPU[g] if PAIRS[e]}


def schedule(name, g):
    """Events and end time of GPU g under one of the four schedules."""
    ex = toy_experts(g)
    n, rem = GPU_PAIRS[g], GPU_REMOTE[g]
    if name == "unfused":
        return staged([("all", n, rem)])
    if name == "attempt 1":                                               # local pairs need no message
        return staged([("local", n - rem, 0), ("remote", rem, rem)])
    if name == "attempt 2":                                               # one expert at a time
        return staged([(f"E{e}", *ex[e]) for e in ex])
    gpu = ToyGPU(ex)
    end = fused_moe_layer(gpu, [[e] for e in ex])                         # waves: one expert each on the toy
    return gpu.ev, end


NAMES = ["unfused", "attempt 1", "attempt 2", "waves"]
RUNS = {nm: [schedule(nm, g) for g in range(NGPU)] for nm in NAMES}
ENDS = {nm: [r[1] for r in RUNS[nm]] for nm in NAMES}
LAYER = {nm: max(ENDS[nm]) for nm in NAMES}
KERNELS = {nm: [sum(1 for e in r[0] if e[3] == "start") for r in RUNS[nm]] for nm in NAMES}


def busy(ev, lane, kinds):
    return sum(t1 - t0 for (ln, t0, t1, k, _) in ev if ln == lane and k in kinds)


def fused_time(experts, waves, **kw):
    gpu = ToyGPU(experts, **kw)
    return fused_moe_layer(gpu, waves), gpu


G0 = toy_experts(0)
T_G0_REV, _ = fused_time(G0, [[2], [1]])                                  # E2 first, then E1
T_G0_ONE, _ = fused_time(G0, [[1, 2]])                                    # one wave: nothing overlaps
G0_COMM = A_READ * GPU_REMOTE[0] + B_WRITE * GPU_REMOTE[0]
G0_COMP = C_PAIR * GPU_PAIRS[0]
G0_F = G0_COMM / (G0_COMM + G0_COMP)

# ---------------------------------------------------------------- 3. the pipeline by hand


def pipeline(r, c, s, W):
    """W equal waves with stage times r (read), c (compute), s (write): the first wave takes the sum of the
    stages, every further wave the slowest stage."""
    return r + c + s + (W - 1) * max(r, c, s)


HAND = {i: (2, 2) for i in range(1, 5)}                                   # 4 experts, 2 pairs each, all remote; chosen
HAND_W2 = [[1, 2], [3, 4]]
T_HAND, GPU_HAND = fused_time(HAND, HAND_W2, start=0)
T_HAND4, GPU_HAND4 = fused_time(HAND, [[1], [2], [3], [4]], start=0)
HAND_R, HAND_C, HAND_S = A_READ * 4, C_PAIR * 4, B_WRITE * 4              # per wave of two experts
HAND_UNFUSED = 2 * (HAND_R + HAND_C + HAND_S)
SLOW = 3                                                                  # the link three times slower; chosen
T_SLOW, GPU_SLOW = fused_time(HAND, HAND_W2, a=SLOW * A_READ, b=SLOW * B_WRITE, start=0)
SLOW_UNFUSED = 2 * (SLOW * HAND_R + HAND_C + SLOW * HAND_S)

# ---------------------------------------------------------------- 4. how many waves
BIG_E, BIG_M, BIG_RHO = 48, 8, 7 / 8                                      # V4-Pro at EP8 holds 48 experts per GPU; 8 pairs each (chosen); 7 of 8 remote
BIG_R = A_READ * BIG_E * BIG_M * BIG_RHO
BIG_C = C_PAIR * BIG_E * BIG_M
BIG_S = B_WRITE * BIG_E * BIG_M * BIG_RHO
BIG_UNFUSED = BIG_R + BIG_C + BIG_S
BIG_F = (BIG_R + BIG_S) / BIG_UNFUSED
SIGMA = 4                                                                 # ticks per wave, chosen: the time of one pair
WAVES = [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]


def big_time(W, sigma=0.0):
    return pipeline(BIG_R / W, BIG_C / W + sigma, BIG_S / W, W)


BEST_W = min(WAVES, key=lambda W: big_time(W, SIGMA))

# ---------------------------------------------------------------- 5. the bound


def bound(f):
    return 1 / (1 - f)


def f_of(speedup):
    return 1 - 1 / speedup


# ---------------------------------------------------------------- 6. the published benchmark (pull request 316)
# batch (tokens per rank), time (us), compute (TFLOPS), global memory (GB/s), interconnect (GB/s), speedup vs legacy
BENCH = {
    "V4-Flash": dict(experts=256, hidden=4096, mid=2048, rows=[
        (1, 56.5, 5, 1311, 1, 1.96), (512, 146.5, 1056, 3192, 266, 1.73),
        (8192, 1283.1, 1928, 998, 499, 1.56), (32768, 4855.5, 2038, 794, 529, 1.62)]),
    "V4-Pro": dict(experts=384, hidden=7168, mid=3072, rows=[
        (1, 108.1, 7, 1758, 1, 1.61), (512, 369.6, 1098, 4619, 182, 1.54),
        (8192, 2818.5, 2304, 1094, 393, 1.50), (32768, 10655.2, 2438, 692, 417, 1.54)]),
}
EP_BENCH, TOPK, FP4 = 8, 6, 0.53125


def bench_derived(model, row):
    cfg = BENCH[model]
    b, t, tf, mem, nvl, sp = row
    h, d = cfg["hidden"], cfg["mid"]
    return dict(legacy=t * sp, saved=t * (sp - 1), f=f_of(sp), rows_per_expert=b * TOPK / (cfg["experts"] / EP_BENCH),
                flops=2 * b * TOPK * h * d * 3, flops_meas=tf * 1e12 * t * 1e-6,
                bytes_net=b * TOPK * h * 3, bytes_net_meas=nvl * 1e9 * t * 1e-6,
                mem_gb=mem * t * 1e-6, flop_per_byte=tf * 1e3 / nvl if nvl > 1 else float("nan"), two_d=2 * d,
                weights_gb=(cfg["experts"] / EP_BENCH) * 3 * h * d * FP4 / 1e9)


# ---------------------------------------------------------------- 8. lesson 20's cost model with a rising term
HID, MID, ROUTED, B_DEC = 5120, 2304, 384, 60                             # V4.1-Flash, 60 sequences per rank (lesson 20)
EXP_MB = 3 * HID * MID * FP4 / 1e6
PAIR_FLOP, PAIR_NET = 6 * HID * MID, 3 * HID
MEM_RATE, CPU_RATE, RANK_US = 4000.0, 2000.0, 1.0                         # GB/s, TFLOP/s, microseconds per rank; chosen


def cost(N, b=B_DEC, rank_us=RANK_US):
    T = N * b
    touched = ROUTED * (1 - (1 - TOPK / ROUTED) ** T)
    read_mb = touched * EXP_MB
    mem_us = read_mb / N / MEM_RATE * 1e3                                 # MB / (GB/s) = ms; x 1000 = us
    comp_us = b * TOPK * PAIR_FLOP / (CPU_RATE * 1e12) * 1e6
    return dict(T=T, per_tok=read_mb / T, per_gpu=read_mb / N, mem_us=mem_us, comp_us=comp_us, rank=rank_us * N,
                layer=max(mem_us, comp_us) + rank_us * N, net_tok=TOPK * (1 - 1 / N) * PAIR_NET)


EPS = [8, 16, 32, 64, 128]


def fmt(v, d=4):
    s = f"{v:.{d}f}".rstrip("0").rstrip(".")
    return s if s else "0"


def lane_text(ev, lane):
    out = []
    for (ln, t0, t1, k, lab) in sorted(ev, key=lambda e: e[1]):
        if ln == lane:
            name = lab if isinstance(lab, str) else "+".join(f"E{e}" for e in lab)
            out.append(f"{k} {name} [{fmt(t0)}, {fmt(t1)}]")
    return "; ".join(out) if out else "idle"


if __name__ == "__main__":
    print("0. Published facts used in the chapter (paraphrased)")
    for f in FACTS:
        print("   " + f)

    print("\n1. Lesson 20's toy as counts")
    for p in range(8):
        es = ROUTE[p]
        print(f"   p{p + 1} {TOKENS[p]:7s} home G{HOME[p]}   E{es[0]} on G{OWNER[es[0]]}, E{es[1]} on G{OWNER[es[1]]}")
    print(f"   pairs per expert, E1 to E8:        {[PAIRS[e] for e in range(1, 9)]}")
    print(f"   remote pairs per expert, E1 to E8: {[REMOTE[e] for e in range(1, 9)]}")
    print(f"   pairs per GPU {GPU_PAIRS}; remote pairs received per GPU {GPU_REMOTE}; local {[n - r for n, r in zip(GPU_PAIRS, GPU_REMOTE)]}")
    print(f"   total pairs {sum(GPU_PAIRS)}, remote {sum(GPU_REMOTE)}, local {sum(GPU_PAIRS) - sum(GPU_REMOTE)}")
    assert GPU_PAIRS == [7, 4, 2, 3] and sum(GPU_REMOTE) == 14

    print("\n2. The clock (chosen): read one remote pair", A_READ, "tick; write one back", B_WRITE, "ticks; compute one pair", C_PAIR,
          "ticks; start one kernel", L_START, "tick")
    print(f"   one remote pair: {A_READ + B_WRITE} ticks on the link against {C_PAIR} on the cores")
    for nm in NAMES:
        print(f"\n   {nm}: end per GPU {[fmt(v) for v in ENDS[nm]]}, layer time {fmt(LAYER[nm])}, kernels started per GPU {KERNELS[nm]}, "
              f"speedup over unfused {LAYER['unfused'] / LAYER[nm]:.4f}")
        for g in range(NGPU):
            ev = RUNS[nm][g][0]
            print(f"      G{g}  link in : {lane_text(ev, 'in')}")
            print(f"          cores   : {lane_text(ev, 'core')}")
            print(f"          link out: {lane_text(ev, 'out')}")
    T0 = LAYER["unfused"]
    print(f"\n   unfused, G0: {L_START} + {A_READ * GPU_REMOTE[0]} + {L_START} + {C_PAIR * GPU_PAIRS[0]} + {L_START} + {B_WRITE * GPU_REMOTE[0]} = {fmt(ENDS['unfused'][0])}")
    for g in range(NGPU):
        ev = RUNS["unfused"][g][0]
        cb = busy(ev, "core", ("compute",))
        print(f"   unfused, G{g}: cores compute {fmt(cb)} of {fmt(T0)} ticks ({cb / T0 * 100:.1f} percent); link in reads {fmt(busy(ev, 'in', ('read',)))}; "
              f"link out writes {fmt(busy(ev, 'out', ('write',)))}; finished at {fmt(ENDS['unfused'][g])}, then waits {fmt(T0 - ENDS['unfused'][g])}")
    tot_core = sum(busy(RUNS["unfused"][g][0], "core", ("compute",)) for g in range(NGPU))
    print(f"   unfused, all four GPUs: cores compute {fmt(tot_core)} of {NGPU} x {fmt(T0)} = {fmt(NGPU * T0)} GPU-ticks, {tot_core / (NGPU * T0) * 100:.1f} percent")
    print(f"   G0 while its cores compute ({C_PAIR * GPU_PAIRS[0]} ticks) both links are idle; while it reads and writes "
          f"({G0_COMM} ticks) its cores are idle")
    print(f"   attempt 1 gains {fmt(T0 - LAYER['attempt 1'])} ticks: G0's one local pair ({C_PAIR} ticks) is computed while dispatch runs")
    print(f"   attempt 2 gains {fmt(T0 - LAYER['attempt 2'])} ticks over unfused; G0 starts {KERNELS['attempt 2'][0]} kernels where unfused starts {KERNELS['unfused'][0]}")
    print(f"   waves gain {fmt(T0 - LAYER['waves'])} ticks over unfused with {KERNELS['waves'][0]} kernel per GPU")
    print(f"   G0 with the two waves in the other order (E2, then E1): {fmt(T_G0_REV)}; with both experts in one wave: {fmt(T_G0_ONE)}")
    print(f"   G0: communication {G0_COMM} ticks, compute {G0_COMP}; f = {G0_COMM} / {G0_COMM + G0_COMP} = {G0_F:.4f}; if all of it were hidden: "
          f"{L_START} + {G0_COMP} = {L_START + G0_COMP} ticks, {T0 / (L_START + G0_COMP):.4f} times faster than unfused")
    print(f"   what stays exposed on G0 under waves: the first read ({A_READ * REMOTE[1]}), and after the last product "
          f"{fmt(LAYER['waves'] - L_START - A_READ * REMOTE[1] - G0_COMP)} ticks of writing")

    print("\n3. The pipeline by hand: 4 experts, 2 remote pairs each, 2 waves of 2 experts")
    print(f"   per wave: read r = {HAND_R}, compute c = {HAND_C}, write s = {HAND_S}; unfused {HAND_UNFUSED}")
    for lane in ("in", "core", "out"):
        print(f"      {lane:5s}: {lane_text(GPU_HAND.ev, lane)}")
    print(f"   layer time {fmt(T_HAND)}; closed form {HAND_R} + {HAND_C} + {HAND_S} + (2 - 1) x {max(HAND_R, HAND_C, HAND_S)} = {pipeline(HAND_R, HAND_C, HAND_S, 2)}; "
          f"speedup {HAND_UNFUSED / T_HAND:.4f}")
    assert T_HAND == pipeline(HAND_R, HAND_C, HAND_S, 2)
    print(f"   4 waves of one expert: {fmt(T_HAND4)} (closed form {pipeline(HAND_R // 2, HAND_C // 2, HAND_S // 2, 4)}), speedup {HAND_UNFUSED / T_HAND4:.4f}; "
          f"compute alone {2 * HAND_C}, bound {HAND_UNFUSED / (2 * HAND_C):.4f}")
    assert T_HAND4 == pipeline(HAND_R // 2, HAND_C // 2, HAND_S // 2, 4)
    print(f"   hidden when r <= c and s <= c: {HAND_R} <= {HAND_C} and {HAND_S} <= {HAND_C}")
    print(f"   link {SLOW} times slower: r = {SLOW * HAND_R}, s = {SLOW * HAND_S}, c = {HAND_C}; unfused {SLOW_UNFUSED}")
    for lane in ("in", "core", "out"):
        print(f"      {lane:5s}: {lane_text(GPU_SLOW.ev, lane)}")
    print(f"   layer time {fmt(T_SLOW)}; closed form {pipeline(SLOW * HAND_R, HAND_C, SLOW * HAND_S, 2)}; speedup {SLOW_UNFUSED / T_SLOW:.4f}; "
          f"each further wave costs max(r, c, s) = {max(SLOW * HAND_R, HAND_C, SLOW * HAND_S)} where c is {HAND_C}")
    assert T_SLOW == pipeline(SLOW * HAND_R, HAND_C, SLOW * HAND_S, 2)

    print(f"\n4. How many waves: {BIG_E} experts on one GPU (V4-Pro at EP8), {BIG_M} pairs each (chosen), {BIG_RHO:g} remote")
    print(f"   R = {fmt(BIG_R)}, C = {fmt(BIG_C)}, S = {fmt(BIG_S)}; unfused {fmt(BIG_UNFUSED)}; f = {BIG_F:.4f}; bound {bound(BIG_F):.4f}")
    print(f"   cost per wave (chosen) {SIGMA} ticks")
    print("   waves   experts per wave   time, no cost per wave   speedup   time with cost   speedup")
    for W in WAVES:
        t0, t1 = big_time(W), big_time(W, SIGMA)
        print(f"   {W:<7d} {BIG_E // W:<18d} {t0:<24.1f} {BIG_UNFUSED / t0:<9.4f} {t1:<16.1f} {BIG_UNFUSED / t1:.4f}")
        assert abs(t0 - (BIG_C + (BIG_R + BIG_S) / W)) < 1e-9
    print(f"   with a cost per wave the best of these is {BEST_W} waves of {BIG_E // BEST_W} experts; "
          f"sqrt((R + S) / cost) = {math.sqrt((BIG_R + BIG_S) / SIGMA):.2f}")
    tb, gb = fused_time({i: (BIG_M, BIG_M * BIG_RHO) for i in range(BIG_E)}, [list(range(i, i + 3)) for i in range(0, BIG_E, 3)], start=0)
    print(f"   cross-check with the listing, 16 waves of 3, no cost per wave: {fmt(tb)} against {fmt(big_time(16))}")
    assert abs(tb - big_time(16)) < 1e-9

    print("\n5. The bound: communication is a share f of the unfused layer; all of it hidden leaves 1 - f; speedup 1 / (1 - f)")
    for f in (0.1, 0.25, 1 / 3, 0.4, 0.5):
        print(f"   f = {f:.4f}: {bound(f):.4f}")
    for sp in (1.50, 1.73, 1.96, 2.00):
        print(f"   speedup {sp:.2f}: f = 1 - 1 / {sp:.2f} = {f_of(sp):.4f}; communication / compute = f / (1 - f) = {f_of(sp) / (1 - f_of(sp)):.4f}")
    print("   the report states only that communication takes less time than computation: f < 0.5, so the bound is below 2")
    print(f"   toy: G0 f = {G0_F:.4f} -> {bound(G0_F):.4f}; by-hand GPU f = {(2 * (HAND_R + HAND_S)) / HAND_UNFUSED:.4f} -> {bound(2 * (HAND_R + HAND_S) / HAND_UNFUSED):.4f}")

    print("\n6. The published benchmark: DeepGEMM pull request 316, EP8, values averaged across 8 ranks")
    for model, cfg in BENCH.items():
        per_rank = cfg["experts"] // EP_BENCH
        print(f"   {model}: {cfg['experts']} experts, top-{TOPK}, hidden {cfg['hidden']}, intermediate {cfg['mid']}; {per_rank} experts per rank; 2d = {2 * cfg['mid']}")
        print("   batch    time us    TFLOPS   memory GB/s   interconnect GB/s   speedup |  legacy us   saved us   f if all overlap   rows per expert   "
              "FLOPs/byte   6hd x pairs / (TFLOPS x time)   GB read from memory")
        for row in cfg["rows"]:
            dv = bench_derived(model, row)
            print(f"   {row[0]:<8d} {row[1]:<10.1f} {row[2]:<8d} {row[3]:<13d} {row[4]:<19d} {row[5]:<7.2f} |  {dv['legacy']:<10.1f} {dv['saved']:<10.1f} "
                  f"{dv['f']:<18.4f} {dv['rows_per_expert']:<17.3f} {dv['flop_per_byte']:<12.0f} {dv['flops'] / dv['flops_meas']:<31.4f} {dv['mem_gb']:.3f}")
        print(f"      weights of the {per_rank} experts of one rank in FP4: {bench_derived(model, cfg['rows'][0])['weights_gb']:.3f} GB")
        sps = [r[5] for r in cfg["rows"]]
        print(f"      smallest {min(sps):.2f} at batch {cfg['rows'][sps.index(min(sps))][0]}, largest {max(sps):.2f} at batch {cfg['rows'][sps.index(max(sps))][0]}")
    allrows = [(m, r) for m, c in BENCH.items() for r in c["rows"]]
    gen = [r[5] for m, r in allrows if r[0] > 1]
    print(f"   batches of 512 and more, both models: {min(gen):.2f} to {max(gen):.2f}; batch 1: {[r[5] for m, r in allrows if r[0] == 1]}")
    pro = BENCH["V4-Pro"]["rows"]
    print(f"   V4-Pro, peak compute {pro[3][2]} TFLOPS: bandwidth that hides it = {pro[3][2]} / 6.144 = {pro[3][2] / 6.144:.0f} GB/s "
          f"(the report's 6.1 TFLOP/s per GB/s: {6144 * 1e9 / 1e12:.3f})")
    fl = BENCH["V4-Flash"]["rows"]
    print(f"   memory rate at batch 1 against batch 512: V4-Flash {fl[0][3]} and {fl[1][3]} GB/s ({fl[1][3] / fl[0][3]:.2f} times), "
          f"V4-Pro {pro[0][3]} and {pro[1][3]} GB/s ({pro[1][3] / pro[0][3]:.2f} times)")

    print("\n7. Kernels and rows")
    print(f"   baseline timed by tests/test_mega_moe.py: 5 steps (dispatch, L1 GEMM, SwiGLU, L2 GEMM, combine); Mega MoE: 1 kernel")
    print(f"   toy: unfused {KERNELS['unfused'][0]} kernels on G0, attempt 2 {KERNELS['attempt 2'][0]} (3 per expert), waves {KERNELS['waves'][0]}")
    for label, experts, N, b in (("V4-Pro, EP8, 8,192 tokens per rank", 384, 8, 8192), ("V4-Pro, EP8, 512 tokens per rank", 384, 8, 512),
                                 ("V4.1-Flash decode, EP8, 60 per rank", 384, 8, 60), ("V4.1-Flash decode, EP64, 60 per rank", 384, 64, 60)):
        per = experts // N
        print(f"   {label}: {per} experts per GPU and layer, {b * TOPK / per:g} rows per expert; one expert at a time = {3 * per} kernels per layer")

    print("\n8. Lesson 20's cost model with a term that grows with the group (decode, 60 sequences per rank, V4.1-Flash sizes)")
    print(f"   chosen: memory {MEM_RATE:g} GB/s, compute {CPU_RATE:g} TFLOP/s, {RANK_US:g} microsecond per rank of communication and synchronization")
    print("   EP     weights read per token   per GPU      memory us   compute us   per-rank us   layer us   tokens per GPU-second of this layer")
    prev = None
    for N in EPS:
        c = cost(N)
        print(f"   {N:<6d} {c['per_tok']:<24.2f} {c['per_gpu']:<8.1f} MB  {c['mem_us']:<11.1f} {c['comp_us']:<12.1f} {c['rank']:<13.1f} {c['layer']:<10.1f} {B_DEC / c['layer'] * 1e6:,.0f}")
        if prev:
            print(f"          doubling from EP{N // 2}: memory saves {prev['mem_us'] - c['mem_us']:.1f} us, the per-rank term adds {c['rank'] - prev['rank']:.1f} us")
        prev = c
    print("   with 0.5 microsecond per rank instead: " + ", ".join(f"EP{N} {cost(N, rank_us=0.5)['layer']:.1f}" for N in EPS))
    print(f"   network bytes per token and layer: " + ", ".join(f"EP{N} {cost(N)['net_tok']:,.0f}" for N in EPS))

    print("\n9. The listing on lesson 20's matrices")
    import contextlib
    import io
    import torch
    with contextlib.redirect_stdout(io.StringIO()):
        import lesson20_check as L20
    assert [tuple(sorted(int(v) + 1 for v in L20.idx[p])) for p in range(8)] == [tuple(sorted(r)) for r in ROUTE]

    class Payload:
        """Real tensors for the listing: fetch = the dispatched rows, compute = SwiGLU experts, deliver = combine."""

        def __init__(self, out):
            self.out = out

        def fetch(self, wave):
            return {e: L20.Y_ep[(L20.idx == e - 1).nonzero(as_tuple=True)[0]] for e in wave}

        def compute(self, wave, x):
            return {e: L20.swiglu(x[e], *L20.EXPERTS[e - 1]) for e in wave}

        def deliver(self, wave, y):
            for e in wave:
                tok, slot = (L20.idx == e - 1).nonzero(as_tuple=True)
                self.out.index_add_(0, tok, L20.gate[tok, slot][:, None] * y[e])

    out = torch.zeros(8, 4)
    ends = []
    for g in range(NGPU):
        gpu = ToyGPU(toy_experts(g), payload=Payload(out))
        ends.append(fused_moe_layer(gpu, [[e] for e in toy_experts(g)]))
    ref = L20.moe(L20.Y_ep)
    print(f"   end per GPU {[fmt(v) for v in ends]}, layer time {fmt(max(ends))}")
    print(f"   output equal to lesson 20's layer on one GPU: {torch.allclose(out, ref, atol=1e-5)}; largest difference {float((out - ref).abs().max()):.2e}")
    print(f"   'bright' (p5), combined expert output: {[round(v, 4) for v in out[4].tolist()]}")
    assert max(ends) == LAYER["waves"] and torch.allclose(out, ref, atol=1e-5)
