Sections parallèles

Dans ce exercice nous allons étudier l'utilisation des sections parallèles d'openMP en nous basant sur l'implémentation d'un QuickSort.

  1. Téléchargez le squelette de quicksort et vérifiez qu'il compile/fonctionne
  2. 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)
  3. 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é
  4. Que se passe-t-il si vous fixez le nombre de threads à 1 ?

Lignes de vue

Un promeneur veut faire une promenade dans une région montagneuse. Pour cela, il se munie d'un relevé topographique de la zone qu'il va visiter. Il s'agit simplement de la hauteur de chacun des sommets qu'il va rencontrer au cours de son parcours. Le promeneur désire savoir quelles montagnes seront visibles au début de son parcours, et pour cela, nous allons écrire un programme ligne-de-vue.c en OpenMP. Pour simplifier le problème, nous allons considérer les hypothèses suivantes:

  • La taille du promeneur est négligeable par rapport à celles des montagnes
  • L'environnement est discretisé, le premier sommet se trouve à la position 1, le deuxième à la position 2, ...
  • Il ne se déplace qu'en ligne droite, sur des sommets désertiques (pas de végétation ni d'obstacles)
  • Il regarde depuis le premier sommet de son parcours
  • Il ne voit pas le sommet sur lequel il se trouve
  • Il n'y a PAS toujours 2^m sommets

  1. Quels sont les sommets visibles par l'observateur placé sur le sommet 1 dans la figure ci-dessous ? lightExample.jpg
  2. En déduire la condition permettant de décider si un sommet n est visible (indication: cette condition utilise les n-1 sommets précédents)
  3. L'algorithme prefix vu en cours permet d'appliquer une opération OP sur un ensemble d'éléments tel que yk=x1 OP x2 OP ... OP X(k-1). Quelle propriété doit avoir OP ?
  4. Implémentez une méthode max-prefix qui applique l'opération max(x,y) sur un tableau passé en paramètre (indication: vous avez implémenté sum-prefix la semaine dernière en utilisant des tableaux remplis partiellement de 0, qui est l'élément neutre pour l'addition. Quel est l'elément neutre pour max? ). Pensez à tester cette méthode, c'est la clef du problème
  5. Pour le Vendredi 16 Novembre complétez votre programme pour calculer les sommets visibles. La liste des sommets sera stockée dans un fichier qui sera passé en paramètre du programme. Le programme devra afficher 0 si un sommet n'est pas visible, et 1 si il est. Votre application doit avoir exactement la même sortie que celle donnée dans l'exemple ci-dessous (rien de plus, rien de moins):
fhuet$ ./ligne-de-vue data1
0 1 1 0 0 0 0 1
fhuet$ ./ligne-de-vue data2
0 1 0 0 0 0 0 0

Le programme ne devra produire aucune autre sortie. Le programme est à déposer dans la boite de dépôt correspondante sur Jalon. Le fichier devra s'appeler nom.c et compiler sans erreurs ni warning avec la ligne gcc -Wall -fopenmp -lm Les critères d'évaluation seront la correction du programme, la qualité du code et sa robustesse. La similarité des fichiers sera testée pour détecter les copies/emprunts. Tout abus sera sanctionné. Tout retard sera sanctionné.

Question bonus
Donnez la possibilité à votre programme de calculer les sommets visibles pour un observateur placé sur un autre sommet que le premier. Le numéro du sommet sera passé comme deuxième paramètre. Les sommets derrière l'observateur seront considérés comme non visibles.

Attachment sort Action Size Date Who Comment
quicksort.c manage 1.7 K 02 Oct 2008 - 16:29 FabriceHuet  
lightExample.jpg manage 19.9 K 02 Oct 2008 - 16:40 FabriceHuet  
data1 manage 0.1 K 02 Oct 2008 - 16:42 FabriceHuet  
data2 manage 0.1 K 07 Oct 2008 - 08:49 FabriceHuet  

Revision: r1.10 - 02 Nov 2012 - 07:24 - LaurentPellegrino
Minfo > ParallRepa > PArallTDM4
Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback