Advanced FPGA HLS: Polyhedral Compiling

The polyhedral model is a mathematical framework used to optimize loop nests, also known as polyhedral compiling. It can be used to perform complex loop transformations that improve parallelism and data locality in FPGA designs.

Fri Dec 19 2025

Fri Jan 02 2026

FPGA HLSPolyhedral CompilingLoop TransformationsParallelismData Locality

Advanced FPGA HLS: Polyhedral Compiling

多面体模型是一种用于优化仿射循环 (Affine Loops) 嵌套的数学框架. 简单来说一组嵌套循环的迭代变量 (i, j, k 等) 可以被视为多维度空间中的点, 而循环的边界条件则定义了这些点所构成的多面体 (Polyhedron). 在仿射循环内部, 所有的内存访问都是关于迭代变量的线性函数, 这使得我们能够使用线性代数和几何工具来分析和转换循环结构.

基本概念

首先说明 SCoP (Static Control Part) 的概念. 如果有一段代码, 其控制流和内存访问模式在编译时都是可预测的, 那么它就可以被视为一个 SCoP.

具体来说, 一个 SCoP 通常由一组循环嵌套, 条件分支和语句组成, 并且满足仿射 (Affine) 要求. 即这段代码的所有结构属性 (循环边界, 分支条件, 内存访问索引) 都可以用循环索引和全局参数 (指在循环迭代中始终保持不变的变量) 的线性组合加上一个常数项来表示. 例如

// is valid SCoP boundary
for (int i = 0; i < N; i++)
    for (int j = 0; j < i; j++)
        // ...
// is NOT valid SCoP boundary
for (int i = 0; i < N; i++)
    for (int j = 0; j < (i*i); j++)
        // ...

if (i + j < N) // is valid SCoP condition
if (i % 2 == 0) // also valid, but need transforms
if (i*j < N) // is NOT valid SCoP condition

int a = A[i + 2*j + 3]; // is valid SCoP access
int b = B[i * j]; // is NOT valid SCoP access
int c = A[B[i]]; // is NOT valid SCoP access

只有当一段代码中所有的内存访问, 循环边界和条件分支都满足上述要求时, 它才能被视为一个 SCoP. 这是因为多面体模型依赖于线性代数和几何工具来静态分析和转换循环结构, 因此需要这些结构属性在编译时是可预测和可分析的.

一个 SCoP 中可能会包含多个 SCoP 语句 (Statement), 但如何划分这些语句并没有严格的定义. 多面体模型优化是尽可能找到不同语句之间的独立性, 使他们尽可能多地并行执行. 所以理论上来讲, 最细粒度的方式是为每一条指令 (操作) 都创建一个独立的 SCoP 语句, 但这是没有必要的. 因为多面体调度到最后是求解一个 ILP (整数线性规划问题), 语句划分过细会导致 ILP 规模过大, 求解时间过长. 考虑到大多数算术运算都是无副作用 (无状态的), 并且通常的计算模式是先加载数据, 然后进行一系列计算, 最后存回内存. 因此可以衍生出两种常见的语句划分方式:

按照代码的控制流结构划分, 即每个基本块 (Basic Block) 对应一个 SCoP 语句. 因为在 SCoP 内部, 不同基本块几乎就代表着代码属于不同的迭代域, 这是最自然也是最简单的划分方式.
按照 Store 指令划分. 由于 Load 实际上是无副作用 (非破坏性的), 它们的位置调整相对灵活. 因此可以先扫描同一个基本块中的所有指令, 每遇到一条 Store 指令, 就向前回溯, 找出它所依赖的所有指令 (包括 Load 和计算指令, 但必须在同一个基本块中), 将它们都划分到同一个 SCoP 语句中. 这样做能获得更细粒度的语句划分, 调度起来更灵活一些. 但问题是这样划分可能出现同一条指令/操作同时属于多个 SCoP 语句的情况, 可能需要额外的处理.

但不管是哪一种划分方式, 基本的原则都是在跨越不同基本块的时候, 必须进行一次硬切割, 因为不同基本块意味着不同的迭代域, 同一个 SCoP 语句内的所有操作必须同属一个迭代域.

我们用最经典的 GEMM (通用矩阵乘) 来说明多面体模型的基本概念. 下面是一个简单的矩阵乘法代码示例:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        C[i][j] = 0;
        for (int k = 0; k < K; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

在这个例子中, 我们有三个嵌套循环, 迭代变量分别是 i, j, k. 迭代范围分别是 0 <= i < M, 0 <= j < N, 0 <= k < K. 如果把所有可能的 (i,j,k) 组合表示出来, 就构成它的迭代域 (Iteration Domain):

\{ (i,j,k) \mid 0 \leq i < M, 0 \leq j < N, 0 \leq k < K \}

这刚好就是三维空间中的一个长方体, 它是一个多面体(Polyhedron). 也就是说, 我们可以将每一次迭代视作一个多维空间中的点, 而所有迭代点的集合则构成了一个多面体.

接着我们来看内存访问. 在这个例子中, 一共访问了三块不同的内存区域 A, B, C (假设它们之间不存在重叠). 这三个区域的访问点和迭代变量之间的映射关系如下:

A[i][k] 对应 $f_A(i,j,k) \mapsto (i,k)$
B[k][j] 对应 $f_B(i,j,k) \mapsto (k,j)$
C[i][j] 对应 $f_C(i,j,k) \mapsto (i,j)$

显然这些函数都是关于迭代变量的仿射函数 (Affine Function), 它指的是输出元组完全由输入元组的线性组合加上一个常数项构成, 例如:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        int x = A[3 * i + 2 * j + 5];
        // ...
    }
}

这里对 A 的访问也是一个仿射函数 $f(i,j) \mapsto 3i + 2j + 5$ .

但这种情况下不是一个仿射函数:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        int x = A[i * j];
    }
}

这里对 A 的访问是一个乘法运算, 不是线性组合, 因此不是仿射函数. 同时, 如果对数组的访问无法在编译期确定, 也就是索引是动态计算值, 同样不能用仿射函数表达这次内存访问.

