les algorithmes graphiques sur GPU

Question

les threads GPU actuels sont en quelque sorte limités (limite de mémoire, limite des structures de données, pas de récursivité ...). Pensez-vous qu'il serait possible d'implémenter un problème de théorie des graphes sur le GPU. par exemple couverture de vertex? ensemble dominant? ensemble indépendant? max clique? ....

est-il également possible d'avoir des algorithmes de branche et de liaison sur les GPU? Retour arrière récursif?

Answer 1

Vous être intéressé par

1. Exploring the Limits of GPUs With Parallel Graph Algorithms
   

2. Accelerating large graph algorithms on the GPU using CUDA.

Answer 2

Ce tangentiellement lié à votre question, mais je l'ai mis en place un « récursive » algorithme retours en arrière pour l'énumération « des promenades auto-évitante » sur un réseau (nb: la pile a été simulé dans le noyau CUDA, à évitez le surcoût de la création de variables locales pour tout un tas d'appels de fonction). C'est possible de le faire efficacement, donc je suis sûr que cela peut être adapté à un contexte théorique graphique. Voici un lien vers un séminaire sur le sujet où j'ai donné une discussion générale sur le retour en arrière dans le paradigme SIMD (Single Instruction Multiple Data); c'est un pdf d'environ 1MB en taille http://bit.ly/9ForGS. Je ne prétends pas connaître la littérature plus large sur les algorithmes théoriques de graphique sur des GPUs, mais j'espère que ce qui précède aide un peu.

(. @TheMachineCharmer, merci pour les liens)