Dans ce exercice nous allons étudier l'utilisation des sections parallèles d'openMP en nous basant sur l'implémentation d'un QuickSort. Ces sections sont activées par la combinaison de deux pragma (omp parallel sections et omp parallel section)
- Téléchargez le squelette de quicksort et vérifiez qu'il compile/fonctionne
- Exécutez le pour des tailles croissantes de tableau, mesurez le temps d'exécution et tracez une courbe du temps en fonction de la taille.
- Que constatez vous ?
- Expliquez ce comportement
- En déduire qu'il faut se méfier du code qu'on vous donne
- Modifiez la méthode quicksort pour que les appels récursifs soient effectués dans deux sections parallèles d'openMP. Combien de threads sont créées lors du tri d'un tableau ? (utilisez l'option -L de ps sous Linux, -M sous BSD, l'option -H de top ou simplement htop)
- OpenMP supporte la notion de parallélisme imbriqué mais elle n'est pas activée par défaut. Utilisez la méthode omp_set_nested pour l'activer. Combien de threads sont créees lors du tri ? En déduire le principe de fonctionnement du parallélisme imbriqué
- Que se passe-t-il si vous fixez le nombre de threads à 1 ?
- Mesurez les performances des versions séquentielles et parallèles en fonction de la taille du tableau. Qu'en concluez vous ?
La lenteur de la version parallèle vient du coût de création des threads au début et du coût d'entrée/sortie des sections parallèles, même quand elles ne créent pas de nouveaux threads.
- Ajoutez un dry run sur un petit tableau juste avant votre mesure de temps pour forcer openMP à créer les threads.
- Modifiez le code de sorte que la pragma
omp parallel sections ne soit executée qu'une unique fois au début de l'exécution. - Comparez à nouveau les temps d'exécution des versions parallèle et séquentielle.
- Une alternative à
sections est l'utilisation de tasks. Implémentez cette nouvelle approche et discutez les résultats.