en fr Parallel heterogeneous Branch and Bound algorithms for multi-core and multi-GPU environments Algorithmes Branch and Bound parallèles hétérogènes pour environnements multi-coeurs et multi-GPU Reportar como inadecuado




en fr Parallel heterogeneous Branch and Bound algorithms for multi-core and multi-GPU environments Algorithmes Branch and Bound parallèles hétérogènes pour environnements multi-coeurs et multi-GPU - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization LIFL - Laboratoire d-Informatique Fondamentale de Lille, Inria Lille - Nord Europe

Abstract : Branch and Bound B&B algorithms are attractive for solving to optimality combinatorial optimization problems COPs by exploring a tree-based search space. Nevertheless, they are highly time-intensive when dealing with large problem instances e.g. Taillard-s FSP benchmarks even using grid computing Mezmaz et al., IEEE IPDPS-2007. Massively parallel computing supplied through today-s heterogeneous GPU-enhanced multicore platforms TOP500 is required to tackle more e fficiently those instances. The challenge is therefore to exploit all the underlying levels of parallelism and thus to rethink accordingly the parallel models of B&B. In this thesis, we revisit the design and implementation of B&B for solving large COPs on large multi-core and multi-GPU platforms. The Flow-Shop scheduling problem FSP is considered as a case study. A preliminary experimental study on some large FSP instances has revealed that the search tree is highly irregular in shape and size and very large billions of billions of nodes, and the bounding operator is time-exorbitant about 97% of B&B. Therefore, our fi rst contribution is to propose a single CPU core GPU-accelerated approach GB&B in which only the bounding operator is performed on the GPU device. The approach deals with two issues: thread divergence and device hierarchical memory optimization. Compared to a single CPU core-based implementation, speed-ups up to 100 are obtained on Nvidia Tesla C2050. Although these good speed-ups, the performance analysis has shown that the overhead induced by the data transfer between CPU and GPU is high. Therefore, the aim of the second contribution is to extend the approach LL-GB&B in order to minimize the CPU-GPU communication latency. Such objective is achieved through a GPU-based fine-grained parallelization of the branching and pruning operators in addition to the bounding one. The major and particularly challenging issue addressed here is thread divergence due to the strongly irregular nature of the explored tree mentioned above. Compared to a single CPU-based execution, LL-GB&B allows accelerations up to 160 for large problem instances. The third contribution consists in investigating the combination of GPU with multi-core processing. Two scenarios have been explored leading to two approaches: a concurrent RLL-GB&B and a cooperative one PLL-GB&B. In the fi rst one, the exploration process is performed concurrently by the GPU and the CPU cores. In the cooperative approach, the CPU cores prepare and o ff-load to GPU pools of subproblems using data streaming while the GPU performs the exploration. When combining multi-core and GPU, we fi gure out that using RLL-GB&B is not bene ficial while PLL-GB&B enables an improvement up to 36% compared to LL-GB&B. Recently computational grids such as Grid5000 on some sites have been enhanced with GPU accelerators, therefore the fourth contribution of this thesis is to address the combination of GPU and multi-core computing with large scale distributed computing. To do that, the di fferent revisited algorithms have been put together in a heterogeneous meta-algorithm which automatically selects the one to be deployed according to the target hardware con figuration. The meta-algorithm is coupled with the B&B@Grid approach proposed in Mezmaz et al., IEEE IPDPS-2007. B&B@Grid distributes the work units search subspaces coded by intervals among the grid nodes while the meta-algorithm selects and applies locally a parallel B&B algorithm on the received intervals. The combined approach allowed us to solve to optimality and e fficiently some Taillard-s FSP instances 20 jobs on 20 machines.

Résumé : Les algorithmes Branch and Bound B&B sont attractifs pour la résolution exacte de problèmes d-optimisation combinatoire POC par exploration d-un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille exemple : benchmarks de Taillard pour FSP même en utilisant le calcul sur grilles informatiques Mezmaz et al., IEEE IPDPS-2007. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d-aujourd-hui TOP500 est requis pour traiter effi cacement de telles instances. Le dé fi est alors d-exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l-implémentation des ces algorithmes pour la résolution de POC de grande taille sur larges plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d-ordonnancement Flow-Shop FSP est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l-arbre de recherche est hautement irrégulier en forme et en taille et très large milliards de milliards de noeuds, et que l-opérateur d-évaluation des bornes est exorbitant en temps de calcul environ 97% du temps de B&B. Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU GB&B dans laquelle seul l-opérateur d-évaluation est exécuté sur GPU. L-approche traite deux dé fis: la divergence de threads et l-optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu-à 100 sont obtenues sur Nvidia Tesla C2050. L-analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l-objectif de la deuxième contribution est d-étendre l-approche LL-GB&B a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d-élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l-arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d-atteindre des accélérations allant jusqu-à 160 pour les plus grandes instances. La troisième contribution consiste à étudier l-utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente RLL-GB&B et une coopérative PLL-GB&B. Dans le premier cas, le processus d-exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l-approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l-exploration. L-utilisation combinée du multi-coeur et du GPU a montré que l-utilisation de RLL-GB&B n-est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu-à 36% par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 certains sites ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l-algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l-approche B&B@Grid proposée dans Mezmaz et al., IEEE IPDPS-2007. B&B@Grid répartit les unités de travail sous-espaces de recherche codés par des intervalles entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L-approche combinée nous a permis de résoudre à l-optimalité et e fficacement les instances 20 20 de Taillard.

en fr

Keywords : Parallel Branch-and-Bound Heterogeneous computing Graphics processing units Multi-core computing Flowshop Scheduling Problem Combinatorial Optimization Exact Methods.

Mots-clés : Branch-and-Bound Parallèlle Calcul hétérogène Processeurs Graphiques Machines multi-coeurs Problème d-ordonnancement du Flowshop Grid-5000 Optimsation Combinatoire Méthodes exactes.





Autor: Imen Chakroun -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados