Parallélisation de la méthode B, B sur GPU appliquée au PFSP / Boucenna, sid ali  

Public ISBD Titre : Parallélisation de la méthode B, B sur GPU appliquée au PFSP Type de document : texte imprimé Auteurs : Boucenna, sid ali ; SAIDI,MOHAMED, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (75f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel parallélisation CUDA NVIDIA GPU PFSP Index. décimale : 004 Informatique Résumé : Résumé Les problèmes d'optimisation combinatoire sont principalement classés NP-Hard. Leur résolution prend un temps de calcul, qui est exponentiel et proportionnel à leur taille. Les algorithmes Branch & Bound (B & B) sont très efficaces pour une résolution précise de ces problèmes. Ils appartiennent à la classe de méthodes d'optimisation exactes, dont l'objectif est de trouver (la) meilleure (s) solution (s) du problème à résoudre. Cependant, ces algorithmes sont insuffisants et nécessitent une puissance de calcul considérable lorsqu'ils sont appliqués à des problèmes d'optimisation de grande taille. La parallélisation de calcule est l'un des moyens les plus efficaces en termes d'amélioration des performances d'exécution, notamment par l'intermédiaire d'unités de traitement graphique (GPUs Graphics Processing Unit). Les GPU sont des processeurs massivement parallèles qui utilisent un multi-thread basé sur le modèle SIMD. L'utilisation des GPU peut accélérer les parties intensives de l'algorithme. Cependant, l'architecture particulière des GPU nécessite l'adaptation d'algorithmes existants pour offrir des performances optimales. Ce projet implique la conception et la mise en Å“uvre d'une architecture parallèle à l'aide d'une CPU et d'un GPU. L'application sera mise en Å“uvre en utilisant C / CUDA et des expériences seront effectuées sur les processeurs graphiques NVIDIA. Note de contenu : Table des matières LISTE DES FIGURES................................................................................................................ VIII LISTE DES TABLEAUX............................................................................................................... IX INTRODUCTION GENERALE ...................................................................................................... 1 CHAPITRE 1 : LES PROBLEMES D’ORDONNANCEMENT .............................................................. 4 1. INTRODUCTION ...........................................................................................................4 2. GENERALITES ET DEFINITIONS ...............................................................................................4 LES TACHES....................................................................................................................................4 LES RESSOURCES .............................................................................................................................5 LES CONTRAINTES ...........................................................................................................................6 3. EVALUATION D’UN ORDONNANCEMENT .........................................................................6 DIAGRAMME DE GANTT .............................................................7 4. CLASSIFICATION DES PROBLEMES D'ORDONNANCEMENT.................................................................................8 PROBLEME A UNE MACHINE ..............................................................................................................8 LES PROBLEMES A MACHINES PARALLELES ............................................................................................8 LES PROBLEMES D’ATELIERS...............................................................................................................8 5. PROBLEME DE FLOW-SHOP DE PERMUTATION (PFSP).................................................................................10 SPECIFICATION DU PROBLEME..........................................................................................................10 EXEMPLE DU PFSP........................................................................................................................11 6. ETUDE DE LA COMPLEXITE ................................................................................................12 7. CONCLUSION .........................................................................................................14 CHAPITRE 2 : APPROCHES DE RESOLUTIONS ............................................................................15 1. INTRODUCTION ............................................................................................................15 2. METHODES DE RESOLUTION.................................................................................................15 METHODES EXACTES......................................................................................................................15 METHODES APPROCHEES................................................................................................................16 3. LA METHODE BRANCHE & BOUND ...........................................................................................................17 PRINCIPE FONDAMENTALE DE LA METHODE ........................................................................................19 STRATEGIES DE PARCOURS ..............................................................................................................21 ENONCE DE L’ALGORITHME B&B .....................................................................................................24 4. ILLUSTRATION DE LA METHODE B&B SUR LE PROBLEME FSP .........................................................................24 CALCUL DE LA BORNE INFERIEURE .....................................................................................................25 CALCUL DE LA BORNE SUPERIEURE ....................................................................................................26 5. CONCLUSION ............................................................................................27 CHAPITRE 3 : NOTIONS DU PARALLELISME ................................................................27 1. INTRODUCTION ....................................................................................................27 2. ARCHITECTURE PARALLELE....................................................................................................27 3. ALGORITHME PARALLELE ................................................................................................28 4. SOURCES DE PARALLELISME ....................................................................................................................28 PARALLELISME DE CONTROLE...........................................................................................................28 PARALLELISME DE DONNEES ............................................................................................................29 PARALLELISME DE FLUX ..................................................................................................................29 5. LES MACHINES PARALLELES ....................................................................................................................30 LA CLASSIFICATION DE MICHAEL J. FLYNN (1966) .............................................................................30 CLASSIFICATION SELON L’ORGANISATION DE LA MEMOIRE .....................................................................31 6. LES MESURES DE PERFORMANCES.............................................................................................................33 LE TEMPS D’EXECUTION..................................................................................................................33 L’ACCELERATION (SPEED UP) ..........................................................................................................34 7. ARCHITECTURE PARALLELE ACTUELLE ........................................................................................................35 PROCESSEUR GRAPHIQUE ...............................................................................................................35 CLOUD........................................................................................................................................35 CLUSTER......................................................................................................................................36 GRILLE INFORMATIQUE ..................................................................................................................36 8. PARALLELISATION D’UN BRANCH AND BOUND............................................................................................36 CLASSIFICATION DE TRIENEKENS ET AL...............................................................................................36 CLASSIFICATION DE GENDRON ET AL .................................................................................................37 CLASSIFICATION DE MELAB .............................................................................................................38 9. CONCLUSION .........................................................................................................40 CHAPITRE 4 : PROGRAMMATION SUR GPU AVEC CUDA-C ........................................................41 1. INTRODUCTION ....................................................................................................41 2. ARCHITECTURE DES GPU NVIDIA...........................................................................................................42 ARCHITECTURE TESLA....................................................................................................................42 ARCHITECTURE FERMI....................................................................................................................43 3. LE LANGAGE CUDA ..............................................................................................................................45 LES THREADS ................................................................................................................................47 LES MEMOIRES .............................................................................................................................49 HOST ET DEVICE ...........................................................................................................................50 4. REGLES D’OPTIMISATIONS ......................................................................................................................53 INSTRUCTIONS DE BASE ..................................................................................................................53 INSTRUCTIONS DE CONTROLE...........................................................................................................53 INSTRUCTIONS DE GESTION MEMOIRE ...............................................................................................54 NOMBRE DE THREADS PAR BLOCK.....................................................................................................56 TRANSFERTS DE DONNEES CPU ↔ GPU ...........................................................................................57 5. CONCLUSION ...............................................................................................57 CHAPITRE 5 : CONCEPTION DE LA SOLUTION ...........................................................................58 1. INTRODUCTION .......................................................................................................58 2. STRATEGIE DE PARALLELISATION ........................................................................................58 3. CALCUL DE LA BORNE INFERIEURE.........................................................................................59 CALCUL SUR CPU..........................................................................................................................60 CALCUL SUR GPU .........................................................................................................................60 4. UNE NOUVELLE BORNE INFERIEURE ..........................................................................................................61 5. ENONCE DE L’ALGORITHME :...................................................................................................62 6. CONCLUSION ........................................................................................................62 CHAPITRE 6 : TEST ET RESULTATS ............................................................................................63 1. INTRODUCTION ........................................................................................................63 2. TESTS...........................................................................................................63 . TYPE DE DONNEES UTILISEES............................................................................................................63 . OUTILS DE MISE EN Å’UVRE .............................................................................................................64 3. RESULTATS ......................................................................................................65 PARALLELISATION..............................................................................................69 4. RESULTATS GENERAUX......................................................................................70 5. CONCLUSION ..................................................................................70 CONCLUSION GENERALE .........................................................................................................72 BIBLIOGRAPHIE ......................................................................................................................73 Côte titre : MAI/0171 En ligne : https://drive.google.com/file/d/1qrI3pYZ4_edkoJ9j-pPuyPuttehoRwDn/view?usp=shari [...] Format de la ressource électronique : pdf Parallélisation de la méthode B, B sur GPU appliquée au PFSP [texte imprimé] / Boucenna, sid ali ; SAIDI,MOHAMED, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (75f.) ; 29 cm. Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie Logiciel parallélisation CUDA NVIDIA GPU PFSP Index. décimale : 004 Informatique Résumé : Résumé Les problèmes d'optimisation combinatoire sont principalement classés NP-Hard. Leur résolution prend un temps de calcul, qui est exponentiel et proportionnel à leur taille. Les algorithmes Branch & Bound (B & B) sont très efficaces pour une résolution précise de ces problèmes. Ils appartiennent à la classe de méthodes d'optimisation exactes, dont l'objectif est de trouver (la) meilleure (s) solution (s) du problème à résoudre. Cependant, ces algorithmes sont insuffisants et nécessitent une puissance de calcul considérable lorsqu'ils sont appliqués à des problèmes d'optimisation de grande taille. La parallélisation de calcule est l'un des moyens les plus efficaces en termes d'amélioration des performances d'exécution, notamment par l'intermédiaire d'unités de traitement graphique (GPUs Graphics Processing Unit). Les GPU sont des processeurs massivement parallèles qui utilisent un multi-thread basé sur le modèle SIMD. L'utilisation des GPU peut accélérer les parties intensives de l'algorithme. Cependant, l'architecture particulière des GPU nécessite l'adaptation d'algorithmes existants pour offrir des performances optimales. Ce projet implique la conception et la mise en Å“uvre d'une architecture parallèle à l'aide d'une CPU et d'un GPU. L'application sera mise en Å“uvre en utilisant C / CUDA et des expériences seront effectuées sur les processeurs graphiques NVIDIA. Note de contenu : Table des matières LISTE DES FIGURES................................................................................................................ VIII LISTE DES TABLEAUX............................................................................................................... IX INTRODUCTION GENERALE ...................................................................................................... 1 CHAPITRE 1 : LES PROBLEMES D’ORDONNANCEMENT .............................................................. 4 1. INTRODUCTION ...........................................................................................................4 2. GENERALITES ET DEFINITIONS ...............................................................................................4 LES TACHES....................................................................................................................................4 LES RESSOURCES .............................................................................................................................5 LES CONTRAINTES ...........................................................................................................................6 3. EVALUATION D’UN ORDONNANCEMENT .........................................................................6 DIAGRAMME DE GANTT .............................................................7 4. CLASSIFICATION DES PROBLEMES D'ORDONNANCEMENT.................................................................................8 PROBLEME A UNE MACHINE ..............................................................................................................8 LES PROBLEMES A MACHINES PARALLELES ............................................................................................8 LES PROBLEMES D’ATELIERS...............................................................................................................8 5. PROBLEME DE FLOW-SHOP DE PERMUTATION (PFSP).................................................................................10 SPECIFICATION DU PROBLEME..........................................................................................................10 EXEMPLE DU PFSP........................................................................................................................11 6. ETUDE DE LA COMPLEXITE ................................................................................................12 7. CONCLUSION .........................................................................................................14 CHAPITRE 2 : APPROCHES DE RESOLUTIONS ............................................................................15 1. INTRODUCTION ............................................................................................................15 2. METHODES DE RESOLUTION.................................................................................................15 METHODES EXACTES......................................................................................................................15 METHODES APPROCHEES................................................................................................................16 3. LA METHODE BRANCHE & BOUND ...........................................................................................................17 PRINCIPE FONDAMENTALE DE LA METHODE ........................................................................................19 STRATEGIES DE PARCOURS ..............................................................................................................21 ENONCE DE L’ALGORITHME B&B .....................................................................................................24 4. ILLUSTRATION DE LA METHODE B&B SUR LE PROBLEME FSP .........................................................................24 CALCUL DE LA BORNE INFERIEURE .....................................................................................................25 CALCUL DE LA BORNE SUPERIEURE ....................................................................................................26 5. CONCLUSION ............................................................................................27 CHAPITRE 3 : NOTIONS DU PARALLELISME ................................................................27 1. INTRODUCTION ....................................................................................................27 2. ARCHITECTURE PARALLELE....................................................................................................27 3. ALGORITHME PARALLELE ................................................................................................28 4. SOURCES DE PARALLELISME ....................................................................................................................28 PARALLELISME DE CONTROLE...........................................................................................................28 PARALLELISME DE DONNEES ............................................................................................................29 PARALLELISME DE FLUX ..................................................................................................................29 5. LES MACHINES PARALLELES ....................................................................................................................30 LA CLASSIFICATION DE MICHAEL J. FLYNN (1966) .............................................................................30 CLASSIFICATION SELON L’ORGANISATION DE LA MEMOIRE .....................................................................31 6. LES MESURES DE PERFORMANCES.............................................................................................................33 LE TEMPS D’EXECUTION..................................................................................................................33 L’ACCELERATION (SPEED UP) ..........................................................................................................34 7. ARCHITECTURE PARALLELE ACTUELLE ........................................................................................................35 PROCESSEUR GRAPHIQUE ...............................................................................................................35 CLOUD........................................................................................................................................35 CLUSTER......................................................................................................................................36 GRILLE INFORMATIQUE ..................................................................................................................36 8. PARALLELISATION D’UN BRANCH AND BOUND............................................................................................36 CLASSIFICATION DE TRIENEKENS ET AL...............................................................................................36 CLASSIFICATION DE GENDRON ET AL .................................................................................................37 CLASSIFICATION DE MELAB .............................................................................................................38 9. CONCLUSION .........................................................................................................40 CHAPITRE 4 : PROGRAMMATION SUR GPU AVEC CUDA-C ........................................................41 1. INTRODUCTION ....................................................................................................41 2. ARCHITECTURE DES GPU NVIDIA...........................................................................................................42 ARCHITECTURE TESLA....................................................................................................................42 ARCHITECTURE FERMI....................................................................................................................43 3. LE LANGAGE CUDA ..............................................................................................................................45 LES THREADS ................................................................................................................................47 LES MEMOIRES .............................................................................................................................49 HOST ET DEVICE ...........................................................................................................................50 4. REGLES D’OPTIMISATIONS ......................................................................................................................53 INSTRUCTIONS DE BASE ..................................................................................................................53 INSTRUCTIONS DE CONTROLE...........................................................................................................53 INSTRUCTIONS DE GESTION MEMOIRE ...............................................................................................54 NOMBRE DE THREADS PAR BLOCK.....................................................................................................56 TRANSFERTS DE DONNEES CPU ↔ GPU ...........................................................................................57 5. CONCLUSION ...............................................................................................57 CHAPITRE 5 : CONCEPTION DE LA SOLUTION ...........................................................................58 1. INTRODUCTION .......................................................................................................58 2. STRATEGIE DE PARALLELISATION ........................................................................................58 3. CALCUL DE LA BORNE INFERIEURE.........................................................................................59 CALCUL SUR CPU..........................................................................................................................60 CALCUL SUR GPU .........................................................................................................................60 4. UNE NOUVELLE BORNE INFERIEURE ..........................................................................................................61 5. ENONCE DE L’ALGORITHME :...................................................................................................62 6. CONCLUSION ........................................................................................................62 CHAPITRE 6 : TEST ET RESULTATS ............................................................................................63 1. INTRODUCTION ........................................................................................................63 2. TESTS...........................................................................................................63 . TYPE DE DONNEES UTILISEES............................................................................................................63 . OUTILS DE MISE EN Å’UVRE .............................................................................................................64 3. RESULTATS ......................................................................................................65 PARALLELISATION..............................................................................................69 4. RESULTATS GENERAUX......................................................................................70 5. CONCLUSION ..................................................................................70 CONCLUSION GENERALE .........................................................................................................72 BIBLIOGRAPHIE ......................................................................................................................73 Côte titre : MAI/0171 En ligne : https://drive.google.com/file/d/1qrI3pYZ4_edkoJ9j-pPuyPuttehoRwDn/view?usp=shari [...] Format de la ressource électronique : pdf

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAI/0171	MAI/0171	Mémoire	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)