模调度

可以把一轮当成一张透明纸，上面标着各操作的启动位置。每隔 II 拍叠上一张新纸。检查一张纸，只能知道一轮内部有没有冲突；把所有纸折叠到 II 个余数格里，才能看到不同轮之间的启动争用。

递推边是另一种限制。即使加法器每拍都能启动一个新加法，下一轮累加若必须读取上一轮的和，仍得等那个和真正完成。多放几个空闲端口不能缩短一条不可打断的数据递推。

四操作前缀和：为什么存储要从6移到7 ​

输入数组 X、整数因子 k 和初始累加值 a。输出数组 Y 与 X 完全不重叠，Y 的各下标也指向不同单元。源循环按 i=0,…,N−1 执行：

A_i: load X[i]             // 延迟2，MEM
B_i: b_i := k * A_i        // 延迟3，MUL
C_i: c_i := c_(i-1) + b_i  // 延迟1，ALU；c_(-1)=a
D_i: store Y[i] := c_i     // 延迟1，MEM

MEM、MUL、ALU 每拍容量都是1。A→B、B→C、C→D 的距离为0，C→C 的距离为1。X 只读，Y 的写入彼此不同且不会改变 X，所以没有遗漏的跨轮存储冲突；加载在启动时采样 X，存储在完成时写入 Y。所有加载、乘法、加法及存储都要实际执行一次。

单轮列表表为 s=(0,2,5,6)，最后在7完成。资源下界为2，因为 MEM 每轮需要加载和存储各一次；累加自环给出递推下界1。因此先试 II=2。但照搬单轮偏移时，A 的余数0与 D 的余数0冲突：例如 D₀ 在6启动，A₃ 也在6启动。第一轮单看完全合法，重复后却超出 MEM 容量。

将 D 的偏移推迟为7，得到 s=(0,2,5,7)。MEM 的 A 占余数0、D 占余数1；MUL 的 B 占余数0，ALU 的 C 占余数1。距离0三条边的松弛量分别为0、0、1，C 自环的松弛量为 $5+2-5-1=1$，全部非负。于是每隔两拍可开始一个新图案，而一轮自身从加载到存储完成仍需8拍。

取 X=[1,2,3,4]、k=2、a=0。四轮的 A 启动于0、2、4、6；B 启动于2、4、6、8；C 启动于5、7、9、11；D 启动于7、9、11、13，分别在8、10、12、14写入 Y。C 的结果依次为2、6、12、20，所以最终 Y=[2,6,12,20]。t=7 可以同时启动 C₁ 与 D₀，因为它们用不同端口，且各自所读结果都已完成。

按两拍分组，0–1、2–3、4–5是逐步填充；6–7这一组包含 A₃、B₂、C₁、D₀，是完整重复图案；8–9、10–11、12–13逐步排空，最后存储于14完成。这里没有把填充和排空当成免费。若逐轮串行用单轮七拍表，四轮需28拍；周期表需14拍。若仅 N=1，周期表反而需8拍，单轮表只需7拍。

真递推限制与下界不充分 ​

把 C 延迟改成3，即使 ALU 仍每拍可启动一次，C 自环也要求 II≥3。II=2 被递推证书直接否决。II=3 时偏移 (0,2,5,8) 合法：Cᵢ 恰好完成时 Cᵢ₊₁ 才启动，Dᵢ 也能读取 cᵢ。容量与递推是两份不同证据。

下界满足也可能无解。另取两个操作 P、Q，均延迟2、均占容量1的同一启动口，边 P→Q 距离0、Q→P 距离2。资源下界2，环下界也为 ceil(4/2)=2。若 II=2，两条依赖迫使 $s(Q)-s(P)\ge 2$ 且 $s(Q)-s(P)\le 2$，所以差值只能为2；两操作必占同一模槽，违反容量。这个等式冲突才是 II=2 不可行的证明，不是“搜索跑了很久”。II=3 时 P=0、Q=2 则可行。

别名会改变正确答案 ​

现在故意破坏主例前提：让 X[i] 指向共享数组第 i 格，Y[i] 指向同一数组第 i+1 格。初始共享数组为 [1,2,3,4,0]。源循环第0轮写出2，下一轮读到2；第1轮写出6，第2轮随后读到6；于是源输出为 [2,6,18,54]。

