Link to CALCM Home  

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.


Department of Electrical and Computer EngineeringCarnegie Mellon UniversitySchool of Computer Science