Niveau: Supérieur, Master, Bac+4
Parallélisme et Répartition M1 IFI/MBDS, Décembre 2010, Session 1 2 heures, Feuille A4 manuscrite recto-verso autorisée 1 Recherche du minimum sur PRAM en temps poly-logarithmique Le but de cet exercice est de proposer des algorithmes permettant de calculer le minimum d'une séquence d'entiers contenue dans un tableau T [1, .., N ] sur une machine PRAM. 1.1 Exécution en O(1) Une première version de l'algorithme fonctionne de la façon suivante. Chaque processeur va comparer un élément du tableau initial (T [i]) avec un autre élé- ment (T [j] avec i 6= j)). Le résultat de cette comparaison sera mis dans un nouveau tableau. Dans une deuxième phase, l'algorithme utilisera ce tableau de résultats pour trouver le minimum. 1. Écrivez une boucle for permettant d'initialiser le nouveau tableau en O(1). 2. Écrivez la boucle for qui effectue les comparaisons et remplis le nouveau tableau en O(1). 3. Écrivez la boucle for qui affiche l'élément minimum du tableau en O(1). 4. Combien de processeurs cet algorithme nécessite-t-il ? 5. Sur quel type de P-RAM peut-il être exécuté ? 1.2 Réduction du nombre de processeurs Nous allons essayer de réduire le nombre de processeurs nécessaires pour trouver le minimum.
- rang du leader
- anneau
- pram
- message election contenant le rang du processus
- élection de leader sur anneau avec passage de message
- tableau initial
- leader
- pram en temps poly-logarithmique