利用仿射函数的性质, 我们可以精确计算不同内存访问之间的数据依赖关系 (Data Dependency). 所谓数据依赖关系, 就是在不同的时刻对同一个内存地址进行读写操作时, 这些操作之间的先后顺序关系. 如果从仿射函数的角度来看, 数据依赖也就是存在至少两个不同的迭代点 $(i_1, j_1, k_1)$ 和 $(i_2, j_2, k_2)$ , 其中第一个迭代点(称为源点, Source)早于第二个迭代点(称为汇点, Sink)发生, 在某个内存访问函数 $f$ 下映射到同一个内存地址:

\vec{p}_1 = (i_1, j_1, k_1) \\ \vec{p}_2 = (i_2, j_2, k_2) \\ f(\vec{p}_1) = f(\vec{p}_2)

那么我们就说在迭代点 $\vec{p}_1$ 和 $\vec{p}_2$ 之间存在数据依赖关系, 并且定义 $\vec{d} = \vec{p}_2 - \vec{p}_1$ (即汇点减去源点) 为依赖向量 (Dependency Vector). 根据这个定义, 不难得知如果依赖向量在某一个维度上是零, 那么就说明在这个维度上没有数据依赖关系, 因此在这个维度上的不同迭代之间可以并行执行.

但我们现在只知道这两个迭代点之间存在依赖关系, 但谁依赖谁呢? 换句话说, 我们需要确定程序的原始语义 (Lexical Order), 它表示不同迭代点之间的执行顺序. 对于上面的 GEMM 例子, 可以用以下的结构来表达:

domain: "[P2, P1, P0] -> { S0[i0, i1, i2] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }"
child:
  schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i0)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
  child:
    schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i1)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
    child:
      schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i2)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"

第一行 domain 定义了整个迭代空间, 也就是最开头提到的多面体. 后续的 schedule 则定义了不同维度上的执行顺序, 首先是 i0 (对应 i), 然后是 i1 (对应 j), 最后是 i2 (对应 k).

这被称为原始程序的调度树 (Schedule Tree). 调度树的每一层都对应一个循环维度, 从外到内表示循环的嵌套关系. 通过调度树, 我们可以清晰地看到不同迭代点之间的执行顺序. 调度树的另一种等价表达方式是调度映射 (Schedule Map), 它为每个迭代点分配一个时间戳, 表示它的执行顺序.

看这个例子:

void atax(float A[4096][4096], float x[4096], float y[4096]) {
    for (int i = 0; i < 4096; i++) {
        y[i] = 0;
    }
    for (int j = 0; j < 4096; j++) {
        for (int i = 0; i < 4096; i++) {
            y[j] += A[i][j] * x[i];
        }
    }
}

它的原始调度树是:

domain: "{ S0[i0] : 0 <= i0 <= 4095; S1[i0, i1] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }"
child:
  sequence:
  - filter: "{ S0[i0] }"
    child:
      schedule: "[{ S0[i0] -> [(i0)] : 0 <= i0 <= 4095 }]"
  - filter: "{ S1[i0, i1] }"
    child:
      schedule: "[{ S1[i0, i1] -> [(i0)] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }]"
      child:
        schedule: "[{ S1[i0, i1] -> [(i1)] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }]"

显然这里有两个独立的循环嵌套, 并且第二个循环嵌套在第一个循环嵌套之后执行. 这个调度树对应的等价调度映射是:

S0[i0] -> [o0, o1, o2] : o0 = 0 and o1 = i0 and o2 = 0 and i0 >= 0 and i0 <= 4095
S1[i0, i1] -> [o0, o1, o2] : o0 = 1 and o1 = i0 and o2 = i1 and i0 >= 0 and i0 <= 4095 and i1 >= 0 and i1 <= 4095;

调度映射实际上将每一个迭代点映射到一个带额外时间维度的元组上. 在这里, 为了区分两个独立的循环嵌套在一个维度上的先后顺序, 在它前面插入了一个额外的时间戳 o0, 第一个循环嵌套的 o0 恒为 0, 第二个循环嵌套的 o0 恒为 1. 这样表达出第一个循环嵌套在第二个循环嵌套之前执行的语义.

到此, 多面体调度中的三大元素: 迭代域, 内存访问函数, 调度树/调度映射都已经介绍完毕. 利用这三大元素, 我们可以精确地分析程序的执行顺序和数据依赖关系, 并且可以在此基础上进行各种复杂的循环变换 (Loop Transformations), 以提高程序的并行性和数据局部性 (Data Locality).

计算数据依赖

回到 GEMM 的例子中研究累加操作. 累加需要加载 C[i][j], 然后进行加法运算, 最后存回 C[i][j]. 我们考虑 Load 和 Store 之间的依赖关系. 首先是 RAW (Read After Write) 依赖, 即先写后读. 在这种情况下, 源点是 Store 操作所在的迭代点, 记为 $\vec{p}_1 = (i_1, j_1, k_1)$ , 汇点是 Load 操作所在的迭代点, 记为 $\vec{p}_2 = (i_2, j_2, k_2)$ . 数据依赖发生的前提是两次操作访问同一个内存地址:

f_C(i_1, j_1, k_1) = f_C(i_2, j_2, k_2) \Rightarrow (i_1, j_1) = (i_2, j_2)

并且根据词典序, 源点必须早于汇点:

\vec{p}_1 \prec \vec{p}_2 \Rightarrow (i_1 < i_2) \lor (i_1 = i_2 \land j_1 < j_2) \lor (i_1 = i_2 \land j_1 = j_2 \land k_1 < k_2)

结合这两个条件, 依赖向量可以计算得到

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

因此在 i 和 j 维度上没有数据依赖关系, 但在 k 维度上存在 RAW 依赖关系. 通常取最小的依赖距离作为依赖向量, 在这里就是 $\vec{d} = (0, 0, 1)$ . 因此在 GEMM 中, k 维度上存在距离为 1 的 RAW 依赖, 这表明写操作不能被提前到读操作之前执行.

接着考虑 WAR (Write After Read) 依赖, 即先读后写. 在这种情况下相反, 源点是 Load 操作所在的迭代点, 记为 $\vec{p}_1 = (i_1, j_1, k_1)$ , 汇点是 Store 操作所在的迭代点, 记为 $\vec{p}_2 = (i_2, j_2, k_2)$ . 数据依赖发生的前提同样是两次操作访问同一个内存地址. 类似上面的推导, 计算出依赖向量

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

