Conditional reduction in CUDA

Question

I need to sum about 100000 values stored in an array, but with conditions.

Is there a way to do that in CUDA to produce fast results?

Can anyone post a small code to do that?

Answer 1

I think that, to perform conditional reduction, you can directly introduce the condition as a multiplication by 0 (false) or 1 (true) to the addends. In other words, suppose that the condition you would like to meet is that the addends be smaller than 10.f. In this case, borrowing the first code at Optimizing Parallel Reduction in CUDA by M. Harris, then the above would mean

__global__ void reduce0(int *g_idata, int *g_odata) {

    extern __shared__ int sdata[];

    // each thread loads one element from global to shared mem
    unsigned int tid = threadIdx.x;
    unsigned int i = blockIdx.x*blockDim.x + threadIdx.x;
    sdata[tid] = g_idata[i]*(g_data[i]<10.f);
    __syncthreads();

    // do reduction in shared mem
    for(unsigned int s=1; s < blockDim.x; s *= 2) {
        if (tid % (2*s) == 0) {
            sdata[tid] += sdata[tid + s];
        }
        __syncthreads();
    }

    // write result for this block to global mem
    if (tid == 0) g_odata[blockIdx.x] = sdata[0];
}

If you wish to use CUDA Thrust to perform conditional reduction, you can do the same by using thrust::transform_reduce. Alternatively, you can create a new vector d_b copying in that all the elements of d_a satisfying the predicate by thrust::copy_if and then applying thrust::reduce on d_b. I haven't checked which solution performs the best. Perhaps, the second solution will perform better on sparse arrays. Below is an example with an implementation of both the approaches.

#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/reduce.h>
#include <thrust/count.h>
#include <thrust/copy.h>

// --- Operator for the first approach
struct conditional_operator { 
    __host__ __device__ float operator()(const float a) const {
    return a*(a<10.f);
    }
};

// --- Operator for the second approach
struct is_smaller_than_10 {
    __host__ __device__ bool operator()(const float a) const {
        return (a<10.f);
    }
};

void main(void) 
{
    int N = 20;

    // --- Host side allocation and vector initialization
    thrust::host_vector<float> h_a(N,1.f);
    h_a[0] = 20.f;
    h_a[1] = 20.f;

    // --- Device side allocation and vector initialization
    thrust::device_vector<float> d_a(h_a);

    // --- First approach
    float sum = thrust::transform_reduce(d_a.begin(), d_a.end(), conditional_operator(), 0.f, thrust::plus<float>());
    printf("Result = %f\n",sum);

    // --- Second approach
    int N_prime = thrust::count_if(d_a.begin(), d_a.end(), is_smaller_than_10());
    thrust::device_vector<float> d_b(N_prime);
    thrust::copy_if(d_a.begin(), d_a.begin() + N, d_b.begin(), is_smaller_than_10());
    sum = thrust::reduce(d_b.begin(), d_b.begin() + N_prime, 0.f);
    printf("Result = %f\n",sum);

    getchar();

}