Karypis and Kumar receive Test of Time award at SC21

Distinguished McKnight University Professor George Karypis and Regents Professor Vipin Kumar have been awarded the 2021 ACM/IEEE Supercomputing Conference Test of Time Award for their 1998 paper “Multilevel Algorithms for Multi-constraint Graph Partitioning."

The annual Supercomputing (SC) Test of Time Award recognizes an outstanding paper that has deeply influenced the high performance computing (HPC) discipline. It is a mark of historical impact and recognition that the paper has changed HPC trends.

The paper by Karypis and Kumar presented algorithms that have subsequently been applied in diverse application domains, from multi-physics scientific simulations and VLSI computer-aided design systems, to database and geographic information systems.

Specifically, this work introduced multi-constraint graph partitioning algorithms that address the need to load balance multi-phase scientific simulations across high-performance computing system nodes to enable efficient parallel execution of computations when each mesh element requires different computation resources (e.g., CPU cycles, memory, and network bandwidth).

These algorithms have been incorporated into the METIS and ParMETIS graph partitioning software packages, which are used extensively to enable the efficient parallel execution of complex scientific computations. These tools, in turn, have been used in a variety of HPC applications, ranging from semiconductor design and designing electoral districts to partitioning the computational graphs of large deep-learning models. Overall, the paper has had a major impact on the field, and is destined to have a continuing impact in the years to come.

“The paper generalized the standard min-cut balanced graph partitioning problem to one that seeks a min-cut partitioning that satisfies multiple balancing constraints, analyzes the feasibility of the partitions, and presents efficient and effective multilevel algorithms for computing them," explained Karypis.