优化求解器与并行计算-开发者社区

优化求解器与并行计算

1. 有限差分和自动微分的 GPU 应用

老师重新回到有限差分与自动微分的计算问题。

前面已经讲过：

Jacobian 的不同列之间可以独立计算。
每一列可以单独分配计算任务。
GPU 可以启动大量线程进行并行计算。

具体应用方式：

启动多个 GPU 线程块。
每个线程块负责计算 Jacobian 的一列或一部分。
同时完成多个方向的函数评估。
将结果组合成完整的 Jacobian 矩阵。

应用场景：

大规模非线性方程组。
CFD（计算流体力学）。
大规模科学计算。

老师强调：高并行度的计算任务，基本上可以优先考虑使用 GPU。

2. 大规模 Krylov 子空间方法：CG 算法

第三类是大规模 Krylov 子空间方法。老师重点介绍 CG（Conjugate Gradient，共轭梯度法），这是求解大规模线性方程组的重要迭代方法。老师在这里主要关注其并行计算结构。

2.1 CG 中的两个核心并行操作

第一：稀疏矩阵与向量乘法（SPMV）

Sparse Matrix-Vector Multiplication，即：
[
y=Ax
]
其中 (A) 为稀疏矩阵。这种操作可以利用矩阵不同元素之间的计算独立性，具有较高的并行性。

第二：向量内积（Dot Product）
[
x^{Ty=\sum_{i=1}}{n}x_i y_i
]
内积计算需要将多个线程或进程计算的局部结果汇总，因此属于全局规约（Global Reduction）操作。

2.2 为什么内积会成为并行瓶颈？

老师特别强调：

不同线程分别计算局部结果。
所有线程需要同步。
线程需要等待其他线程完成计算。
最后进行全局规约。

这种同步等待会影响整体并行效率。

因此，内积造成的同步等待，是并行 CG 算法的重要性能瓶颈。SPMV 本身高度并行，但 Dot Product 的全局同步可能限制整体效率。

2.3 通信与计算重叠

老师提出一种学术研究和工程实现中常见的优化方法：

Overlapping Communication with Computation（通信与计算重叠）。

核心思想：当系统正在等待内积计算结果时，不要让所有计算资源完全空闲。可以提前开始下一轮 SPMV 的部分计算，尽可能让通信等待与计算过程重叠，从而减少同步造成的时间浪费。

2.4 Pipelined GMRES 与 BGMRES

老师还提到了：

GMRES。
BGMRES。
Pipelined GMRES 等流水线方法。

流水线方法可以通过调整计算顺序，减少传统迭代方法中的同步依赖。老师讲解的重点是：通过流水线方式打破部分同步链，提高并行执行效率。

注：课堂转写中相关方法的英文发音不够清晰，这里保留能够确认的 GMRES、BGMRES 及流水线优化思路，不进一步推断具体算法变体。

3. Multi-Start 与进化算法：任务并行

第四类是 Multi-Start 和进化算法。老师指出，这类算法的并行本质是Task Parallelism（任务并行）。

3.1 Multi-Start

Multi-Start 的基本思想：从多个不同的初始点启动优化算法，分别进行求解。每个初始点对应一个独立的优化任务，不同任务之间可以同时执行。

3.2 Evolutionary Algorithms（进化算法）

在一个进化算法的种群中，每个个体都需要进行适应度评估。不同个体的适应度评估通常相互独立，因此可以并行执行。

3.3 异构部署

老师进一步介绍了异构计算部署，可以将种群评估任务分配给：

GPU 数千个核心。
分布式集群。
不同计算节点。

每个计算核心可以运行一个轻量级求解器，通过这种方式提高整体种群评估速度。

老师感叹，GPU 的出现为人类科技发展带来了巨大的推动作用。

4. 难以并行的优化算法环节

前面讲的是适合并行的计算任务。接下来老师讨论哪些优化算法具有较强的数据依赖关系，因此难以直接并行，主要包括：

Line Search（线搜索）。
Simplex Method（单纯形法）。
SQP（序贯二次规划）。

4.1 Line Search（线搜索）

4.1.1 为什么线搜索难以并行？

线搜索是一个具有强顺序依赖关系的决策过程。给定当前迭代点和下降方向，需要确定合适的步长 (\alpha)。

例如：

先尝试 (\alpha=1)。
如果不满足条件，再尝试 (\alpha=0.5)。
如果仍然不满足，再继续缩小。

老师提到的条件是 Armijo 条件（转写中该术语识别不够清晰，课堂整理暂按 Armijo 记录）。

关键在于：下一步的步长选择依赖上一步的函数评估结果。因此，不能简单地把整个线搜索循环拆成完全独立的任务同时执行。

4.1.2 线搜索内部仍然可以并行

虽然线搜索的外部循环具有顺序依赖，但是内部计算仍然可以并行，例如：

有限差分计算。
目标函数评估。
目标函数内部的物理模拟。
梯度计算。

因此，不能因为线搜索整体是串行过程，就认为其中所有计算都不能并行。

核心工程思想：外部顺序决策，内部并行计算。

4.2 Simplex Method（单纯形法）

老师指出，单纯形法的主要瓶颈在于每一步的基变换（Pivot）依赖前一步的计算结果。

4.2.1 单纯形法的串行依赖

每一步涉及：

选择入基变量。
选择出基变量。
执行 Pivot（主元变换）。
更新当前基。
进入下一轮迭代。

下一轮基变换必须依赖上一轮的结果，因此主循环具有较强的顺序依赖。

4.2.2 最陡边规则的限制

老师指出，虽然理论上可能存在多个入基、出基候选变量，但是标准的最陡边规则需要全局信息，这限制了直接并行化的空间。

