前言与阅读路线

本教程讨论 Presburger 算术如何成为 polyhedral analysis 的表示语言，并把表示、依赖、调度和代码生成放进一条连续推理链。读者应熟悉线性代数、离散数学和一阶逻辑的基本记号，并已见过简单循环优化或 Polyhedral Model 的最小例子；无需预先掌握整数规划或完整的编译器实现。

这里的 Presburger Algebra 是一个教学用简称：它指 Presburger 可定义集合/关系及其并、交、补、投影、逆、复合、像和逆像等闭包运算。它不是一个独立于 Presburger arithmetic 的标准理论名称。全文还会明确区分自然数版与整数版 Presburger 算术、实数多面体与其整数格点、单个凸多面体与一般 Presburger 集合。

十二章路径

1. Polyhedral Model 的最小回顾：从静态控制部分、语句实例和参数出发，说明为什么循环优化关心整数格点。
2. Presburger 算术的语法与语义：区分自然数与整数版本，建立加法、序、量词、整除和同余的边界。
3. 可判定性、量词消去与表达能力：解释可判定性、Cooper 消元、投影及变量乘法和间接访问的表达边界。
4. Presburger 集合与关系代数：学习集合、映射、关系、逆、复合、像、逆像、投影和词典序。
5. 半线性集合、格点与多面体：区分半线性等价、凸多面体、整数点、析取和周期结构。
6. 循环程序的关系建模：把迭代域、读写访问、语句身份和原始顺序写成关系。
7. 数据依赖分析：从同址候选到精确 RAW、WAR、WAW 和最后写入者，包含归约的边界。
8. 仿射调度：用整数时间戳和词典序表示顺序，区分合法性、并行性与局部性。
9. Farkas 引理与调度约束有限化：把“对所有依赖实例”成立的条件转成有限系数约束，并定位整数规划的角色。
10. 调度变换：比较 interchange、fusion、distribution、skewing、strip-mining、tiling 和 wavefront 的合法性与性能目标。
11. 扫描与代码生成：从调度像空间扫描整数点，恢复含 floor、ceil、min、max、步长和参数分支的循环 AST。
12. 端到端案例与工具表示：以二维时间—空间 stencil 串联 SCoP 识别、建模、依赖、调度、变换、AST 与 isl/Omega 风格表示。

三种阅读方式

数学主线：按第 2 → 3 → 4 → 5 → 9 → 11 章阅读，再以第 12 章检查这些定义怎样落到程序。它适合希望先建立可表达性、消元、关系运算和整数点语义的人。

编译器主线：按第 1 → 6 → 7 → 8 → 10 → 11 → 12 章阅读；遇到符号或定理时回看第 2、4、5、9 章。它适合已有循环优化直觉、希望追踪编译器调用链的人。

完整主线：从第 1 章顺序读到第 12 章。每章都依照“直觉 → 形式定义 → 手算示例 → 编译器用途 → 常见误区 → 练习”的模板推进；二维时间—空间 stencil 是贯穿案例，矩形域、三角域、同余/步长、析取、多语句、归约与非仿射反例用于检验边界。

开始第 1 章前，尤其要记住：依赖关系恒写作 source → sink，且实数多面体 $P$ 与整数点集 P ∩ ℤ^d 不可混用。全书统一记号可随时查阅附录中的术语与符号速查，原始论文与官方工具资料按学习目标整理在延伸阅读路径中；附录还给出全部 78 道练习的参考答案。