图分割算法荣获SC21时间检验奖

George Karypis（某中心高级首席科学家）与明尼苏达大学教授Vipin Kumar共同获得SC21时间检验奖，表彰其1998年发表的论文《多约束图分割的多级算法》。该论文提出的算法已成功应用于电子设计自动化工具、美国州级选区划分、大型深度学习模型计算图分割等多元领域。

算法核心贡献

论文创新性地将标准最小割平衡图分割问题扩展为满足多重平衡约束的优化问题，并提出高效的多级算法解决方案。该算法能同时平衡计算资源（如CPU周期、内存和网络带宽）的分配需求，显著提升了多相科学模拟在高性能计算节点上的并行效率。

技术实现原理

1. 建模方式：用稀疏图的顶点表示计算任务（权重对应计算量），边表示任务交互（权重对应数据交换量）
2. 分割目标：将图划分为k个部分（k通常为处理器数量），要求：
   • 各分区计算负载均衡（顶点权重总和相近）
   • 跨分区边权重总和最小化（减少通信开销）
3. 多约束突破：通过创新算法同时满足计算量、内存占用等多维度平衡需求

实际应用

• 现场可编程门阵列(FPGA)电子设计自动化工具开发
• 图神经网络训练过程中的计算优化
• 超大规模集成电路(VLSI)计算机辅助设计系统
• 地理信息系统空间数据处理

该算法已被集成至Metis、ParMetis和hMetis等主流图/超图分割软件。Karypis近期还在某机构机器学习峰会上就"大规模深度图学习"发表主题演讲，探讨图神经网络的前沿进展。