TD — Séance 1 — Fondements de l’architecture parallèle

TD de la séance 1 d’Architecture et Programmation Parallèles : fondements de l’architecture parallèle.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer chaque notion du cours sur des données nouvelles : gain théorique et classification de Flynn, temps d’accès mémoire en cycles, parcours d’un tableau en cache, lecture de mesures (accélération, efficacité, fraction séquentielle), loi d’Amdahl, loi de Gustafson, choix d’une granularité. Durée : une séance de TD.

NoteConventions

\(n\) désigne le nombre de processeurs, \(S(n)=T(1)/T(n)\) l’accélération, \(E(n)=S(n)/n\) l’efficacité, \(f\) la fraction séquentielle (Amdahl) et \(s\) la fraction du temps passée en séquentiel sur \(n\) processeurs (Gustafson). Les tâches sont réparties de façon équilibrée (chaque tâche va au processeur libre le plus tôt). Les résultats se donnent avec deux décimales ; chaque réponse se justifie par le calcul ou la règle appliquée.

Exercice 1 : gain théorique et classification de Flynn

  1. Un Pentium 4 de 2004 fonctionne à \(3{,}8\) GHz. Un processeur actuel de serveur a \(12\) cœurs à \(2{,}8\) GHz. Calculer le gain théorique maximal, puis le rapport des vitesses pour un programme séquentiel. Quelle hypothèse faut-il faire ?

  2. Classer selon Flynn (SISD, SIMD, MISD, MIMD) et justifier en une phrase :

    1. un Raspberry Pi 4 (quatre cœurs) exécute quatre programmes différents ;
    2. une instruction NEON additionne quatre paires de nombres réels ;
    3. le microcontrôleur ESP32-C3 (un seul cœur, sans instructions vectorielles) d’une station météorologique de l’ANACIM relève la température toutes les minutes ;
    4. trois unités appliquent chacune un traitement différent (moyenne glissante, détection de pics, seuil d’alarme) à la même mesure d’un capteur de vibrations d’un pont ;
    5. seize serveurs d’une grappe résolvent ensemble un même système d’équations, chacun sur sa partie des données.

Exercice 2 : temps d’accès en cycles

Un processeur à \(2{,}5\) GHz a un cache L1 accessible en \(1{,}2\) ns, un L2 en \(4\) ns, un L3 en \(16\) ns et une mémoire principale en \(80\) ns.

  1. Durée d’un cycle.

  2. Compléter le tableau.

    niveau temps d’accès calcul cycles
    L1 \(1{,}2\) ns
    L2 \(4\) ns
    L3 \(16\) ns
    mémoire \(80\) ns

  3. Combien de fois un accès mémoire est-il plus lent qu’un accès L1 ?

  4. Pourquoi ces écarts justifient-ils une hiérarchie de caches plutôt qu’un seul grand cache ?

Exercice 3 : parcours d’un tableau

Un programme lit dans l’ordre un tableau de \(300\) nombres réels de \(8\) octets (double). Une ligne de cache fait \(64\) octets ; un succès coûte \(2\) ns et un défaut \(120\) ns. Le tableau commence au début d’une ligne et n’est pas en cache au départ.

  1. Combien de nombres tiennent dans une ligne ? Combien de lignes le tableau occupe-t-il ? Combien de nombres utiles contient la dernière ligne ?

  2. Compléter le tableau et calculer le temps total.

    nombre coût unitaire temps
    défauts
    succès
    total \(300\)

  3. Temps sans cache (chaque lecture va en mémoire) ; rapport entre les deux temps ; taux de défauts.

  4. Le programme ne lit plus qu’un nombre sur huit (t[0], t[8], t[16], …). Combien de lectures, combien de défauts, quel temps total ? Quel temps moyen par lecture, comparé à celui de la question (b) ? Quel principe de localité n’est plus exploité ?

Exercice 4 : lecture d’une mesure

Le calcul des moyennes de pluviométrie de toutes les stations du pays dure \(150\) s en séquentiel et \(37{,}5\) s sur \(6\) processeurs.

  1. Calculer l’accélération et l’efficacité.
  2. En supposant la loi d’Amdahl, retrouver la fraction séquentielle \(f\) (calcul en fractions).
  3. Quelle accélération maximale ce programme peut-il atteindre ?
  4. Le service veut une efficacité d’au moins \(0{,}5\). Jusqu’à combien de processeurs peut-il aller ?

Exercice 5 : la loi d’Amdahl

Un programme de traitement d’images satellites a une partie séquentielle de \(8\,\%\).

  1. Compléter le tableau.

    \(n\) calcul de \(S(n)\) \(S(n)\) \(E(n)\)
    \(2\)
    \(4\)
    \(8\)
    \(16\)
    \(64\)

  2. Accélération maximale.

  3. Nombre de processeurs pour atteindre \(80\,\%\) de cette accélération maximale.

  4. De \(8\) à \(16\) processeurs, puis de \(16\) à \(64\), de combien l’accélération augmente-t-elle (en pourcentage) ? Commenter l’efficacité à \(64\) processeurs.

Exercice 6 : Amdahl et Gustafson

Un modèle de prévision météorologique passe \(5\,\%\) de son temps en séquentiel. Il tourne sur \(32\) processeurs.

  1. Accélération selon Amdahl (on prend \(f=0{,}05\)).
  2. Accélération selon Gustafson (on prend \(s=0{,}05\)).
  3. Les prévisionnistes gardent le même temps de calcul (une heure) mais affinent la grille du modèle quand ils ont plus de processeurs. Laquelle des deux lois décrit leur situation ? Que signifie alors le résultat de (b) ?

Exercice 7 : choix d’une granularité

Un traitement se découpe de deux façons :

  • option A : \(2000\) tâches de \(0{,}5\) ms, surcoût de \(0{,}05\) ms par tâche ;
  • option B : \(12\) tâches de \(80\) ms, surcoût de \(2\) ms par tâche.
  1. Granularité de chaque option. Travail total (calcul et surcoût) de chaque option.
  2. Temps d’exécution de chaque option sur \(6\) processeurs. Laquelle est la meilleure ?
  3. Même question sur \(50\) processeurs.
  4. Expliquer pourquoi le classement s’inverse. Que faudrait-il pour que l’option B profite de \(50\) processeurs ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet