counting different values in a vector with Aparapi

Question

i want to implement an Entropy function in parallel with APARAPI. in that function i need to count different keys in a vector but it cant execute correctly.

assume that we have just 3 different values. here is my codes:

final int[] V = new int[1024];
// Initialization for V values
final int[] count = new int[3];
Kernel kernel = new Kernel(){
    @Override
    public void run(){
        int gid = getGlobalId();
        count[V[gid]]++;
    }
};
kernel.execute(Range.create(V.length));
kernel.dispose();

after run this code segment, when i print count[] values it gives me 1,1,1. it seems that count[V[gid]]++ execute just 1 time for each V[gid].

thanks.

Answer 1

So here is the problem. The ++ operator is actually three operations in one: read the current value, increment it, write the new value. In Aparapi you have potentially 1024 GPU threads running simultaneously. That means they will read the value, probably all the same time when the value is 0, then increment it to 1, then all 1024 threads will write 1. So it is acting as expected.

What you are trying to do is called a Map-reduce function. You are just skipping a lot of steps. You need to remember Aparapi is a system that has no Thread safety, so you have to write your algorithms to accommodate that. That is where Map-reduce comes in and here is how to do one. I just wrote it and added it to the Aparapi repository at its new home, details below.

int size = 1024;
final int count = 3;
final int[] V = new int[size];

//lets fill in V randomly...
for (int i = 0; i < size; i++) {
    //random number either 0, 1, or 2
    V[i] = (int) (Math.random() * 3);
}

//this will hold our values between the phases.
int[][] totals = new int[count][size];

///////////////
// MAP PHASE //
///////////////
final int[][] kernelTotals = totals;
Kernel mapKernel = new Kernel() {
    @Override
    public void run() {
        int gid = getGlobalId();
        int value = V[gid];
        for(int index = 0; index < count; index++) {
            if (value == index)
                kernelTotals[index][gid] = 1;
        }
    }
};
mapKernel.execute(Range.create(size));
mapKernel.dispose();
totals = kernelTotals;

//////////////////
// REDUCE PHASE //
//////////////////
while (size > 1) {
    int nextSize = size / 2;
    final int[][] currentTotals  = totals;
    final int[][] nextTotals = new int[count][nextSize];
    Kernel reduceKernel = new Kernel() {
        @Override
        public void run() {
            int gid = getGlobalId();
            for(int index = 0; index < count; index++) {
                nextTotals[index][gid] = currentTotals[index][gid * 2] + currentTotals[index][gid * 2 + 1];
            }
        }
    };
    reduceKernel.execute(Range.create(nextSize));
    reduceKernel.dispose();

    totals = nextTotals;
    size = nextSize;
}
assert size == 1;

/////////////////////////////
// Done, just print it out //
/////////////////////////////
int[] results = new int[3];
results[0] = totals[0][0];
results[1] = totals[1][0];
results[2] = totals[2][0];

System.out.println(Arrays.toString(results));

Keep in mind while it may seem inefficient it actually works pretty well on much larger number. This algorithm works just fine with

size = 1048576.

With the new size the following result was computed on my system in about a second.

[349602, 349698, 349276]

One final note, you might want to consider moving to the more active project at aparapi.com. It includes several fixes to bugs and a lot of extra features and performance enhancements over the older library you linked above. It is also in maven central with about a dozen releases. so it is easier to use. I just wrote the code in this answer but decided to use it in the new Aparapi repository's example section, you can find that at the following link in the new Aparapi repository.