| Titre : | Exploitation des potentialités des cartes graphiques à l'optimisation des algorithimes évolutionnaires |
| Auteurs : | NOUR EL-HOUDA BENALIA, Auteur ; Noureddine Djedi, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2015 |
| ISBN/ISSN/EAN : | TINF/86 |
| Format : | 1 vol. (133 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Cette thèse constitue l’une des premières études sur l’impact de la programmation orientée GPU sur quelques aspects de la vie artificielle, telle que la robotique évolutionnaire.A cette occasion, nous fournissons une série L’expérimentations nouvelles dans le domaine de la conception de robots humanoïdes. La robotique évolutionnaire est un domaine qui s’intéresse à la création de programmes réalisant des contrôles adaptatifs pour des robots artificiels en exploitant les principes évolutionnistes. Atteindre l’objectif ultime de robots évolutionnaires viables nécessitera une puissance de calcul considérable, cette puissance étant jusqu’alors fournie principalement par des processeurs (CPUs) standards.La demande sans cesse croissante du marché hautes performances pour les graphiques 3D temps réel a permis de faire subir aux architectures massivement parallèles des processeurs graphiques (GPUs) une évolution spectaculaire en matière de puissance de calcul graphique. Cette augmentation de la puissance et la flexibilité qu’elle dénote, conjuguées au faible coût de ces GPUs ont eu comme conséquence inattendue de voir leur utilisation s’étendre à des domaines étrangers à celui pour lequel ils ont été conçus, le graphisme. Par son extension, cet usage a reçu un nom, c’est le GPGPU (General Purpose computation on GPU). Motivés par les besoins de calcul considérables liés aux domaines de recherche s’inscrivant dans les thématiques de la vie artificielle, nous nous proposons dans cette thèse d’exploiter les concepts GPGPU à des applications spécifiques du domaine de la vie artificielle.Différents modèles évolutionnaires intéressants ont été élaborés pour traiter des questions scientifiques importantes pour l’acquisition et la génération des actions de robots.Bien qu’il ne nous est pas aisément offert de mieux comprendre les aspects scientifiques les plus importants, la compréhension de leur complexité et la multiplication de leur utilisation ont fait émerger une évolution favorable au cours de ces dernières années.En raison de leur parallélisme inhérent, les algorithmes évolutionnaires semblent bien adaptés pour être exécutés sur des architectures massivement parallèles telles que les GPUs.Dans cette thèse, nous mettons cette assertion à l’épreuve en effectuant des expériences complètes pour une approche en rapport avec la robotique évolutionnaire. Cette thèse présente plusieurs cas où l’application du concept du GPU Computing sur des algorithmes de la vie artificielle et spécialement ceux de la robotique évolutionnaire a abouti à l’élaboration de modèles à grande échelle avec une complexité inédite permettant la réalisation de nouvelles expérimentations. |
| Sommaire : |
1 Introduction Générale 1 1.1 Cadre de la Thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Émergence des architectures multicoeurs . . . . . . . . . . . . . . . 2 1.2.2 Émergence du calcul général GPGPU sur les architectures GPUs . . 2 1.2.3 Programmation GPGPU pour les méthodes bio-inspirées . . . . . . 3 1.3 Problématique, Objectifs, et Contributions . . . . . . . . . . . . . . . . . . 4 1.4 Structure du manuscrit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Intelligence artificielle bio-inspirée : Algorithmes évolutionnaires, Notions,Complexité et Analyse 7 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Évolution naturelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Qu’est-ce qu’un algorithme évolutionnaire (AE) ? . . . . . . . . . . 10 2.2.2 Domaines d’application des AEs . . . . . . . . . . . . . . . . . . . . 18 2.3 Analyse de complexité des algorithmes évolutionnaires . . . . . . . . . . . 18 2.3.1 Définition de l’analyse algorithmique . . . . . . . . . . . . . . . . . 18 2.3.2 Analyse des algorithmes évolutionnaires . . . . . . . . . . . . . . . 19 2.3.3 Travaux concernant l’analyse des algorithmes évolutionnaires . . . . 20 2.3.4 Éléments d’analyse des algorithmes évolutionnaires . . . . . . . . . 22 2.3.5 Méthodes d’analyse des algorithmes évolutionnaires . . . . . . . . . 23 2.4 Calcul de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4.1 De l’individu à la population . . . . . . . . . . . . . . . . . . . . . . 24 2.4.2 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Mesures de performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3 Évolution des architectures parallèles classiques et modernes dans la parallélisation des algorithmes évolutionnaires 28 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Parallélisme : phases et définitions . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Architectures parallèles modernes et avancés . . . . . . . . . . . . . . . . . 31 3.3.1 Classification des architectures classiques . . . . . . . . . . . . . . . 31 3.3.2 Environnements et langages de programmation . . . . . . . . . . . 33 3.4 Émergence des GPUs comme un outil de calcul général . . . . . . . . . . . 34 3.4.1 Pourquoi les processeurs multi-coeurs et les GPUs ? . . . . . . . . . 34 3.4.2 Panorama matériel et logiciel des GPUs . . . . . . . . . . . . . . . 35 3.4.3 Développement du software GPU : Historiques vs Actualités . . . . 36 3.4.4 Futur du calcul GPU . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.5 Architecture matérielle et logiciel du GPU . . . . . . . . . . . . . . 38 3.5 Applications GPGPU pour la vie artificielle. . . . . . . . . . . . . . . . . . 42 3.5.1 Bioinformatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2 Réseaux de neurones artificiels et les algorithmes évolutionnaires . . 42 3.5.3 L-Systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.4 Traitement de la vision artificielle . . . . . . . . . . . . . . . . . . . 43 3.6 Modèles parallèles des algorithmes évolutionnaires . . . . . . . . . . . . . . 45 3.6.1 Sources de parallélisation des algorithmes évolutionnaires . . . . . . 45 3.6.2 Classification des Modèles Parallèles des AEs . . . . . . . . . . . . . 47 3.7 Outils de parallélisation des AEs . . . . . . . . . . . . . . . . . . . . . . . 51 3.7.1 Cluster et MPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.7.2 Grille de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.7.3 Les architectures multicoeurs et les systèmes HPC . . . . . . . . . 52 3.7.4 Le Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.8 Travaux de recherche sur les AEs à base GPU . . . . . . . . . . . . . . . . 55 3.8.1 GPU-AEs basés chromosome . . . . . . . . . . . . . . . . . . . . . . 55 3.8.2 GPU-AEs basés Gènes . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.9 Considérations pour une implémentation parallèle . . . . . . . . . . . . . . 56 3.10 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4 PEvoRNN : GPU Computing pour la robotique évolutionnaire (Framework GPGPU) 60 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2 Analyse du parallélisme au sein du problème . . . . . . . . . . . . . . . . . 64 4.2.1 Niveau stratégie évolutionnaire . . . . . . . . . . . . . . . . . . . . 64 4.2.2 Niveau réseau de neurones . . . . . . . . . . . . . . . . . . . . . . . 66 4.2.3 Niveau simulateur physique . . . . . . . . . . . . . . . . . . . . . . 66 4.3 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4 Robotique évolutionnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.5 Contrôleurs évolutifs sur machines parallèles . . . . . . . . . . . . . . . . . 70 4.6 Facteurs limitatifs des modèles actuels . . . . . . . . . . . . . . . . . . . . 71 4.7 RNAs exploitant les GPU pour les contrôleurs des robots . . . . . . . . . . 72 4.8 Simulateurs physiques à base GPU . . . . . . . . . . . . . . . . . . . . . . 73 4.9 Hybridation SE-RNN à base GPU du contrôleur du robot . . . . . . . . . . 74 4.9.1 Aperçu général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.9.2 Modèle du robot humanoïde et de stockage de données . . . . . . . 76 4.9.3 Architecture hybride SE-RNN du Contrôleur du Robot . . . . . . . 81 4.9.4 Analyse de complexité du problème . . . . . . . . . . . . . . . . . . 86 4.10 Expérimentation, Résultats et Discussion . . . . . . . . . . . . . . . . . . . 86 4.10.1 Configuration de l’environnement d’exécution . . . . . . . . . . . . 86 4.10.2 Convergence de la proposition évolutive . . . . . . . . . . . . . . . . 87 4.10.3 Analyse de performance et de qualité des solutions, sous les limites de temps . . . . . . 88 4.10.4 Discussion de performance en termes d’efficience et d’efficacité . . . 88 4.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5 Coopération CPU-GPU, distribution des tâches et gestion de la mémoire dans pEvoRNN 92 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.2 Coopération CPU-GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.2.1 Répartition des tâches pour les algorithmes évolutionnaires sur GPU 93 5.3 Équilibrage de la Charge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.3.1 Équilibrage de tâche Inter-GPUs . . . . . . . . . . . . . . . . . . . 96 5.3.2 Équilibrage de tâche Intra-GPUs . . . . . . . . . . . . . . . . . . . 96 5.4 Mapping efficace de la population . . . . . . . . . . . . . . . . . . . . . . . 96 5.4.1 Réglage automatique de la configuration pour l’AE utilisé . . . . . 97 5.4.2 Contribution à la détermination de l’aménagement optimal . . . . . 98 5.5 Gestion de la Mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.5.1 Concepts communs de gestion de la mémoire . . . . . . . . . . . . . 100 5.5.2 Transformation vers la coalescence . . . . . . . . . . . . . . . . . . 102 5.5.3 Notre proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6 Étude Comparative 105 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.2 Notre approche évolutive à l’égard d’autres approches . . . . . . . . . . . . 105 6.3 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7 Conclusion Générale 110 7.1 Récapitulatif des Contributions . . . . . . . . . . . . . . . . . . . . . . . . 110 7.2 Discussions et Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.2.1 Nouvelle vision concernant la démarche pour les nouveaux GPUs . 112 Annexe : Mesures de performance d’un algorithme parallèle du point de vue GPU 113 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 2 Outils d’analyse de performance des applications CUDA . . . . . . . . . . 114 2.1 CUDA Visual Profiler . . . . . . . . . . . . . . . . . . . . . . . . . 114 2.2 GPUOcelot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 2.3 Decuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 2.4 Cuobjdump . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3 Comparaison des applications basées CPU vs GPU . . . . . . . . . . . . . 115 3.1 Comparaison des applications CPU vs GPU . . . . . . . . . . . . . 115 3.2 Informations et métriques nécessaires à la mesure de performances sous GPU? . . . . . . . . 116 3.3 Évaluation de la performance des approches à base de GPU utilisant les modèles analytiques . . . . . . . . . . . . . . . . . . . . . . . . . 116 4 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Bibliographie 120 |
| En ligne : | http://thesis.univ-biskra.dz/2301/1/Info_LMD_d1_2016.pdf |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/86 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
