die aktuellen GPU-Threads sind irgendwie begrenzt (Speicherlimit, Grenze der Datenstrukturen, keine Rekursion ...).Graph-Algorithmen auf GPU
Denken Sie, es wäre machbar, ein Graph-Theorie-Problem auf GPU zu implementieren. zum Beispiel Vertex Cover? dominierendes Set? unabhängiges Set? max clique? ....
ist es auch möglich, Branch-and-Bound-Algorithmen auf GPUs zu haben? Rekursives Zurückverfolgen?
Sie werden in
Dies wird tangential zu Ihrer Frage, aber ich habe für Aufzählen „Selbst vermeiden walks“ auf einem Gitter (nb einen „rekursive“ Backtracking-Algorithmus implementiert: der Stapel wurde simuliert innerhalb des CUDA Kernel zu Vermeiden Sie den Aufwand, lokale Variablen für eine ganze Reihe von Funktionsaufrufen zu erstellen. Es ist möglich, dies effizient zu tun, ich bin mir sicher, dass dies an einen graphentheoretischen Kontext angepasst werden kann. Hier ist ein Link zu einem Seminar zu dem Thema, wo ich eine allgemeine Diskussion über Backtracking innerhalb des SIMD-Paradigmas (Single Instruction Multiple Data) geführt habe; Es ist ein PDF von etwa 1 MB in der Größe http://bit.ly/9ForGS.
Ich behaupte nicht, über die breitere Literatur über graphentheoretische Algorithmen auf GPUs zu wissen, aber hoffe, das oben genannte hilft ein wenig.
(. @TheMachineCharmer, danke für die Links)
Lassen Sie uns dieses man hinzufügen, dass in der Zwischenzeit aufgetaucht: [Beschleunigte CUDA Graphenalgorithmen bei Maximum Warp] (http: //citeseerx.ist.psu. edu/viewdoc/herunterladen? doi = 10.1.1.220.1923 & rep = rep1 & type = pdf). Bei bestimmten Grafiken verbessert sich das Ergebnis gegenüber dem zweiten Ergebnis, zu dem Sie eine Verknüpfung herstellen, erheblich. –