Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Calculs parallèles et Distribués
Benmoussa Yahia
Université M’hamed Bougara de Boumerdès
Calculs parallèles et Distribués
Introduction
Parallélisation sur mémoire distribuée.
Parallélisation sur mémoire partagée
2
3
Introduction
Architectures parallèles Pourquoi?
– Il est très naturel de partager un gros travail parmi
plusieurs personnes.
En informatique, le parallélisme a rapidement considéré comme une option naturelle pour calculer.
répondre à une forte demande
– En puissance de calcul: simulation, modélisation
– En puissance de traitement: base de données, serveurs multimédia
Problématique: Calculs trop gros, Calculs trop long
4
Architectures parallèles Pourquoi?
Solutions :
Approche classique: diminuer le temps de calcul
– Matériels plus rapides: évolution processeurs et mémoire
En calcul parallèle: Exécution simultané de plusieurs opérations (Tâches).
– Meilleurs algorithmes
– Machines parallèles
5
Architectures parallèles Pourquoi?
Avantages :
– Amélioration des performances de calcul
– Accroissement de la taille des problèmes à résoudre
– Résolution de nouveaux problèmes
Problèmes
– La remise en question des concepts d'algorithmique classique basés sur le principe de la machine séquentielle.
– Diversité des modèles d'architectures parallèles
– Difficulté de la programmation des machines parallèles.
6
Algorithmique Parallèle Pourquoi?
Approches de résolution de problèmes dans un contexte d’exécution parallèle.
Modèles algorithmiques : contextes d’exécution parallèle simplifiés pour faciliter la conception.
Analyse théorique de la performance
Historique
7
Historique
8
Historique
9
Historique
10
Historique
11
Historique
1990 → 2000 : faillite, disparition
– fort retrait des supercalculateurs entre 1990 et 1995
– nombreuses faillites
– disparition des architectures originales
Pourquoi ?
– Manque de réalisme
– faible demande en supercalculateurs
– coût d’achat et d’exploitation trop élevés
– Une utilisation peu pratique
– systèmes d’exploitation propriétaires
– difficulté d’apprentissage
– Manque ou absence d’outils
– difficulté d’exploitation 12
Historique
2000 : l'apparition des grilles
– Améliorations apportées par la microinformatique micro-processeurs rapides
– réseaux haut débit/faible latence de plus en plus répandus
– facilité de mise à jour (changer un composant)
Evolution du Logiciel
– bibliothèques standardisées (PVM, MPI,OpenMP)
– compilateurs parallèliseurs
13
Historique
14
Définitions
Un programme séquentiel se caractérise par l’exécution de plusieurs tâches l’un après l’autre avec un ordre prédéfini.
Un programme parallèle se caractérise par l’exécution de plusieurs tâches distinctes ou non en même temps.
Un ordinateur parallèle : est une machine composée de plusieurs processeurs qui coopèrent à la solution de même problème.
Un système distribué (ou réparti) est un système de plusieurs processeurs impliqués dans la résolution d’un ou plusieurs problèmes.
15
Définitions
Qu’est-ce que le parallélisme ?
– Exécution d’un algorithme en utilisant plusieurs processeurs plutôt qu’un seul.
– Division d’un algorithme en tâches pouvant être exécutées en même temps sur des processeurs différents.
Le but : réduire le temps de résolution d’un problème un utilisant un ordinateur parallèle.
3 niveaux d’abstraction
– Architectures
– Algorithmes
– Programmation 16
Définitions
Le type de parallélisme: physique et logique
– Le parallélisme physique: Exécution de plusieurs tâches distincts ou égales.
– Le parallélisme logique (pseudo-parallélisme): Exécution de plusieurs tâches par un seul processeurs qui les traite alternativement.
17
Architectures parallèles
Plusieurs types d’architectures
– Distribuées
– Centralisées
Modèles d’architecture : simplification du fonctionnement des ordinateurs parallèles
– SIMD
– MIMD
– MIMD
18
Parallélisme : Mémoire partagé vs Mémoire Distribuée
19
Modèle de programmation parallèles
20
Programmation parallèle vs Programmation distribuée
Programmation parallèle
– Programmation dans un langage permettant d’exprimer le parallélisme dans une application réelle
Différents niveaux d’abstraction possibles
La parallélisation automatique serait la solution idéale, mais difficile à mettre en œuvre
La façon de programmer n’est pas indépendante de la machine utilisée
21
Programmation parallèle vs Programmation distribuée
La programmation distribuée :
– Chaque composant s'exécute sur un matériel interconnecté par un réseau local ou global.
– Les processus envoient entre eux des messages. Exemple :
• un serveur de fichiers dans un réseau ;
• une base de données
• es serveurs Web
Le modèle de programmation est souvent celui du client/serveur.
Souvent les composants distribués sont eux même multi programmés
22
Programmation parallèle vs Programmation distribuée
Calcul parallèle & Calcul distribué
– Parallèle : homogénéité, haut niveau de couplage des tâches.
– Distribué : hétérogénéité, indépendance logique et physique des tâches, client-serveur.
23
Calcul parallèle & Calcul concurrent
Calcul parallèle & Calcul concurrent
– Parallèle : coopération des processus dans la
résolution d’un problème.
– Concurrent : compétition entre processus,
partage des ressources.
24
Parallélisation sur mémoire distribuée en utilisant MPI
25
MPI : Message Passing Interface
Standard développé en 1993-1994 pour le développement d'applications parallèles portables. En regroupant les meilleurs aspects des bibliothèques de communications existantes.
Implémentation (gratuite) : www.lam-mpi.org
MPI : Modèle de programmation
26
Le modèle de programmation est le passage de message, dés qu’une machine (un processus) désir de communiquer avec un autre, il luit envoie un message en utilisant des fonctions en c, fortran et c++.
MPI : Objectifs
Objectifs :
– Portabilité
– Performance
– Fiabilité
– Simplicité
– Spécification indépendante du langage.
27
MPI : Modèle de programmation
Une application MPI est un ensemble de processus exécutant chacun son propre code (modèle SPMD) et communiquant via des appels à des sous-programmes de la bibliothèque MPI.
Le modèle d'exécution d'une application MPI est le SPMD (Single Program Multiple Data), soit l'exécution du même programme pour tous les processus. Les paramètres et les données sont privés à chaque processus, la synchronisation des processus MPI est de la responsabilité de l'utilisateur
28
MPI : Modèle de programmation
groupes et communicateurs.
communications point à point,
communications collectives,
types de données dérivées,
29
MPI : Communicateur
Communicateur constitué :
– D’un groupe de processus,
– d’un contexte de communication,
– une propriété des communicateurs qui permet de partager l'espace de communication, gérer les communications point-à-point et collectives.
30
Communicateur
31
Mode de communication
32
Communication Point à point
33
Communication collective
34