同样在 i 和 j 维度上没有数据依赖关系, 但在 k 维度上存在 WAR 依赖关系. 取最小的依赖距离作为依赖向量, 在这里也是 $\vec{d} = (0, 0, 1)$ . 因此在 GEMM 中, k 维度上也存在距离为 1 的 WAR 依赖, 这表明读操作不能被延后到写操作之后执行.

最后考虑 WAW (Write After Write) 依赖, 即两次写入之间的依赖. 在这种情况下, 源点是第一次 Store 操作所在的迭代点, 记为 $\vec{p}_1 = (i_1, j_1, k_1)$ , 汇点是第二次 Store 操作所在的迭代点, 记为 $\vec{p}_2 = (i_2, j_2, k_2)$ . 根据上面的推导, 同样可以计算出依赖向量

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

这说明在 i 和 j 维度上没有数据依赖关系, 但在 k 维度上存在 WAW 依赖关系. 取最小的依赖距离作为依赖向量, 在这里也是 $\vec{d} = (0, 0, 1)$ . 因此在 GEMM 中, k 维度上也存在距离为 1 的 WAW 依赖, 这表明两次写操作之间必须保持顺序执行.

综上所述, 在 GEMM 中, k 维度上存在距离为 1 的 RAW, WAR 和 WAW 依赖关系. 这表明在 k 维度上存在非常严重的数据依赖, 因此无法对 k 维度进行简单并行化处理. 但 i 和 j 维度上可以直接简单并行化.

还有一种依赖关系是 RAR (Read After Read), 即两次读操作之间的依赖. 在大多数情况下这种依赖关系都不需要考虑, 因为读操作本身是无副作用的, 它们之间的执行顺序并不影响程序的正确性. 除非有显式的内存屏障 (Memory Barrier) 或同步操作, 又或者在考虑数据复用的情况下, 否则 RAR 依赖通常可以忽略.

在编译器的数据依赖分析中, RAW 又通常称为真依赖 (True Dependency), 它是制约程序并行化最主要的瓶颈. WAR 则通常称为反依赖 (Anti Dependency), WAW 则称为输出依赖 (Output Dependency). 反依赖和输出依赖通常可以通过寄存器重命名 (Register Renaming) 或内存版本化 (Memory Versioning) 等技术来消除, 对并行化的影响相对较小. 因此在优化的过程中重点考虑的是真依赖.

在上面几个例子中, 计算出来的依赖向量都是正的, 那依赖向量有没有可能是负的呢? 准确而言, 依赖向量的分量可以是负的, 但整个依赖向量必须保证词典序正. 例如 $(0,1,-5)$ 是合法的依赖向量, 因为第一个非零分量是正数, 表明源点在第二个维度上早于汇点发生, 那无论第三个维度上是正是负, 源点都是早于汇点的. 但 $(0,-1,5)$ 就是不合法的依赖向量, 因为第一个非零分量是负数, 表明源点在第二个维度上晚于汇点发生, 那无论第三个维度上是正是负, 源点都是晚于汇点的. 而原始的程序语义就要求了源点必须早于汇点发生, 因此这种依赖向量是不合法的. 总而言之, 一个依赖向量是否合法, 看它第一个非零分量的符号即可.

Pluto 算法

Pluto 算法是目前多面体编译中最为著名和广泛应用的算法之一. LLVM/Polly 使用的 ISL 库就是 Pluto 算法的一些变种实现. 下面介绍 Pluto 算法.

算法的核心目标是, 在满足程序原始语义的前提下 (也就是尊重所有有效性依赖), 通过重新安排循环调度 (通过各种循环变换, 例如循环交换和倾斜), 同时实现最大化并行度和最佳数据局部性 (最小化依赖距离). 这个问题可以形式化为一个整数线性规划问题 (ILP, Integer Linear Programming), 从而获得超越传统启发式方法的优化效果.

数学推导过程如下:

对于程序中的每一个语句 $S$ , 将它的迭代向量记为 $\vec{p}$ . 接着寻找一个形如下式的线性调度函数 $\Phi_S (\vec{p})$ , 它将原始迭代向量映射到一个新空间中:

\Phi_S (\vec{p}) = M_S\vec{p} + \vec{c}_{0,S}

其中矩阵 $M_S$ 就是变换系数矩阵, 例如对一个二维迭代变量, 矩阵

M_S = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}

就是将两个迭代变量交换的变换.

接着为了保证程序的正确性, 给定一个合法性约束(Validity Constraint)集合, 其中的每一个约束都对应程序中的一个数据依赖 $\vec{d}$ . 这些约束在新调度下必须同样保持合法. 通常 RAW, WAR 和 WAW 依赖都需要保持合法, 而 RAR 由于没有任何破坏性操作,通常可以忽略不计. 设 $\vec{d} = \vec{p}_2 - \vec{p}_1$ 是原始调度下的依赖向量, 这里 $\vec{p}_1$ , $\vec{p}_2$ 不一定属于相同的语句 $S$ , 那么

\vec{d}' = \Phi_{S_2} (\vec{p}_2) - \Phi_{S_1} (\vec{p}_1) \succeq \vec{0}

必须被满足. $\succeq \vec{0}$ 表示词典序非负, 也就是从左到右看第一个非零分量是否为正. 利用这个性质, 求解变换矩阵 $M_S$ 和偏置向量 $\vec{c}_{0,S}$ 可以转换成逐维度求解, 也就是对于每个维度 $n$ , 定义一个新的调度函数 $\phi_{S,n}$ , 形如

\phi_{S,n} (\vec{p}) = \vec{m}_{S,n} \cdot \vec{p} + c_{0,S,n}

其中 $\vec{m}_{S,n}$ 是矩阵 $M_S$ 的第 $n$ 行, $c_{0,S,n}$ 是偏置向量 $\vec{c}_{0,S}$ 的第 $n$ 个分量. 那么以上条件可以被分解为对第一个分量非零维度 $n$ 都有

