Is it possible to run the sum computation in parallel in OpenCL?

Question

I am a newbie in OpenCL. However, I understand the C/C++ basics and the OOP. My question is as follows: is it somehow possible to run the sum computation task in parallel? Is it theoretically possible? Below I will describe what I've tried to do:

The task is, for example:

double* values = new double[1000]; //let's pretend it has some random values inside
double sum = 0.0;

for(int i = 0; i < 1000; i++) {
    sum += values[i];
}

What I tried to do in OpenCL kernel (and I feel it is wrong because perhaps it accesses the same "sum" variable from different threads/tasks at the same time):

__kernel void calculate2dim(__global float* vectors1dim,
                            __global float output,
                            const unsigned int count) {
    int i = get_global_id(0);
    output += vectors1dim[i];
}

This code is wrong. I will highly appreciate if anyone answers me if it is theoretically possible to run such tasks in parallel and if it is - how!

Answer 1

If you want to sum the values of your array in a parallel fashion, you should make sure you reduce contention and make sure there's no data dependencies across threads.

Data dependencies will cause threads to have to wait for each other, creating contention, which is what you want to avoid to get true parallellization.

One way you could do that is to split your array into N arrays, each containing some subsection of your original array, and then calling your OpenCL kernel function with each different array.

At the end, when all kernels have done the hard work, you can just sum up the results of each array into one. This operation can easily be done by the CPU.

The key is to not have any dependencies between the calculations done in each kernel, so you have to split your data and processing accordingly.

I don't know if your data has any actual dependencies from your question, but that is for you to figure out.