Skip to topic | Skip to bottom
Home
Minfo
Minfo.ParallTD1r1.8 - 07 Sep 2010 - 19:00 - FabriceHuettopic end

Start of topic | Skip to actions

Première Séance de TD

Exercice 1 (Jouons avec la loi de Moore)

Un effet de la loi de Moore est qu'il vaut mieux parfois attendre la nouvelle génération de processeurs avant de lancer un calcul. Au final le temps total (attente+exécution) sera réduit. Quelle est la durée d'attente minimum pour avoir un tel résultat?

Exercice 2 (sur le pipeline)

Revenons sur la manière dont fonctionne un processeur pipeliné (notamment les processeurs vectoriels qui reposent principalement sur ce principe)

Soit un pipeline pour calculer une fonction f, décomposable en fn o ... f2 o f1. Les données produites par l'étage 1 sont passées à l'étage 2, etc, et le résultat de f sur la donnée initiale d est obtenu en sortie de l'étage n. Supposons que le temps complet pour calculer f(d) soit T.

Si le circuit pour calculer f n'était pas pipeliné, celui-ci ne pourrait s'occuper que d'une donnée d à la fois.

  • Combien de temps au total faudrait-il pour traiter en tout k données (ces k données étant typiquement les éléments d'un vecteur) ?

Nous cherchons à évaluer le gain en temps si ce circuit est un pipeline de n étages.

  • Y'a-t-il un gain quelconque si on n'a qu' une seule donnée à traiter ?

Supposons que le temps de traitement dans chaque étage quelconque du pipeline soit Ti, bien sûr Ti <= T, plus précisément le cas idéal où T_i = T / n

  • Combien de temps faut-il attendre pour obtenir le résultat sur la première donnée d1 ? (ce qui correspondra à ce que l'on appelle temps de réponse ou latence du pipeline)
  • Combien de temps faut-il attendre pour le résultat sur la donnée dk ? (ce qui nous donne le temps total de traitement pipeliné pour le vecteur de taille k)
  • Exprimer le facteur d'accélération obtenu
  • Discuter ensuite ce facteur avec différentes hypothèses sur le nombre de données, cad k=1 d'une part, et à l'extrème, un k très grand
  • En conclure sur le parallélisme maximal que l'on peut obtenir en utilisant un pipeline ayant n étages

Exercice 3 (Structural Hazard et Data Hazard)

On considère un pipeline à 4 étages (Fetch, Decode, Execute, Write) sur une machine ayant une unique unité de calcul sur entier (ALU), utilisée lors du Decode et de l'_Execute_ de certaines instructions. Soit une instruction assembleur

ADD src dest

qui fait la somme des valeurs contenues dans les registres src et dest et les place dans dest.

  • Donnez un exemple de programme (3 instructions) provoquant un structural hazard
  • Lorsqu qu'un structural hazard est détecté le pipeline doit bloquer certaines instructions. Lesquelles et pour quelle durée?
  • Donnez un exemple de programme (3 instructions) provoquant un data hazard.
  • Une solution simple au data hazard consiste à bloquer les instructions dans le pipeline. Proposez une solution alternative.

Exercice 4 (Control Hazard)

  • Quel est le coût d'une erreur de prédiction de branchement ?
  • Un programme est composé de 20000 instructions dont 10% sont des sauts. On dispose d’un processeur qui a un taux de succès de 90% aux prédictions de branchement. Calculez le nombre de cycles nécessaires à l’exécution de ce programme sur un processeur dont le pipeline a 5 étages.
  • Même question si le pipeline a 20 étages
  • Commentez l'efficacité de ces processeurs en fonction du taux de succés de la prédiction de branchement

Exercice 5 (on revient sur les notions SIMD, MIMD)

  • Soit trois processus indépendants exécutant un même programme sur 3 processeurs différents. Dites si le temps de calcul sera typiquement plus court sur une architecture SIMD ou sur une architecture MIMD? Justifiez.
  • Soit les trois architectures parallèles suivantes: A- MIMD avec mémoire locale ou privée, B- MIMD avec mémoire globale ou partagée, C- SIMD. Dites quelle architecture (A, B, C) correspond le mieux à chaque description ci-apres :
1)Communication par passage de messages. 2)Synchronisation barrière. 3)Couplage lâche. 4)Chaque processeur emmagasine son propre programme et partage les données avec les autres. 5)Parallélisme réalisé au niveau des instructions. 6) Un seul programme s'execute a chaque moment mais sur plusieurs processeurs en meme temps dont chacun traite des donnees differentes. 7) systeme reparti. 8) systeme asynchrone. 9) synchronisation automatique pour les communications entre processeurs. 10) parallelisme realise au niveau des instructions.

Exercice 6 (on compare --un peu-- les architectures des supercalculateurs)

On va se concentrer sur quelques uns des plus performants du moment http://www.top500.org/lists/2010/06. Pour la semaine prochaine, il vous est demande de rendre, par binome, un petit document (maxi 2 feuilles recto/verso) qui prend 2 des 5 supercalculateurs proposés ici, et les compare sommairement. Ce travail sera releve en debut de la seance.

Pour chacun d'eux proposes ci apres, etudier (rapidement) les documents afin de donner leur classification dans les topologies vues en cours, topologies que l'on peut retrouver ici


to top

You are here: Minfo > ParallRepa > ParallTD1

to top

Copyright © 1999-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding WIKIDeptinfo? Send feedback