Scalable Empirical Search of Multidimensional Schedules for Optimization and Parallelization

din, 2008-01-15 11:00 - 12:00

I cordially invite you to the presentation of Albert Cohen (INRIA/professor at Ecole Polytechnique, France) in Ghent.


Scalable Empirical Search of Multidimensional Schedules for Optimization and Parallelization

Date and time: Tuesday, January 15, 11 am

Place: Jozef Plateauzaal, Jozef Plateaustraat 22, 9000 Gent


High-level loop optimizations are necessary to achieve good
performance over a wide variety of processors. Their performance
impact can be significant because they involve in-depth program
transformations that aim to sustain a balanced workload over the
computational, storage, and communication resources of the target
architecture. Therefore, it is mandatory that the compiler
accurately models the target architecture and the effects of complex
code restructuring.

However, because optimizing compilers (1) use simplistic performance
models that abstract away many of the complexities of
modern architectures, (2) rely on inaccurate dependence analysis, and
(3) lack frameworks to express complex interactions of transformation
sequences, they typically uncover only a fraction of the peak
performance available on many applications. We propose a complete
iterative framework to address these issues. We rely on the polyhedral
model to construct and traverse a large and expressive search space.
This space encompasses only legal, distinct versions resulting from
the restructuring of any static control loop nest.

We first propose a feedback-driven iterative heuristic tailored to
the search space properties of the polyhedral model. Though it
quickly converges to good solutions for small kernels, larger benchmarks
containing higher dimensional spaces are more challenging and our
heuristic misses opportunities for significant performance improvement.
Thus, we introduce the use of a genetic algorithm with specialized
operators that leverage the polyhedral representation of program
dependences. We provide experimental evidence that the genetic
algorithm effectively traverses huge optimization spaces, achieving
good performance improvements on the optimization and parallelization of
large loop nests.


Albert Cohen is a senior research scientist in the Alchemy group at
INRIA and a part time associate professor at Ecole Polytechnique,
France. His research interests include program optimization for
high-performance architectures and embedded systems, static analysis,
parallel programming and automatic parallelization. He graduated from
Ecole Normale Superieure de Lyon, and received his PhD from the
University of Versailles in 1999 (awarded two national prizes). He has
been a visiting scolar at the University of Illinois for six months in
two consecutive years (2000 and 2001). He has coauthored more than 40
papers in refereed journals, international conferences and workshops,
and he is or has been the advisor for 14 PhD theses. He has been a
program committee member of major international conferences and
journals. He is coordinating a long-term applied research project,
within the HiPEAC European Research Network, involving the GNU
Compiler Collection (GCC) as a platform for compilation research.

Prof. Dirk Stroobandt