## Pattern-Driven Automatic Parallelization

### Christoph W. Keßler

Scientific Programming 5, pp. 251-274, 1996.

### Abstract:

This paper describes a knowledge--based system for automatic parallelization of a wide class of sequential numeric codes operating on vectors and dense matrices, and for execution on distributed memory message-passing multiprocessors. Its main feature is a fast and powerful pattern recognition tool that locally identifies frequently--occurring computations and programming concepts in the source code. This tool works also for dusty deck codes that have been encrypted' by former machine-specific code transformations. Successful pattern recognition guides sophisticated code transformations including local algorithm replacement such that the parallelized code need {\em not} emerge from the sequential program structure by just parallelizing the loops. It allows access to an expert's knowledge on useful parallel algorithms, available machine--specific library routines, and powerful program transformations, The partially restored program semantics also supports local array alignment, distribution and redistribution, and allows for faster and more exact prediction of the performance of the parallelized target code than is usually possible.

This is a summary of the main results of my PhD project 1991-94 at the University of Saarbrücken, Germany.
Idiom recognition for reductions and recurrences in scientific codes was a hot research topic in the early 1990's and is nowadays a standard transformation in parallelizing compilers.

Later I did some more research in this area, on pattern-driven automatic parallelization of sparse matrix computations. A summary of that work can be found in my Habilitation thesis, 2000.

### BibTeX:

@article{ Kessler_j2,
author = {Christoph W. Ke{\ss}ler},
title = {Pattern-Driven {A}utomatic {P}arallelization},
journal = {Scientific Programming},
volume = {5},
pages = {251--274},
publisher = {Wiley},
year = {1996}
}
`