每日练习与编程练习

我会把任务拆成两个时间尺度：离线编译期做 kernel/tile 候选集生成与代价建模，在线运行期做带截止时间约束的请求调度、KV 内存管理和 admission control。

1. 离线代价建模 对 prefill 和 decode 分别生成一组候选 kernel。每个候选 k 记录： - mem_sram(k, B, T)：片上 SRAM 占用； - mem_hbm(k, B, T)：HBM 读写量； - time(k, B, T)：预测延迟； - arithmetic_intensity(k)：计算/访存比。 只保留满足 mem_sram <= S 的 Pareto frontier，即在相同 B、T 下没有同时被更低延迟和更低访存支配的 tile。prefill 的 attention 复杂度近似 O(L * B * T^2 * d)，decode 单步复杂度近似 O(L * B * T_ctx * d)，其中 T_ctx 是当前上下文长度。离线可以用 profile + 回归模型拟合 time，线上查表或插值。

2. Prefill/decode 分离 prefill 是大块计算，容易阻塞 decode；decode 是短周期、强 SLA。在线调度采用两级队列： - DecodeQueue：按 next-token deadline 排序，优先保证 TPOT； - PrefillQueue：按 TTFT deadline、prompt 长度和优先级排序。 每个调度 tick 先为 decode 预留算力窗口，再用剩余 slack 执行 prefill。长 prompt 做 chunked prefill，比如每次处理 C 个 token，避免一个超长 prompt 长时间占用设备。chunk 大小 C 由 TTFT slack 和 decode backlog 动态调节。

3. 动态 batching decode batching 的目标是让同一步 token 的请求合并执行，但请求上下文长度不同。可以按长度 bucket 分组，例如 [0,512)、[512,1024)、[1024,2048) 等，减少 padding 和无效 attention。每个 tick 选择一个或多个 bucket 组成 micro-batch。选择策略可以近似为带截止时间的背包： value_i = w_i / estimated_time_i 或 w_i * lateness_penalty_i constraint = 本轮可用时间预算、KV 内存预算、最大 batch size。 精确求解太贵，线上用贪心：先选快到 deadline 的请求，再在同 bucket 内填充高权重请求。复杂度 O(n log n)，n 是活跃请求数。

prefill batching 与 decode 不同，更适合按 prompt chunk 长度聚合。对于 prompt 很短的请求可以合并 prefill；对于超长 prompt，切 chunk 后与其他请求交错执行。

4. KV cache 管理 KV cache 按 page/block 管理，例如每页存固定 token 数 P 的所有层 KV，维护： - request -> page table； - free page list； - active length； - refcount 或状态。 每个请求需要的 KV 大小约为： KV_bytes_i = 2 * L * n_kv_heads * head_dim * bytes * current_len_i。 为避免连续大块分配导致碎片，使用 paged KV。释放请求时回收 page；增长时按需追加 page。复杂度：分配/释放 O(number_of_pages)，查找 page table O(1) 或 O(log pages)。

当 KV 内存紧张时按代价分层处理： - 首选拒绝或排队新请求； - 对低优先级长上下文请求降级最大生成长度； - KV 量化，例如 FP16 -> INT8/FP8； - 对低优先级或可容忍延迟请求 spill 到 HBM/CPU，但会显著伤害 TPOT； - 最后才考虑丢弃请求或重算，因为自回归重算成本通常高。

5. Admission control 对新请求估计其资源消耗： - prefill_time(p_i)； - per_token_decode_time(current_batch, expected_ctx)； - KV_peak = KV_bytes(p_i + g_i)。 如果加入后预测 TTFT/TPOT p95 会超过 SLA，或者 KV_peak 超过安全水位，则拒绝、降级或排队。这里不能只看平均吞吐，要维护滚动窗口 p95 预测。可以用保守水位，例如 KV 使用超过 85% 时停止接收长上下文低优先级请求。

6. 在线调度伪流程 每个 tick： - 更新所有活跃请求的 deadline、上下文长度、KV 占用； - 从 DecodeQueue 中选出最紧急且可 batch 的请求； - 查 Pareto kernel 表，选满足 SRAM 约束且预测延迟最低的 tile； - 执行 decode micro-batch，生成 token，更新 KV page； - 若还有时间 slack，从 PrefillQueue 选 chunked prefill batch； - 若 KV 或延迟水位过高，触发 admission 降级策略。

7. 复杂度 设活跃请求数为 N，KV page 总数为 P，bucket 数为 K： - 每次调度队列维护 O(log N)，一轮选 batch 约 O(N log N) 或按 bucket 优化到 O(K log N + B)； - KV 分配释放 O(pages_per_request)，通常远小于 token 数； - tile 查询若离线建表，线上 O(1) 或 O(log R)，R 是候选 tile 数； - 主要计算仍在 transformer kernel，调度开销应控制在亚毫秒级。

• 工程取舍和风险
• 过大 batch 提高吞吐但增加单请求 TPOT，decode 需要小 batch 高频调度；
• chunked prefill 降低 head-of-line blocking，但会增加 kernel launch 和调度开销；
• KV 量化节省显存，但可能影响长上下文质量，需要灰度和 per-layer 误差评估；
• spill KV 可以提升接纳率，但尾延迟容易失控；
• 静态 profile 与线上分布可能漂移，需要在线校准 cost model；
• 对 speculative decoding、MoE 或不同 LoRA adapter，需要把 expert/router/adaptor 也纳入 batching 维度，否则 batch 合并收益会下降。

参考解法使用已经建立好的上一层 next 链，原地构造下一层 next 链，因此不需要队列，额外空间为 O(1)。

python
from typing import Optional


class Node:
    def __init__(
        self,
        val: int = 0,
        left: Optional["Node"] = None,
        right: Optional["Node"] = None,
        next: Optional["Node"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        """
        填充每个节点的 next 指针，使其指向同层右侧相邻节点。
        返回原二叉树根节点。
        """
        cur = root

        # cur 指向当前层的最左节点。
        # 当前层已经通过 next 串起来，因此可以像遍历链表一样遍历当前层。
        while cur:
            # dummy.next 指向下一层的第一个节点
            # tail 始终指向下一层已连接链表的尾节点
            dummy = Node(0)
            tail = dummy

            # 遍历当前层所有节点，并把它们的孩子按从左到右顺序串起来
            while cur:
                if cur.left:
                    tail.next = cur.left
                    tail = tail.next

                if cur.right:
                    tail.next = cur.right
                    tail = tail.next

                cur = cur.next

            # 移动到下一层的最左节点
            cur = dummy.next

        return root