Pattern-Driven Automatic Parallelization
Christoph W. Keßler
Scientific Programming 5(3), 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.
Comments:
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},
number = {3},
pages = {251--274},
publisher = {Wiley},
year = {1996}
}
Download:
Copyright notice:
This section contains links to material covered by copyright;
copyright may be held by the author and/or the publisher.
You may browse them at your convenience
(in the same spirit as you may read a journal or a proceedings article in a public library).
Retrieving, copying, or distributing these files, however, may violate
the copyright protection law. We recommend that the user obey international law
in accessing this directory.
Note also that the material made accessible below may be based
on a submitted version and thus differ in minor details from the published version.
Christoph Kessler