Algorithmique Parallèle
Épreuve PRAM/Réseaux de communication/Algorithmes sur des réseaux
Oguz Kaya Master 1 PDCS/2020-21
1 La somme d’un tableau d’entiers
Soit X[N] un tableau d’entiers de taille N. Question 1
2
a)
b) c) d)
Concevoir un algorithme parallèle Somme(X[N]) qui rend la somme d’éléments d’un tableau X sur une machine PRAM EREW.
Calculer le temps d’exécution, le coût, et le travail total de l’algorithme. Est-il “work-optimal”? Faire pareil sur une machine PRAM CRCW (en précisant le mode de fusion choisi).
Calculer le temps d’exécution, le coût, et le travail total de l’algorithme. Est-il “work-optimal”?
Renverser une liste
Soit next[N] une liste enchaînée. Question 2
a) Développer un algorithme Renverser(next[N],prev[N]) pour EREW PRAM qui calcule l’inverse de cette liste dont pointeurs sont stockés dans prev[N].
b) Quel est le temps d’exécution?
3 Trier un tableau d’entiers uniques
Soit X[N] un tableau d’entiers uniques. Question 3
a) Développer un algorithme Sort(X[N]) qui tri ce tableau sur une machine CRCW PRAM. 4 Simulation de mode de fusion en CRCW
Pour cet exercice, considérez la machine CRCW avec le mode de fusion consistent (c’est à dire, écritures simultanées sur une case mémoire sont permises à condition que toutes les PUs écrivent exactement la même valeur).
Question 4
a) Prouvez que avec cette machine CRCW en mode de fusion consistent, on peut simuler l’exécution d’un algorithme sur un CRCW en mode de fusion minimum (qui garde la valeur minimum en cas d’écritures simultanées par plusieurs PUs) tout en restant dans la même complexité asymptotique de temps d’exécution en utilisant un nombre infini de PUs.
1
6
TD1-PRAM 2020-21
5 Transposition sur un anneau unidirectionnel
Dans un anneau unidirectionnel ayant p processeurs, on suppose que chaque processeur à un tableau sendMsg[i] de taille N à envoyer à chaque processeur i (0 ≤ i < p) dans l’anneau (y compris lui-même).
Question 5
a)
b)
RéaliserlafonctionTransposition(sendMsg[p],recvMsg[p],N)dansunanneauunidirectionneltelquechaque processeur i renvoi son tableau local sendMsg[j] au processeur j dans l’anneau et reçoit le tableau envoyé à lui-même par le processeur k dans recvMsg[k]. Tous les tableaux sendMsg[] et recvMsg[] sont de taille N dans tous les processeurs.
Trouver le temps d’exécution en fonction de L,b,N. Mergesort dans un hypercube
Développer un algorithme parallèle qui tri un tableau X[N] en parallèle sur un d-cube ayant p = 2d processeurs. Supposer que p divise N et que le tableau X[N] est distribué aux processeurs par des blocs de taille r = N/p tel que P0 possède X[0,...,r−1], P1 a X[r,...,2r−1], etc.
Question 6
a) Implanter l’algorithme Mergesort(X[r]) qui effectue le mergesort sur ce d-cube ayant le tableau X[N] distribué initialement aux processus. Utiliser la fonction Sort(A[t]) pour trier localement un tableau de taille t et Merge(A[t],B[k]) pour fusionner localement deux tableaux triés de taille t et k qui rend leur fusion étant un tableau trié de t + k éléments.
b) Soit L, b, w respectivement la latence, l’inverse de la bande passante et le temps d’effectuer une opération arith- métique dans un processeur. Trouver le temps d’exécution, l’accéleration et l’efficacite de cet algorithme en fonction de L, b, w, N, p.
- 2-