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(cid:23)les de Machine Leaming sur un flot de données D.
-
P est constitué des l3 étapes Ei (i=0..12) suivantes
E0: 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 D1, D2 des données d'apprentissage D4.
E3: Créer les 4 modèles MI, M2, M3 et M4.
E4, ES, E6, E7: Entrainer les mod(cid:23)les M1, M2, M3, M4 par les données d'apprentissage D4 pour obtenir respectivement MTI, MT2, MT3, MT4.
Publicité
E8. E9, E1O. El1 : Prédire les modéles MT 1, MT2, MT3, MT4 par rapport aux données de test D3. pour obter 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
EO El, E2 E3 EA, ES E6, E7 E8, E9 E10. El TEL2 1. Calculer le temps / 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.
roposer un ordonnancement paralletle optimat; Makespan= Topt, en utiisant un nombre
optimal de processeurs Popt que l'on déterminera Calculer l'efficacité Eopt.
Publicité
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(cid:23)lèration l'efficacite.
et
Problème 2: (10 points) Soit le nid de boucles suivant
Do i- 1, n Do j=1,
Do k-l, n3
Do m=l, n4
S
Aij.k.m) = A(i-1 jik+3,m) + A(i+2jk+l.m+2) A(ij-I.k+4,m-1)
End Do
End Do
Publicité
End Do
End Do
On supposera que chaque opération arithmétique coûte I 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 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 (7-ijkm)
a. Déterminer la nature des boucles (séquentielles ou parallèles). b. Si une certaine parall(cid:23)lisation
est possible, indiquer le nombre p de processeurs
Publicité
nécessaires. le makespan 7p. l'accélération Sp et l'eficacité Ep. 4. Donner les permutations valides (avec inversion si n(cid:23)cessaire) qui permettent d'améliorer le
parallélisme de
5. Dans chacun des cas suivant, choisir la (ou les) meilleure(s) transfomations 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'eflicacité Ep.
a. Cas où ni= n>s ns n4
b. Cas où ni=10, n:=20. n3=100 et na=2
Bon Travail.