《Journal of Computational Science》:Fitness-time-energy investigation of selected five applications using a parallel multi-GPU genetic algorithm under power capping
编辑推荐:
摘要翻译
本文是会议论文(Magdziak和Czarnul,2025)的显著扩展版本,研究人员将功率上限(power capping)应用于多GPU并行遗传算法(Parallel Genetic Algorithm,PGA)执行的性能-能量优化中。研究人员设计
摘要翻译
本文是会议论文(Magdziak和Czarnul,2025)的显著扩展版本,研究人员将功率上限(power capping)应用于多GPU并行遗传算法(Parallel Genetic Algorithm,PGA)执行的性能-能量优化中。研究人员设计并实现了一个基于CUDA的框架,该框架可在节点内多个GPU之间扩展,并能轻松适用于多个不同问题的求解。研究人员提供了针对五个问题的多GPU PGA实现:旅行商问题(Traveling Salesman Problem,TSP)、背包问题(Knapsack Problem,KP)、划分问题(Partition Problem,PP)、作业车间调度问题(Job-Shop Scheduling Problem,JSSP)和图着色问题(Graph Coloring Problem,GCP)。研究人员在一台配备2个Intel Xeon CPU和8个NVIDIA Quadro RTX 6000 GPU的高性能计算服务器上,使用Yokogawa WT-310E功率计进行能量测量,展示了大量实验结果。研究人员证明了GPU功率上限对执行时间和能耗的影响,表明与默认的260 W功率上限相比,将每个GPU的功率上限降至100–140 W可带来可观的能量节省,例如,TSP节省20.21%,KP节省16.11%,PP节省29.36%,JSSP节省12.5%,GCP节省22.9%,但代价是运行时间增加:TSP增加1.12%,KP增加0.88%,PP增加7.84%,JSSP几乎不增加,GCP增加19.31%。研究人员的PGA实现表明,在1至8个GPU范围内算法质量具有可扩展性,因为更大数量的GPU显著提高了适应度水平。此外,研究人员展示了每个问题的适应度与能量-延迟乘积(Energy-Delay Product,EDP)对比图,该图允许选择在所需适应度(最大化)与EDP(最小化)之间取得最佳权衡的配置。研究表明,最佳适应度在8个GPU时达到,且对该配置而言,EDP在每GPU 140 W功率上限时最小化。
论文解读文章
一、研究背景与问题
随着高性能计算(High Performance Computing,HPC)系统规模不断扩大以及电力价格持续上涨,能耗已成为算法设计与系统评估中的关键约束。现代HPC系统几乎完全转向GPU加速,尽管GPU具有较高的能效,但在大规模部署下功耗依然可观,且以最短执行时间为目标优化的配置往往在能量层面并不经济。因此,仅以时间和解质量作为算法评估指标可能产生误导,有必要将能量作为与性能同等重要的指标纳入评估。
进化算法(Evolutionary Algorithm,EA)尤其并行遗传算法(Parallel Genetic Algorithm,PGA)因群体-迭代结构非常适合并行执行,常用于求解难以建立精确解析模型的组合优化问题。然而,在多GPU环境下对PGA进行显式能耗感知分析的研究仍然有限。GPU功率上限(power capping)作为一种可行的功耗管理机制,可以降低功率消耗但可能带来性能损失,从而在解质量、能耗和执行时间之间引入复杂的平衡。这种功率控制机制对多GPU PGA以及不同类别组合优化问题的影响尚未得到充分理解,这正是本文研究的动机。本文是作者先前会议论文(Magdziak和Czarnul,2025)的显著扩展,针对该研究空白开展了系统的实验研究。
二、研究工作与结论概述
研究人员设计并实现了一个基于CUDA的多GPU PGA框架,支持五个NP难组合优化问题的求解:旅行商问题(TSP)、背包问题(KP)、划分问题(PP)、作业车间调度问题(JSSP)和图着色问题(GCP)。实验在一台配备2个Intel Xeon 4210 CPU(共40逻辑处理器)和8个NVIDIA Quadro RTX 6000 GPU的高性能计算服务器上进行,采用Yokogawa WT-310E功率计以10 Hz采样率测量整机功率并转换为能耗。研究系统考察了GPU功率上限(100、140、180、220、260 W)、GPU数量(1、2、4、8)和种群规模(4608、8192、65 536个体/GPU)对适应度、执行时间和能耗的影响,每个配置重复100次并报告平均结果,使用Cohen's d效应量进行实际显著性评估。
主要结论包括:功率上限对适应度无实质影响,但可显著降低能耗;在8 GPU配置下,TSP、KP、PP在140 W功率上限时能耗最小,而JSSP和GCP在100 W时能耗最小;最佳适应度在8 GPU时获得,且此时EDP在每GPU 140 W功率上限下最小化。这些结果为在多GPU PGA执行中选择功耗配置、在解质量与能耗之间进行权衡提供了量化依据。
三、主要关键技术与方法
研究人员开发了一个统一的CUDA多GPU框架,采用单进程多GPU节点执行模型,每个GPU绑定一个CPU线程作为控制器。算法采用锦标赛选择、单点交叉和1%概率突变等通用遗传算子模板,各问题以其特有的CUDA内核实现。种群基因组及快照副本完全存储于GPU全局内存中,快照用于保证交叉读取上一代的一致视图;每5代通过环形迁移在GPU间交换个体。所有问题实例使用统一种子控制的64位伪随机数生成器(mt19937_64)生成以保证可重复性,TSP实例由二维坐标欧氏距离生成,KP包含1000个物品且容量为500,PP含32 000个元素,JSSP含10个作业×15个操作共150个操作,GCP含4096个顶点和20 480条边。能耗由外部Yokogawa WT-310E功率计测量。
四、研究结果
4.1 TSP结果
对于旅行商问题(100城市对称欧氏距离矩阵),适应度箱线图显示各功率上限下相同GPU数的适应度中位数基本一致,Cohen's d值较低,表明功率上限不影响解质量;适应度随GPU数从1增至8而显著提高。能量分析显示,8 GPU时140 W功率上限能耗最低,相比默认260 W节省20.21%,时间仅增加1.12%。EDP图中可见8 GPU配置适应度最高,140 W时EDP最小。
4.2 KP结果
对于背包问题(1000个物品,容量500,适应度最大化),功率上限对适应度同样无显著影响;8 GPU时140 W功率上限能耗最低,节能16.11%,时间仅增加0.88%,是所有问题中时间惩罚最小的。适应度-EDP图显示,8 GPU获得最佳适应度,而140 W在相同GPU数下EDP最小。
4.3 PP结果
对于划分问题(32 000个元素划分至三组),种群规模为4608时出现1 GPU适应度优于多GPU的例外情况,但高方差不稳定,且8 GPU时最终追赶;种群规模65 536时则观察到从1到8 GPU适应度持续提高。8 GPU下140 W功率上限节能效果最显著,达29.36%,为五个问题中最大,但时间增加7.84%,也相对较大。
4.4 JSSP结果
对于作业车间调度问题(10×15操作),该问题计算负载较小,100 W功率上限时能耗最低,较260 W节能14.36%,但时间增加20.96%;而140 W时节能12.5%,时间几乎无增加(7.27对7.31 s),是更优的权衡点。适应度随GPU数增加而提高,100 W超低功率下通信开销明显增大,导致时间增长显著。
4.5 GCP结果
对于图着色问题(4096顶点、20 480边、10种颜色),100 W功率上限时能耗最低,节能22.9%,但时间增加19.31%。与JSSP类似,该问题因计算密集度较低,低功率上限的能量收益较大但时间惩罚也较高。8 GPU时适应度最高,EDP在140 W时相对最优。
五、讨论部分总结与结论翻译
讨论部分指出,功率上限主要影响执行时间和能耗,而对适应度的影响可忽略,其影响程度取决于问题的计算-通信时间比;对计算密集度较高的大问题(如TSP、KP、PP在65 536种群下)效果尤为明显。能耗普遍随GPU数增加而增加,因为更多GPU带来更高总功耗和通信开销。适应度与EDP之间存在固有权衡:更多GPU可显著提高适应度,但也会使EDP成倍增加;在相同GPU数下,选择适当功率上限(140 W或100 W)可以在几乎不损失适应度的前提下明显降低EDP,具体取舍取决于用户对适应度改进与能耗代价的偏好。
结论部分可翻译为:本文全面研究了多GPU GA框架在GPU功率上限下的实现及其性能-能量行为。研究人员在单个多GPU节点上评估了多个组合优化问题,并量化了不同功率上限设置和GPU数量下的解质量、执行时间和端到端能耗。研究结果允许选择优化适应度、能耗以及适应度与EDP之间期望权衡的功率上限配置和GPU数量。具体而言,最佳适应度在8 GPU配置下获得,而能耗在每GPU 100 W或140 W功率上限时最小化,优于每GPU默认260 W功率上限。未来工作包括:将框架扩展至多节点更大GPU规模、集成CUDAMPILIB等支持全局功率上限的多节点执行框架、研究基于运行时工作负载特征的自适应动态功率上限策略、与无迁移的独立GPU并行变体进行比较,以及扩展配置空间维度分析(包括每GPU种群规模、迁移间隔与迁移量、内核启动参数等)。