los hilos de GPU actuales son de alguna manera limitados (límite de memoria, límite de estructuras de datos, sin recurrencia ...).algoritmos de gráfico en la GPU
crees que sería factible implementar un problema de teoría de grafos en la GPU. por ejemplo, cobertura de vértice? conjunto dominante? conjunto independiente? max clique? ....
¿También es posible tener algoritmos de ramificación y enlace en las GPU? Retroceso recursivo?
usted estará interesado en
Esto se relaciona tangencialmente a 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, a evite la sobrecarga de crear variables locales para un montón de llamadas a funciones). Es posible hacerlo de manera eficiente, por lo 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 di una discusión general sobre retroceso dentro del paradigma de datos múltiples de instrucción única (SIMD); es un pdf de aproximadamente 1 MB de tamaño http://bit.ly/9ForGS.
No pretendo conocer la literatura más amplia sobre algoritmos teóricos de gráficos en GPU, pero espero que lo anterior ayude un poco.
(. @TheMachineCharmer, gracias por los enlaces)
Vamos a añadir éste, que ha aparecido en la media hora: [Aceleración CUDA Gráfico Algoritmos al máximo Warp] (http: //citeseerx.ist.psu. edu/viewdoc/download? doi = 10.1.1.220.1923 & rep = rep1 & type = pdf). Para ciertos gráficos, mejora dramáticamente en el segundo resultado al que se vincula. –