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 d’apprentissage 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 d’apprentissage D4 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 d’exécution) de chaque tâche.
Tâche
Coût
Publicité
E0 E1, E2 E3 E4, E5 E6, E7 E8, E9 E10, E11 E12
2 1 1 3 4 2 3 1
1. Calculer le temps T1 de l’exé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 d’exécution optimal Topt que peut avoir une
exécution parallèle de P sur une infinité de processeurs. Donner l’accélération Sopt.
4. Proposer un ordonnancement parallèle optimal ; Makespan= Topt, en utilisant un nombre
optimal de processeurs Popt que l’on déterminera. Calculer l’efficacité Eopt.
5. On suppose maintenant que les 13 tâches sont indépendantes et que l’on 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, l’accélération et l’efficacité.
Problème 2 : (10 points)
Soit le nid de boucles N suivant :
Do i= 1, n1 Do j=1, n2 Do k=1, n3
Do m=l, n4
Publicité
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 d’exécution séquentiel T1.
2. Etudier les dépendances entre les instances d’instructions de N :
a. Donner l’ensembles des itérations de dépendances en indiquent le type de chaque
dépendance.
b. Donner la matrice des distances des dépendances.
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
Publicité
nécessaires, le makespan Tp, l’accélération Sp et l’efficacité Ep.
4. Donner les permutations valides (avec inversion si nécessaire) qui permettent d’amé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 qu’il 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, l’accélération Sp et l’efficacité Ep.
a. Cas où n1= n2= n3= n4
b. Cas où n1=10, n2=20, n3=100 et n4=2
Bon Travail.