在多面体模型中表示张量操作及其数据依赖,能够系统地改变循环迭代的执行顺序。这种重排,称为调度,是由作用于迭代向量的数学变换指导的。主要目标是改善数据局部性,提升缓存利用率,并显现可供多核CPU或GPU利用的并行性。调度会为循环嵌套中语句的每个动态实例分配一个逻辑执行时间戳(通常是多维的)。对于在迭代向量$\vec{x}$处执行的语句实例$S_i$,其调度表示为$T(S_i, \vec{x})$。一个基本要求是调度必须遵守所有数据依赖。如果语句实例$(S_i, \vec{x})$因数据依赖(写作$(S_i, \vec{x}) \rightarrow (S_j, \vec{y})$)而必须在$(S_j, \vec{y})$之前执行,那么调度必须保证它们的逻辑时间戳能体现这个顺序: $$ T(S_i, \vec{x}) \prec T(S_j, \vec{y}) $$ 此处,$\prec$表示字典序。找到一个满足所有依赖并同时优化局部性或并行性的调度$T$,是核心工作。在多面体模型中,调度通常被限制为循环迭代器($\vec{x}$)和循环边界或访问中存在的任何符号常量(参数)的仿射函数。两种基本且广泛使用的调度仿射变换是分块和倾斜变换。循环分块 (阻塞)分块,也称为阻塞,可以说是现代内存层级结构中对性能影响最显著的变换。它将迭代空间划分为更小、规则的块(瓦片),这些块以原子方式执行。动机:在瓦片内执行迭代,能将数据复用置于首位。如果一个瓦片访问总体数据的一小部分,这些数据更有可能适合内存层级结构中更快的级别(寄存器、L1/L2缓存)。这提升了时间局部性(复用相同数据元素)和空间局部性(访问附近数据元素)。此外,如果依赖允许,瓦片本身通常可以并行执行,显现粗粒度并行性。以矩阵乘法$C = A \times B$为例。分块将大的乘法分解为更小的矩阵乘法,这些乘法作用于A、B和C的块,这些块更适合缓存。多面体分块:在多面体框架中,通过将原始迭代向量$\vec{x}$转换为更高维的向量来实现分块,该向量将瓦片坐标与瓦片内坐标分离。对于具有迭代器$(i, j)$和方形瓦片大小$B$的二维循环嵌套,一种常见的分块变换将$(i, j)$映射到$(ii, jj, i', j')$,其中:$ii = \lfloor i / B \rfloor$ 和 $jj = \lfloor j / B \rfloor$ 是瓦片坐标。$i' = i \pmod B$ 和 $j' = j \pmod B$ 是瓦片内的点坐标。结果调度可能看起来像$T(i, j) = (ii, jj, i', j')$。这将原始的2层循环嵌套转换为4层循环嵌套:两个外层循环迭代瓦片($ii, jj$),两个内层循环迭代瓦片内的点($i', j'$)。digraph G { node [shape=point, width=0.05, height=0.05, label=""]; graph [splines=false]; subgraph cluster_tile_00 { label = "瓦片 (ii=0, jj=0)"; bgcolor="#e9ecef"; p00; p01; p10; p11; p00 -> p01; p10 -> p11; p00 -> p10; p01 -> p11; } subgraph cluster_tile_01 { label = "瓦片 (ii=0, jj=1)"; bgcolor="#e9ecef"; p02; p03; p12; p13; p02 -> p03; p12 -> p13; p02 -> p12; p03 -> p13; } subgraph cluster_tile_10 { label = "瓦片 (ii=1, jj=0)"; bgcolor="#e9ecef"; p20; p21; p30; p31; p20 -> p21; p30 -> p31; p20 -> p30; p21 -> p31; } subgraph cluster_tile_11 { label = "瓦片 (ii=1, jj=1)"; bgcolor="#e9ecef"; p22; p23; p32; p33; p22 -> p23; p32 -> p33; p22 -> p32; p23 -> p33; } // 示例依赖 edge [color="#f03e3e", penwidth=1.5]; p11 -> p21 [label=" 依赖 D1", fontsize=10]; // 示例依赖 p13 -> p22 [label=" 依赖 D2", fontsize=10]; // 跨瓦片示例依赖 {rank=same; p00; p01; p02; p03;} {rank=same; p10; p11; p12; p13;} {rank=same; p20; p21; p22; p23;} {rank=same; p30; p31; p32; p33;} }将4x4迭代空间划分为2x2瓦片。像D1这样的依赖包含在一个瓦片内(如果瓦片大小足够大),或者跨越瓦片边界。像D2这样的依赖跨越瓦片边界(瓦片间依赖)。合法性:只有当所选调度(包括瓦片循环和点循环)遵守所有原始数据依赖时,分块才是合法的。依赖可以分为:瓦片内依赖:依赖的源和目的地位于同一瓦片内。这些依赖通过瓦片内的执行顺序($i', j'$循环)处理。瓦片间依赖:源和目的地位于不同的瓦片中。瓦片循环($ii, jj$)的调度必须遵守这些依赖。为了使分块能够实现瓦片间的并行(例如,并行执行$ii$循环),调度中该循环维度不得带有任何依赖。像Pluto调度器这样的算法旨在找到多维仿射调度,以实现合法且高效的分块,通常会最大化可以合法并行化的维度。循环倾斜变换Loop skewing是另一种仿射变换,常用于使能其他变换,如分块或向量化,当依赖原本会阻止这些变换时。动机:考虑一个循环嵌套,其依赖结构形成“波前”模式,这在模板计算或某些动态规划算法中很常见。例如,依赖$(i, j) \rightarrow (i+1, j+1)$。直接分块可能不合法,因为纯粹按列或按行执行瓦片会违反对角线依赖。倾斜变换改变了迭代空间相对于依赖的形状。机制:倾斜变换会改变迭代器,从而改变依赖迭代的相对顺序。对于二维循环嵌套,一种常见的倾斜变换是: $$ i' = i $$ $$ j' = j + \alpha \cdot i $$ 其中$\alpha$是倾斜因子。这将原始的矩形迭代空间映射为一个平行四边形。主要影响在于依赖向量。如果原始依赖向量是$\vec{d} = (d_i, d_j)$,则在$(i', j')$空间中的新依赖向量$\vec{d}'$变为$(d_i, d_j + \alpha \cdot d_i)$。digraph G { rankdir=LR; graph [splines=false]; node [shape=point, width=0.1, height=0.1, label=""]; subgraph cluster_0 { label = "原始空间 (i, j)"; edge [color="#f03e3e", penwidth=1.5]; node [group=orig]; o00; o01; o02; o10; o11; o12; o20; o21; o22; {rank=same; o00; o10; o20;} {rank=same; o01; o11; o21;} {rank=same; o02; o12; o22;} o00->o10->o20; o01->o11->o21; o02->o12->o22; // i 依赖 o00->o01->o02; o10->o11->o12; o20->o21->o22; // j 依赖 // 对角线依赖示例 o11 -> o22 [label=" d=(1,1)", fontcolor="#f03e3e", fontsize=10]; } subgraph cluster_1 { label = "倾斜空间 (i'=i, j'=i+j, alpha=1)"; edge [color="#1c7ed6", penwidth=1.5]; node [group=skewed]; // i'=i, j'=i+j 映射:(0,0)->(0,0), (0,1)->(0,1), (0,2)->(0,2) // (1,0)->(1,1), (1,1)->(1,2), (1,2)->(1,3) // (2,0)->(2,2), (2,1)->(2,3), (2,2)->(2,4) s00; s01; s02; s11; s12; s13; s22; s23; s24; {rank=same; s00;} {rank=same; s01; s11;} {rank=same; s02; s12; s22;} {rank=same; s13; s23;} {rank=same; s24;} s00->s01->s02; s01->s11; s02->s12; s11->s12->s13; s12->s22; s13->s23; s22->s23->s24; // 变换后的依赖:T(1,1)=(1,2), T(2,2)=(2,4) // 新向量 d' = (2-1, 4-2) = (1, 2) s12 -> s24 [label=" d'=(1,2)", fontcolor="#1c7ed6", fontsize=10]; } }倾斜变换 ($i'=i, j'=i+j$) 对二维迭代空间的影响。原始依赖$d=(1,1)$被转换为$d'=(1,2)$。此变化可能使能沿$i'$维度进行分块。使能分块:通过改变依赖向量,倾斜变换可以使原本有问题的维度上的依赖在字典序上变为正向。对于依赖$d=(1,1)$,在通过$\alpha=1$进行倾斜变换后,依赖变为$d'=(1, 2)$。如果我们现在对倾斜空间$(i', j')$进行分块,依赖总是沿$i'$维度跨瓦片传递(因为$d'_{i'} = 1 > 0$)。这使得分块合法,而在原始空间上简单分块可能不合法。结果执行沿倾斜的波前进行。组合变换与自动调度Skewing和分块各自都很有用,但它们常被结合使用。一种常见策略是“先倾斜后分块”,即倾斜变换首先调整依赖,然后分块在倾斜空间中提升局部性和并行性。寻找倾斜变换、分块以及其他潜在仿射变换(如置换或缩放)的最佳组合是复杂的。它很大程度上取决于具体的依赖模式和目标硬件架构。这正是基于多面体库(如isl,整数集库)的自动调度工具发挥作用的地方。这些工具分析多面体表示(域、依赖、访问函数),并采用算法(例如Pluto算法或Feautrier算法)来搜索合法的仿射调度$T$,以优化特定目标,例如最大化并行外层循环的数量或最小化数据移动,并根据需要纳入分块和倾斜变换。一旦确定了合适的调度$T$(代表变换后的循环结构,可能包括分块和倾斜变换参数),下一步,在代码生成中讨论,是生成实现该调度的实际优化循环代码。