A Transformational Framework for Skeleton-Based Parallelism
Sergei Gorlatch(FMI, Universität Passau, D-94030 Passau, Germany
), Susanna Pelagatti(Dipartimento di Informatica Corso Italia, 40 56125 PISA Italy
)
To appear at (HIPS'99), San Juan, Puerto Rico, USA, April 12, 1999
Abstract
Structured parallel programming systems allow a parallel application
to be built composing a primitive set of recurring patterns of task-
and data-parallel computations (the \textit{skeletons}).
First academic and commercial experiences with structured parallel
programming systems (such as P3L, SCL and SKIECL)
have shown the benefits of the approach from the point of view of
optimization and performance, and have called for
a special methodology for designing parallel
algorithms, transforming them into skeletal programs and
predicting their performance in the design process.
In this paper, we take a first step towards such a methodology
by developing a general transformational framework.
Our particular contributions are: (1) a new functional abstract
notation for expressing parallel algorithms based on skeletons
(2) a set of semantics-preserving program transformation rules,
(3) analytical estimates for the performance impact of the transformations,
(4) a case study in applying our transformational framework for
the maximum segment sum problem.
We also report on the results of experiments
with the algorithm developed in the framework and then translated
in P3L, on the parallel machine Fujitsu AP1000.
