Program Generation for the All-Pairs Shortest Path Problem

Tuesday May 1, 2007
Hamerschlag Hall D-210
4:30 pm

Sungchul Han
Carnegie Mellon University

A recent trend in computing is domain-specific program generators, designed to alleviate the effort of porting and reoptimizing libraries for fast-changing and increasingly complex computing platforms. Examples include ATLAS, SPIRAL, and the codelet generator in FFTW. Each of these generators produces highly optimized source code directly from a problem specification.

In this talk, we extend this list with a program generator for the well-known Floyd-Warshall (FW) algorithm that solves the all-pairs shortest path problem, which is important in a wide range of engineering applications. We derive variants of the FW algorithm that make it possible to apply many of the optimization techniques developed for matrix-matrix multiplication. The program generator, which uses tiling, loop unrolling, and SIMD vectorization combined with a hill climbing search, provides a speed-up of up to six times over a straight-forward single-precision implementation on Pentium 4.

Sungchul is a Ph.D. candidate in the ECE Department at Carnegie Mellon University, working with Prof. Rohit Negi and Prof. Markus Püschel. His research interests are signal processing and coding systems for communication systems.