Programmation parallèle

Ce document présente les bases de la programmation parallèle, en particulier pour les étudiants et développeurs souhaitant comprendre et utiliser les API MPI et OpenMP. Il explique les paradigmes de mémoire distribuée et partagée, les méthodes d’installation, ainsi que des exemples de programmes illustrant ces concepts.

Introduction à la programmation parallèle

La programmation parallèle consiste à écrire des programmes capables d'exécuter plusieurs tâches simultanément, afin d'améliorer les performances sur des machines parallèles ou des grilles de calcul (Grid). Deux API principales sont utilisées en C ou C++ pour ce type de programmation :

• MPI (Message Passing Interface) : illustre le paradigme de la mémoire distribuée, où chaque unité de traitement possède sa propre mémoire.
• OpenMP (Open Multiprocessing) : illustre le paradigme de la mémoire partagée, où plusieurs threads partagent un espace mémoire commun.

Ces deux API sont complémentaires et peuvent être utilisées ensemble dans une programmation hybride, mais dans cette introduction, elles seront utilisées séparément.

Installation et compilation

Pour utiliser OpenMP, il suffit d'avoir le compilateur gcc installé, car il intègre déjà le support de cette API. Pour MPI, il est conseillé d'installer OpenMPI.

La compilation d'un programme OpenMP se fait avec l'option -fopenmp. Par exemple :

gcc -fopenmp prog.c -o executable

L'exécutable se lance ensuite simplement avec :

./executable

Pour MPI, la compilation se fait avec la commande mpicc :

mpicc prog.c -o executable

L'exécution se fait avec mpirun en précisant le nombre de processus :

mpirun -np nb_processus ./executable

Programmation avec OpenMP

OpenMP permet de lancer plusieurs threads dans une application mono-processus. Le thread principal peut créer plusieurs threads en parallèle. Les variables du programme peuvent être :

• shared (communes) : accessibles par tous les threads
• private (privées) : chaque thread possède sa propre copie

La synchronisation entre threads est importante, notamment via des barrières qui assurent que tous les threads atteignent un point donné avant de continuer.

Exemples de programmes OpenMP

• omp_hello.c : lance plusieurs threads, chacun affichant son numéro. Plusieurs versions (V2 à V5) illustrent l'usage des variables partagées ou privées et l'importance des barrières de synchronisation.
• anneau.c : les threads communiquent en formant un anneau virtuel basé sur leur numéro.
• date_Paques.c : calcule la date de Pâques, démontrant un exercice simple en parallèle.
• somme_omp.c : calcule la somme d'un tableau de valeurs aléatoires en divisant les données en blocs de taille égale (+1).
• somme_omp_V2.c : version améliorée avec un thread supplémentaire et un dernier bloc de taille « reste ».
• tri_omp.c : implémente un tri exhaustif en parallèle.
• prefixe_parallel.c : calcule un préfixe en parallèle, avec une version incorrecte prefixe_blague.c pour illustrer les erreurs possibles.

Exemple simple : affichage des numéros de threads

#include <omp.h>
#include <stdio.h>

int main() {
  #pragma omp parallel
  {
    int id = omp_get_thread_num();
    printf("Thread numéro %d\n", id);
  }
  return 0;
}

Ce programme lance plusieurs threads qui affichent chacun leur numéro. La directive #pragma omp parallel crée une région parallèle.

Programmation avec MPI

MPI est une API pour la programmation parallèle en mémoire distribuée. Une application MPI est composée de plusieurs processus, issus du même code (SPMD : Single Program Multiple Data) ou de codes différents (MPMD : Multiple Program Multiple Data). Il est conseillé de ne pas utiliser plus de trois programmes différents dans une même application MPI.

Compilation et exécution

Chaque programme MPI est compilé séparément avec :

mpicc prog.c -o executable

L'exécution se fait avec :

mpirun -np nb_processus ./executable

Si plusieurs exécutables sont utilisés, la commande devient :

mpirun -np n1 ./executable1 -np n2 ./executable2 ...

Exemples de programmes MPI

• mpi_code.c : détecte et affiche le numéro du processus (équivalent d'un "Hello, world!").
• mpi_anneau.c : les processus forment un anneau virtuel basé sur leur numéro.
• mpi_pascal.c : calcule le triangle de Pascal en parallèle (exemple plus complexe).

Dans tous ces programmes, la détection du numéro d'ordre du processus dans son groupe (communicateur) est essentielle pour la communication entre processus.

Exemple simple : affichage du numéro de processus MPI

#include <mpi.h>
#include <stdio.h>

int main(int argc, char** argv) {
  MPI_Init(&argc, &argv);

  int rank;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  printf("Processus numéro %d\n", rank);

  MPI_Finalize();
  return 0;
}

Problèmes résolus en parallèle

• Calcul de la date de Pâques : solutions séquentielle, en mémoire partagée (OpenMP) et en mémoire distribuée (MPI). L'exécutable attend en entrée l'année de référence.
• Produit matrice-vecteur : solution séquentielle, parallélisme par threads avec un nombre prédéfini de threads, et version MPI. L'exécutable attend en entrée les noms des fichiers d'entrée et de sortie.

Glossaire des termes clés

• API : Interface de Programmation d'Applications, ensemble de fonctions pour programmer.
• MPI : Message Passing Interface, API pour la programmation parallèle en mémoire distribuée.
• OpenMP : Open Multiprocessing, API pour la programmation parallèle en mémoire partagée.
• Thread : unité d'exécution légère dans un processus.
• Processus : instance d'un programme en cours d'exécution, avec sa propre mémoire.
• SPMD : Single Program Multiple Data, modèle où plusieurs processus exécutent le même programme sur des données différentes.
• MPMD : Multiple Program Multiple Data, modèle où plusieurs processus exécutent des programmes différents.
• Communicateur : groupe de processus MPI qui peuvent communiquer entre eux.
• Barrière de synchronisation : point où tous les threads/processus doivent arriver avant de continuer.
• Shared : variable partagée entre plusieurs threads.
• Private : variable privée à chaque thread.

Points clés à retenir

• OpenMP est adapté à la mémoire partagée, avec des threads dans un même processus.
• MPI est adapté à la mémoire distribuée, avec plusieurs processus communiquant par messages.
• La compilation et l'exécution diffèrent selon l'API utilisée : -fopenmp pour OpenMP, mpicc et mpirun pour MPI.
• Les variables peuvent être partagées ou privées en OpenMP, ce qui influence la gestion de la mémoire et la synchronisation.
• Les programmes parallèles doivent gérer la synchronisation et la communication entre unités d'exécution.
• Des exemples concrets comme le calcul de la date de Pâques ou la somme d'un tableau illustrent ces concepts.