高效的区间分支定界类型方法加速策略

《International Journal of Approximate Reasoning》：Efficient acceleration strategies for interval branch-and-bound type methods

　　

公共GPU（图形处理器）兼容的区间分析框架。区间分支定界方法的GPU加速策略比较。硬件加速的能量感知基准测试。电池单元建模背景下GPU加速参数估计的应用。

**论文解读：基于GPU加速的区间分支定界方法高效并行策略研究**

**研究背景与问题**
区间分析（Interval Analysis, IA）为根查找、全局优化和参数估计等广泛问题提供验证方法，其确定性处理有界不确定性具有吸引力，但实际应用常受限于计算开销和快速过度保守的包络。在优化领域，分支定界（Branch-and-Bound, B&B）方法常与IA结合，用于在未知但有界域中迭代缩小解空间。然而，B&B方法向高维扩展的主要障碍是指数级增长。当前最常用的高维问题界定技术是收缩器（contractors），但针对特定问题构建最优收缩器本身极具挑战性。经典区间方法多本质串行，克服IA计算开销的途径之一是硬件级并行化。但传统CPU设计受限于“功耗墙”（power wall），随着制造工艺接近物理极限，集成CPU与专用加速器的异构系统成为科学计算标准。研究人员旨在重用成熟的区间算法，通过专用硬件实现扩展。近年已有研究探索图形处理器（GPU）上的区间方法，但有效并行化方式尚无共识，且多数现有区间软件仍优先验证而非高吞吐量。研究人员先前将GPU暴力（brute-force）方法应用于参数估计，但暴力方法指数增长且受限于初始搜索空间体积。因此，本文聚焦单一集合逆（Set Inversion）算法，研究实用并行化策略以实现优于暴力方法的扩展能力。论文发表于《International Journal of Approximate Reasoning》。

**研究方法与关键技术**
研究人员采用如下关键技术：1）开发跨平台区间算术库，基于Boost.Interval并针对GPU添加直接舍入（direct rounding）模式，利用CUDA线程安全特性实现无状态舍入，同时适配FADBAD++自动微分库；2）提出三类并行化策略：显式网格（基于叶级并行PSIVIA）、递归节点级并行（NSIVIA）和向量化迭代分割（VSIVIA，基于标志-置换方案）；3）使用Griewank函数作为基准测试问题，记录时间到解（TTS）和能量到解（ETS），能量测量采用专用设备ElmorLabs PMD-USB3，采样间隔Δt=435×10^-6s；4）在参数估计中，采用一阶RC等效电路模型（ECM），结合单调性与中点测试作为剪枝准则，并利用GPU向量化IBB方法进行阶段式参数估计。实验系统为AMD Ryzen 7 2700X CPU与NVIDIA GeForce RTX 2080 Ti GPU，运行Debian GNU/Linux 12与CUDA 12.6。

**研究结果**
**3.1 显式网格与递归变体**
通过预先在设备内存中划分子空间并利用运行时生成网格（runtime-generated grid）消除预热阶段，但可能产生多余计算。递归GPU实现因同步开销未体现优势。
**3.2 向量化与混合方法**
基于标志-置换方案的向量化SIVIA（VSIVIA）在单一队列上操作，通过迭代分割与标记，避免动态缓冲区管理开销。混合方法结合初始粗粒度细分与GPU向量化，可提升初次占用率。
**3.3 效率基准测试**
针对1至4维问题，测试105种配置。结果表明：维度n<3时，CPU并行化（OpenMP）在TTS和ETS上最优；n=2时，GPU暴力方法在TTS上可行但能耗更高；n=3和n=4时，GPU向量化方法（VSIVIA）在TTS和ETS上均显著优于其他方法，递归GPU和分布式版本无增益。
**4. 参数估计应用**
将GPU向量化IBB方法应用于锂离子电池一阶RC模型参数估计，测量了离散电流阶跃下的端电压响应。使用单调性与中点测试剪枝，FADBAD++计算梯度。估计过程在3分17.71秒内得到参数包络[p]*，而CPU优化器GOP在100小时内无法求解。最终包络成功覆盖真实电压，仅在高电流阶段出现略微扩大，表明模型简化导致。

**总结与讨论**
研究人员展示了不同IBB并行化策略在GPU上的映射与局限性：显式网格方法适用于低维问题，向量化或混合策略随维度增长扩展更好。最佳方案是GPU向量化结合初始细分以避免低占用率。硬件加速并未解决“高维诅咒”，方法选择需平衡内存限制、同步开销与占用率。除传统时间比较外，能量效率作为新指标被引入。未来工作可探索泰勒模型（Taylor models）或GPU兼容收缩器原语，以及基于管的收缩（contractions on tubes）的并行化。研究人员还介绍了首个跨平台异构区间分析软件栈，计划进一步测试修改后的Boost.Interval实现。

**研究结论**
本文演示了不同并行化策略如何映射到GPU硬件与并行处理器，以及实际限制出现在何处。显式网格方法可为低维问题提供优异吞吐量，而向量化或混合策略随维度增长扩展性更佳。最佳方案是GPU向量化结合初始细分以防止低占用率。硬件加速本身不能解决“高维诅咒”，方法选择必须平衡内存限制、同步开销与可达占用率以获取最高性能。除传统时间比较外，本文添加了能量效率作为新的同等重要指标。未来应探索其他基于集合的概念（如泰勒模型）或GPU兼容收缩器原语，以进一步改善计算时间；基于管的收缩等广泛概念也可能受益，因其通常以切片形式评估，属于完全可并行化任务。通过扩展先前工作的CPU-GPU区间软件栈，本文首次引入了用于异构计算机系统的开放跨平台统一区间分析库。计划未来进一步测试修改后Boost.Interval实现的区间算术。在接近实际的应用中测试了最高效GPU方法，参数估计过程产生有前景的结果，可通过进一步细化获得更紧凑包络。当前形式已可与成熟工具结合使用加速计算。目前方法依赖动态模型精确解，未来工作将集中于开发GPU兼容的基于集合的初值问题求解技术，适用于GPU的同步执行模型与有限线程资源。