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 :
Taille de bloc : 256.
Thread 1 : Itérations 0 à 255.
Thread 2 : Itérations 256 à 511.
Thread 3 : Itérations 512 à 767.
Thread 4 : Itérations 768 à 999.
c. Avantages
Prévisibilité : Chaque thread sait exactement quelles itérations il va exécuter.
Faible overhead : La répartition est effectuée une seule fois avant l'exécution, ce qui minimise la surcharge.
d. Inconvénients
Déséquilibre potentiel : Si certaines itérations sont plus coûteuses que d'autres, certains threads peuvent terminer plus tôt, laissant des ressources inactives.
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 :
Taille de bloc : 256.
Dès qu'un thread termine son bloc, il prend un nouveau bloc de 256 itérations.
c. Avantages
Équilibrage dynamique de la charge : Si certaines itérations prennent plus de temps que d'autres, les threads plus rapides peuvent prendre en charge davantage d'itérations.
d. Inconvénients
Overhead plus élevé : Le système doit réattribuer des blocs dynamiquement, ce qui implique une surcharge.
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 :
Taille de bloc initiale : 256.
Les premiers blocs sont grands (256 itérations), puis la taille des blocs diminue progressivement.
c. Avantages
Optimisation de l'équilibrage : Les grands blocs initiaux permettent d'attribuer rapidement du travail, tandis que les petits blocs finaux équilibrent la charge restante.
d. Inconvénients
Complexité accrue : Gérer des blocs de taille variable peut compliquer certaines tâches.
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.