Examen- Session Principale
Module: Calcul Parallèele et Distribué Enseignant responsable: Yosr SILAMA 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
EO: Nettoyer les données D et en extraire les données dataset DI et labelset D2.
El Extraire à partir de DI, D2 des données de test D3.
E2 Extraire à partir de Di, 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 MI, M2, M3, M4 par les données d'apprentissage D4 pour obtenir respectivement MTI, MT2, MT3, MT4.
E8, E9, E10, ElI: Prédire les modèles MTI, 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 PI, 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.
Publicité
Tache
EO El, E2 | E3 E4, ES E6, E7 | E8, E9 E10. El E12
Cout
3
. Calculer le temps Ti 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 taches critiques ainsi que le temps d'exécution optimal Topt que peut avoir une
execution parallèle de P sur une infinit(cid:23) de processeurs. Donner l'accélération Sopt.
4. Proposer un ordonnancennent parallele optmal , Makespan= Topt, en utilisant un nonmbre
optimal de processeurs Popt que l'on détermnera. Calculer l'efficacité Eopt.
5. On suppose maintenant que les 13 tâches sont indépendantes et que l'on dispose de deux
processeurs Pl et P2 de vitesses diffërentes vl=l 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 Nsuivant: 1, n Do j1, n2
Do i
Publicité
Do k=1, n
Do m=l, n4
S
A(1J.k.m) = A(-1j.k+3,m)+ A(i+2j.kt1,m+2)* A(ij-1,k+4m-1)
End Do
End Do
End Do
End Do
On supposera que chaque opération arithmétique coûte l unité de temps.
1. Donner le temps d'ex(cid:23)cution
séquentiel TI.
2. Etudier les dépendances entre les instances d'instructions de
a. Donner 'ensembles 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 (W-ijkm)
a. Déteminer 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 7p, 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
5. Dans chacun des cas suivant, choisir la (ou les) meilleure(s) transfommations qui extrait le
plus de parallélisme en indiquant le eritè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
anakespan Tp. l'accelération Sp et l'eficacité Ep.
a. Cas où ni= n2= n= n4
b. Cas oun=10, n>-20. n3=100 et n4=2
Bon Travail.