1. COST OPTIMALITY AND PREDICTABILITY OF PARALLEL PROGRAMMING WITH SKELETONS.
- Author
-
Bischo, Holger, Gorlatch, Sergei, and Kitzelmann, Emanuel
- Subjects
PARALLEL processing ,COST effectiveness ,COMPUTER software ,SEMANTICS ,PARALLEL algorithms ,DATA structures - Abstract
Skeletons are reusable, parameterized program components with well-defined semantics and pre-packaged efficient parallel implementation. This paper develops a new, provably cost-optimal implementation of the DS (double-scan) skeleton for programming divide-and-conquer algorithms. Our implementation is based on a novel data structure called plist (pointed list); implementation's performance is estimated using an analytical model. We demonstrate the use of the DS skeleton for parallelizing a tridiagonal system solver and report experimental results for its MPI implementation on a Cray T3E and a Linux cluster: they confirm the performance improvement achieved by the cost-optimal implementation and demonstrate its good predictability by our performance model. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF