Test of Time Award Past Winners

The SC14 Test of Time Winner

Bruce Hendrickson and Rob Leland
Sandia National Laboratories

A Multi-level Algorithm for Partitioning Graphs

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.”

Read Hendrickson and Leland’s paper on IEEE’s Xplore Digital Library.

The SC13 Test of Time Winner

William Pugh
Professor Emeritus of Computer Science at the
University of Maryland at College Park

The Omega Project and Constraint Based Analysis Techniques
in HIgh Performance Computing

The Omega test paper was one of the first to suggest general use of an exact algorithm for array data dependence analysis, which is the problem of determining if two array references are aliased. Knowing this is essential to knowing which loops can be run in parallel. Array data dependence is essentially the problem of determining if a set of affine constraints have an integer solution. This problem is NP-complete, but the paper described an algorithm that was both fast in practice and always exact. More important than the fact that the Omega test was exact was that it also could use arbitrary affine constraints (as opposed to many existing algorithms which could only use constraints occurring in certain pre-defined patterns), and could produce symbolic answers, rather than just yes/no answers. This work was the foundation of the Omega project and library, which significantly expanded the capabilities of the Omega test and added to the range of problems and domains that it could be applied to. The Omega library could calculate things such as actual data flow (rather than just aliasing), analyze and represent loop transformations, calculate array sections that needed to be communicated and generate loop nests. 

We invite anyone to submit a nomination by the deadline of March 31, 2015. Please submit your nomination by going to the SC website: https://submissions.supercomputing.org/?page=Submit&id=TestofTime&site=sc15.

Click here to view the Test of Time Award flier.