CODEWITHSUNDEEP
openclgpgpu
Dmitry Galchinsky
Dmitry Galchinsky

Reputation: 2201

Partial sorting of small array in OpenCL private memory

The task is to find N largest elements in array. The array is quite small (~40 items). I am using this algorithm:

    float max1 = -inf;
    int max1I = -1;
    float max2 = -inf;
    int max2I = -1;
    float max3 = -inf;
    int max3I = -1;
    float max4 = -inf;
    int max4I = -1;
    float max5 = -inf;
    int max5I = -1;
    float performances[MAX_NUMBER_OF_SELECTIONS];
    for (int i = 0; i < numberOfSelections; ++i) {
        float performance = /*some calculations*/;
        performances[i] = performance;
        if (performance > max1) {
            max5 = max4; max5I = max4I;
            max4 = max3; max4I = max3I;
            max3 = max2; max3I = max2I;
            max2 = max1; max2I = max1I;
            max1 = performance; max1I = i;
        } else if (performance > max2) {
            max5 = max4; max5I = max4I;
            max4 = max3; max4I = max3I;
            max3 = max2; max3I = max2I;
            max2 = performance; max2I = i;
        } else if (performance > max3) {
            max5 = max4; max5I = max4I;
            max4 = max3; max4I = max3I;
            max3 = performance; max3I = i;
        } else if (performance > max4) {
            max5 = max4; max5I = max4I;
            max4 = performance; max4I = i;
        } else if (performance > max5) {
            max5 = performance; max5I = i;
        }
    }

The approach was good enough but now I need to make it top10 instead of top5. Should I copy-paste this pattern? Or maybe there is something better?

Upvotes: 0

Views: 288

Answers (1)

DarkZeros
DarkZeros

Reputation: 8410

If you want to do it on a large array this code is NOT valid. I am supposing that you have lots of small arrays and each work item works on one of them.

I would do something like:

//Init
float maxs[10+1];
for(int i=0; i<10+1; i++){
    maxs[i] = -inf;
}

for(int i=0; i<size; i++){
    //Is it higher than the element 0?
    if(data[i] > maxs[0]){
        maxs[0] = data[i];
        for(int j=0; j<10; j++){
            if(maxs[j] > maxs[j+1])
                swap(maxs[j], maxs[j+1]);
            else break;
        }
    }
}

Now you have an array of 11 elements ordered from small to high, just take the last 10 elements.

The code can be further optimized, but it is very simple.

Upvotes: 1

Related Questions