Y a-t-il de bons papiers discutant de la manière de prendre un programme dynamique et de le paralléliser?
3 Réponses :
IIRC, ce que vous faites généralement avec la programmation dynamique consiste à diviser récursivement un problème en subproblèmes et à assembler des solutions optimales à partir de substructions optimales. Ce qui le rend efficace est que toutes les substructions optimales sont intégrées à un cache afin de ne pas avoir besoin de recalcules.
Si le problème peut être divisé de plusieurs manières, vous pouvez rechercher le solveur pour chaque sous-soluité. Si chaque problème (sous) est en moyenne de 1 + epsilon (pour EPSILON intéressant plus que zéro) des substructions possibles, vous obtiendrez ainsi beaucoup de parallélisme de cette façon. Vous aurez probablement besoin de verrous sur les entrées de cache pour protéger les solutions individuelles d'être construites plus d'une fois.
Vous avez besoin d'une langue dans laquelle vous pouvez faire des sous-tâches de fourchettes plus à moindre coût que le travail de les résoudre et qui est heureux d'avoir beaucoup de tâches fourchues à la fois. Les offres parallèles typiques dans la plupart des langues font cela mal; Vous ne pouvez pas avoir beaucoup de tâches fourchues dans des systèmes qui utilisent "le grand modèle de pile" (voir Comment une langue sans empilement fonctionne-t-elle? ).
Nous avons mis en place notre programmation parallèle Langauge, Parlanse, pour obtenir une langue qui avait les bonnes propriétés.
Nous avons récemment publié un document montrant comment paralléliser n'importe quel D.P. Sur une mémoire multicœur de mémoire partagée au moyen d'une table de hachage sans verrou partagée:
Stivala, A. et Stuckey, P. J. et Garcia de la Banda, M. et Hermenegildo, M. et Wirth, A. 2010 "Programmation dynamique parallèle sans verrouillage" J. parallèle distribuée. Compu. 70: 839-848 DOI: 10.1016 / J.JPDC.2010.01.004
http://dx.di.org/10.1016/j.jpdc. 2010.01.004
essentiellement, vous démarrez plusieurs threads, tout en exécutant le même code à partir de la valeur du D.P. Vous souhaitez calculer, calculer le top-down (récursivement) et la mémotant dans une table de hachage sans verrou partagée, mais aléatoire l'ordre dans lequel les sous-programmes sont calculés de manière à ce que les threads divergent dans lesquels ils calculent.
En termes de mise en œuvre, nous venons d'utiliser C et Pthreads sur des systèmes de type UNIX, tout ce dont vous avez besoin est de pouvoir disposer de la mémoire partagée, et du comparaison comparable (CAS) pour la synchronisation sans verrouillage entre les threads.
Parce que ce papier a été publié dans un journal d'Elsevier, vous devrez accéder à ce qui précède via une bibliothèque universitaire ou similaire avec un abonnement. Vous pourrez peut-être obtenir une copie de pré-imprimée via la page Web du professeur Stuckey cependant.
Si la table de hachage stocke des réponses est importante, le taux de conflit pour tout élément de table de hachage est probablement proche de zéro. Il n'est pas clair pour moi que la version «Lock Free» serait plus rapide qu'une serrure bien mise en œuvre bien implémentée, car chaque tentative de verrouillage réussira statistiquement lors du premier essai. (Les CAS peuvent être utilisés pour le verrouillage sans verrouillage, mais serront toujours l'accès à une ligne de cache lors de l'exécution de la CAS, de même que toute primitive de synchronisation)
Certaines œuvres ont été liées à la mise en œuvre d'algorithmes de programmation dynamiques sur GPU. Par E.g.:
Programmation dynamique avec Cuda
Programmation dynamique optimisée GPU
Une implémentation GPU de programmation dynamique pour la triangulation polygone optimale
J'ai fait un papier à ce sujet au collège et j'ai trouvé une tonne de livres dans la bibliothèque, mais presque pas de papiers.
Et où trouvons-nous votre papier?
@WindFinder: Voici votre chance ....