Halide 调度入门：算法与调度分离的编程模型与三个性能杠杆-平芜编程栈

编译器
图像处理
编程语言
高性能计算

【免费下载链接】Halide

a language for fast, portable>项目地址：https://gitcode.com/gh_mirrors/ha/Halide

Halide 是一门面向快速、可移植数据并行计算的语言，它的核心设计是把每一个程序拆成**算法（Algorithm）与调度（Schedule）**两个独立编写的部分。本文基于仓库内调度指南的引言章节，讲解这两个部分各是什么、为什么这种拆分如此重要、调度究竟影响哪些性能要素，并给出本指南四大部分的完整导读，帮助你在编写或优化 Halide 调度时快速建立正确的思维框架。

一切程序都由两部分组成

Halide 程序始终被拆成两个部分分别编写，而"保持二者分离"正是这门语言工作机制的核心：

第一部分是算法（Algorithm）。算法只描述"每个值是什么"，完全不涉及"这个值怎么被算出来"。程序声明Func，并把它们定义为参数Var的纯函数，还可以附加可选的**更新定义（update definitions）**来细化这些值。在这一阶段，描述就是纯粹的数学，对执行方式只字未提。

第二部分是调度（Schedule）。调度描述"每个值在何时、何地（哪个循环层级）被计算和存储"。调度由附着在每个Func上的指令（directive）构成，例如compute_root、compute_at、vectorize等。所有性能决策都集中在调度这一层。

以仓库内调度技能的核心说明（.claude/skills/scheduling/SKILL.md）为证，Halide 将每个程序拆为"算法（每个值是什么）"与"调度（每个值何时何地被计算和存储）"两部分，这一表述与指南引言完全一致。调度 API 的实际声明位于 src/Func.h 与 src/Schedule.h，而真正消费这些调度的流水线则集中在 src/ScheduleFunctions.cpp、src/Bounds.cpp 与 src/BoundsInference.cpp 中。

算法部分的代码形态

算法部分的典型写法如下（取自指南第二章 The Programming Model）：

Func hist("hist"); hist(x) = 0; // 第 0 阶段：纯（初始）定义 RDom r(0, N, "r"); hist(in(r)) += 1; // 第 1 阶段：更新定义

初始定义加上后续的更新定义，构成一个有序的阶段（stage）列表：s0（纯定义）、s1等。每个阶段完成后下一个阶段才开始，它们写入同一块存储。阶段属于算法的一部分，它们说明"这个 Func 是什么"，因此理解它们不需要任何调度知识。但每个阶段仍会被独立调度，通过f.update(n)指定（见 Reshaping Loops）。

调度部分的代码形态

调度则是对这些Func附加指令。一个典型调度（同样来自指南，见 Scheduling for CPUs）：

output.split(y, yo, yi, /*strip*/ 32) .reorder(x, yi, c, yo) // 向量化轴在最内层 .vectorize(x, vec) .parallel(yo); producer_1.compute_at(output, yo).vectorize(x, vec); producer_2.compute_at(output, yo).vectorize(x, vec);

可以注意到：算法部分一字未动，调度部分通过链式调用直接修改的是"怎么算"而非"算什么"。

这种拆分为什么有用：调度永远不能改变结果

让"算法/调度"分离如此有价值的根本原因在于：对给定的算法和输入，无论怎么调度，结果都是一样的——除了舍入或溢出这类细微的浮点效应。这为性能优化留下了巨大空间：计算可以被大胆重排以换取速度，而不用担心悄悄改变程序的计算结果。

需要精确理解的是"一样"的含义：

整数运算在任意调度下结果逐位一致；
浮点运算可能因求值顺序不同产生舍入、溢出等微小差异；
除此之外，调度的自由度是"无损"的——这也是为什么 Halide 敢于激进地重排、融合、并行化。

调度真正影响的只有三件事

既然调度不改变结果，那它到底改变什么？引言把调度的影响归结为三个杠杆：

值被计算的顺序（order）——循环的拆分、重排、融合决定了求值次序；
发生了多少冗余重算（redundant recomputation）——compute_root会整块预计算，compute_at会把中间结果内联到消费者循环里反复重算，store_at则可能让滑动窗口复用避免重算；
流水线需要多少临时存储（temporary storage）——中间结果何时分配、分配多大、能否通过折叠（fold_storage）变成循环缓冲。

