复习：从并行程序到系统与大模型

并行优化可以看作三层相互约束：算法依赖决定有哪些工作能同时做；调度与数据布局决定工作如何到达执行资源；硬件吞吐、带宽和同步成本决定实际完成速度。只改变其中一层，未必能改善最终结果。

一条完整诊断路径

假设四线程程序只比单线程快 10%。先确认它完成了相同工作、得到正确答案，并且计时口径相同。然后画任务依赖图：是否有无法并行的长阶段？若没有，检查各 worker 的工作量：是否平均分了元素数量却没有平均分计算量？

负载均衡之后，检查同步频率和通信：每处理一个元素是否争用同一个原子变量？多个线程的独立统计是否放在同一缓存行？再检查数据流量：相邻线程或 SIMD lane 是否访问规则地址，工作集是否超出缓存，是否反复写出只会立即读回的中间结果？

最后才根据证据改变算法、任务粒度、布局或同步结构。每次修改保留正确性测试与一个针对性性能假设。若一次改了调度、数据类型、算法精度和编译选项，就很难知道收益来自哪里。

这张表列的是可检验假设，不是现象到原因的一一映射。多个因素可以同时存在。

map 对每项独立变换；reduce 把多项合成一个结果；scan 为每个位置产生此前元素的累积结果；filter/compaction 根据谓词保留元素。掌握这些结构，能把原本顺序叙述的算法改写成更显式的数据依赖。

例如 filter 可先生成 0/1 标记，再做前缀和，得到每个保留元素应写入的独占输出位置，最后散写。这样避免所有线程争用一个输出计数器，但增加标记、scan 与中间空间。需要根据规模与输出稀疏度测量，而不是默认原语更多就更快。

reduce 与 scan 的差别也体现在 work/span。两者都可以设计为 O(N) work、O(log N) span 的并行算法，但 scan 需要保留每个前缀结果，不能简单拿“只输出一个总和”的归约代码替代。

Transformer 的训练与推理都会用矩阵乘法、归约、归一化、注意力和数据搬运。批量维度提供独立工作；张量形状影响 kernel 利用率；注意力中间矩阵影响内存流量；分布式训练还增加跨设备通信。并行计算的性能模型能帮助判断哪一类优化值得尝试。

融合算子可减少中间张量写回设备内存，例如把逐元素处理合并进相邻计算；代价可能是更高寄存器压力和更复杂的调度。低精度可以降低字节流量并提高特定单元吞吐，但必须重新检查数值误差。这里的每项技术都需要正确性与测量支持，不能把“用了 GPU”当作优化完成。

本机并行程序通常共享内存，线程通过锁、原子和 join 建立顺序。跨机器则面对消息延迟、部分失败和状态复制，不能直接把共享内存的假设搬过去。任务编号唯一分配在单进程里可用一个原子变量，跨机器需要考虑调度器失败与重复执行。

但共同方法仍有价值：明确状态、所有权、依赖和完成条件；区分通知与真实状态；对不变量进行验证。一个任务收到“已提交”响应，并不代表结果已经完成，这与线程池里提交队列和完成计数的区别相通。

设计一张任务图。 将“读取一批数据 → 预处理 → 多个矩阵操作 → 汇总写出”拆成 DAG。给每节点假想时间，计算 work、span 和 4 worker 的可行调度。把 I/O 与计算重叠后，指出哪些边必须保留。

改造 benchmark。 给每 worker 增加独立任务计数与工作步数，在线程结束后打印。先将统计放在每线程局部变量，最后一次写回；再对比每项原子增加。说明减少共享写频率为什么通常比只加 padding 更直接。

扩展归约。 在有 CUDA 环境时，让每个线程处理多个输入并加入第二阶段设备归约。先检查 N=1、255、256、257、100003 的结果，再比较端到端与 kernel 时间。没有设备时画出索引和每轮读写范围，明确该部分尚未实测。

自测：只要没有数据竞争，浮点并行求和就一定逐位等于串行吗？

不一定。浮点加法的舍入使不同结合顺序可能产生不同结果。需要事先定义精度要求，并采用合适的参考、容差或更稳定的算法。无竞争解决访问顺序合法性，不自动解决数值等价性。

自测：什么时候可以说“这次优化完成了”？

在明确输入与环境范围内，结果满足正确性要求，性能指标有可重复改善，资源代价与退化场景已说明，并保留可重放代码和数据。无需承诺所有机器、所有规模都更快。