错误沿用无别名的 II=2 表会提前加载原来的3和4，仍算出 [2,6,12,20]。端口和原来的四条边都通过，并没有挽救语义。正确依赖图还需要 D→A、距离1，保证上一轮存储完成后下一轮加载才启动。A→B→C→D→A 的延迟和为7、距离和为1，所以 II≥7。依赖分析给出的原距离和存储对象分离证明，是这个优化不可跳过的输入。

从两条证书到每个有限实例 ​

对边 (u,v,d) 和实际消费者轮号 j≥d，把周期不等式加上 (j−d)II，得到 $s(v)+jII\ge s(u)+(j-d)II+L(u)$。所以每一条真正存在的生产者—消费者实例边都满足完成先于启动。j<d 时没有负轮号指令，必须使用合同中给定的初始值；主例只需要 c₋₁=a。不能凭空执行一次“第−1轮”加载或存储。

固定时刻 t 和资源 r。能在此时启动的某种操作 v 至多有一个轮号 i，因为 II>0；它一定满足 s(v)≡t mod II。模槽中最多 cᵣ 种操作，所以该时刻最多 cᵣ 次启动。删除超过 N 的轮号只会减少启动数，因而有限填充和排空同样不超容量。这也说明为什么图案的模检查无需枚举无穷多轮。

对前缀和，X 不变使每个 Aᵢ 采到源循环的 X[i]。按轮号归纳，Bᵢ=kX[i]，Cᵢ 在 Bᵢ 和 Cᵢ₋₁ 都交付后启动，故得到 $a+\sum _{j=0}^{i}kX[j]$。Dᵢ 读取这个结果，且只写自己独立的 Y[i]。于是所有输出与源循环相同；访存顺序允许不同，只因已经逐项检查它不会改变任一加载值或覆盖别人的输出。若别名条件失效，这个证明的第一步就失效。

有限展开器为每个 v 与 0≤i<N 建立一个具名实例，逐一生成启动与完成事件。它检查全部实例边和各绝对时刻的启动容量，再实际计算数值并执行每次存储。N>0 且循环体非空时，最后完成时刻为

N=0 或循环体为空时没有任何操作，完成时刻为0，不能把上式机械代成负的启动轮数。这个交付是有限事件程序及其轨迹，不是已经解决分支控制和寄存器轮换的目标汇编循环。

搜索成本与交付边界 ​

一张给定周期表的验证需 O(n+e+r) 时间和空间，模槽用稀疏字典，无需申请长度 II 的数组。下界参考器显式枚举全部简单环，并保存每条证据；环和搜索到的简单路径前缀数量可能指数增长，空间除图本身外，还包含保存环路径的总长度；当前深度优先栈逐层复制路径与已访问集合，另有最坏 O(n²) 的临时空间。这部分发生在试放预算之前，不能把 budget 宣传为整个调用的时间上限。教学脚本只针对小图。

固定 H 后至多有 (H+1)ⁿ 个完整候选，回溯还访问部分候选。若实际试放次数为 B，每次扫描已分配端点的全部边需 O(e+1)，故试放阶段为 O(B(e+1))；另加输入处理、下界计算及最终验证。活动赋值和槽计数为 O(n)，递归深度为 n。Python 递归与内存有限，过大的输入还可能超出实现能力，不能把数学上的有限搜索当成无限资源保证。

展开器先验证原图与周期表，再遍历 N 轮，因此图与证书工作统一为 O((N+1)(n+e+1)+r)，峰值空间为 O((N+1)(n+e)+r+1)。这个写法也计入零轮时的原图验证，以及空体时仍遍历 N 轮的参考实现成本。参考数值执行器为清晰起见排序事件时刻，并保存轨迹，另有 O(Nn log(Nn+1)) 的排序时间，轨迹空间已包含在上述界内。以上均不把大整数算术与 JSON 排序算成常数免费工作，也不等同于被调度机器的 T_N。

可执行终点要求分别交付四种搜索状态、真正的边与模槽证书、零轮和一轮边界、完整的四轮访存轨迹，以及别名失效后的错误输出和新增递推。找到较小 II 的时间表是优化结果；证明它在给定语义下可执行，才是交付完成。