PARAMAT
PARallelize Automatically by pattern MATching
PARAMAT is an automatic parallelization system
developed 1992-1995 by Christoph Kessler.
PARAMAT is based on the following key ideas:
- the observation that there is a rather limited amount of typical
(mostly dataparallel) basic operations called 'patterns'
that often occur in
numerical application programs operating on vectors and
dense matrices, and only a very limited amount of 'programming idioms' that
are typically used to express these in the standard HPC programming languages
(Fortran, C);
- a modular, fast and powerful bottom-up
pattern recognition tool that locally identifies
occurrences of these idioms (and thus, patterns) in a given sequential C source program,
and
- a code generator that replaces each pattern occurrence by a
call to an equivalent parallel library routine and, in the case of a distributed
memory target machine, performs global optimization of array
distribution. Array distribution and fast and exact performance
prediction are supported by the information provided in the
pattern instances.
The project was started in 1992 and finished in 1995.
The pattern recognition tool has been implemented, detailed results
can be found in the references below and in
C. Kessler's PhD thesis (1994).
Also, a very simple code generator for the
SB-PRAM,
a massively-parallel
shared-memory multiprocessor, has been created; it generates
Fork95 source code.
The follow-up project
SPARAMAT
built upon the PARAMAT approach and
addressed program recognition techniques for detecting
and parallelizing sparse matrix computations in sequential codes.
SPARAMAT was funded by the DFG from 1997 to 2000 and
located at the University of Trier, Germany.
More recently, a generic variant of PARAMAT has been realized
with the PRT tool (2013),
which was mainly applied to the DSP domain.
References
- Christoph W. Kessler:
Pattern-Driven Automatic Parallelization
Scientific Programming vol. 5(3), pp. 251-274, 1996.
-
Beniamino diMartino, Christoph W. Kessler:
Two Program Comprehension Tools for Automatic Parallelization
IEEE Concurrency, IEEE CS Press, vol. 8(1), pages 37-47,
Spring 2000.
-
Further papers on PARAMAT
-
Amin Shafiee Sarvestani, Erik Hansson, Christoph Kessler:
Extensible Recognition of Algorithmic Patterns in DSP Programs
for Automatic Parallelization.
Int. Journal of Parallel Programming, Nov. 2012.
Springer,
DOI 10.1007/s10766-012-0229-2.
This page by Christoph W. Kessler