[PDF] [PDF] Parallélisme et Répartition-Correction

View - Download [PDF] Parallélisme et Répartition-Correction

Previous PDF

Next PDF

Parallélisme et Répartition-Correction

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 tableauT[1;::;N]sur une machine PRAM.

1.1 Exécution enO(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=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. Écriv ezune b oucleforpermettant d"initialiser le nouveau tableau enO(1). Il y a deux façons de procéder, soit faire un tableau de tailleN2, soit faire un tableau de tailleN. La version avecNest plus simple à écrire. La caseresult[i]va contenir le nombre de valeurs inférieures àT[i]. pour i de 1 à N en parallèle { result[i]=0; 2. Écriv ezla b oucleforqui effectue les comparaisons et remplis le nouveau tableau enO(1). pour i,j de 1 à N en parallèle { si (T[i]>T[j]) { result[i]=result[i]+1; 3. Écriv ezla b oucleforqui affiche l"élément minimum du tableau enO(1). Par construction, siresult[i]contient 0, c"est qu"aucun élément plus petit queT[i]n"a été trouvé, c"est donc lui le plus petit 1 pour i de 1 à N en parallèle { si(result[i]==0) { afficher(i); } 4. Com biende pro cesseurscet algorithme nécessite-t-il ? Pour N éléments, on doit faire de l"ordre deN2comparaisons, doncO(N2)processeurs. 5. Sur quel t ypede P-RAM p eut-ilêtre exécuté ? On a des accés concurrents en lecture suivant les valeurs du couple(i;j), mais aussi des accés en

écriture surresult[i]. Donc une CRCW.

1.2 Réduction du nombre de processeurs

Nous allons essayer de réduire le nombre de processeurs nécessaires pour trouver le minimum. SoitA1l"algorithme écrit dans la section précédente. SoitA2 l"algorithme fonctionnant de la façon suivante Le tableau initial est découpé (logiquement) en blocs de taillepn A1est appliqué sur chacun des blocs pour obtenir un tableau depncases.

A1est appliqué sur le tableau précédent

1.

Exécutez A2sur le tableau[4;5;17;3;8;9;0;2;20]

2. Dans le cas général, q uecon tientle tableau crée à l"e tape2 ? Il contient le minimum de chaque bloc de taillepN. 3.

Mon trezque A2nécessiteN1+12

processeursEn partant d"un tableau de tailleN, il va y avoirpNblocs depNéléments. Or pour traiter un bloc, il fautpNpNcomme montré dans l"exercice précédent. Nous avons donc besoin depNpNpN=N1+12 4.

Prop osezun algorithme A3nécessitantN1+14

processeurs.On divise le tableau initial en blocs de taillepNet on appliqueA2sur chacun d"eux. Donc on apNalgorithmesA2en parallèle, chacun travaillant sur un tableau de taillepN. En utilisant le résultat de la question précédente, on trouve que chaqueA2nécessiteN12 +14 et donc un total depNN12 +14 N 1+14 5. Décrire brièv ementun algorithme Akutilisant l"algorithmeAk1pour trouver le minimum d"un tableau deNéléments (on ne demande pas d"écrire cet algorithme pour une PRAM).On divise le tableau initial en blocs de taillepNsur lesquels ont appliqueAk1 6. Quel est le nom brede pro cesseursnécessaires p ourAk?En utilisant les résultats précédents, on voir que le nombre de processeurs estN1+12 k1. Il suffit de vérifier pourA1=N2,A2=N1+12 7. Quelle est la complexité en temps de Ak?La difficulté ici est de trouver le plus grandkpour une valeur deNdonnée. Ça indique la profondeur de l"arbre et donc la complexité en temps de l"algorithme. Pour cela, remar- quons que siAktravaille sur un tableau deNcases,Ak1travaille sur 2 Figure 1: Représentation arborescente de l"algorithme pNtableaux depNcases,Ak2sur des tableaux de4pN... Autrement dit, les blocs ont une taille deN12 iet l"algorithme s"arrête quand le bloc est trop petit pour être sub-divisé. Il suffit donc de résoudreN12 i= 2, ce qui donnei=O(log(log(N)).

2 Tri fusion de Batcher sur PRAM

On rappelle que le tri fusion de Batcher utilise des comparateurs pour construire des réseauxFUSIONm, tel queFUSION1fusionne deux listes triées de21

éléments.

1. Commen tconstruit-on un réseau FUSIONm? Combien de comparateurs sont-ils nécessaires? 2. Com bienfaut-il de pro cesseurssur une PRAM p ourimplémen terun com- parateur ? 3. En déduire le nom brede pro cesseursn écessairesp ourimplémen terFUSIONm 4.

Commen tconstruit-on TRIm?

5. Com biende pro cesseursson t-ilsnécessaires p ourimplémen terTRImsur une PRAM ?

3 Élection de 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. Le but 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 3 Quand le message revient au processus initial, il identifie le leader, et envoie sur l"anneau un messageOKcontenant le rang du leader 1. Com biende Sendet deReceivesont effectués lors d"une élection sur un anneau de N processus? 2. Sac hantque le temps de comm unicationest 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. Écriv ezune métho de(en pseudo) C/MPI election(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. On supp osequ"une panne arriv ep endantune é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 Anneau et Hypercube

On considère un anneau de2dnoeuds et un hypercube de dimensiond. 1.

Com biende no eudsy"a-t-il dans u nd-cube?

2. Rapp elezcommen test cons truitun d-cubeet comment son numérotés les sommets 3. Mon trezqu"un anneau de 8 no eudsp eutêtre construit sur un 3cube(i.e. il est possible de relier les noeuds de l"hypercube sous forme d"un anneau). 4. Une idée p ourle cas général de 2dnoeuds ? 4quotesdbs_dbs7.pdfusesText_13

[PDF] MLO - TD logique des prédicats - Ensiie

[PDF] EXERCICE 1 (5 points ) (Commun ? tous les - Math France

[PDF] Fiabilité

[PDF] Machine frigorifique : corrigé

[PDF] Travaux dirigés de magnétisme

[PDF] Fiabilité

[PDF] Dossier de Maintenance- Corrigé - Eduscol

[PDF] Marche de potentiel

[PDF] Corrigé Mathématiques financières 2

[PDF] Mathématiques financières EXERCICES CORRIGES - Cours

[PDF] Exercices et examens résolus: Mécaniques des Systèmes de

[PDF] Mécanique Quantique 2`eme édition - Laboratoire de Physique

[PDF] LA COMPTABILITE A BASE D 'ACTIVITES Méthode - IUT en Ligne

[PDF] Analyse Numérique

[PDF] TD - corrigé