Sommaire: Parallélisation d’algorithmes d’optimisation combinatoire
Résumé
Table des Matières
Liste des Figures
Liste des Tableaux
Introduction Générale
Chapitre1 Optimisation combinatoire
1.1 Introduction
1.2 Notion d’optimisation combinatoire
1.3 Formulation de problèmes d’optimisation combinatoire
1.4 Stratégie d’extraction de solution
1.4.1 Solution Exacte
1.4.2 Les Heuristiques
1.4.3 Algorithmes hybrides
1.5 Programmation Linéaire
1.5.1 Programmation linéaire en nombres entiers PLNE
1.5.2 La méthode du simplexe
1.6 Séparation et évaluation (Branch and Bound)
1.7 Source de parallélisme dans l’algorithme Branch & Bound
1.7.1 Stratégies pour la parallélisation
1.7.2 Classifications des algorithmes parallèles B&B
1.7.3 Anomalies dues à l’accélération
1.7.4 Logiciels Banch and Bound
1.8 Les avantages et inconvénients pour B&B Parallèle et séquentiel
1.8.1 Les points pour B&B séquentiel
1.8.2 Points pour B&B parallèle
1.9 Conclusion
Chapitre 2 Notions du parallélisme
2.1 Introduction
2.2 Algorithme parallèle
2.3 Les Machines Parallèles
2.3.1 Les machines parallèles à mémoire partagée
2.3.2 Les machines parallèles à mémoire distribuée
2.4 Modèles de machines parallèles
2.4.1 Le Modèle PRAM
2.4.2 Les modèles de bas niveau
2.4.3 Modèles à mémoires hiérarchique
2.4.4 Modèles réseau
2.5 Conception d’algorithme parallèle
2.5.1 Partitionnement
2.5.2 Communication
2.5.3 Agglomération
2.5.4 Mapping
2.6 Sources de parallélisme
2.6.1 Parallélisme de contrôle
2.6.2 Parallélisme de données
2.6.3 Parallélisme de Flux
2.7 Mesure de performance
2.7.1 Accélération
2.7.2 Accélération relative
2.7.3 Efficacité
2.7.4 Iso-efficacité
2.8 Complexité d’un algorithme parallèle
2.8.1 Complexité en temps
2.8.2 Complexité en communication
2.8.3 Complexité en mémoire
2.9 Conclusion
Chapitre 3 Présentation d’outils de parallélisation OpenMP & MPI
3.1 Introduction
3.2 Open MP (Open Multi Processing)
3.2.1 Historique
3.2.2 C’est quoi OpenMP ?
3.2.3 Concepts Généraux
3.2.4 Structure OpenMP
3.2.5 Principe d’OpenMP
3.2.6 Les Variables de contrôle Interne (ICVs)
3.2.7 Syntaxe générale d’une directive
3.2.8 Les Variables d’environnements
3.2.9 Construction des régions parallèles
3.3 MPI (Message Passing Interface)
3.3.1 Concepts de l’échange de messages
3.3.2 Les objectifs de MPI
3.3.3 Environnement
3.3.4 Communication Point à point
3.3.5 Communication collective
3.3.6 Optimisations
3.3.7 Types de données dérivées
3.3.8 Topologie des processus
3.3.9 Groupes et Communicateurs
3.3.10 Installation et exécution de programme MPI (exemple MPICH)
3.3.11 Les routines MPI
3.4 Conclusion
Chapitre 4 Nouvelle approche de parallélisation et implémentation
4.1 Introduction
4.2 Approche de parallélisation proposée
4.2.1 La stratégie de parcours de l’arbre
4.2.2 Gérer le grain de parallélisme
4.2.3 L’équilibre de charge
4.2.4 Gestion optimale de la mémoire
4.2.5 Assurer la communication entre les processeurs utilisés
4.2.6 Parallélisme de contrôle ou de données
4.3 La loi d’Amdahl
4.4 Complexité de l’algorithme B&B parallèle
4.4.1 Complexité en temps de calcul
4.4.2 Complexité en mémoire
4.4.3 Complexité en communication
4.5 Implémentation Parallèle de l’algorithme Branch and Bound
4.5.1 Etude expérimentale
4.5.2 Génération de l’ensemble de test
4.5.3 Résultats de l’expérimentation
4.5.4 Discutions globale
4.6 Conclusion
Conclusion et Perspectives
Bibliographie
Extrait du mémoire parallélisation d’algorithmes d’optimisation combinatoire
Chapitre1: Optimisation combinatoire
1.1 Introduction
L’optimisation combinatoire est l’une des plus jeunes branches et les plus actives des mathématiques discrètes de ces dernières années. Dans ce chapitre nous allons donner quelques définitions des notions de l’optimisation combinatoire et de stratégies d’extraction de problèmes et parmi elle la méthode Branch And Bound sur laquelle nous allons nous pencher avec plus de détails.
Parallélisation d’Algorithmes
1.2 Notion d’optimisation combinatoire
» Combinatoire » désigne la discipline des mathématiques concernée par les structures » discrètes » ou » finies « . Citons quelques branches de cette discipline : la théorie des graphes, la combinatoire énumérative, les problèmes de dénombrement, la combinatoire polyèdrale, l’optimisation combinatoire, etc. Les frontières entre ces branches ne sont pas hermétiques, les différentes branches expriment plutôt des orientations méthodologiques différentes.
L' » optimisation « , ou » programmation mathématique » (Mathematical Programming) sont des termes utilisés pour recouvrir toutes les méthodes qui servent à déterminer l’optimum d’une fonction avec (ou sans) contraintes. Cette fonction modélise le choix optimal. On optimise déjà à l’école, quand on apprend comment déterminer l’optimum (minimum ou maximum) d’une fonction différentiable. Les ingénieurs, les économistes, la nature, font souvent des choix optimaux (ou quasi-optimaux), d’où l’importance de l’optimisation dans les sciences, qu’elles soient techniques, mathématiques, physiques, informatiques, économiques, naturelles, etc.
Parallélisation d’Algorithmes
L’ » Optimisation combinatoire » consiste à trouver le meilleur entre un nombre fini de choix. Autrement dit, minimiser une fonction, avec contraintes, sur un ensemble fini. Quand le nombre de choix est exponentiel (par rapport à la taille du problème), mais que les choix et les contraintes sont bien structurés, des méthodes mathématiques doivent et peuvent intervenir, comme dans le cas » continu « , pour permettre de trouver la solution en temps polynomial (par rapport à la taille du problème). Alors, l’optimisation combinatoire consiste à développer des algorithmes polynomiaux et des théorèmes sur des structures discrètes qui permettent de résoudre ces problèmes [11].
………
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Mémoire Online: Parallélisation d’algorithmes d’optimisation combinatoire (2.0 MO) (Cours PDF)
