M1 IFI MBDS Décembre Session

Description

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

Sujets

• Anneau
• Leader

Informations

• Publié par: larec
• Publié le: 01 décembre 2010
• Nombre de lectures: 42
• Langue: Français

Extrait

ParallÉlisme et RÉpartition

M1 IFI/MBDS, DÉcembre 2010, Session 1

2 heures, Feuille A4 manuscrite recto-verso autorisÉe

1 Recherchedu 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 tableauT[1, .., N]sur une machine PRAM. 1.1 ExÉcutionenO(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]aveci6=jrsultat de cette comparaison sera mis dans un)). Le nouveau tableau.Dans une deuxime phase, l’algorithme utilisera ce tableau de rsultats pour trouver le minimum. 1. Ècrivezune boucleforpermettant d’initialiser le nouveau tableau enO(1). 2. Ècrivezla boucleforqui effectue les comparaisons et remplis le nouveau tableau enO(1). 3. Ècrivezla boucleforqui affiche l’lment minimum du tableau enO(1). 4. Combiende processeurs cet algorithme ncessite-t-il ? 5. Surquel type de P-RAM peut-il tre excut ? 1.2 RÉductiondu nombre de processeurs Nous allons essayer de rduire le nombre de processeurs ncessaires pour trouver le minimum.SoitA 1 Soitl’algorithme crit dans la section prcdente.A 2 l’algorithme fonctionnant de la faÇon suivante √ •Le tableau initial est dcoup (logiquement) en blocs de taillen √ •A 1 est appliqu sur chacun des blocs pour obtenir un tableau dencases. •A 1 est appliqu sur le tableau prcdent 1. ExcutezA 2 sur le tableau[4,5,17,3,8,9,0,2,20] 2. Dansle cas gnral, que contient le tableau cre À l’etape 2 ?

1

1 1+ 3. MontrezqueA 2 ncessitenprocesseurs 2 1 1+ 4 4. Proposezun algorithmeA 3 ncessitantnprocesseurs. 5. Dcrire brivement un algorithmeA k utilisant l’algorithmeA k−1 pour trouver le minimum d’un tableau deNlments (on ne demande pas d’crire cet algorithme pour une PRAM). 6. Quelest le nombre de processeurs ncessaires pourA k ? 7. Quelleest la complexit en temps deA k ?

2 Trifusion de Batcher sur PRAM On rappelle que le tri fusion de Batcher utilise des comparateurs pour construire 1 des rseauxF U SION m , tel queF U SION 1 fusionne deux listes tries de2 lments. 1. Commentconstruit-on un rseauF U SION m ? Combiende comparateurs sont-ils ncessaires? 2. Combienfaut-il de processeurs sur une PRAM pour implmenter un com- parateur ? 3. Endduire le nombre de processeurs ncessaires pour implmenterF U SION m 4. Commentconstruit-onT RI m ? 5. Combiende processeurs sont-ils ncessaires pour implmenterT RI m sur une PRAM ?

3 Electionde leader sur anneau avec passage de message De nombreux algorithmes distribus ncessitent qu’un processus ait un rÔle particulier et soit doncleader. Lebut de cet exercice est d’crire un algorithme en C/MPI pour lire un processus sur une topologie en anneau.Leleadersera le processus de plus haut rang actuellement sur l’anneau.L’algorithme est excut par le premier processus qui dtecte l’absence de leader (suite À une panne par exemple). •Un messageElectioncontenant le rang du processus est envoy au suivant sur l’anneau •Chaque processus ajoute son rang dans le message et le transmet au suiv- ant •Quand le message revient au processus initial, il identifie le leader, et envoie sur l’anneau un messageOKcontenant le rang du leader 1. CombiendeSendet deReceivesont effectus lors d’une lection sur un anneau de N processus?

2

2. Sachantque le temps de communication est de la formeβ+L.τet que le rang d’un processus occupe une taille de1dans un message, quelle est la dure totale d’une lection ? 3. Ècrivezune mthode (en pseudo) C/MPIelection(int k)permettant d’effectuer une lection.Cette mthode sera appele par tous les processus en mme temps mais seul le processus de rangkmettra le message. 4. Onsuppose qu’une panne arrive pendant une lection.Discutez des prob- lmes engendrs et des solutions possibles pour assurer l’lection lorsque c’est possible.On pourra considrer les diffrents cas suivant le processus qui tombe en panne (initiateur de l’lection ou autre) et suivant le moment de la panne (avant messageElection, avant messageOK...).

4 Anneauet Hypercube d On considre un anneau de2noeuds et un hypercube de dimensiond. 1. Combiende noeuds y’a-t-il dans und-cube? 2. Rappelezcomment est construit und-cubeet comment son numrots les sommets 3. Montrezqu’un anneau de 8 noeuds peut tre construit sur un3−cube(i.e. il est possible de relier les noeuds de l’hypercube sous forme d’un anneau). d 4. Uneide pour le cas gnral de2noeuds ?

3