Program
Generation for the AllPairs Shortest Path Problem
Tuesday May 1, 2007
Hamerschlag Hall D210
4:30 pm
Sungchul Han
Carnegie Mellon University
A recent trend in computing is domainspecific program generators, designed to
alleviate the effort of porting and reoptimizing libraries for fastchanging 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 wellknown
FloydWarshall (FW) algorithm that solves the allpairs 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 matrixmatrix multiplication. The program generator, which uses
tiling, loop unrolling, and SIMD vectorization combined with a hill climbing search,
provides a speedup of up to six times over a straightforward singleprecision
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.
