George Karypis（某中心高级首席科学家）与明尼苏达大学教授Vipin Kumar因其1998年共同发表的论文《多约束图划分的多级算法》获得SC21时间考验奖。该奖项由国际高性能计算会议颁发，表彰对HPC领域产生深远影响的论文。
算法核心贡献
论文提出了多约束图划分算法，解决了高性能计算系统中多阶段科学模拟的负载均衡问题。当每个网格元素需要不同计算资源（如CPU周期、内存和网络带宽）时，该算法能实现计算任务的高效并行执行。
“论文将标准的最小割平衡图划分问题泛化为满足多重平衡约束的最小割划分问题，分析了划分的可行性，并提出了高效的多级算法。“Karypis解释道。
应用场景
该算法已被应用于：
- 现场可编程门阵列(FPGA)的电子设计自动化工具开发
- 美国州级选举选区划分
- 大型深度学习模型计算图划分
- 图神经网络训练中的计算任务分配
算法核心已被集成到Metis、ParMetis和hMetis等图与超图划分软件中。
技术原理
在并行和分布式处理中，稀疏图常被用于建模计算任务（顶点表示）及其交互（边表示）。图划分算法需满足：
- 负载均衡：各分区的任务权重总和需基本相等
- 通信优化：最小化跨分区边界的边权重总和
标准的有界容量最小割划分无法满足多重约束场景（如同时平衡计算和内存需求）。论文提出的多约束算法通过多级划分框架，能同时满足多个平衡标准。
其他荣誉
Karypis近期还获得了：
- 2021年PAKDD会议杰出贡献奖
- 2020年IEEE ICDM会议十年最高影响力奖
- 在某机构机器学习峰会上发表《深度图库：大规模深度图学习》主题演讲
该研究属于机器学习领域，相关技术持续影响高性能计算和分布式系统优化。