algoritmos de grafos en GPU

Question

los hilos GPU actuales de alguna manera están limitados (límite de memoria, límite de estructuras de datos, sin recursividad ...).

¿cree que sería factible implementar un problema la teoría de grafos en la GPU. por ejemplo de cobertura de vértices? Dominando establecido? conjunto independiente? max camarilla? ....

También es factible tener algoritmos y con destino a la rama en las GPU? backtracking recursivo?

Answer 1

Usted estará interesado en

1. explorar los límites de las GPU Con Parallel Graph Algoritmos < br>

2. Acelerar grandes algoritmos gráfico de la GPU usando CUDA .

Answer 2

Este es tangencialmente relacionado con su pregunta, pero he implementado un "recursivo" algoritmo de retroceso para enumerar los "paseos auto-evitar" en un enrejado (NB: la pila se simuló en el kernel de CUDA, para evitar la sobrecarga de la creación de variables locales para un montón de llamadas de función). Es posible hacer esto de manera eficiente, así que estoy seguro de que esto se puede adaptar a un contexto teórico gráfico. Aquí hay un enlace a un seminario sobre el tema en el que me dio un poco de discusión general sobre el retroceso dentro de los múltiples datos (SIMD) paradigma Single Instruction; que es un pdf de alrededor de 1 MB de tamaño http://bit.ly/9ForGS .

No pretendo saber acerca de la literatura más amplia sobre el gráfico de algoritmos teóricos sobre las GPU, pero espero que el anterior ayuda un poco.

(@ TheMachineCharmer, gracias por los enlaces.)