Niveau: Supérieur, Master, Bac+4
Parallélisme et Répartition M1 IFI/MBDS, Janvier 2011, Session 2 2 heures, Feuille A4 manuscrite recto-verso autorisée 1 Recherche du premier élément d'une séquence Le but de cet exercice est de proposer des algorithmes PRAM permettant de chercher la première occurrence d'un élément dans une liste ou un tableau. Pour simplifier, nous allons considérer un tableau T de N éléments pouvant prendre la valeur 0 ou 1 et l'algorithme donnera l'indice du premier 1. 1.1 Algorithme A Dans un premier temps, nous allons implémenter une version simple de l'algorithme. Il construit un tableau RESULT de taille N dont les cases sont remplies de la façon suivante. Pour chaque case i de T contenant un 1, si il existe un élément 1 d'indice plus petit, alors RESULT [i] = 0, sinon RESULT [i] = 1. Il suffit ensuite de regarder le contenu de RESULT pour connaître l'indice du premier élément 1. 1. Exécutez l'algorithme sur le tableau [0, 0, 0, 0, 1, 0, 1] 2. Ecrivez l'algorithme qui remplit le tableau RESULT 3. Ecrivez l'algorithme qui donne l'indice du premier élément 1. 4. Combien de processeurs cet algorithme nécessite-t-il pour avoir un paral- lélisme maximal ? 1.2 Réduction du nombre de processeurs Nous allons essayer de réduire le nombre de processeurs nécessaires pour trou- ver le premier élément.
- recto-verso autorisée
- feuille a4 manuscrite
- algorithme sur le tableau
- code mpi
- processeur
- topologie de grille
- tri de séquence bitonique
- parallélisme maximal
- pseudo- mpi