这三个杠杆几乎承载了全部的性能收益。一个漫不经心的调度与一个精心设计的调度之间，性能差距可以是数量级的；更极端的是，一个选错的调度甚至可能无法编译——但它在语义上计算的仍是完全相同的东西。这三重杠杆的概念也在 directive-cheatsheet 中得到一一对应：compute_root/compute_at管计算位置，store_at/store_root/hoist_storage/fold_storage管存储位置，split/fuse/tile/reorder/parallel/vectorize/unroll管循环形状与执行方式。

调度到底控制什么

对于每一个Func，以及它的每一个阶段，调度需要决定四类事情：

在哪里计算（Where it's computed）：内联到它的消费者里；在消费者的某个循环层级计算；还是在最顶层一次算完（Halide 称之为 "root"）。
存储在哪里（Where its storage lives）：存储可以位于比计算更粗的循环层级上——这正是滑动窗口能够复用一个中间值的机制。注意store_at与compute_at是相互独立的两个决策，存储比计算粗粒度，恰恰是滑动窗口复用的来源（这也是 cheatsheet 里专门点出的陷阱之一）。
循环如何塑形（How its loops are shaped）：循环可以被split（拆分）、tile（分块）、reorder（重排），还可以被标记为parallel（并行）、vectorize（向量化）或unroll（展开）。
存储如何布局（How its storage is laid out）：内存中的维度顺序可以通过reorder_storage改变，从而匹配访问模式。

后面的章节会逐一展开这些维度。就引言而言，最需要记住的结论是：调度是一组彼此独立的、按 Func 逐个做出的选择——计算位置、存储位置、循环形状、存储布局互不绑定，可以单独调整。

从源码看，这四类决策被组织为Func上的不同方法族。在 src/Func.h 中可以看到它们成组出现：计算位置相关（如 273–327 行的compute_at/compute_root文档示例）、存储相关（store_at/store_root）、循环塑形（split/fuse/tile/reorder）、执行方式（parallel/vectorize/unroll），以及 1091 行的print_loop_nest()声明——它打印调度产生的循环结构，是验证"调度是否做对了"的第一工具。

一个具体的验证手段：print_loop_nest()

调度是否真的如你所想？不要靠猜，直接打印循环嵌套。指南的惯例是所有示例都构建一个小int main()，调用Func::print_loop_nest()观察调度产生的循环结构（见 Reading a Loop Nest）。这在教程中有完整演示，例如 tutorial/lesson_05_scheduling_1.cpp 从第 57 行起，对默认（行优先）调度打印伪代码循环，随后逐步叠加reorder、split、vectorize、parallel、tile等指令并反复打印循环结构，直观展示每个指令对循环嵌套的改变。

指南还强调：Part III 会忽略print_loop_nest()输出中的两类内容——具体的循环变量名和常量循环边界。前者不影响结构，后者来自**边界推断（bounds inference）**而非调度结构本身（详见 Bounds Inference）。

本指南覆盖范围：四大部分导读

调度指南（指南首页 README）把全部内容组织成四个部分，引言对此做了总览：

Part I：模型（The Model）——被调度的对象与流水线的实现

这一部分打地基，回答"到底在调度什么、流水线如何被实现、缓冲区与循环的边界从哪来"：

Introduction：算法与调度的关系，以及调度控制什么（即本文）；
The Programming Model：Func、阶段（stages）、RDom、RVar、ImageParam、Expr等对象，以及它们组成的流水线图（pipeline graph）——Func之间通过 producer 边连接成有向无环图，被realize/print_loop_nest调用的那个Func是输出，所有可达对象构成流水线，其余一概不算；
Realizing a Pipeline：计算何时真正运行；realize()触发 JIT，AOT 则编译为对象文件加 C 头文件，纯 AOT 部署可只链接halide-runtime而彻底去掉编译器与 LLVM 依赖；实现流程依次是边界推断 → 临时内存分配 → 线程池激活 → 计算与存储 → 释放；
Bounds Inference：由输出请求反向推导每个输入与中间Func的所需区域——以三抽头模糊blur(x) = (input(x-1)+input(x)+input(x+1))/3.0f为例，请求blur在x ∈ [0,99]，推断出input必须在[-1,100]有效，外部缓冲不足时由BoundaryConditions包装（repeat_edge、mirror_image等）保证越界安全。

Part II：策略（Strategy）——给一条流水线，什么样的调度值得写

这一部分是"通往跑得快调度的快车道"，回答"该修哪里、怎么看出来"：

Scheduling for CPUs：几乎每个快速 CPU 流水线最终都是同一形状——一个外层并行循环 + 沿 stride-1 轴向量化 + 每个非平凡中间量都compute_at进并行循环内部。校验方法：profiler 中流水线级parallel loops应为 1；
Scheduling for GPUs：把循环映射到 GPU 的 block 与 thread（gpu_tile/gpu_blocks/gpu_threads等）；
What to Schedule：inline 与compute_at与compute_root如何取舍；
Benchmarking & Profiling：测量并读懂 profile，HL_TARGET=host-profile输出按 Func 统计的 profiler 表；
Reading the .stmt File：核对向量化形状；
Recipes：滑动窗口、分块、金字塔、stencil 链、直方图等经典配方；
Pitfalls：递推（recurrence）、并行放置、重算倍数等常见陷阱。

Part III：机制（Mechanics）——给定一个调度，它实际产出什么样的循环嵌套

这一部分逐条讲解每个指令的确切效果，从读Func::print_loop_nest()输出开始：

Reading a Loop Nest：print_loop_nest的记法，以及单个 Func 的循环；
Defaults and Inlining：默认内联，以及三个计算层级；
Placement: compute_root and compute_at：一个 Func 在哪里被构建；
Storage Levels：store_at、store_root、hoist_storage与滑动窗口；
Reshaping Loops：split、fuse、reorder、tile；
Loop Types：串行、并行、向量化、展开、GPU 五类循环；
Advanced Directives：rfactor、in/clone_in、compute_with、specialize；
How the Loop Nest Is Built：循环嵌套的完整组装步骤。

当 Part II 提到某个指令时，其精确效果在 Part III 中逐条可查。

Part IV：参考（Reference）——紧凑的速查

Directive Reference：全部指令的签名与效果；
Checklist and Worked Example：起飞前检查清单 + 一个端到端完整示例。

此外，仓库还配套一份一屏速查表 directive-cheatsheet.md，按"计算与存储位置、循环形状、循环类型、包装与约简、尾部策略、诊断"分组列出每个指令的签名与效果，适合快速查阅。

如何在当前仓库中继续深入

引言确立了概念框架后，你可以沿着下面的仓库路径继续验证与实操：

教程（tutorial）：调度概念的可运行示例集中在 tutorial/lesson_05_scheduling_1.cpp（向量化、并行、展开、分块）、tutorial/lesson_08_scheduling_2.cpp（compute_at与compute_root）、tutorial/lesson_12_using_the_gpu.cpp（GPU 调度）与 tutorial/lesson_18_parallel_associative_reductions.cpp（rfactor并行化约简）。编译方式见各文件头部注释：g++ lesson_05*.cpp -g -I <path/to/include> -L <path/to/lib> -lHalide -lpthread -ldl -o lesson_05 -std=c++17，之后设置LD_LIBRARY_PATH并运行；
调度 API：指令声明位于 src/Func.h 与 src/Schedule.h；消费调度的关键 pass 位于 src/ScheduleFunctions.cpp、src/Bounds.cpp 与 src/BoundsInference.cpp——对应引言"边界从哪来"与"循环嵌套怎么拼出来"两个问题；
自动调度器（Autoschedulers）：如果不打算手写调度，可以通过Pipeline::apply_autoscheduler让 Halide 代为提出调度，实现在 src/autoschedulers/ 下的mullapudi2016、adams2019、li2018、anderson2021等；
Python 绑定：指南示例是 C++，但调度 API 在 Python 中完全相同——同样的指令是halide.Func上的方法，C++ 调度可以直接映射过来，Python 教程镜像位于 python_bindings/halide/tutorial/；
诊断环境变量：HL_DEBUG_CODEGEN=1（调大数字获得更多细节）打印关键 lowering pass 之后的 IR；HL_JIT_TARGET/HL_TARGET设置目标平台；内置 profiler（HL_TARGET=host-profile）与.stmt文件分别回答"时间花在哪"与"热点循环是否为单位步长向量化存储"。

小结

引言所确立的核心心智模型可以浓缩为三句话：

算法与调度彻底分离——算法是纯数学描述，调度是性能决策，二者独立编写；
调度不改变结果——只可能带来舍入/溢出级别的浮点差异，因此可以放心激进重排；
性能全部来自三个杠杆——计算顺序、冗余重算、临时存储，全部通过一组按Func独立做出的选择（计算位置、存储位置、循环形状、存储布局）来操纵。

带着这个框架，后续 Part I 讲解被调度的对象与流水线实现，Part II 教你快速写出跑得快的调度，Part III 逐条精确解释每个指令对循环嵌套的改写，Part IV 则提供随取随用的索引。在编写或修改任何调度之前，先读对应章节，并用print_loop_nest()验证结果，而不是凭假设。