Graphenalgorithmen auf GPU

Question

werden die aktuellen GPU-Threads irgendwie begrenzt (Memory Limit, Limit von Datenstrukturen, keine Rekursion ...).

denken Sie, es möglich wäre, eine Graphentheorie Problem auf GPU umzusetzen. zum Beispiel Vertex Cover? dominierend Satz? unabhängiger Satz? max Clique? ....

ist es auch möglich zu haben, Branch-and-Bound Algorithmen auf GPUs? Rekursive Rückzieher?

Answer 1

Sie werden in interessiert sein

1. Die Erforschung der Grenzen der GPUs mit parallelen Graphenalgorithmen < br>

2. Accelerating große Graphenalgorithmen auf der GPU mit CUDA .

Answer 2

Dies ist tangential zu Ihrer Frage, aber ich habe einen „rekursive“ Backtracking-Algorithmus implementiert für Aufzählen „Selbst vermeiden Spaziergänge“ auf einem Gitter (nb: der Stapel wurde in der CUDA Kernel simuliert, den Overhead zu vermeiden Erstellen von lokalen Variablen für eine ganze Reihe von Funktionsaufrufen). Es ist möglich, dies effizient zu tun, so bin ich sicher, kann dies zu einer graphentheoretischen Kontext angepasst werden. Hier ist ein Link zu einem Seminar zum Thema, wo ich in der Single Instruction Multiple einige allgemeine Diskussion gab über Backtracking-Daten (SIMD) Paradigma; es ist ein pdf von etwa 1 MB groß http://bit.ly/9ForGS .

Ich behaupte nicht, um die breitere Literatur auf graphentheoretische Algorithmen auf GPUs zu wissen, aber hoffen, dass die oben etwas hilft.

(@ TheMachineCharmer, vielen Dank für die Links.)