Ich habe ein hübsches Standardproblem auf der GPU lösen müssen, aber ich bin ziemlich neu in der praktischen GPGPU, also suche ich nach Ideen, um dieses Problem anzugehen.segmentierte Reduktion mit verstreuten Segmenten
Ich habe viele Punkte in 3-Raum, die einer sehr kleinen Anzahl von Gruppen zugeordnet sind (jeder Punkt gehört zu einer Gruppe), speziell 15 in diesem Fall (ändert sich nicht). Jetzt möchte ich die Mittelwert- und Kovarianzmatrix aller Gruppen berechnen. Also auf der CPU ist es ungefähr das gleiche wie:
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
Da die Anzahl der Gruppen extrem klein ist, kann der letzte Schritt auf dem CPU durchgeführt werden (Ich brauche diese Werte auf der CPU, sowieso). Der erste Schritt ist eigentlich nur eine segmentierte Reduktion, aber mit den verstreuten Segmenten.
Also war die erste Idee, die ich hatte, zuerst die Punkte nach ihren Gruppen zu sortieren. Ich dachte über eine einfache Bucket-Sortierung mit atomic_inc, um Bucket-Größen und pro-Punkt Relokalisierung Indizes zu berechnen (bekam eine bessere Idee für die Sortierung?, Atomics möglicherweise nicht die beste Idee). Danach werden sie nach Gruppen sortiert und ich könnte möglicherweise eine Adaption der segmentierten Scanalgorithmen entwickeln, die here präsentiert werden.
Aber in diesem speziellen Fall, ich habe eine sehr große Menge an Daten pro Punkt (9-10 Schwimmer, vielleicht sogar verdoppelt, wenn die Notwendigkeit entsteht), so die Standard-Algorithmen mit einem gemeinsamen Speicherelement pro Thread und einem Thread pro Punkt könnte Probleme in Bezug auf Pro-Multiprozessor-Ressourcen als Shared Memory oder Register (Ok, viel mehr auf Rechenleistung 1.x als 2.x, aber immer noch).
Aufgrund der sehr kleinen und konstanten Anzahl von Gruppen dachte ich, es könnte bessere Ansätze geben. Vielleicht gibt es bereits existierende Ideen, die für diese spezifischen Eigenschaften eines solchen Standardproblems geeignet sind. Oder vielleicht ist mein allgemeiner Ansatz nicht so schlecht und Sie haben Ideen zur Verbesserung der einzelnen Schritte, wie ein guter Sortieralgorithmus, der für eine sehr kleine Anzahl von Schlüsseln geeignet ist, oder einen segmentierten Reduktionsalgorithmus, der die gemeinsame Speicher-/Registerbenutzung minimiert.
Ich suche nach allgemeinen Ansätzen und möchte keine externen Bibliotheken verwenden. FWIW Ich verwende OpenCL, aber es sollte nicht wirklich wichtig sein, da die allgemeinen Konzepte des GPU-Computing sich nicht wirklich von den wichtigsten Frameworks unterscheiden.
Dies ist ein ziemlich häufiges Muster. Mit Thrust würden Sie zunächst 'sort_by_key' aufrufen, um die Daten in jedem Segment zusammenzuführen, und dann' reduce_by_key', um den Mittelwert und die Kovarianz jeder Gruppe zu berechnen. –