并行化与依赖

代码我有一个代码如下所示：并行化与依赖

阵列a包含组是元素属于信息。即元素i属于组a[i]。每个组可以包含两个元素。我想将这些信息存储在长度为2*number的组中。所以，值为b[j]和b[j+1]会给我属于组j/2（整数除法）和j是偶数的元素。

void assign(int *a, int *b){ 
    for(int i = 0; i<N; i++){ 
     int group = a[i]; 
     int posit=2*group; 
     if(b[2*i]!=0){ 
      posit++; 
     } 
     b[posit] = i; 
    } 
} 

N as is clear length of a.

默认情况下，b []中的值为零，表示没有元素。

有明确的数据依赖性，并且看起来并不容易并行化。我正在寻找更多的建议，如果有一个聪明的方式，我错过了。

来源

2016-08-12 user2178841

通常，您可以尝试在包含对{i, a[i]}的数组上使用并行排序算法。也许有一种更快的通用方法，我目前没有看到......

但是，在CUDA中，您可以利用这一事实，即当您有2个冲突线程写入32位字相同的内存位置 - 一个保证成功（但你不知道哪一个）。形式上，它充当一台Arbitrary CRCW机器。

因此，你可以在2个内核调用解决您的问题：

__global__ void assign1(int* a, int* b, int elementCount) { 
    int idx = threadIdx.x + blockIdx.x*blockDim.x; 
    if (idx<elementCount) { 
     int group = a[idx]; 
     b[2*group] = idx; 
    } 
} 

__global__ void assign2(int* a, int* b, int elementCount) { 
    int idx = threadIdx.x + blockIdx.x*blockDim.x; 
    if (idx<elementCount) { 
     int group = a[idx]; 
     if (b[2*group] != idx) 
      b[2*group+1] = idx; 
    } 
} 

__host__ void assign(int* dev_a, int* dev_b, int elementCount) { 
    int gridSize = elementCount/512+1; 
    int blockSize = 512; 
    assign1<<<gridSize,blockSize>>>(dev_a, dev_b, elementCount); 
    assign2<<<gridSize,blockSize>>>(dev_a, dev_b, elementCount); 
}

在assign1最多2个线程写入同一个存储位置b[2*group]。其中一个线程保证成功。在assign2写入失败的线程重复使用b[2*group+1]的过程。

如果组中最多有3个或4个元素，则可以重复使用此方法，但随着数量增加，可能会很快停止执行。

来源

2016-08-12 22:43:54 CygnusX1

并行化与依赖

回答

相关问题