Existe-t-il de bons articles traitant de la manière de prendre un programme dynamique et de le paralléliser ?
Réponses
Trop de publicités?
Alex Stivala
Points
31
Nous avons récemment publié un article montrant comment paralléliser n'importe quelle p.d. sur un ordinateur multicœur à mémoire partagée au moyen d'une table de hachage partagée sans verrou :
Stivala, A. et Stuckey, P. J. et Garcia de la Banda, M. et Hermenegildo, M. et Wirth, A. 2010 "Lock-free parallel dynamic programming" J. Parallel Distrib. Comput. 70:839-848 doi:10.1016/j.jpdc.2010.01.004
http://dx.doi.org/10.1016/j.jpdc.2010.01.004
Essentiellement, vous lancez plusieurs threads, qui exécutent tous le même code à partir de la valeur du p.d. que vous souhaitez calculer, en le calculant de haut en bas (de manière récursive) et en le mémorisant dans une table de hachage partagée sans verrou, mais en randomisant l'ordre dans lequel les sous-problèmes sont calculés afin que les threads divergent dans les sous-problèmes qu'ils calculent.
En termes de mise en œuvre, nous avons simplement utilisé C et pthreads sur les systèmes de type UNIX, tout ce dont vous avez besoin est d'avoir une mémoire partagée, et CompareAndSwap (CAS) pour une synchronisation sans verrou entre les threads.
Cet article ayant été publié dans une revue Elsevier, vous devrez y accéder par l'intermédiaire d'une bibliothèque universitaire ou d'une institution similaire disposant d'un abonnement à cette revue. Vous pourrez peut-être obtenir une copie préimprimée via la page web du professeur Stuckey.
En règle générale, la programmation dynamique consiste à diviser récursivement un problème en sous-problèmes et à assembler des solutions optimales à partir de sous-solutions optimales. L'efficacité de cette méthode réside dans le fait que toutes les sous-solutions optimales sont intégrées dans un cache, de sorte qu'il n'est pas nécessaire de les recalculer.
Si le problème peut être divisé en plusieurs parties, vous pouvez utiliser le solveur pour chaque sous-solution. Si chaque (sous) problème a en moyenne 1+epsilon (pour epsilon supérieur à zéro) sous-solutions possibles, vous obtiendrez beaucoup de parallélisme de cette manière. Vous aurez probablement besoin de verrous sur les entrées du cache pour éviter que les solutions individuelles ne soient construites plus d'une fois.
Vous avez besoin d'un langage dans lequel vous pouvez forker des sous-tâches à un coût inférieur à celui du travail nécessaire pour les résoudre, et qui est heureux d'avoir beaucoup de tâches forkées en même temps. Les offres parallèles typiques de la plupart des langages ne permettent pas d'atteindre cet objectif ; il n'est pas possible d'avoir un grand nombre de tâches forkées dans les systèmes qui utilisent le "modèle de la grande pile" (cf. Comment fonctionne une langue sans pile ? ).
Nous avons implémenté notre langage de programmation parallèle, PARLANSE, pour obtenir un langage ayant les bonnes propriétés.
Hari
Points
927
Certains travaux ont été consacrés à la mise en œuvre d'algorithmes de programmation dynamique sur les GPU. Par exemple :
Programmation dynamique avec CUDA
Programmation dynamique optimisée par le GPU
Une implémentation GPU de la programmation dynamique pour la triangulation optimale des polygones
