Home
Assefaw Gebremedhin, Papers on Parallel Computation Models
Title:
PRO:
A Model for the Design and Analysis of Efficient and Scalable Parallel
Algorithms
Authors:
A. Gebremedhin, M. Essaidi, I. Guerin-Lassous, J. Gustedt, J.A. Telle,
Status:
Nordic Journal of Computing, Vol 13, pp 1--25,
2006.
Abstract
We present a new parallel computation model called
the Parallel Resource-Optimal computation model.
PRO is a framework being proposed to enable the design
of efficient and scalable parallel algorithms in an
architecture-independent manner, and to simplify the
analysis of such algorithms.
A focus on three key features distinguishes PRO from
existing parallel computation models.
First, the design and analysis of a parallel algorithm in the PRO
model is performed relative to the time and space complexity
of a specific sequential algorithm.
Second, a PRO algorithm is required to be both time- and space-optimal
relative to the reference sequential algorithm.
Third, the quality of a PRO algorithm is measured by the maximum number
of processors that can be employed while optimality is maintained.
Inspired by the Bulk Synchronous Parallel model, an algorithm in the
PRO model is organized as a sequence of supersteps .
Each superstep consists of distinct computation and communication
phases, but the supersteps are not required to be separated by
synchronization barriers.
Both computation and communication costs are accounted for
in the runtime analysis of a PRO algorithm.
Experimental results on parallel algorithms designed using the PRO
model---and implemented using its accompanying programming
environment SSCRAP---demonstrate that the model indeed delivers efficient
and scalable implementations on a wide range of platforms.
Download Paper in PDF
Title:
PRO: a Model
for Parallel Resource-Optimal Computation
Authors:
A.H. Gebremedhin, I. G. Lassous, J. Gustedt and J.A. Telle
Status:
In Proc. of HPCS'2002
- Symposium on High Performance Computing Systems and Applications, Moncton,
NB, Canada, June 17-19, 2002, pages 106-113, IEEE Compter Society Press.
Remark :
a preliminary version of the paper in Nordic Journal of Computing
(listed above).
Download Paper in PDF
Go to
Research Areas
Coloring and Automatic Differentiation
Parallel Algorithms
Parallel Computation Models