\Delta(\vec{p_1}, \vec{p_2}) = \phi_{S_2,n} (\vec{p}_2) - \phi_{S_1,n} (\vec{p}_1) = (\vec{m}_{S_2,n} \cdot \vec{p_2} + c_{0,S_2,n}) - (\vec{m}_{S_1,n} \cdot \vec{p_1} + c_{0,S_1,n}) \geq 0

对任意数据依赖 $\vec{d}$ 都成立. 但在 Pluto 算法中, 它还要尽可能使得新循环能被 Tiling (分块) 优化. 因此在 Pluto 中实际上要求对每个维度都满足以上条件, 而不只是第一个非零分量.

接着利用 Farkas 引理 (Farkas Lemma) 的仿射形式, 即, 如果一个仿射函数 $f(\vec{x})$ 在多面体 $P = \{\vec{x} \mid A\vec{x} + \vec{b} \geq 0\}$ 上恒非负, 那么 $f(\vec{x})$ 一定可以表示为该多面体的约束的非负线性组合.

我们构造一个组合向量 $\vec{x} = [\vec{p_1}, \vec{p_2}]^\text{T}$ (也就是拼接两个迭代空间的维度). 根据仿射程序的定义, 原始数据依赖一定是源点和汇点的迭代向量的线性组合加上一个常数项, 因此根据原始数据依赖构造出的 $\vec{x}$ 可以构成一个形如 $P = \{\vec{x} \mid A \vec{x} + \vec{b} \geq 0\}$ 的多面体, 且在这个多面体上 $\Delta(\vec{x}) \geq 0$ 恒成立.

那利用 Farkas 引理, 存在一个非负向量 $\vec{\lambda} \geq 0$ 和非负标量 $\lambda_0$ , 使得

\Delta(\vec{x}) \equiv \vec{\lambda}^\text{T} (A \vec{x} + \vec{b}) + \lambda_0

展开后得到:

(\vec{m}_{S_2,n} \cdot \vec{p_2} + c_{0,S_2,n}) - (\vec{m}_{S_1,n} \cdot \vec{p_1} + c_{0,S_1,n}) = \lambda_0 + \lambda^\text{T} (A [\vec{p_1}, \vec{p_2}]^\text{T} + \vec{b})

比较两边系数得到

\vec{m}_{S_2,n} = A_{2}^\text{T} \vec{\lambda} \\ -\vec{m}_{S_1,n} = A_{1}^\text{T} \vec{\lambda} \\ c_{0,S_2,n} - c_{0,S_1,n} = \lambda_0 + \vec{b}^\text{T} \vec{\lambda}

其中 $A_{1}$ 和 $A_{2}$ 分别是矩阵 $A$ 中对应 $\vec{p_1}$ 和 $\vec{p_2}$ 的列子矩阵. 它们都是根据原始数据依赖计算得到的已知矩阵. $\vec{b}$ 也是已知向量. 于是到这里就消去了迭代变量 $\vec{p_1}$ 和 $\vec{p_2}$ , 得到了关于未知变量 $\vec{m}_{S,n}, c_{0,S,n}, \vec{\lambda}, \lambda_0$ 的一组线性方程组.

这么做的原因是迭代变量的取值范围通常非常大, 如果直接将它们的全体取值纳入 ILP 求解, 会导致 ILP 规模过大, 无法求解. 而通过 Farkas 引理, 可以将迭代变量消去, 从而大幅度减少 ILP 的规模.

到此, 我们得到了 ILP 的约束条件. 接着需要定义 ILP 的目标函数 (Objective Function). Pluto 的目标是增加数据局部性, 因此希望最小化依赖距离. 首先定义一个上界约束:

\delta(\vec{n}) = \vec{u} \cdot \vec{n} + w

使得对于每一对数据依赖, 都满足:

\phi_{S_2} (\vec{p}_2) - \phi_{S_1} (\vec{p}_1) \leq \delta(\vec{n})

那么 Pluto 的目标函数就是最小化 $\delta(\vec{n})$ , 也就是最小化 $\vec{u}, w$ . 结合上面的约束条件, 就得到了完整的 ILP 定义. 求解这个 ILP 就能得到这种建模下的最优循环调度, 而这种建模下的优化目标是最大化并行度和数据局部性.

ISL 简介

ISL (Integer Set Library) 是一个用于操作整数集合和关系的开源库, 并且提供了多面体优化的 Pluto 算法及其衍生算法实现. 非常适合用作多面体模型优化的基础工具. 应用比较广泛的多面体优化器例如 LLVM/Polly 和 GCC/Graphite 都是基于 ISL 实现的. ISL 原本是使用 C 编写的, 功能强大但是内存管理比较麻烦. 后来提供了 C++ 绑定 (利用 RAII 管理内存), 但 C++ 绑定不太完整, 缺乏一些常用的 API 封装. 因此后续将使用 C++ 绑定和 C API 混合使用的方式来介绍 ISL.

ISL 提供了一整套用于表示和操作整数集合和关系的 API, 例如集合 (Set), 映射 (Map), 仿射关系 (包括分段仿射), 调度树等基本数据结构以及对它们进行各种运算和分析的函数. 常见的数据结构包括:

isl::basic_set: 表示一个基本整数集合, 由一组线性不等式定义. 这个集合构成多维空间中的一个凸多面体 (Convex Polyhedron), 例如

{ S0[i0, i1, i2] : 0 <= i0 < 16 and 0 <= i1 < 16 and 0 <= i2 < 16 }

isl::set: 表示一个整数集合, 由多个基本集合的并集构成. 这个集合可以表示更复杂的多面体结构, 例如非凸多面体或有孔洞的多面体.

{ S0[i0]: (0 <= i0 < 8) or (10 <= i0 < 12) }

isl::union_set: 表示一组整数集合的并集, 也就是多个定义在不同空间上的 isl::set 的集合

{ S0[i0] : 0 <= i0 <= 4095; S1[i0, i1] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }

显然这三者之间可以从低到高安全地提升, 也就是 isl::basic_set -> isl::set -> isl::union_set. 但反之则需要进行额外的验证和转换.

