Bei der Parallelverarbeitung ist es normalerweise der erste Schritt, das Ursprungsproblem in eine Unteraufgabe zu zerlegen und sie auf Blöcke und Threads abzubilden.Gibt es eine effiziente Möglichkeit, Graphen auf Blöcke in der CUDA-Programmierung abzubilden?
Bei Problemen mit der regulären Datenstruktur ist es sehr einfach und effizient, z. B. Matrix Multiplikation, FFT und so weiter.
Aber Graphtheorie Probleme wie kürzester Weg, Graph Traversal, Baumsuche, haben unregelmäßige Datenstruktur. Es scheint mir nicht einfach zu sein, das Problem bei der Verwendung von GPU auf Blöcke und Threads zu verteilen.
Ich frage mich, ob es effiziente Lösungen für diese Art von Partition gibt?
Der Einfachheit halber, nehmen Sie als Beispiel ein Shortcap-Problem mit einer Quelle. Ich bin daran fest, wie man den Graphen so teilt, dass sowohl die Lokalität als auch die Koaleszenz entsteht.
Das ist eine sehr weit gefasste Frage, die sehr schwer zu beantworten. Hatten Sie eine bestimmte Anwendung im Hinterkopf? Könnten Sie den Umfang dessen, nach dem Sie fragen, verfeinern? – talonmies
Können Sie mehr über den Anwendungsbereich der Algorithmen sagen, nach denen Sie suchen? Ich kann meine Erfahrungen in der Suche nach dem nächsten Nachbarn austauschen, aber ich kann nicht hilfreich sein. Wenn Sie nach einem allgemeinen Grafikproblem wie der Spanning-Tree-Suche fragen ... – geek
@ marina.k Ich arbeite nicht an einem Single-Source-Problem mit dem kürzesten Pfad. Erstens scheint der Dijkstra-Algorithmus schwierig zu sein, wenn er in einem Vielkernsystem realisiert wird. Zweitens, wenn eine dem Dijkstra-Algorithmus ähnliche Iterationslösung verwendet wird, weil die Beschränkung zwischen Knoten sehr komplex und unregelmäßig ist, ist es schwierig, die Lokalität und das Verschmelzen zu gewährleisten, selbst wenn geteilter Speicher zum Zwischenspeichern verwendet wird. – konjac