Comprendre les méthodes fondamentales d'algorithmique, savoir utiliser ces méthodes pour proposer des solutions informatiques à des problèmes en maîtrisant bien leur complexité de calcul.Horaires : Cours : 42h. Travaux dirigés : 6h. Travaux Pratiques : 12h.
Connaitre quelques applications classiques de ces méthodes en recherche opérationnelle, traitement du signal, traitement d'informations textuelles.
Approfondir et maîtriser les algorithmes fondamentaux liés à l'analyse et au traitement d'images. Savoir mettre en oeuvre une chaîne de traitement d'image afin de résoudre un problème spécifique
Responsable : Mohamed
AKIL et Laurent PERROTON
Objectifs :
Maîtriser des techniques liées à la parallélisation et la répartition d'applications. On illustrera les concepts à travers la parallélisation d'algorithmes de base dans les domaines du traitement numérique des graphes et de l'imagerie.Pré-requis :
Mise en oeuvre de ces techniques à l'aide de PVM et dans un environnement Multi-thread sous UNIX.
|
|
|||
|
|
|
|
|
|
|
|
|
|
| Parallélisme :
Modèles de calcul parallèles, sources de parallélisme, SIMD, MIMD, PRAM - architecture à passage de messages - communications - topologies - hypercube - algorithmique - analyse de dépendances - ordonnancement |
|
|
|
| Architectures parallèles dédiées et applications
:
Modèles systoliques et programmation dynamique - Parallélisation d'algorithmes en traitement d'images : convolution, histogramme, étiquetage en régions, sur différents modèles et différentes topologies : grille 2D, hypercube, pyramide et architectures reconfigurables |
|
|
|
| Répartition :
Introduction aux systèmes répartis : Les incertitudes spatiales et temporelles induites par la répartition Exclusion mutuelle et allocation de ressources : exclusion mutuelle distribuée, allocation répartie de ressources. Synchronisation répartie : synchronisation par rendez-vous - synchronisation par temps global virtuel - ordonnancement causal des messages - détection de la terminaison |
|
|
|
Evaluation :
|
|
|
|
| Oral, Analyse d'articles sur le parallélisme |
|
|
| Rapport de T.P. Algorithmes répartis |
|
|
| Rapport de T.P. Algorithmes parallèles |
|
|
| Rapport de T.P. Imagerie parallèle |
|
Bibliographie :
Commentaires : Intervenants principaux - L. Perroton, M. Akil, P. Bonnin
- Algorithmique parallèle - M.COSNARD, M.NIVAT, Y.ROBERT (Masson) -
- Computer Architecture and Parallel Processing - H.WANG, F.BRIGGS (Mac Graw-Hill) -
- Informatique parallèle et systèmes multiprocesseurs - J.L.JACQUEMIN (Hermès)
- Les ordinateurs massivement parallèles - C.GERMAIN-RENAUD, J.P.SANSONNET (Armand Colin 1991) -
- Synchronisation et état global dans les systèmes répartis - M.RAYNALD (Eyrolles) -
- The design and analysis of parallel algorithms - S.AKL (Prentice Hall 1989) -
Moyens pédagogiques particuliers : Analyse et présentations
d'articles