Übertragen von großen variablen Speichermengen von Cuda

Question

Cuda ist genial und ich benutze es wie verrückt, aber ich nutze nicht ihr volles Potential, weil ich ein Problem beim Übertragen von Speicher habe und mich fragte, ob es einen besseren Weg gäbe eine variable Menge an Speicher aus. Grundsätzlich sende ich 65535 Artikel-Array in Cuda und Cuda analysiert jedes Datenelement um 20.000 verschiedene Möglichkeiten und wenn es eine Übereinstimmung in meiner Programmlogik gibt, dann speichert es eine 30-Liste als Ergebnis. Denken Sie an meine Logik, jede unterschiedliche Kombination zu analysieren und dann auf die Summe zu schauen und wenn die Summe gleich einer Zahl ist, die ich suche, dann speichert sie die Ergebnisse (was eine 30 int-Liste für jeden analysierten Gegenstand ist).

Das Problem ist 65535 (Blöcke/Elemente im Datenarray) * 20000 (insgesamt getestete Kombinationen pro Element) = 1.310.700.000. Das bedeutet, dass ich ein Array dieser Größe erstellen muss, um die Chance zu nutzen, dass alle Daten eine positive Übereinstimmung ergeben (was extrem unwahrscheinlich ist und das Erstellen von int output[1310700000][30] scheint verrückt nach Speicher zu sein). Ich war gezwungen, es kleiner zu machen und weniger Blöcke zum Prozess zu senden, weil ich nicht weiß, ob Cuda effizient in eine verknüpfte Liste oder eine dynamisch große Liste schreiben kann (mit dieser Methode schreibt es die Ausgabe mit Block in den Host-Speicher) * number_of_different_way_tests).

Gibt es einen besseren Weg, dies zu tun? Kann Cuda irgendwie freien Speicher schreiben, der nicht von der Blockid abgeleitet ist? Wenn ich diesen Prozess auf der CPU teste, haben weniger als 10% des Element-Arrays eine positive Übereinstimmung, so dass es extrem unwahrscheinlich ist, dass ich jedes Mal so viel Speicher verwende, wenn ich Arbeit an den Kernel sende.

p.s. Ich schaue oben und obwohl es genau das ist, was ich tue, wenn es verwirrend ist, dann eine andere Art darüber nachzudenken (nicht genau das, was ich tue, aber gut genug, um das Problem zu verstehen), sende ich 20.000 Arrays enthalten 65.535 Elemente) und jedes Element mit seinem Peer in den anderen Arrays hinzufügen und wenn die Summe gleich einer Zahl (sagen wir 200-210), dann möchte ich die Zahlen kennen, die es hinzugefügt, um dieses übereinstimmende Ergebnis zu erhalten. Wenn die Zahlen sehr weit reichen, dann werden nicht alle übereinstimmen, aber mit meinem Ansatz bin ich gezwungen, diese riesige Menge an Speicher zu malloc. Kann ich die Ergebnisse mit mallocing weniger Speicher erfassen? Meine derzeitige Herangehensweise an malloc ist so viel wie ich frei habe, aber ich bin gezwungen, weniger Blöcke zu laufen, was nicht effizient ist (Ich möchte so viele Blöcke und Threads pro Zeit ausführen, weil ich die Art mag, wie Cuda die Blöcke organisiert und ausführt) . Gibt es irgendwelche Cuda oder C Tricks, die ich dafür benutzen kann oder ich bin fest daran beteiligt, die maximal möglichen Ergebnisse zu mallocen (und viel mehr Speicher zu kaufen)?

Answer 1

Wie Roger Dahls großartige answer: Die Funktionalität, die Sie suchen, heißt Stream-Komprimierung.

Sie müssen wahrscheinlich ein Array bereitstellen, das Platz für 4 Lösungen pro Thread enthält, da der Versuch, die Ergebnisse in einer kompakten Form zu speichern, wahrscheinlich so viele Abhängigkeiten zwischen den Threads erzeugt, die die Leistung beim Kopieren erhalten hat Weniger Daten zurück zum Host gehen durch eine längere Kernel-Ausführungszeit verloren. Die Ausnahme ist, wenn fast alle Threads keine Lösungen finden. In diesem Fall können Sie möglicherweise eine atomare Operation verwenden, um einen Index in einem Array zu verwalten. Für jede gefundene Lösung würden Sie sie also in einem Array an einem Index speichern und dann mit einer atomaren Operation den Index erhöhen. Ich denke, es wäre sicher atomicAdd() dafür zu verwenden. Vor dem Speichern eines Ergebnisses würde der Thread atomicAdd() verwenden, um den Index um eins zu erhöhen. atomicAdd() gibt den alten Wert zurück und der Thread kann das Ergebnis mit dem alten Wert als Index speichern.

In einer häufigeren Situation, in der es jedoch viele Ergebnisse gibt, ist die beste Lösung, einen Verdichtungsvorgang als separaten Schritt durchzuführen. Eine Möglichkeit, dies zu tun, ist mit Schub :: copy_if. Siehe diese Frage für mehr Hintergrund.