[Omp] how to do prefix sum in OpenMP? (remove data dependency)

[Breshears, Clay]

One parallel solution divides the array into pieces equal to the number
of threads.  Each thread performs a scan of it's local portion, and then
the last value at each thread participates in a scan across threads.
This scan gives the sum of all values that precede the local portion
given to each thread.  Finally, the results of the thread-scan is added
to each local element that a thread controls.  Unfortunately, this
algorithm doesn't easily translate into an OpenMP solution.
 
                    clay

________________________________

From: omp-bounces at openmp.org [mailto:omp-bounces at openmp.org] On Behalf
Of Qihang Huang
Sent: Thursday, August 30, 2007 5:24 AM
To: omp at openmp.org
Subject: [Omp] how to do prefix sum in OpenMP? (remove data dependency)


Hi list,

I'd like to parallel a serial code for computing prefix sum, but the
second loop has data dependency.
How can I remove it? I checked some parallel algorithm for prefix sum,
and it uses n processors, clearly 
it is not possible with shared-memory OpenMP when n is large (say 100).
The serial code is listed below:

Thanks for any advice or pointer on the web!

----------------------------------------serial code
begin------------------------------------------------- 
#include <stdio.h>
#define n 100000
int a[n];
main() {
  int i;

  for(i=0; i<n; i++) 
    a[i] = i;

  for(i=0; i<n; i++) 
    a[i] += a[i-1];

  for(i=0; i<n; i++) 
    printf("a[%d] = %d ",i,a[i]);
  printf("\n");
}
---------------------------------------serial code
end-------------------------------------------------------

Cheers,
Qihang

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://openmp.org/pipermail/omp/attachments/20070830/2ca85541/attachment.html