Abstract FR:

Le but de cette these est d'etudier la parallelisation des algorithmes des familles a* et minimax, issues de l'intelligence artificielle, pour les problemes d'optimisation combinatoire. Dans les deux premiers chapitres, nous montrons que ces methodes utilisent le meme paradigme d'exploration d'espaces de recherche que les algorithmes branch and bound et degageons les parties susceptibles a etre parallelisees. Le troisieme chapitre fait le point sur l'evolution des machines paralleles, les differents types de parallelisme possibles dans une exploration d'espace de recherche et les travaux anterieures des familles a* et minimax. Nous proposons, au chapitre quatre, une nouvelle structure de donnees appelee concurrent treap, a double critere (priorite et cle) et acces concurrent pour une implantation parallele efficace de a* (cas). Cette structure permet d'eviter le probleme d'interblocage des structures combinees classiques. Le chapitre cinq presente un modele theorique pour la famille minimax, permettant le calcul des bornes d'acceleration et d'efficacite pour un arbre uniforme donne. Deux parallelisations de l'algorithme alpha-beta sont proposees dans le dernier chapitre. L'une (saba), pour machines simd a parallelisme massif, permet la validation du modele theorique. L'autre (cabp), pour machines mimd a memoire partagee, est fondee sur l'exploration d'un arbre critique et l'introduction d'un degre d'elagages concurrent k. Ce parametre autorise un controle dynamique du surcout d'exploration en cours de recherche