0

我有一些代码，可以并行计算某些数组前缀的总和（例如out_arr[0]= in_arr[0]，out_arr[1]= in_arr[0]+in_arr[1].. 等）。我的代码有N线程，有N许多in_arr元素，每个线程只处理数组的 1 个元素。这不是一个好的解决方案，所以我想N/num_of_threads在每个线程中处理，但我失败了。

我试图创建具有值的共享变量，并在第一个指令后面使用这个变量来N/num_of_threads组织循环，但我无法在标准输出中调试这些幻数。for#pragma

这是«坏»解决方案的工作版本：

void CalcSum2(int a[], int s[], int n) { 
    int* old = new int [n], *cnt = new int [n]; 
    #pragma omp parallel num_threads(N) {
    int i = omp_get_thread_num(), d = 1; 
    s[i] = a[i]; 
    cnt[i] = 1; 
     #pragma omp barrier 
    while (d < n) { 
        old[i] = s[i]; 
     #pragma omp barrier 
         if (i >= d) { 
             s[i] += old[i-d]; 
         cnt[i]++; 
         } 
         d += d; 
     #pragma omp barrier 
    }
    }
    delete[] old; delete[] cnt; 
    return; 
}
4

2 回答 2

1

你正在做一个累积和。也称为前缀和。这可以与 OpenMP 并行完成。我最近使用 OpenMP 中的 OpenMP并行累积（前缀）总和解决了这个问题：在线程之间通信值

您必须在阵列上并行运行两次。第一次进行部分和，第二次用偏移量校正部分和。

我在下面为您转换了您的代码。作为测试，我做了计数的总和，它有一个封闭形式的解决方案i*(i+1)/2。您可以看到 prefix_sum 函数得到了正确的答案。

#include <stdio.h>
#include <omp.h>

void prefix_sum(int a[], int s[], int n) {
    int *suma;
    #pragma omp parallel
    {
        const int ithread = omp_get_thread_num();
        const int nthreads = omp_get_num_threads();
        #pragma omp single
        {
            suma = new int[nthreads+1];
            suma[0] = 0;
        }
        int sum = 0;
        #pragma omp for schedule(static) nowait // do partial sum in parallel
        for(int i=0; i<n; i++) {
            sum += a[i];
            s[i] = sum;
        }
        suma[ithread+1] = sum;
        #pragma omp barrier
        int offset = 0;
        for(int i=0; i<(ithread+1); i++) {
            offset += suma[i];
        }

        #pragma omp for schedule(static) //run over array again in parallel for full sum
        for(int i=0; i<n; i++) {
            s[i] += offset;
        }
    }
    delete[] suma;
}

int main() {
    const int n = 100;
    int *a = new int[n];
    int *s = new int[n];
    for(int i=0; i<n; i++) {
        a[i] = i;
    }
    prefix_sum(a, s, n);
    for(int i=0; i<n; i++) {
        printf("%d ", s[i]);
    } printf("\n");

    for(int i=0; i<n; i++) {
        printf("%d ", i*(i+1)/2);
    } printf("\n");
}

编辑 此方法的一个问题是，对于大型数组，大多数值在第二遍开始时已从缓存中逐出。我想出了一个解决方案，它并行运行一个块，然后依次移动到下一个块。我将 chunck_size 设置为二级缓存（实际上是四倍，因为有四个内核）。这为更大的阵列提供了很大的改进。这是函数的概要。完整的功能可以在我的回答中找到simd-prefix-sum-on-intel-cpu。

void scan_omp_SSEp2_SSEp1_chunk(float a[], float s[], int n) {
    float *suma;
    const int chunk_size = 1<<18;
    const int nchunks = n%chunk_size == 0 ? n / chunk_size : n / chunk_size + 1;    
    #pragma omp parallel
    {
        //initialization code 
        for (int c = 0; c < nchunks; c++) {
            const int start = c*chunk_size;
            const int chunk = (c + 1)*chunk_size < n ? chunk_size : n - c*chunk_size; 
            //pass1: pass1_SSE(&a[start], &s[start], chunk);                
            //get offset
            //pass2: pass2_SSE(&s[start], offset, chunk);
        }
    }
    delete[] suma;
}
于 2013-10-18T07:17:08.417 回答
1

并行扫描的方式使用了太多可能会损害性能的障碍。

多核 CPU 上的并行扫描效率不高，因为求和操作的数量从n-1增加到大约2n. 所以时间成本是2n/m，其中m是 CPU 核心数。

为了减少障碍的数量，您可以首先对数据的每个段进行顺序扫描，然后为每个段结果添加适当的偏移量。下面的代码演示了这个想法。在1G时，它在 8 核 CPU 上的速度提高了2.4倍。len您仍然可以改进第二部分以获得更高的性能。

inline void scan(int a[], int s[], int len)
{
    int sum=0.0;
    for(int i=0;i<len;i++) {
        sum+=a[i];
        s[i]=sum;
    }
}

void ParallelScan(int a[], int s[], int len)
{
    int nt;
    int seglen, subseglen;
    int* segsum;
    #pragma omp parallel
    {
        #pragma omp single
        {
            nt = omp_get_num_threads();
            seglen = (len+nt-1)/nt;
            subseglen = (seglen+nt-1)/nt;
            segsum = new int[nt];
        }
        int tid = omp_get_thread_num();
        int start = seglen*tid;
        int end = seglen*(tid+1);
        end = end > len ? len : end;

        scan(&a[start],&s[start],end-start);
        segsum[tid]=s[end-1];
        #pragma omp barrier

        #pragma omp single
        for(int i=1; i<nt; i++) {
            segsum[i]+=segsum[i-1];
        }

        for(int segid=1; segid<nt; segid++) {
            int segstart=seglen*segid;
            int start = segstart + subseglen*tid;
            int end = start + subseglen;
            end = end > len ? len : end;
            end = end > segstart+seglen ? segstart+seglen : end;

            int offset = segsum[segid-1];
            for(int i=start; i<end; i++) {
                s[i]+=offset;
            }
        }
    }


    delete[] segsum;
}
于 2013-10-17T20:40:26.660 回答