Schnell Art in GLSL?

Question

Ich betrachte einen großen Teil der Verarbeitung auf der GPU Portierung eines GLSL Shader verwendet. Eine der unmittelbaren Probleme, die ich über gestolpert ist, dass in einer der Schritte, der Algorithmus eine Liste von Elementen zu halten braucht, sortieren sie und die wenigen Größten nehmen (die Nummer auf dem Daten abhängig ist). Auf der CPU ist dies einfach ein STL-Vektor und qsort geschieht mit (), aber in GLSL habe ich nicht solche Einrichtungen. Gibt es eine Möglichkeit mit diesem Mangel zu begegnen?

Answer 1

Disclosure: Ich weiß wirklich GLSL nicht - ich habe GPGPU Programmierung mit der AMD Stream-SDK wurde tun, die unterschiedliche Programmiersprache hat

.

Von Ihnen auf Bjorn Antwort kommentieren, entnehme ich, dass Sie nicht interessiert sich für die GPU mit einer riesigen Datenbank zu sortieren - wie ein Reverse-Telefonbuch erstellen oder was auch immer, aber stattdessen haben Sie eine kleine Datenmenge und jedes Fragment hat seine eigene Datenmenge zu sortieren. Mehr wie der Versuch, mittlere Bildpunkt-Filterung zu tun?

Ich kann nur allgemein sagen:

Für kleine Datensätze, der Sortieralgorithmus wirklich keine Rolle spielt. Während der Menschen verbracht haben Karrieren sich Gedanken über den der beste Sortieralgorithmus für sehr große Datenbanken, für kleinen N ist es wirklich egal, ob Sie Schnell Art verwenden, Haufen Sortieren, Radix Sortieren, Sortieren Shell, Optimierter Bubble Sort, nicht optimiert Bubble Sort, usw. Zumindest dest~~POS=HEADCOMP ist es nicht Sache tut viel auf einer CPU.

GPUs sind SIMD-Geräte, so dass sie wie jeden Kernel haben die gleichen Operationen im Gleichschritt ausgeführt wird. Die Berechnungen sind billig, aber Zweige sind teuer und datenabhängigen Branchen, in denen jeder Kern eine andere Art und Weise BRANCHS ist sehr, sehr, sehr teuer.

Also, wenn jeder Kern seine eigene kleine Datenmenge hat zu sortieren, und die Anzahl der Daten zu sortieren, Daten abhängig, und es könnte eine andere Zahl für jeden Kernel sein, sind Sie wahrscheinlich besser dran, eine maximale Größe Kommissionierung (wenn Sie können ), die Arrays mit Unendlich oder eine große Anzahl Klotzen, und von denen jeder Kern die genaue gleiche Art durchführen, die eine nicht optimierte branchless Blasensortierung, etwa wie folgt sein würde:

Pseudocode (da ich weiß, GLSL nicht), eine Art 9 Punkte

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
  for (size_t i = 0; i < n; ++i) {
    TwoSort (A[i], A[i+1]);
  }
}

Answer 2

Hast Du diesen Artikel gesehen? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

war ich nicht sicher, ob Sie waren auf der Suche nach einem Quicksort-Algorithmus oder einem schnellen Sortieralgorithmus. Der Algorithmus in dem Artikel verwendet Mergesort ...

Answer 3

Ich habe keine Kenntnisse über GPU-Programmierung nicht bekommt.

würde ich Heapsort verwenden, anstatt quicksort, weil Sie sagten, Sie nur an den oberen paar Werte zu suchen. Der Heap kann in O(n) Zeit gebaut werden, aber die Top-Wert bekommen ist log(n). Deshalb, wenn Sie die Anzahl der Werte, die Sie benötigen, ist deutlich kleiner als die Gesamtzahl der Elemente, die Sie einige Performance gewinnen konnte.