Generation for the All-Pairs Shortest Path Problem
Tuesday May 1, 2007
Hamerschlag Hall D-210
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.