Introduction à l'ordonnancement en OpenMP

Dans une boucle parallélisée avec OpenMP, le travail, c'est-à-dire les itérations de la boucle, est réparti entre plusieurs threads. L'ordonnancement (ou scheduling) détermine comment ces itérations sont distribuées entre les threads. Le principal objectif de l'ordonnancement est de maximiser l'efficacité de la parallélisation en répartissant équitablement la charge de travail. Un mauvais choix d'ordonnancement peut entraîner une sous-utilisation des ressources, où certains threads restent inactifs tandis que d'autres achèvent leur tâche.

1. Ordonnancement Static

a. Définition

cpp

Copier le code

#pragma omp parallel for schedule(static, 256)


Avec l'ordonnancement static, les itérations de la boucle sont réparties de manière fixe entre les threads avant même le début de l'exécution. Chaque thread se voit attribuer un bloc fixe d'itérations, qui ne changera pas au cours de la boucle. Dans l'exemple ci-dessus, chaque thread se voit attribuer des blocs de 256 itérations à traiter.

b. Exemple

Prenons une boucle avec 1000 itérations réparties entre 4 threads :

c. Avantages

d. Inconvénients

e. Cas d'utilisation

L'ordonnancement static est idéal lorsque les itérations sont homogènes en termes de temps de calcul, par exemple pour des boucles où chaque itération consiste en des calculs simples.


2. Ordonnancement Dynamic

a. Définition

cpp

Copier le code

#pragma omp parallel for schedule(dynamic, 256)


Avec l'ordonnancement dynamic, les itérations de la boucle sont réparties dynamiquement au fur et à mesure que les threads terminent leur travail. Ici, chaque bloc contient 256 itérations, et lorsqu'un thread a fini d'exécuter son bloc, un autre bloc lui est attribué.

b. Exemple

Pour une boucle de 1000 itérations avec 4 threads :

c. Avantages

d. Inconvénients

e. Cas d'utilisation

L'ordonnancement dynamic est recommandé lorsque le temps d'exécution des itérations est variable. Par exemple, pour des boucles où certaines itérations contiennent des calculs complexes.


3. Ordonnancement Guided

a. Définition

cpp

Copier le code

#pragma omp parallel for schedule(guided, 256)


L'ordonnancement guided combine les avantages de static et dynamic. Les premiers blocs attribués sont grands, mais à mesure que les threads terminent leur travail, les blocs deviennent de plus en plus petits, permettant un équilibrage de la charge sans trop de surcharge.

b. Exemple

Pour une boucle de 1000 itérations avec 4 threads :

c. Avantages

d. Inconvénients

e. Cas d'utilisation

Utilisez guided lorsque le temps d'exécution des itérations est modérément variable.


4. Comparaison entre les types d'ordonnancement

Ordonnancement

Attribution des blocs

Overhead

Cas d'utilisation

Static

Fixe

Faible

Itérations homogènes

Dynamic

Dynamique

Élevé

Itérations hétérogènes

Guided

Grands blocs au début, petits à la fin

Moyen

Itérations modérément variables


5. Conclusion

Le choix de l'ordonnancement dépend du comportement des itérations dans la boucle. Pour des itérations homogènes, static est souvent optimal. Lorsque les itérations sont très variables en termes de temps d'exécution, dynamic ou guidedpermettent un meilleur équilibrage de la charge de travail. Il est important de tester les performances de chaque méthode pour chaque situation spécifique.


Annexe : Exécution Asynchrone et Répartition Dynamique des Tâches

1. Exécution asynchrone

L'exécution asynchrone signifie que les tâches ne s'exécutent pas de manière séquentielle ou synchrone. Cela permet de mieux utiliser les ressources, car les tâches peuvent s'exécuter en parallèle.

2. Répartition dynamique des tâches

Avec la répartition dynamique, les tâches sont distribuées aux threads au fur et à mesure que ceux-ci deviennent disponibles. Cela permet une meilleure utilisation des threads lorsque le temps d'exécution des tâches est variable.


Exemple avec OpenMP Tasks

Voici un exemple de multiplication matrice-vecteur avec OpenMP Tasks, permettant d'illustrer l'exécution asynchrone et la répartition dynamique des tâches.

cpp

Copier le code

#include <iostream>

#include <omp.h>


int main() {

  const int dim = 3;  

  double A[dim * dim] = {1, 2, 3, 4, 5, 6, 7, 8, 9};  

  double x[dim] = {1, 1, 1};  

  double b[dim] = {0};  


  #pragma omp parallel

  {

    #pragma omp single

    {

      for (int i = 0; i < dim; i++) {

        #pragma omp task firstprivate(i)

        {

          b[i] = 0;  

          for (int j = 0; j < dim; j++) {

            b[i] += A[i * dim + j] * x[j];  

          }

          std::cout << "Tâche pour b[" << i << "] terminée, résultat: " << b[i] << std::endl;

        }

      }

      #pragma omp taskwait  

    }

  }


  std::cout << "Produit matrice-vecteur terminé. Résultats b[i] :\n";

  for (int i = 0; i < dim; i++) {

    std::cout << "b[" << i << "] = " << b[i] << std::endl;

  }


  return 0;

}


Ce code montre comment les tâches OpenMP peuvent être utilisées pour exécuter des calculs de manière asynchrone, tout en répartissant dynamiquement les tâches entre les threads disponibles.