isl::basic_map: 表示一个基本整数映射, 由一组线性不等式定义. 它表示从一个空间上定义的整数集合到另一个空间上定义的整数集合之间的映射关系. 源空间被称为域 (Domain), 目标空间被称为值域 (Range). 域和值域的维度数量不一定相同, 例如

{ S0[i0, i1, i2] -> M0[o0, o1] : o0 = i0 and o1 = i1 and 0 <= i0 < 16 and 0 <= i1 < 16 and 0 <= i2 < 16 }

isl::map: 表示一个整数映射, 由多个基本映射的并集构成. 它可以表示更复杂的映射关系, 例如非凸映射或有条件的映射.

{ S0[i0, i1] -> M0[o0, o1] : (o0 = i0 and o1 = i1 and 0 <= i0 < 8) or (o0 = i0 + 2 and o1 = i1 and 10 <= i0 < 12) }

isl::union_map: 表示一组整数映射的并集, 也就是多个定义在不同空间上的 isl::map 的集合.

{ S0[i0] -> M0[o0] : o0 = i0 and 0 <= i0 <= 4095; S1[i0, i1] -> M1[o0, o1] : o0 = i0 and o1 = i1 and 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }

同样这三者之间也可以从低到高安全地提升, 也就是 isl::basic_map -> isl::map -> isl::union_map. 反之则需要进行额外的验证和转换.

isl::schedule: 表示一个调度树, 它是多面体调度的核心数据结构. 调度树由多个节点 isl::schedule_node 组成, 常见的节点类型包括 Band Node (表示循环嵌套), Sequence Node (表示某些 SCoP 语句必须顺序执行), Set Node (表示某些 SCoP 语句执行先后无所谓), Filter Node (表示筛选出某些 SCoP 语句), Leaf Node (表示 SCoP 语句的终端节点) 等等. 通过调度树, 我们可以清晰地表示不同 SCoP 语句之间的执行顺序和嵌套关系. 例如这是一个 GEMM 的调度树:

domain: "[P2, P1, P0] -> { S0[i0, i1, i2] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }"
child:
  # Band Node
  schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i0)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
  child:
    # Band Node
    schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i1)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
    child:
      # Band Node
      schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i2)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"

如前面所述, 调度树可以使用等价的调度映射来表示, 也就是 isl::schedule 一定可以使用一个等价的 isl::union_map 来表示.

isl::aff: 表示一个简单的仿射函数, 它是从一个整数向量空间到一个标量的映射. 例如

{ [i0, i1] -> 3 * i0 + 2 * i1 + 5 }

isl::pw_aff: 表示一个分段 (Piecewise) 仿射函数, 它在同一个定义域空间内，根据不同的约束条件应用不同的 isl::aff. 例如在这个例子中, 当 i0 < 10 时使用第一个仿射关系, 否则使用第二个仿射关系.

{ [i0, i1] -> 3 * i0 + 2 * i1 + 5 : i0 < 10; [i0, i1] -> 4 * i0 + i1 + 2 : i0 >= 10 }

isl::multi_aff: 表示一个多维仿射映射, 它是从一个整数向量空间到另一个整数向量空间的映射. 和 isl::aff 类似, 但输出不一定是标量, 通常是向量. 例如

{ [i0, i1] -> [3 * i0 + 2 * i1 + 5, i0 - i1] }

isl::pw_multi_aff: 表示一个分段多维仿射映射, 它是由多个 isl::multi_aff 的分段定义构成的. 例如

{ [i0, i1] -> [i0 + 1, i1] : i0 < 10; [i0, i1] -> [i0, i1 + 1] : i0 >= 10 }

isl::multi_pw_aff: 表示一个分段仿射函数 isl::pw_aff 数组, 即 $(f_1, f_2, ..., f_n)$ , 每个 $f_i$ 都是一个分段仿射函数. 最终输出的结果也是一个 $n$ 维向量. 它在数学上和 isl::pw_multi_aff 是等价的, 但数据管理方式不同. 例如

[ { [i0, i1] -> i0 + i1 + 1 : i0 < 10; [i0, i1] -> i0 - i1 - 1 : i0 >= 10 },
  { [i0, i1] -> i0 + i1 : i0 < 10; [i0, i1] -> i0 - i1 : i0 >= 10 } ]

可以被等价用一个 isl::pw_multi_aff 表示为:

{ [i0, i1] -> [i0 + i1 + 1, i0 + i1] : i0 < 10; [i0, i1] -> [i0 - i1 - 1, i0 - i1] : i0 >= 10 }

isl:multi_pw_aff 方便提取输出空间的每个维度进行单独分析处理, 而 isl::pw_multi_aff 则更方便进行整体处理和变换.

isl::union_pw_aff: 表示一些定义在不同空间上的分段仿射函数 isl::pw_aff 的集合. 它允许你处理来自不同语句（如 S0, S1）的映射，每个映射返回一个标量.

[ { S0[i, j] -> i; S1[k] -> k }, { S0[i, j] -> j; S1[k] -> 2k } ]

isl::union_pw_multi_aff: 表示一些定义在不同空间上分段多维仿射映射 isl::pw_multi_aff 的集合. 和 isl::union_pw_aff 类似, 但每个映射返回一个多维向量. 例如

{ S0[i, j] -> [i+j, i-j]; S1[k] -> [k, 2k, k+1] }

isl:multi_union_pw_aff: 表示一个 isl::union_pw_aff 数组. 即 $(f_1, f_2, ..., f_n)$ , 每个 $f_i$ 都是一个 isl::union_pw_aff. 最终输出的结果也是一个 $n$ 维向量. 它在数学上和 isl::union_pw_multi_aff 是等价的, 但数据管理方式不同. 这个关系和 isl::multi_pw_aff 与 isl::pw_multi_aff 之间的关系是一样的, 例如

[ { S0[i, j] -> i; S1[k] -> k }, 
  { S0[i, j] -> j; S1[k] -> 2k } ]

可以被等价用一个 isl::union_pw_multi_aff 表示为:

{ S0[i, j] -> [i, j]; S1[k] -> [k, 2k] }

isl:multi_union_pw_aff 方便提取输出空间的每个维度进行单独分析处理, 而 isl::union_pw_multi_aff 则更方便进行整体处理和变换.

