Paper Info
Title
Hierarchical Computation in the SPMD Programming Model.
Abstract
Large-scale parallel machines are programmed mainly with the single program, multiple data (SPMD) model of parallelism. While this model has advantages of scalability and simplicity, it does not fit well with divide-and-conquer parallelism or hierarchical machines that mix shared and distributed memory. In this paper, we define the recursive single program, multiple data model (RSPMD) that extends SPMD with a hierarchical team mechanism to support hierarchical algorithms and machines. We implement this model in the Titanium language and describe how to eliminate a class of deadlocks by ensuring alignment of collective operations. We present application case studies evaluating the RSPMD model, showing that it enables divide-and-conquer algorithms such as sorting to be elegantly expressed and that team collective operations increase performance of conjugate gradient by up to a factor of two. The model also facilitates optimizations for hierarchical machines, improving scalability of particle in cell by 8x and performance of sorting and a stencil code by up to 40% and 14%, respectively.
Year
DOI
Venue
2013
10.1007/978-3-319-09967-5_1
Lecture Notes in Computer Science
Field
DocType
Volume
SPMD,Programming paradigm,Computer science,Parallel computing,Deadlock,Distributed memory,Stencil code,Sorting,Recursion,Scalability
Conference
8664
ISSN
Citations 
PageRank 
0302-9743
9
0.50
References 
Authors
9
2
Name
Order
Citations
PageRank
Amir Kamil120212.00
Katherine A. Yelick23494407.23