NEW ORLEANS, La., July 10 — The Supercomputing Conference (SC14) awards committee has announced that “A Multi-level Algorithm for Partitioning Graphs,” co-authored by Bruce Hendrickson and Rob Leland of Sandia National Laboratories, has won the prestigious Test of Time Award. The award recognizes the most transformative and inspiring research published at the SC conference and will be presented at the SC14 awards ceremony in New Orleans, LA in November 2014.
Hendrickson, Affiliated Professor of Computer Science at University of New Mexico and Senior Manager for Extreme Scale Computing at Sandia National Laboratories, and Leland, Director of Computing Research at Sandia National Laboratories, were selected for their achievements in laying the inspirational groundwork for graph partitioning. Published in 1995 in the Proceedings of Supercomputing, “A Multi-level Algorithm for Partitioning Graphs” has had a tremendous impact on parallel computing, as graph partitioning lies at the heart of numerous scientific computations and is actively used to this day.
“The innovative methods so elegantly introduced in this paper represented the starting point for a collection of popular partitioning and load-balancing approaches, together with toolsets that have enabled scalable parallelism for countless applications over the past two decades,” says Ewing (“Rusty”) Lusk, Argonne Distinguished Fellow Emeritus at Argonne National Laboratory.
Multi-level graph partitioning is a method that partitions a series of smaller graphs and then propagates the result back to the original graph. Hendrickson and Leland were the first to develop this concept in their initial software, Chaco. Hendrickson and Leland’s work served as the basis for many widely used libraries in the HPC community, which was almost solely due to the publication of this paper.
“The idea of hierarchical graph partitioning, as introduced by Hendrickson and Leland, has proven essential, especially given the increased importance of unstructured meshes in science and engineering simulations,” says Kathy Yelick, Associate Laboratory Director of Computing Sciences at the Lawrence Berkeley National Laboratory and Professor of Electrical Engineering and Computer Sciences at the University of California at Berkeley. “Today, this methodology helps deal with the exponential increase in computational problem sizes and the increased scale of parallelizing these problems.”
Making its inaugural appearance at the SC conference’s 25th anniversary in 2013, the Test of Time Award recognizes the most transformative and inspiring research in the HPC community. The first Test of Time Award was presented to William Pugh, Emeritus Professor of Computer Science at the University of Maryland at College Park, at SC13 for his paper, “The Omega Project and Constraint Based Analysis Techniques in High Performance Computing.”