这几个数据结构之间的关系和提升规则就显得很绕了. 核心是理解 union, multi 和 pw 三个前缀的含义:

pw 表示分段 (Piecewise), 也就是在同一个定义域空间内, 根据不同的约束条件应用不同的映射关系. 所以不带 pw 的版本可以直接提升到带 pw 的版本, 但反之则需要进行额外的验证和转换.
multi 表示多维 (Multi-dimensional), 也就是输出是一个向量而不是标量. 所以不带 multi / union 的版本可以直接提升到带 multi 的版本, 但反之则需要进行额外的验证和转换.
union 表示联合 (Union), 也就是定义在不同空间上的多个映射关系的集合. 所以不带 multi/ union 的版本可以直接提升到带 union 的版本, 但反之则需要进行额外的验证和转换.
multi 可以通过对按输出维度进行拆分得到 union, union 将不同维度上的映射关系合并得到 multi. 因此 multi 和 union 之间是可以直接相互转换的.

不过弯弯绕绕, 最后感觉还是直接回来查表最快, 省的想来想去头晕 😇 .

到这里可能发现 Map 和 Aff 之间有点类似, 但一句话总结最大的区别就是, Aff 的一个输入点只能对应一个输出点, 而 Map 的一个输入点可以对应多个输出点. Aff 是一个仿射函数 (Affine Function), Map 是一个多值关系 (General Relation). 比如在 Map 里面这是合法的:

{ [i, j] -> [i', j'] : i' = i + 1 and j' > j }

这里对于同一个输入点 [i,j], 可以对应多个输出点 [i+1,j'], 其中 j' 可以取任意大于 j 的值. 但在 Aff 里面这是不合法的.

Back to Archives

Advanced FPGA HLS: Polyhedral Compiling

Fri Dec 19 2025

Fri Jan 02 2026

FPGA HLSPolyhedral CompilingLoop TransformationsParallelismData Locality

Advanced FPGA HLS: Polyhedral Compiling

基本概念

首先说明 SCoP (Static Control Part) 的概念. 如果有一段代码, 其控制流和内存访问模式在编译时都是可预测的, 那么它就可以被视为一个 SCoP.

// is valid SCoP boundary
for (int i = 0; i < N; i++)
    for (int j = 0; j < i; j++)
        // ...
// is NOT valid SCoP boundary
for (int i = 0; i < N; i++)
    for (int j = 0; j < (i*i); j++)
        // ...

if (i + j < N) // is valid SCoP condition
if (i % 2 == 0) // also valid, but need transforms
if (i*j < N) // is NOT valid SCoP condition

int a = A[i + 2*j + 3]; // is valid SCoP access
int b = B[i * j]; // is NOT valid SCoP access
int c = A[B[i]]; // is NOT valid SCoP access

按照代码的控制流结构划分, 即每个基本块 (Basic Block) 对应一个 SCoP 语句. 因为在 SCoP 内部, 不同基本块几乎就代表着代码属于不同的迭代域, 这是最自然也是最简单的划分方式.
按照 Store 指令划分. 由于 Load 实际上是无副作用 (非破坏性的), 它们的位置调整相对灵活. 因此可以先扫描同一个基本块中的所有指令, 每遇到一条 Store 指令, 就向前回溯, 找出它所依赖的所有指令 (包括 Load 和计算指令, 但必须在同一个基本块中), 将它们都划分到同一个 SCoP 语句中. 这样做能获得更细粒度的语句划分, 调度起来更灵活一些. 但问题是这样划分可能出现同一条指令/操作同时属于多个 SCoP 语句的情况, 可能需要额外的处理.

我们用最经典的 GEMM (通用矩阵乘) 来说明多面体模型的基本概念. 下面是一个简单的矩阵乘法代码示例:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        C[i][j] = 0;
        for (int k = 0; k < K; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

\{ (i,j,k) \mid 0 \leq i < M, 0 \leq j < N, 0 \leq k < K \}

A[i][k] 对应 $f_A(i,j,k) \mapsto (i,k)$
B[k][j] 对应 $f_B(i,j,k) \mapsto (k,j)$
C[i][j] 对应 $f_C(i,j,k) \mapsto (i,j)$

显然这些函数都是关于迭代变量的仿射函数 (Affine Function), 它指的是输出元组完全由输入元组的线性组合加上一个常数项构成, 例如:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        int x = A[3 * i + 2 * j + 5];
        // ...
    }
}

这里对 A 的访问也是一个仿射函数 $f(i,j) \mapsto 3i + 2j + 5$ .

但这种情况下不是一个仿射函数:

for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
        int x = A[i * j];
    }
}

\vec{p}_1 = (i_1, j_1, k_1) \\ \vec{p}_2 = (i_2, j_2, k_2) \\ f(\vec{p}_1) = f(\vec{p}_2)

domain: "[P2, P1, P0] -> { S0[i0, i1, i2] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }"
child:
  schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i0)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
  child:
    schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i1)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
    child:
      schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i2)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"

看这个例子:

void atax(float A[4096][4096], float x[4096], float y[4096]) {
    for (int i = 0; i < 4096; i++) {
        y[i] = 0;
    }
    for (int j = 0; j < 4096; j++) {
        for (int i = 0; i < 4096; i++) {
            y[j] += A[i][j] * x[i];
        }
    }
}

它的原始调度树是:

domain: "{ S0[i0] : 0 <= i0 <= 4095; S1[i0, i1] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }"
child:
  sequence:
  - filter: "{ S0[i0] }"
    child:
      schedule: "[{ S0[i0] -> [(i0)] : 0 <= i0 <= 4095 }]"
  - filter: "{ S1[i0, i1] }"
    child:
      schedule: "[{ S1[i0, i1] -> [(i0)] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }]"
      child:
        schedule: "[{ S1[i0, i1] -> [(i1)] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }]"

显然这里有两个独立的循环嵌套, 并且第二个循环嵌套在第一个循环嵌套之后执行. 这个调度树对应的等价调度映射是:

S0[i0] -> [o0, o1, o2] : o0 = 0 and o1 = i0 and o2 = 0 and i0 >= 0 and i0 <= 4095
S1[i0, i1] -> [o0, o1, o2] : o0 = 1 and o1 = i0 and o2 = i1 and i0 >= 0 and i0 <= 4095 and i1 >= 0 and i1 <= 4095;

