Algorithmes Branch-and-Bound parallèles revisités pour la résolution de problèmes d’optimisation combinatoire de permutation sur processeurs multi-cœurs et coprocesseurs

Solving large permutation Combinatorial Optimization Problems (COPs) using Branch-and-Bound (B&B) algorithms results in the generation of a very large pool of subproblems. Therefore, defining a dedicated data structure is crucial to store and manage efficiently that pool. In this Ph.D thesis, we propose an original data structure called Integer-Vector-Matrix (IVM) for permutation COPs based on the factorial number system. Consequently, we redefine the operators of the B&B algorithm acting on it. For performance evaluation in terms of memory footprint and CPU time usage, we conduct a complexity analysis and an extensive experimentation using the permutation Flow-Shop Scheduling Problem (FSP) as a case study. Compared to the Linked-List (LL) data structure usually used for B&B, IVM requires up to two orders of magnitude less memory than LL for large FSP instances such as scheduling 500 jobs on 20 machines. Moreover, the IVM-based B&B is up to one order of magnitude faster than its LL-based counterpart in managing the pool of subproblems. Another advantage of IVM over LL is that its memory requirement is constant and predictable. On the other hand, according to the Top500 international ranking the tendency of HPC technologies is to use multi-core processors and many-core accelerators/coprocessors as key-building blocks. Another contribution of this thesis is to revisit parallel B&B for multi-core processors, GPU accelerators and MIC coprocessors using IVM and LL. As the tree explored by a B&B applied to FSP is highly irregular in shape and size, the thread-based Work Stealing (WS) paradigm is used for parallelization on multi-core processors. Unlike most related works that use concurrent data structures, we propose a private IVM-based and LL-based WS mechanism. In addition, work units are coded in a coalesced thus optimized way using factoradic-based intervals. We also investigate five different WS strategies. Extensive experiments show that in overall IVM outperforms LL in memory footprint and CPU time usage whatever is the used WS strategy. For the many-core parallelization, the proposed approach consists in performing the branching and bounding operators on the coprocessor. Such approach raises some issues, addressed in this thesis, mainly thread mapping, thread/branch divergence and data placement optimization on GPU, and vectorization on Intel Xeon Phi. An extensive experimental study shows that IVM is particularly more efficient than LL within the many-core context. Moreover, even with vectorization (of the lower bound), which allows a significant performance improvement on Intel Xeon Phi, the GPU-based approach is faster. Finally, the many-core approaches are faster than their multi-core counterpart by one order of magnitude.La résolution de problèmes de permutation en optimisation combinatoire à l’aide d’algorithmes Branch-and-Bound (B&B) génère un très grand pool de sous-problèmes. Par conséquent, la définition d'une structure de données dédiée est cruciale pour stocker et gérer efficacement ce pool. Dans cette thèse, nous proposons une structure de données originale appelée Integer-Vector-Matrix (IVM) pour les problèmes de permutation basée sur la numération factorielle. En conséquence, nous redéfinissons les opérateurs de l'algorithme B&B agissant sur celle-ci. Pour l'évaluation de performance en termes de consommation mémoire et d’utilisation du CPU, nous avons réalisé une analyse de complexité et une expérimentation intensive en utilisant le problème d’ordonnancement de type Flow-Shop (FSP) comme étude de cas. Par rapport à la liste chaînée (LL) traditionnellement utilisée pour B&B, IVM nécessite jusqu'à deux ordres de grandeur moins de mémoire que LL pour les grandes instances de FSP telles que l’ordonnancement de 500 jobs sur 20 machines. En outre, B&B basé sur IVM est environ 10 fois plus rapide que son équivalent basé sur LL dans la gestion du pool de sous-problèmes. Un autre avantage d’IVM sur LL est que ses besoins en mémoire sont constants et prévisibles.D'autre part, d’après le classement international Top500 la tendance des technologies HPC est d'utiliser des processeurs multi-coeurs et des accélérateurs/coprocesseurs comme des briques-clés pour la construction de machines. Une autre contribution de cette thèse est de revisiter l’algorithme B&B parallèle pour les processeurs multi-coeurs, les accélérateurs GPU et les coprocesseurs MIC en utilisant IVM et LL. Comme l'arbre exploré par un B&B appliqué au FSP est hautement irrégulier en forme et en taille, le paradigme de vol de cycles (WS) basé sur les threads est utilisé pour la parallélisation multi-coeur. Contrairement à la majorité des travaux existants, qui utilisent des structures de données concurrentes, nous proposons un mécanisme de WS utilisant des structures (IVM et LL) privées ou « distribuées ». En outre, les unités de travail sont codées de manière compressée et donc optimisée en utilisant des intervalles de factorielles. Nous étudions également cinq stratégies de WS différentes. Une expérimentation intensive montre que globalement IVM est plus efficace que LL en termes d’empreinte mémoire et d'utilisation du temps CPU et ce quel que soit la stratégie WS utilisée. Pour la parallélisation multi-coeur, l'approche proposée consiste à effectuer le branchement et l’évaluation des bornes sur le coprocesseur. Cette approche soulève des problèmes, adressés dans cette thèse, notamment le mapping de threads, la divergence de branches/threads et l’optimisation du placement des données sur GPU, et la vectorisation sur Intel Xeon Phi. Une étude expérimentale montre qu’IVM est particulièrement plus efficace que LL dans le contexte many-core. En outre, même avec la vectorisation (de la borne inférieure), ce qui permet une amélioration significative des performances sur les processeurs Intel Xeon Phi, l’approche sur GPU est plus rapide. Enfin, les approches many-core sont environ 10 fois plus rapides que leurs homologues multi-core