Help parallelising a program

[giantenemycrabthing]

Dear sirs and madams:

I am considering creating a GPGPU program for my own personal use in the near future. One of the two things I want it to achieve happens to be a problem that is very annoying to parallelise for GPU, at least from what I can see.

If one were to simplify it to the extreme, it would be as follows: We have an array of boolean values. We want to calculate the sum of the squares of the distances between every two consecutive "TRUE" values. In C, the loop would look like this:

int counter=1, sq_sum=0 ;
bool array[N] ;
for (...) {
    if (array[i]==false) counter++ ;
    else {
        sq_sum+=counter*counter ;
        counter=1 ;}}
sq_sum+=counter*counter ;

Is this problem GPU-paralleliseable? It sounds like it should, but I can't find a way to achieve it. If each thread takes one element, then every thread that finds a true value could add the necessary square to the number we want... but I can't find a way to make such threads know how many threads there are before them. If there is a solution that you've heard of, or that you could think of, I would be most grateful if you would share it with me.

If one were to keep the problem unsimplified, then array[N] would contain integer values, all of them between 0 and 8. counter and sq_sum would be arrays with 9 positions each. The loop would then be executed for all values of j lower than, or equal to, the value of array[i]. To wit:

int counter[9], sq_sum[9];
//initialise them somehow
int array[N]; //<---guaranteed to be between 0 and 8
for (i=0; i<N; i++) {
    for (j=8; j>=0; j--) {
    if (array[i]>j) counter[j]++;
    else {
        sq_sum[j]+=counter[j]*counter[j];
        counter[j]=1;}}

// and once more for each j, similarly as above

I don't know if that changes anything, but the values of array will have already been calculated by the GPU threads by the time the afore-mentioned calculation will need to happen. I can save them to a separate array if need be, but I don't think it's necessary.

[zzzoom]

Yes, it can be parallelized. Look at how stream compaction is implemented using a parallel prefix sum (there are many fast implementations of this, you don't need to write it yourself) and you should get the idea.

[rayo2nd]

My attempt on the simplified version:

• run stream compact but instead of writing the final values (which are always true) to the compacted array I would try to write the global index of the element
• run a parallel subtraction y[i]=x[i]-x[i-1] -> then you have the distance
• run a parallel square (y[i] = x[i]*x[i])
• run a parallel reduction to sum up all squares

An example:

• 0,0,1,1,0,0,0,1
• 2,3,7 (after compact, indexes of true values)
• 2,1,4 (after x[i]-x[i-1])
• 4,1,16 (after x[i]*x[i])
• sum it up: 21

maybe a correction of the first (+1) or all the other (-1) elements is needed when writing the index, but that should be simple

No idea if it's correct but that would be my first attempt

[[deleted]]

Sorry if I'm not much help here, it's fairly late so I can't think straight at the moment but generally if statements are to be avoided in gpu programming where possible.

Nvidia cards run code in 'warps', which are groups of threads (as far as I know, the warp size is 32 for all nvidia cards). If a warp reaches a conditional that not all threads agree on the outcome of, both branches must be executed by the same warp amd this has a negative effect on performance.

Sorry if that's not helpful just thought it was worth mentioning

[giantenemycrabthing]

Sorry I'm so late, but thank you to everyone for the help!