计算数据依赖

f_C(i_1, j_1, k_1) = f_C(i_2, j_2, k_2) \Rightarrow (i_1, j_1) = (i_2, j_2)

并且根据词典序, 源点必须早于汇点:

\vec{p}_1 \prec \vec{p}_2 \Rightarrow (i_1 < i_2) \lor (i_1 = i_2 \land j_1 < j_2) \lor (i_1 = i_2 \land j_1 = j_2 \land k_1 < k_2)

结合这两个条件, 依赖向量可以计算得到

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

\vec{d} = \vec{p}_2 - \vec{p}_1 = (0, 0, d_k), d_k > 0

Pluto 算法

Pluto 算法是目前多面体编译中最为著名和广泛应用的算法之一. LLVM/Polly 使用的 ISL 库就是 Pluto 算法的一些变种实现. 下面介绍 Pluto 算法.

数学推导过程如下:

\Phi_S (\vec{p}) = M_S\vec{p} + \vec{c}_{0,S}

其中矩阵 $M_S$ 就是变换系数矩阵, 例如对一个二维迭代变量, 矩阵

M_S = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}

就是将两个迭代变量交换的变换.

\vec{d}' = \Phi_{S_2} (\vec{p}_2) - \Phi_{S_1} (\vec{p}_1) \succeq \vec{0}

\phi_{S,n} (\vec{p}) = \vec{m}_{S,n} \cdot \vec{p} + c_{0,S,n}

其中 $\vec{m}_{S,n}$ 是矩阵 $M_S$ 的第 $n$ 行, $c_{0,S,n}$ 是偏置向量 $\vec{c}_{0,S}$ 的第 $n$ 个分量. 那么以上条件可以被分解为对第一个分量非零维度 $n$ 都有

\Delta(\vec{p_1}, \vec{p_2}) = \phi_{S_2,n} (\vec{p}_2) - \phi_{S_1,n} (\vec{p}_1) = (\vec{m}_{S_2,n} \cdot \vec{p_2} + c_{0,S_2,n}) - (\vec{m}_{S_1,n} \cdot \vec{p_1} + c_{0,S_1,n}) \geq 0

那利用 Farkas 引理, 存在一个非负向量 $\vec{\lambda} \geq 0$ 和非负标量 $\lambda_0$ , 使得

\Delta(\vec{x}) \equiv \vec{\lambda}^\text{T} (A \vec{x} + \vec{b}) + \lambda_0

展开后得到:

(\vec{m}_{S_2,n} \cdot \vec{p_2} + c_{0,S_2,n}) - (\vec{m}_{S_1,n} \cdot \vec{p_1} + c_{0,S_1,n}) = \lambda_0 + \lambda^\text{T} (A [\vec{p_1}, \vec{p_2}]^\text{T} + \vec{b})

比较两边系数得到

\vec{m}_{S_2,n} = A_{2}^\text{T} \vec{\lambda} \\ -\vec{m}_{S_1,n} = A_{1}^\text{T} \vec{\lambda} \\ c_{0,S_2,n} - c_{0,S_1,n} = \lambda_0 + \vec{b}^\text{T} \vec{\lambda}

\delta(\vec{n}) = \vec{u} \cdot \vec{n} + w

使得对于每一对数据依赖, 都满足:

\phi_{S_2} (\vec{p}_2) - \phi_{S_1} (\vec{p}_1) \leq \delta(\vec{n})

ISL 简介

isl::basic_set: 表示一个基本整数集合, 由一组线性不等式定义. 这个集合构成多维空间中的一个凸多面体 (Convex Polyhedron), 例如

{ S0[i0, i1, i2] : 0 <= i0 < 16 and 0 <= i1 < 16 and 0 <= i2 < 16 }

isl::set: 表示一个整数集合, 由多个基本集合的并集构成. 这个集合可以表示更复杂的多面体结构, 例如非凸多面体或有孔洞的多面体.

{ S0[i0]: (0 <= i0 < 8) or (10 <= i0 < 12) }

isl::union_set: 表示一组整数集合的并集, 也就是多个定义在不同空间上的 isl::set 的集合

{ S0[i0] : 0 <= i0 <= 4095; S1[i0, i1] : 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }

显然这三者之间可以从低到高安全地提升, 也就是 isl::basic_set -> isl::set -> isl::union_set. 但反之则需要进行额外的验证和转换.

isl::basic_map: 表示一个基本整数映射, 由一组线性不等式定义. 它表示从一个空间上定义的整数集合到另一个空间上定义的整数集合之间的映射关系. 源空间被称为域 (Domain), 目标空间被称为值域 (Range). 域和值域的维度数量不一定相同, 例如

{ S0[i0, i1, i2] -> M0[o0, o1] : o0 = i0 and o1 = i1 and 0 <= i0 < 16 and 0 <= i1 < 16 and 0 <= i2 < 16 }

isl::map: 表示一个整数映射, 由多个基本映射的并集构成. 它可以表示更复杂的映射关系, 例如非凸映射或有条件的映射.

{ S0[i0, i1] -> M0[o0, o1] : (o0 = i0 and o1 = i1 and 0 <= i0 < 8) or (o0 = i0 + 2 and o1 = i1 and 10 <= i0 < 12) }

isl::union_map: 表示一组整数映射的并集, 也就是多个定义在不同空间上的 isl::map 的集合.

{ S0[i0] -> M0[o0] : o0 = i0 and 0 <= i0 <= 4095; S1[i0, i1] -> M1[o0, o1] : o0 = i0 and o1 = i1 and 0 <= i0 <= 4095 and 0 <= i1 <= 4095 }

同样这三者之间也可以从低到高安全地提升, 也就是 isl::basic_map -> isl::map -> isl::union_map. 反之则需要进行额外的验证和转换.

