第 8 章：仿射调度与多维时间
直觉
第 7 章把程序真正必须保持的跨实例顺序汇总为依赖关系
$$ \Delta_{S\to T}\subseteq D_S\times D_T. $$
其中第一元是 source，第二元是 sink。调度的任务不是重新猜测值从哪里来，而是给每个语句实例分配一个新时间戳，并保证每条已有依赖仍从早指向晚。
一个时间戳可以有多维。例如 $(3,5)$ 早于 $(4,-100)$，因为词典序只查看第一个不同分量；第二分量再小也不能推翻第一分量已经确定的先后。因此，多维调度的合法性不是“每一维都严格递增”，而是“第一个非零距离分量为正”。这个区别正是循环交换、融合、倾斜和并行维构造的基础。
仿射调度把时间戳限制为循环变量和全局参数的仿射函数。限制看似很强，却把寻找循环变换的问题变成寻找有限多个系数的问题。第 9 章会继续说明，如何用 affine Farkas 引理把“对所有依赖实例成立”也变成有限约束。
本章始终分开两个问题：
- 合法性：所有 source → sink 依赖是否严格向前；
- 性能：合法候选中，哪个更利于并行、局部性、向量化或 tiling。
前者是必须满足的语义边界，后者才是优化选择。
形式定义
一维与多维仿射调度
令语句 $S$ 的迭代向量为 $x\in D_S(p)\subseteq\mathbb Z^{d_S}$，参数向量为 $p\in\mathbb Z^q$，参数上下文为 $C(p)$。一维仿射调度写成
$$ \theta_S(x,p)=C_Sx+E_Sp+c_S\in\mathbb Z. $$
这里 $C_S$ 是迭代变量的系数行向量，$E_S$ 是参数的系数行向量，$c_S$ 是常数；它们是待求的调度系数。$E_S$ 使用尚未被域记号占用的字母，因而不会与迭代域 $D_S(p)$ 混淆；符号 $C_S$ 也不同于参数上下文 $C(p)$。要求整数时间戳时，这些系数取整数；也可先求有理系数，再按保持顺序的统一正尺度清除分母。
一个 $k$ 维仿射调度为
$$ \Theta_S(x,p) =\bigl(\theta_S^{(1)}(x,p),\ldots,\theta_S^{(k)}(x,p)\bigr) \in\mathbb Z^k, $$
每个分量各有一组仿射系数。不同语句的系数可以不同，因此常数分量可以表达同一循环坐标处的语句顺序。
合法性的固定方向：source 严格早于 sink
对每条依赖 $(x,y)\in\Delta_{S\to T}(p)$，合法调度必须满足
$$ \boxed{ \Theta_S(x,p)\mathrel{\mathrm{lex}<}\Theta_T(y,p) } $$
即 source 的时间戳严格小于 sink 的时间戳。不能交换两端后仍称作同一方向。
一维时定义调度差
$$ d(x,y,p)=\theta_T(y,p)-\theta_S(x,p). $$
若时间戳属于整数，则严格先后等价于
$$ d(x,y,p)\ge1. $$
“至少 1”使用了整数刻度；若尚在未归一化的有理时间上求解，只能先写 $d>0$，再统一清分母或规定尺度，不能无条件把任意正有理数说成至少 1。
词典序的逐层语义
对多维调度，令第 $r$ 维的距离为
$$ d_r(x,y,p) =\theta_T^{(r)}(y,p)-\theta_S^{(r)}(x,p). $$
从某条依赖关系或其一个非空分支开始，记尚未被先前维度严格承载的实例集合为 $U_0=\Delta_{S\to T}$。第 $r$ 层只在当前残余集合 $U_{r-1}$ 上要求
$$ \forall(x,y)\in U_{r-1}:\quad d_r(x,y,p)\ge0. $$
这叫本维对残余依赖的 weak satisfaction（弱满足）。其中
$$ K_r=U_{r-1}\cap\{(x,y)\mid d_r(x,y,p)\ge1\} $$
中的整数依赖实例在前面各维距离都为零，而在第 $r$ 维严格为正，所以由本维 strictly carried（严格承载）。距离仍为零的实例形成下一层残余关系
$$ U_r=U_{r-1}\cap\{(x,y)\mid d_r(x,y,p)=0\}. $$
若最终 $U_k=\varnothing$，每条依赖都在某个最早非零维得到正距离，因而整个向量严格词典序合法。对已经属于某个 $K_r$ 的依赖，后续距离可以为正、零或负，因为词典序先后已经由第 $r$ 维决定。于是下面三个术语必须分开：
- weak satisfaction：当前残余关系上本维距离非负，允许为零；
- strict carry：此前各维为零、本维距离至少为 1 的整数依赖实例；
- residual dependence：此前各维距离都为零，尚须交给下一维处理的实例。
Feautrier 的 Part I 研究一维时间及其约束化；Part II 把算法扩展到词典序多维时间，并按需要构造足够的调度维数。本节的 $U_r$ 写法是为突出逐层语义所作的教学性整理。
固定候选的语义与逐维合成的顺序
上面的 $K_r,U_r$ 首先定义了一个已经固定的多维候选调度如何承载依赖：此时每个 $d_r$ 的系数已知，集合交可以直接计算。自动合成时，当前维的 $C_S^{(r)},E_S^{(r)},c_S^{(r)}$ 尚未知，不能把含这些未知系数的 $d_r=0$ 立即当成下一层 Farkas 的已知前提。
本教程采用以下顺序流程：
- 第 $r$ 轮开始时，$U_{r-1}$ 已知；$r=1$ 时它就是输入依赖 $U_0$，以后各轮则来自已经固定的前一维。
- 只在这个已知 $U_{r-1}$ 上，为当前 $d_r\ge0$ 建立 Farkas 约束，求出当前维，并按该轮的进展或性能准则选定一组系数。
- 对本轮涉及的每个语句 $S$，固定 $C_S^{(r)},E_S^{(r)},c_S^{(r)}$。代入后 $d_r$ 成为已知仿射式，再计算 $K_r=U_{r-1}\cap\{d_r\ge1\}$ 与 $U_r=U_{r-1}\cap\{d_r=0\}$。
- 若 $U_r\ne\varnothing$，把这个已知的新 residual dependence 化为下一轮可处理的分支或多面体描述，再为第 $r+1$ 维重新建立有限系统；若为空，严格词典序构造结束。
顺序中的“先固定、再求 $U_r$”是线性有限化的必要边界。若同时求所有维，下一层残余域的约束矩阵会含上一维未知调度系数；它再与下一层 Farkas 乘子相乘，出现“未知调度系数 × 未知乘子”的双线性项。普通 LP/ILP 不会仅因变量声明为整数就自动线性化这种乘积。联合求多维调度需要另行设计带有效界的离散或线性化编码；本教程没有给出、也不声称当前公式已经给出这种联合 ILP。
Permutable band 与 coincident 维
一个 band 是准备作为整体处理的一组连续调度维。仅有整个时间向量 lex-positive，并不足以任意交换这些维：某条依赖可能靠较早分量的正值掩盖较晚分量的负值，一旦交换，负值就可能先出现。
在常用的教学性判据下，先只看进入 band 时尚未由外层严格承载的活动依赖：若它们在 band 内每一维的距离都非负，这些维可构成 permutable band。其中在 band 内出现正分量的依赖由 band 承载；band 内距离全为零的依赖仍可留给后续维处理。分量非负保证交换 band 内的循环维不会让活动依赖以负分量开头；这种结构也是矩形 tiling 的重要入口。实际调度树还要结合依赖过滤、语句域和工具对 band 的具体定义。
若某一调度维对进入该维时仍活动、会限制并行执行的相关依赖距离都为零，则称该维 coincident；在没有归约、同步、别名等额外障碍时，它可对应并行循环维。coincident 指依赖距离为零，不是“该维调度系数全部为零”，也不能只检查一条依赖便下结论。
手算示例
一维 shift：identity、reverse 与 constant 逐条验证
沿用第 7 章的精确 RAW 关系：
$$ \Delta_{S\to S} =\{[i]_S\to[i+1]_S\mid1\le i<N-1\}. $$
对任意 source $i$ 和 sink $i+1$，逐一验证三个一维候选。
Identity schedule 取 $\theta(i)=i$。调度差为
$$ \theta(i+1)-\theta(i)=(i+1)-i=1\ge1. $$
所以每条 source → sink 依赖都严格向前，identity 合法。
Reverse schedule 取 $\theta(i)=-i$。调度差为
$$ \theta(i+1)-\theta(i)=-(i+1)-(-i)=-1<1. $$
它让 sink 早于 source，reverse 非法。
Constant schedule 取 $\theta(i)=0$。调度差为
$$ \theta(i+1)-\theta(i)=0. $$
两端时间戳相同，无法区分这条已有依赖的先后，所以作为完整一维调度非法。常数分量并非总无用：它可以是多维调度中允许并列、交给后续维处理的弱满足维，也可区分不同语句，例如 $\theta_P(i)=0,\theta_C(i)=1$。这里的非法结论来自 shift 确实存在自依赖，而不是“任何两个相同时间戳都无条件非法”。
生产者—消费者：sequence 与 fusion 都可以合法
设各个 $i$ 之间独立，唯一依赖为
$$ \Delta_{P\to C} =\{[i]_P\to[i]_C\mid0\le i<N\}. $$
一种分阶段的 sequence/distribution 风格调度是
$$ \Theta_P(i)=(0,i),\qquad \Theta_C(i)=(1,i). $$
每条依赖的距离为 $(1,0)$，第一维严格承载它；所有 producer 阶段在所有 consumer 阶段之前。
另一种逐元素融合调度是
$$ \Theta_P(i)=(i,0),\qquad \Theta_C(i)=(i,1). $$
每条依赖的距离为 $(0,1)$：第一维弱满足且留下全部残余依赖，第二维再严格承载。它产生 $P(0),C(0),P(1),C(1),\ldots$ 的顺序。
两个调度都满足同一 source → sink 严格词典序约束，但性能取舍不同。融合通常缩短中间值复用距离并减小工作集；分阶段则可能更利于每个阶段独立向量化、批处理或采用不同并行策略。融合还可能增加寄存器压力或把资源需求不同的两个 kernel 绑在一起。因此，合法性没有宣布哪一个更快。
对融合调度，第一维在这组依赖上的距离恒为零；若确实不存在跨 $i$ 的其他依赖，它是 coincident 候选，可让不同 $i$ 并行。第二维仅编码同一 $i$ 内 producer 在 consumer 之前。
二维循环交换：要检查变换后的第一个非零距离
考虑二维语句实例 $S(i,j)$，并有依赖
$$ \Delta =\{[i,j]_S\to[i+1,j-1]_S \mid0\le i<I-1\land1\le j<J\}. $$
原 identity 调度 $\Theta(i,j)=(i,j)$ 的距离为
$$ (i+1,j-1)-(i,j)=(1,-1). $$
虽然第二分量为负，第一非零分量是 $+1$，所以它严格词典序合法。这也直接反驳“合法要求每维都非负或严格递增”。
交换两个循环相当于候选 $\Theta'(i,j)=(j,i)$。同一依赖的距离变为
$$ (j-1,i+1)-(j,i)=(-1,1). $$
第一个非零分量是 $-1$，故 interchange 非法。若程序只有 $[i,j]\to[i,j+1]$ 这样的内层前向依赖，则交换后距离从 $(0,1)$ 变成 $(1,0)$，仍合法。循环交换本身既非总合法也非总非法；答案由完整依赖关系决定。
主 stencil：skewing 把负的空间分量变为可置换结构
主案例的三个依赖分支为
$$ \Delta_\delta =\{[t-1,i+\delta]_S\to[t,i]_S \mid \delta\in\{-1,0,1\}\ \land\ \text{两端均在域内}\}. $$
identity 调度 $\Theta(t,i)=(t,i)$ 下，从 source $(t-1,i+\delta)$ 到 sink $(t,i)$ 的距离是
$$ (1,-\delta). $$
三个分支分别得到 $(1,1),(1,0),(1,-1)$。它们都 lex-positive，因为时间维首先增加 1；但最后一个分支的空间距离为负，所以 $(t,i)$ 两维不满足上述 permutable band 的分量非负充分条件，直接交换也会出错。
取倾斜调度
$$ \Theta'(t,i)=(t,t+i). $$
则距离变成
$$ \begin{aligned} \Theta'(t,i)-\Theta'(t-1,i+\delta) &=(t,t+i)-(t-1,t-1+i+\delta)\\ &=(1,1-\delta). \end{aligned} $$
对 $\delta=-1,0,1$，分别是 $(1,2),(1,1),(1,0)$，每个分量都非负，且第一分量严格为正。于是这两个调度维形成适合交换与矩形 tiling 的非负距离结构。skewing 没有删除依赖；它改变坐标，使 wavefront 的合法顺序更容易组织成可置换 band。是否真的更快仍取决于 tile 大小、边界代码、并行粒度和存储层次。
编译器用途
- 把依赖变成调度可行域。 对第 7 章产生的每个 $\Delta_{S\to T}$，编译器建立 source 早于 sink 的约束；第 9 章将说明如何有限化其中的全称量词。
- 组织 sequence 与 fusion。 不同语句的常数和循环系数决定它们是分阶段执行，还是在共同循环坐标下交错执行。
- 识别 interchange 与 skewing。 变换后重新计算依赖距离；严格词典序检查决定语义合法性，分量非负结构进一步决定 band 是否适合置换和 tiling。
- 逐层暴露并行性。 一维调度严格承载一部分依赖后，调度器先固定该维、计算已知残余关系，再为下一维重新建模；某维对所有相关依赖距离为零时，才可能标为 coincident。
- 保留参数化结构。 $E_Sp$ 让调度随合法参数上下文变化，但参数条件必须与依赖域一起参与全称合法性检查。
- 传给后续代码生成。 合法的调度不是最终循环文本。编译器还须扫描调度像、生成边界与 guard，并保持语句内部事件语义。
Feautrier Part I 与 Part II 给出仿射调度的经典算法路线。Pluto 项目与作者资料 展示了面向并行性和局部性的自动仿射变换实践。它们都在合法域上进一步选择调度，而不是用性能目标代替依赖合法性。
常见误区
- 把方向写成 sink → source。 固定条件是 $\Theta_S(x)\mathrel{\mathrm{lex}<}\Theta_T(y)$，其中 $(x,y)\in\Delta_{S\to T}$。
- 要求每一维都严格递增。 严格词典序只要求第一个非零距离为正；之前各维为零，之后各维不再决定该依赖。
- 把 weak satisfaction 当作已经完成合法性。 $d_r=0$ 的实例仍在残余关系中，必须由后续维严格承载。
- 认为较晚维也必须非负。 对已经由更早维严格承载的依赖，较晚维可为负；只有构造 permutable band 时才另加更强的非负结构。
- 把 permutable 等同于 lex-positive。 lex-positive 允许 $(1,-1)$，但交换两维会得到非法的 $(-1,1)$。
- 把 coincident 解释为系数为零。 判断对象是所有相关依赖的该维距离，还要排除归约、同步和别名等其他限制。
- 宣布 constant schedule 总非法。 对 shift 自依赖，完整一维常数调度确实非法；作为多维前缀或跨语句常数顺序，它可以有合法用途。
- 对未归一化有理时间直接写差至少 1。 $>0$ 到 $\ge1$ 依赖整数时间戳或清分母后的尺度约定。
- 把合法调度当成高性能调度。 sequence 与 fusion 可以同时合法，却有不同的局部性、并行和资源取舍。
- 只检查一个代表距离。 参数边界、析取分支和不同语句依赖都必须纳入完整关系，不能用一个平均距离替代全称检查。
- 把未知 $U_r$ 直接送进下一层 Farkas。 合成时必须先解出并固定第 $r$ 维，才能让 $d_r=0$ 成为已知线性约束；否则下一层乘子会与上一层未知调度系数形成双线性乘积。
练习
练习 EX08-B01｜Shift 候选调度合法性（基础）
对 shift 关系 $[i]\to[i+1]$，分别检验 $\theta(i)=2i+3$、$\theta(i)=-2i$、$\theta(i)=7$。统一计算 $\theta(\mathrm{sink})-\theta(\mathrm{source})$，并判定一维合法性。
答案索引： ANS-EX08-B01
练习 EX08-B02｜Producer/consumer 常数次序（基础）
对 $P(i)\to C(i)$，验证 $\Theta_P=(i,1),\Theta_C=(i,0)$ 为何非法；再只改一个常数使它合法。
答案索引： ANS-EX08-B02
练习 EX08-D01｜Lex-positive 与 permutable band（推导）
取二维距离 $(1,-3)$。说明它为何 lex-positive，却不能直接证明两维构成 permutable band；交换两维后重新判断。
答案索引： ANS-EX08-D01
练习 EX08-D02｜Residual dependence 分层（推导）
设已知残余关系 $U_0$ 被第一维距离分成 $d_1=1$ 与 $d_1=0$ 两类，且在 $d_1=0$ 类上 $d_2=2$。只用集合条件写出 $K_1,U_1,K_2,U_2$，说明哪些依赖由哪一维严格承载；不要求枚举未给出的具体实例。
答案索引： ANS-EX08-D02
练习 EX08-C01｜两支依赖下的 identity/interchange（综合）
对依赖 $[i,j]\to[i,j+1]$ 和 $[i,j]\to[i+1,j-2]$ 的并，分别检查调度 $(i,j)$ 与 $(j,i)$；不能只检查其中一个分支。
答案索引： ANS-EX08-C01
练习 EX08-D03｜Stencil skew 系数下界（推导）
将 stencil 的倾斜推广为 $\Theta_k(t,i)=(t,kt+i)$。求三个 source-to-sink 距离 $(1,k-\delta)$，给出使第二分量对所有 $\delta\in\{-1,0,1\}$ 非负的最小整数 $k$。
答案索引： ANS-EX08-D03
练习 EX08-C02｜Sequence 与 fusion 的性能权衡（综合）
为逐元素 $P(i)\to C(i)$ 比较分阶段与融合调度：分别列出 $N=3$ 时的执行顺序，并各写一个可能的性能优势和一个代价。不得把合法性直接当作加速结论。
答案索引： ANS-EX08-C02
练习 EX08-D04｜后续负维不推翻词典序合法性（推导）
构造一个两维调度，使某条依赖第一维距离为 0、第二维为 1；再添加第三维距离 $-100$，解释为何完整调度仍合法。
答案索引： ANS-EX08-D04
本章小结
- 仿射调度把语句实例和参数映到整数时间戳；合法性始终按 source → sink 写成 $\Theta_S(x)\mathrel{\mathrm{lex}<}\Theta_T(y)$。
- 对整数一维时间，严格先后等价于 sink 减 source 至少为 1；identity shift 合法，reverse 与完整 constant schedule 非法。
- 多维调度逐层处理残余依赖：本维先 weakly satisfy，正距离实例由本维 strictly carry，零距离实例继续进入 residual dependence。
- 验证固定候选时可直接定义所有 $U_r$；合成时必须按“已知 $U_{r-1}$ → 求并固定当前维 → 计算已知 $U_r$ → 下一维重新建模”的顺序执行，本文不提供联合多维 ILP。
- 词典序合法不要求每维严格递增；已经由前维承载的依赖，其后续距离甚至可以为负。
- Permutable band 要求比普通 lex-positive 更强的非负距离结构；coincident 维则要求所有相关保序依赖在该维距离为零。
- sequence、fusion、interchange 与 skewing 都必须从完整依赖关系证明合法；stencil 倾斜 $(t,t+i)$ 把三个距离变为 $(1,2),(1,1),(1,0)$。
- 两个调度可以同样合法却有不同并行性与局部性；合法性定义可行边界，性能目标在边界内另行选择。