优化求解器与并行计算

优化求解器与并行计算1. 有限差分和自动微分的 GPU 应用老师重新回到有限差分与自动微分的计算问题。前面已经讲过Jacobian 的不同列之间可以独立计算。每一列可以单独分配计算任务。GPU 可以启动大量线程进行并行计算。具体应用方式启动多个 GPU 线程块。每个线程块负责计算 Jacobian 的一列或一部分。同时完成多个方向的函数评估。将结果组合成完整的 Jacobian 矩阵。应用场景大规模非线性方程组。CFD计算流体力学。大规模科学计算。老师强调高并行度的计算任务基本上可以优先考虑使用 GPU。2. 大规模 Krylov 子空间方法CG 算法第三类是大规模 Krylov 子空间方法。老师重点介绍 CGConjugate Gradient共轭梯度法这是求解大规模线性方程组的重要迭代方法。老师在这里主要关注其并行计算结构。2.1 CG 中的两个核心并行操作第一稀疏矩阵与向量乘法SPMVSparse Matrix-Vector Multiplication即[yAx]其中 (A) 为稀疏矩阵。这种操作可以利用矩阵不同元素之间的计算独立性具有较高的并行性。第二向量内积Dot Product[xTy\sum_{i1}{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-StartMulti-Start 的基本思想从多个不同的初始点启动优化算法分别进行求解。每个初始点对应一个独立的优化任务不同任务之间可以同时执行。3.2 Evolutionary Algorithms进化算法在一个进化算法的种群中每个个体都需要进行适应度评估。不同个体的适应度评估通常相互独立因此可以并行执行。3.3 异构部署老师进一步介绍了异构计算部署可以将种群评估任务分配给GPU 数千个核心。分布式集群。不同计算节点。每个计算核心可以运行一个轻量级求解器通过这种方式提高整体种群评估速度。老师感叹GPU 的出现为人类科技发展带来了巨大的推动作用。4. 难以并行的优化算法环节前面讲的是适合并行的计算任务。接下来老师讨论哪些优化算法具有较强的数据依赖关系因此难以直接并行主要包括Line Search线搜索。Simplex Method单纯形法。SQP序贯二次规划。4.1 Line Search线搜索4.1.1 为什么线搜索难以并行线搜索是一个具有强顺序依赖关系的决策过程。给定当前迭代点和下降方向需要确定合适的步长 (\alpha)。例如先尝试 (\alpha1)。如果不满足条件再尝试 (\alpha0.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序贯二次规划的并行限制SQPSequential Quadratic Programming序贯二次规划本身具有明显的串行依赖关系。4.3.1 为什么 SQP 具有串行依赖在第 (k) 次迭代中需要根据当前点的梯度信息和 Hessian 近似构建一个 QP 子问题。QP 子问题求解后得到搜索方向。执行线搜索。更新当前点。更新 Hessian 近似。进入下一次迭代。其依赖关系可以表示为[\text{第 }k\text{ 步}\rightarrow \text{QP求解}\rightarrow \text{线搜索}\rightarrow \text{更新}\rightarrow \text{第 }k1\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分布式进程并行。OpenMPCPU 多线程并行。GPUGPU 加速。通过组合不同层次的并行计算提高整体计算效率。5.4 串行算法的工程挑战核心问题算法存在强数据依赖不能直接将所有迭代过程并行化。老师给出了两种解决思路。第一算法重构例如使用前面课程讲过的内点法Interior Point Method替代单纯形法从算法层面改变求解过程降低原算法中的串行依赖。第二内部并行即使外部迭代是串行的内部仍然可能存在并行计算例如线搜索中的函数评估。梯度计算。目标函数中的物理模拟。老师将这种方式形容为曲线救国当整体算法不容易并行时通过优化内部可并行部分提升总体性能。5.5 四类工程优化问题总结算法类别主要瓶颈工程解决方案MILP 分支定界NP-hard、搜索树爆炸强分支、伪费用、割平面、并行搜索并行矩阵计算内存带宽、GPU 占用率Tensor Core、FP8/FP16、共享内存Krylov 方法内积导致的全局同步通信隐藏、流水线 GMRES、MPI OpenMP GPU串行优化算法强数据依赖内点法重构、内部并行