CSC/ECE 506 Spring 2010/ch 2 maf: Difference between revisions
| Line 7: | Line 7: | ||
Whereas the shared memory and message passing models focus on how parallel tasks access common data, the data parallel model focuses on how to divide up work between parallel tasks. Data parallel algorithms exploit parallelism by dividing up work into a number of identical tasks which are executed on different subsets of the common data. | Whereas the shared memory and message passing models focus on how parallel tasks access common data, the data parallel model focuses on how to divide up work between parallel tasks. Data parallel algorithms exploit parallelism by dividing up work into a number of identical tasks which are executed on different subsets of the common data. | ||
The logical opposite of data parallel is ''task parallel,'' in which a number of distinct tasks operate on the same common data. A major limitation of task parallel algorithms is that the maximum degree of parallelism attainable is limited to the number of tasks that have been formulated. This is in contrast to data parallel algorithms, for which the number of parallel tasks may be increased by | The logical opposite of data parallel is ''task parallel,'' in which a number of distinct tasks operate on the same common data. A major limitation of task parallel algorithms is that the maximum degree of parallelism attainable is limited to the number of tasks that have been formulated. This is in contrast to data parallel algorithms, for which the number of parallel tasks may be increased by partitioning the data into a greater number of smaller subsets. | ||
The shared memory and message passing models do not, in general, impose constraints on what kind of work is to be performed by each task, and the data parallel model does not necessarily require a particular methodology for controlling access to common data. | The shared memory and message passing models do not, in general, impose constraints on what kind of work is to be performed by each task, and the data parallel model does not necessarily require a particular methodology for controlling access to common data. | ||
Revision as of 18:49, 28 January 2010
Supplement to Chapter 2: The Data Parallel Programming Model
Chapter 2 of Solihin (2008) covers the shared memory and message passing parallel programming models. However, it does not address the data parallel model, another commonly recognized parallel programming model covered in other treatments like Foster (1995) and Culler (1999). The goal of this supplement is to provide a treatment of the data parallel model which complements Chapter 2 of Solihin (2008).
Overview
Whereas the shared memory and message passing models focus on how parallel tasks access common data, the data parallel model focuses on how to divide up work between parallel tasks. Data parallel algorithms exploit parallelism by dividing up work into a number of identical tasks which are executed on different subsets of the common data.
The logical opposite of data parallel is task parallel, in which a number of distinct tasks operate on the same common data. A major limitation of task parallel algorithms is that the maximum degree of parallelism attainable is limited to the number of tasks that have been formulated. This is in contrast to data parallel algorithms, for which the number of parallel tasks may be increased by partitioning the data into a greater number of smaller subsets.
The shared memory and message passing models do not, in general, impose constraints on what kind of work is to be performed by each task, and the data parallel model does not necessarily require a particular methodology for controlling access to common data.
In fact, the data parallel model can be used in conjunction with either the shared memory or the message passing model, as explored by Klaiber (1994).
| Aspects | Shared Memory | Message Passing | Data Parallel |
|---|---|---|---|
| Communication | implicit (via loads/stores) | explicit messages | implicit |
| Synchronization | explicit | implicit (via messages) | typically implicit |
| Hardware support | typically required | none | |
| Development effort | lower | higher | higher |
| Tuning effort | higher | lower |
A Code Example
// Simple sequential code from Solihin 2008, page 25.
for (i = 0; i < 8; i++)
a[i] = b[i] + c[i];
sum = 0;
for (i = 0; i < 8; i++)
if (a[i] > 0)
sum = sum + a[i];
Print sum;
// Data parallel implementation in C++ with OpenMP.
#include <omp.h>
#include <iostream>
int main(void)
{
double a[8], b[8], c[8], localSum[2];
long s = 4;
int id, i;
#pragma omp parallel for private(id, i) reduction(+:s)
for (int i = 0; i < 8; i++)
{
a[i] = b[i] + c[i];
}
for (int i = 0; i < 2; i++) localSum[i] = 0;
#pragma omp parallel for private(id, i) reduction(+:s)
for (int i = 0; i < 8; i++)
{
id = omp_get_thread_num();
if (a[i] > 0)
localSum[id] = localSum[id] + a[i];
}
double sum = localSum[0] + localSum[1];
std::cout << sum << std::endl;
}
Hardware Examples
References
- David E. Culler, Jaswinder Pal Singh, and Anoop Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Morgan-Kauffman, 1999.
- Ian Foster, Designing and Building Parallel Programs, Addison-Wesley, 1995.
- Magne Haveraaen, "Machine and collection abstractions for user-implemented data-parallel programming," Scientific Programming, 8(4):231-246, 2000.
- W. Daniel Hillis and Guy L. Steele, Jr., "Data parallel algorithms," Communications of the ACM, 29(12):1170-1183, December 1986.
- Alexander C. Klaiber and Henry M. Levy, "A comparison of message passing and shared memory architectures for data parallel programs," in Proceedings of the 21st Annual International Symposium on Computer Architecture, April 1994, pp. 94-105.
- Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, 2008.