Добавление всех комбинаций элементов массива с использованием GPU

Question

Я новичок в программировании CUDAfy и не могу вычислить сумму всех комбинаций элементов в массиве. Я не могу представить себе алгоритм, достаточно подходящий для переноса на графический процессор. Любая помощь или любой алгоритм очень ценится.

Серийная версия кода приводится ниже:

for (int i = 0; i < Array.Count - 1; i++) 
{ 
    for (int j = (i + 1); j < Array.Count; j++) 
    { 
     ans.Add(Array.ElementAt(i) + Array.ElementAt(j));  

    } 
} 

Answer 1

Это не дает ГПУ очень много работы, кроме одного дополнения. Массив должен быть значительным, прежде чем вы увидите преимущество. Во всяком случае:

Я использую C++ и не знаком с C# или CUDAfy, но должно быть легко переносить логику. Функция ядра, которая хранит сумму каждой пары элементов в массиве:

template<typename T> 
__global__ void sum_combinations_of_array(const T* arr, const size_t len, T* dest) 
{ 
    const int tx = blockIdx.x*blockDim.x+threadIdx.x; 
    const int ty = blockIdx.y*blockDim.y+threadIdx.y; 
    if(tx < len && ty < len && tx < ty) { 
     dest[tx*len+ty] = arr[tx]+arr[ty]; 
    } 
} 

Вы просто используя 2D резьбы блоки, чтобы решить, какие элементы массива для добавления (они просто занимают место i и j в вашем коде). arr должно быть не менее len, а dest должно быть не менее len*len. Хост-код, чтобы установить все это и запустить его, будет примерно таким:

const int len = 1000; 

int* arr; 
cudaMalloc(&arr, len*sizeof(int)); 

int* matrix; 
cudaMalloc(&matrix, len*len*sizeof(int)); 
// cudaMalloc2D could also be used here, but then you'll 
// have to pay attention to the pitch 
cudaMemset(matrix, 0, len*len*sizeof(int)); 

// copy host array to arr with cudaMemcpy 
// ... 

const int numThreads = ???; // depends on your hardware 
dim3 grid(len, (len+numThreads-1)/numThreads), threads(1, numThreads); 
sum_combinations_of_array<int><<<grid,threads>>>(arr, len, matrix); 
cudaDeviceSynchronize(); // wait for completion 

// copy device matrix to host with cudaMemcpy (or cudaMemcpy2D) 
// remember any element i<=j will be 0 
// ... 

cudaFree(arr); 
cudaFree(matrix);