Zählen verschiedener Werte in einem Vektor mit Aparapi

Question

Ich möchte eine Entropie-Funktion parallel zu APARAPI implementieren. In dieser Funktion muss ich verschiedene Schlüssel in einem Vektor zählen, aber es kann nicht korrekt ausgeführt werden.

angenommen, dass wir nur 3 verschiedene Werte haben. hier ist mein 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(); 

nach Laufe dieses Codesegment, wenn i [] Werte Druckzähldaten es gibt mir 1,1,1. Es scheint, dass nur 1 mal für jedes V [gid] ausführen.

danke.

Answer 1

Also hier ist das Problem. Der ++ Operator ist eigentlich drei Operationen in einem: Lesen Sie den aktuellen Wert, inkrementieren Sie ihn, schreiben Sie den neuen Wert. In Aparapi laufen möglicherweise 1024 GPU-Threads gleichzeitig. Das bedeutet, dass sie den Wert lesen werden, wahrscheinlich alle die gleiche Zeit, wenn der Wert 0 ist, dann wird er auf 1 erhöht, dann schreiben alle 1024 Threads 1. Also verhält es sich wie erwartet.

Was Sie versuchen zu tun ist eine Map-Reduce-Funktion. Du überspringst einfach eine Menge Schritte. Sie müssen sich daran erinnern, dass Aparapi ein System ist, das keine Thread-Sicherheit hat, also müssen Sie Ihre Algorithmen dafür schreiben. Hier kommt Map-reduce ins Spiel und hier ist, wie man es macht. Ich schrieb es einfach und fügte es dem Aparapi-Repository in seinem neuen Zuhause hinzu, Details unten.

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)); 

Denken Sie daran, während es ineffizient scheint, funktioniert es ziemlich gut auf viel größere Anzahl. Dieser Algorithmus funktioniert gut mit

size = 1048576. 

Mit der neuen Größe das folgende Ergebnis auf meinem System in etwa einer Sekunde berechnet wurde.

[349602, 349698, 349276] 

Ein letzter Hinweis, möchten Sie vielleicht bei aparapi.com zu den aktiveren Projekt bewegen zu betrachten. Es enthält mehrere Fehlerbehebungen und viele zusätzliche Funktionen und Leistungsverbesserungen gegenüber der älteren Bibliothek, die Sie oben verlinkt haben. Es ist auch in Maven Central mit etwa einem Dutzend Releases. So ist es einfacher zu benutzen. Ich habe gerade den Code in dieser Antwort geschrieben, aber ich entschied mich, ihn im Beispielabschnitt des neuen Aparapi-Repositorys zu verwenden. Sie finden ihn unter the following link in the new Aparapi repository.