isl::schedule: 表示一个调度树, 它是多面体调度的核心数据结构. 调度树由多个节点 isl::schedule_node 组成, 常见的节点类型包括 Band Node (表示循环嵌套), Sequence Node (表示某些 SCoP 语句必须顺序执行), Set Node (表示某些 SCoP 语句执行先后无所谓), Filter Node (表示筛选出某些 SCoP 语句), Leaf Node (表示 SCoP 语句的终端节点) 等等. 通过调度树, 我们可以清晰地表示不同 SCoP 语句之间的执行顺序和嵌套关系. 例如这是一个 GEMM 的调度树:

domain: "[P2, P1, P0] -> { S0[i0, i1, i2] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }"
child:
  # Band Node
  schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i0)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
  child:
    # Band Node
    schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i1)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"
    child:
      # Band Node
      schedule: "[P2, P1, P0] -> [{ S0[i0, i1, i2] -> [(i2)] : 0 <= i0 < P2 and 0 <= i1 < P1 and 0 <= i2 < P0 }]"

如前面所述, 调度树可以使用等价的调度映射来表示, 也就是 isl::schedule 一定可以使用一个等价的 isl::union_map 来表示.

isl::aff: 表示一个简单的仿射函数, 它是从一个整数向量空间到一个标量的映射. 例如

{ [i0, i1] -> 3 * i0 + 2 * i1 + 5 }

isl::pw_aff: 表示一个分段 (Piecewise) 仿射函数, 它在同一个定义域空间内，根据不同的约束条件应用不同的 isl::aff. 例如在这个例子中, 当 i0 < 10 时使用第一个仿射关系, 否则使用第二个仿射关系.

{ [i0, i1] -> 3 * i0 + 2 * i1 + 5 : i0 < 10; [i0, i1] -> 4 * i0 + i1 + 2 : i0 >= 10 }

isl::multi_aff: 表示一个多维仿射映射, 它是从一个整数向量空间到另一个整数向量空间的映射. 和 isl::aff 类似, 但输出不一定是标量, 通常是向量. 例如

{ [i0, i1] -> [3 * i0 + 2 * i1 + 5, i0 - i1] }

isl::pw_multi_aff: 表示一个分段多维仿射映射, 它是由多个 isl::multi_aff 的分段定义构成的. 例如

{ [i0, i1] -> [i0 + 1, i1] : i0 < 10; [i0, i1] -> [i0, i1 + 1] : i0 >= 10 }

isl::multi_pw_aff: 表示一个分段仿射函数 isl::pw_aff 数组, 即 $(f_1, f_2, ..., f_n)$ , 每个 $f_i$ 都是一个分段仿射函数. 最终输出的结果也是一个 $n$ 维向量. 它在数学上和 isl::pw_multi_aff 是等价的, 但数据管理方式不同. 例如

[ { [i0, i1] -> i0 + i1 + 1 : i0 < 10; [i0, i1] -> i0 - i1 - 1 : i0 >= 10 },
  { [i0, i1] -> i0 + i1 : i0 < 10; [i0, i1] -> i0 - i1 : i0 >= 10 } ]

可以被等价用一个 isl::pw_multi_aff 表示为:

{ [i0, i1] -> [i0 + i1 + 1, i0 + i1] : i0 < 10; [i0, i1] -> [i0 - i1 - 1, i0 - i1] : i0 >= 10 }

isl:multi_pw_aff 方便提取输出空间的每个维度进行单独分析处理, 而 isl::pw_multi_aff 则更方便进行整体处理和变换.

isl::union_pw_aff: 表示一些定义在不同空间上的分段仿射函数 isl::pw_aff 的集合. 它允许你处理来自不同语句（如 S0, S1）的映射，每个映射返回一个标量.

[ { S0[i, j] -> i; S1[k] -> k }, { S0[i, j] -> j; S1[k] -> 2k } ]

isl::union_pw_multi_aff: 表示一些定义在不同空间上分段多维仿射映射 isl::pw_multi_aff 的集合. 和 isl::union_pw_aff 类似, 但每个映射返回一个多维向量. 例如

{ S0[i, j] -> [i+j, i-j]; S1[k] -> [k, 2k, k+1] }

isl:multi_union_pw_aff: 表示一个 isl::union_pw_aff 数组. 即 $(f_1, f_2, ..., f_n)$ , 每个 $f_i$ 都是一个 isl::union_pw_aff. 最终输出的结果也是一个 $n$ 维向量. 它在数学上和 isl::union_pw_multi_aff 是等价的, 但数据管理方式不同. 这个关系和 isl::multi_pw_aff 与 isl::pw_multi_aff 之间的关系是一样的, 例如

[ { S0[i, j] -> i; S1[k] -> k }, 
  { S0[i, j] -> j; S1[k] -> 2k } ]

可以被等价用一个 isl::union_pw_multi_aff 表示为:

{ S0[i, j] -> [i, j]; S1[k] -> [k, 2k] }

isl:multi_union_pw_aff 方便提取输出空间的每个维度进行单独分析处理, 而 isl::union_pw_multi_aff 则更方便进行整体处理和变换.

这几个数据结构之间的关系和提升规则就显得很绕了. 核心是理解 union, multi 和 pw 三个前缀的含义:

pw 表示分段 (Piecewise), 也就是在同一个定义域空间内, 根据不同的约束条件应用不同的映射关系. 所以不带 pw 的版本可以直接提升到带 pw 的版本, 但反之则需要进行额外的验证和转换.
multi 表示多维 (Multi-dimensional), 也就是输出是一个向量而不是标量. 所以不带 multi / union 的版本可以直接提升到带 multi 的版本, 但反之则需要进行额外的验证和转换.
union 表示联合 (Union), 也就是定义在不同空间上的多个映射关系的集合. 所以不带 multi/ union 的版本可以直接提升到带 union 的版本, 但反之则需要进行额外的验证和转换.
multi 可以通过对按输出维度进行拆分得到 union, union 将不同维度上的映射关系合并得到 multi. 因此 multi 和 union 之间是可以直接相互转换的.

不过弯弯绕绕, 最后感觉还是直接回来查表最快, 省的想来想去头晕 😇 .

{ [i, j] -> [i', j'] : i' = i + 1 and j' > j }

这里对于同一个输入点 [i,j], 可以对应多个输出点 [i+1,j'], 其中 j' 可以取任意大于 j 的值. 但在 Aff 里面这是不合法的.