Examen Session Principale
Module : Calcul Parall le et Distribu
Enseignant responsable : Yosr SLAMA
Section : BADs S1
Documents : Non autoris s
Date : 06 f vrier 2021
Dur e : 2H
Soyez clairs, pr cis et concis. Lisez bien l nonc . Justifiez vos r ponses.
Probl me 1 : (10 points)
Soit un programme P d valuation de 4 Mod les de Machine Learning sur un flot de donn es
D.
P est constitu des 13 tapes Ei (i=0..12) suivantes :
E0 : Nettoyer les donn es D et en extraire les donn es dataset D1 et labelset D2.
E1 : Extraire partir de D1, D2 des donn es de test D3.
E2 : Extraire partir de D1, D2 des donn es dapprentissage D4.
E3 : Cr er les 4 mod les M1, M2, M3 et M4.
E4, E5, E6, E7 : Entrainer les mod les M1, M2, M3, M4 par les donn es dapprentissage D4
Publicité
pour obtenir respectivement MT1, MT2, MT3, MT4.
E8, E9, E10, E11 : Pr dire les mod les MT1, MT2, MT3, MT4 par rapport aux donn es de test
D3, pour obtenir respectivement les pr dictions P1, P2, P3 et P4.
E12 : Evaluer la meilleure pr diction parmi P1, P2, P3, et P4 pour obtenir le meilleur mod le.
Ci-dessous un tableau donnant le co t (temps dex cution) de chaque t che.
T che
Co t
E0
E1, E2
E3
E4, E5
E6, E7
E8, E9
E10, E11
E12
2
1
Publicité
1
3
4
2
3
1
1. Calculer le temps T1 de lex cution s quentielle de P.
2. Etudiant les d pendances entre les t ches de P. Dessiner le graphe de pr c dences.
3. Donner les t ches critiques ainsi que le temps dex cution optimal Topt que peut avoir une
ex cution parall le de P sur une infinit de processeurs. Donner lacc l ration Sopt.
4. Proposer un ordonnancement parall le optimal ; Makespan= Topt, en utilisant un nombre
optimal de processeurs Popt que lon d terminera. Calculer lefficacit Eopt.
5. On suppose maintenant que les 13 t ches sont ind pendantes et que lon dispose de deux
processeurs P1 et P2 de vitesses diff rentes v1=1 et v2= .
Proposer un ordonnancement en utilisant LPT-2. Donner le makespan, lacc l ration et
lefficacit .
Probl me 2 : (10 points)
Publicité
Soit le nid de boucles N suivant :
Do i= 1, n1
Do j=1, n2
Do k=1, n3
Do m=l, n4
S
A(i,j,k,m) := A(i-1,j,k+3,m) + A(i+2,j,k+1,m+2) * A(i,j-1,k+4,m-1)
End Do
End Do
End Do
End Do
On supposera que chaque op ration arithm tique co te 1 unit de temps.
1. Donner le temps dex cution s quentiel T1.
2. Etudier les d pendances entre les instances dinstructions de N :
a. Donner lensembles des it rations de d pendances en indiquent le type de chaque
d pendance.
b. Donner la matrice des distances des d pendances.
Publicité
c. Donner la matrice des signes des distances des d pendances.
3. Etudier la parall lisation des boucles du nid dans sa version initiale (N -ijkm).
a. D terminer la nature des boucles (s quentielles ou parall les).
b. Si une certaine parall lisation est possible, indiquer le nombre p de processeurs
n cessaires, le makespan Tp, lacc l ration Sp et lefficacit Ep.
4. Donner les permutations valides (avec inversion si n cessaire) qui permettent dam liorer le
parall lisme de N.
5. Dans chacun des cas suivant, choisir la (ou les) meilleure(s) transformations qui extrait le
plus de parall lisme en indiquant le crit re quil faudrait prendre en compte dans ce cas.
Donner le programme parall le r sultant. Indiquer le nombre p de processeurs n cessaires, le
makespan Tp, lacc l ration Sp et lefficacit Ep.
a. Cas o n1= n2= n3= n4
b. Cas o n1=10, n2=20, n3=100 et n4=2
Bon Travail.