4.2.3 学术界的并行优化尝试

第一：矩阵分解并行化。

课堂转写中的术语类似 “Pair Augmented Hessian”，具体名称存在识别不确定性。核心思想是通过矩阵分解过程的并行化加速计算。老师给出的经验性描述是：加速比通常不能超过约 4—8 倍。

第二：定价并行（Pricing Parallelism）。

具体做法：

将非基变量划分成若干组。
将不同变量组分配到不同线程。
并行计算各组的 Reduced Cost（约化成本）。
汇总计算结果。
找到最符合规则的变量，确定后续基变换。

老师认为，定价并行是目前工程上比较有效的单纯形法并行化手段。

4.2.4 对高级算法工程师的要求

老师特别指出，如果未来希望成为顶尖 AI 算法工程师，甚至进一步发展到算法架构师，那么这些底层算法优化知识是必须掌握的内容。这不只是普通的软件开发问题，而是更深入的算法设计与计算架构问题。

4.3 SQP：序贯二次规划的并行限制

SQP（Sequential Quadratic Programming，序贯二次规划）本身具有明显的串行依赖关系。

4.3.1 为什么 SQP 具有串行依赖？

在第 (k) 次迭代中，需要根据当前点的梯度信息和 Hessian 近似，构建一个 QP 子问题。QP 子问题求解后：

得到搜索方向。
执行线搜索。
更新当前点。
更新 Hessian 近似。
进入下一次迭代。

其依赖关系可以表示为：
[
\text{第 }k\text{ 步}
\rightarrow \text{QP求解}
\rightarrow \text{线搜索}
\rightarrow \text{更新}
\rightarrow \text{第 }k+1\text{ 步}
]
下一步依赖上一步完成。

4.3.2 Asynchronous SQP（异步 SQP）

老师介绍了学术界提出的一种尝试：Asynchronous SQP。

基本思想：当当前迭代正在等待线搜索结果时，可以利用预测方向，提前构建下一轮 QP 子问题，以尝试减少等待时间。

但是老师指出，这种方法存在重要局限：可能破坏算法原有的收敛性证明。

原因是提前构建的下一轮问题使用了预测方向，而当前线搜索结果还没有最终确定。如果后续结果与预测不一致，就可能需要回溯（Rollback）。

由此产生的工程问题包括：

需要设计复杂的回溯机制。
需要处理状态恢复。
需要保证计算过程的一致性。
需要重新考虑收敛性证明。

老师指出，异步 SQP 已经有相关研究，但目前还没有在工程界得到广泛普及应用。老师也鼓励对这一方向感兴趣的同学尝试研究和实现；如果能够解决相关问题，将是一项有价值的研究成果。

5. 优化求解器的工程实现与性能优化

老师将前面的内容归纳为四类工程问题。

5.1 MILP 分支定界的工程挑战

核心挑战：

NP-hard。
隐式枚举。
搜索树指数级增长。
Tree Search 可能发生规模爆炸。

工程上的解决办法：

在强分支与伪费用之间进行平衡。
使用可靠性分支控制计算开销。
使用割平面收紧下界。
对搜索树进行并行搜索。
多个节点同时进行计算。

老师强调，这些方法都是前面已经讲过的知识点，需要把理论和实际求解器实现联系起来。

5.2 并行矩阵计算的工程挑战

核心挑战：

内存带宽瓶颈。
GPU Occupancy（占用率）。
大规模数据访问效率。

老师提到的优化措施：

混合精度计算

利用 Tensor Core 等硬件计算单元，涉及：

FP8。
FP16。
混合精度计算。

目的：在保证必要计算精度的前提下，提高计算吞吐量。

Shared Memory（共享内存）

使用共享内存提高数据复用率，减少全局内存访问。

老师希望大家理解：GPU 性能优化不仅仅是增加线程数量，还需要考虑内存带宽、计算资源利用率和数据访问模式。

5.3 Krylov 方法的工程挑战

这里主要对应前面讲解的 CG 等方法。

核心挑战：全局规约与内积计算造成同步等待。

老师给出的优化方法：

Communication Hiding（通信隐藏）。
Overlapping Communication with Computation（通信与计算重叠）。
Pipelined GMRES。
BGMRES。
混合并行。

老师特别提到了混合并行的技术组合：

MPI：分布式进程并行。
OpenMP：CPU 多线程并行。
GPU：GPU 加速。

通过组合不同层次的并行计算，提高整体计算效率。

5.4 串行算法的工程挑战

核心问题：算法存在强数据依赖，不能直接将所有迭代过程并行化。

老师给出了两种解决思路。

第一：算法重构

例如，使用前面课程讲过的内点法（Interior Point Method）替代单纯形法，从算法层面改变求解过程，降低原算法中的串行依赖。

第二：内部并行

即使外部迭代是串行的，内部仍然可能存在并行计算，例如：

线搜索中的函数评估。
梯度计算。
目标函数中的物理模拟。

老师将这种方式形容为"曲线救国"：当整体算法不容易并行时，通过优化内部可并行部分提升总体性能。

5.5 四类工程优化问题总结

算法类别	主要瓶颈	工程解决方案
MILP 分支定界	NP-hard、搜索树爆炸	强分支、伪费用、割平面、并行搜索
并行矩阵计算	内存带宽、GPU 占用率	Tensor Core、FP8/FP16、共享内存
Krylov 方法	内积导致的全局同步	通信隐藏、流水线 GMRES、MPI + OpenMP + GPU
串行优化算法	强数据依赖	内点法重构、内部并行

优化求解器与并行计算