Algorithme branch and bound sur processeurs graphique ( gpu).

Abstract

Les problèmes d’optimisation combinatoire sont en général classés NP-Difficiles. Leur résolution nécessite un temps très élevé. La méthode B&B est l’une des méthodes exactes les plus importantes pour résoudre ces problèmes. Néanmoins, elle reste insuffisante quand elle est appliquée à des instances de grande taille. La parallélisassions du calcul est l’un des moyens les plus efficaces en termes d’amélioration de performances d’exécution, notamment à travers l’utilisation des processeurs graphiques GPU (Graphics Processing Unit). Dans ce travail, nous nous somme intéressé à la parallélisassions sur la plateforme GPU de la méthode B&B. Nous avons proposé une méthode pour la parallélisassions des algorithmes B&B sur GPU afin d’accélérer le parcours de l’arbre. Pour obtenir de meilleurs performance d’accélération nous avons opté pour une stratégie de parallélisassions basée sur la subdivision de l’arbre total en plusieurs centaines de sous arbres pour les exécutés simultanément en parallèle, où chaque thread fait le traitement d’un sous arbre. La solution est basée sur la modification complète de l’algorithme séquentiel afin de l’adapter à l’environnement limité et compliqué du GPU.