Dans le livre Systèmes informatiques: une perspective d'un programmeur em>, l'exercice 5.5 montre un morceau de code pour calculer la valeur d'un polynôme l'exercice suppose que Les cycles d'horloge nécessaires à l'addition et la multiplication de point flottant à double précision sont 3 et 5 respectivement. Le lecteur est invité à expliquer en fonction de la réponse de l'exercice, dans chaque itération, nous devons mettre à jour les variables xpwr code> et mais je pense que le flux de données devrait être quelque chose comme ceci: P> résultat code> et les opérations dont nous avons besoin est une addition à point flottant (pour résultat code>) et une multiplication de point flottant (pour xpwr code>), de sorte que ce dernier domine la latence, ce qui entraîne 5. p> xpwr result
| |
+-----+ +--[load] |
| | | |
[mul] [mul] |
| | |
| +---+ +-----+
| | |
| [add]
| |
| +------+
| |
xpwr result
4 Réponses :
Le chemin critique est le chemin le plus long à travers le graphique, dans ce cas, huit horloges. C'est ce que le Livre Dragon a à dire sur les chemins critiques (10.3. 3 commandes topologiques prioritaires):
Sans contraintes de ressources, l'horaire le plus court est donné par le Chemin critique, le chemin le plus long à travers le graphique de dépendance de données. UNE métrique utile en tant que fonction prioritaire est la hauteur du nœud, qui est la longueur d'un chemin le plus long dans le graphique provenant de la noeud.
Je pense que vous avez trouvé une erreur dans le livre. Vous devriez envisager de contacter les auteurs afin qu'ils puissent le corriger dans les futures impressions.
Le chemin critique est en effet 8 cycles, mais la question demande le CPE, qui ressemble à la durée moyenne de la moyenne pour générer un cycle de plus de la boucle.
Autre que le premier et dernier cycle, le processeur peut faire l'addition de l'itération précédente de la boucle et des multiplications actuelles en même temps, car les opérandes ne dépendent pas l'une de l'autre. La première itération de la boucle prend les 8 cycles complètes, mais toutes les itérations après, la boucle ne prend que 5 cycles à courir, rendant les cycles de CPE 5.
P.s. Je conviens que la manière du livre de la présentation du chemin critique est confuse. Leur définition du chemin critique n'est pas simplement le chemin qui prend le chemin le plus long, mais le chemin doit également avoir des opérations ayant des opérandes qui dépend des opérations précédentes et doivent donc être en ordre. Cette définition facilite la recherche du chemin critique plutôt non intuitif.
'xpwr = x * xpwr;' est la seule déclaration qui n'est pas entièrement indépendante entre les itérations, il est donc de sorte que la latence à 5 cycles est ce qui empêche un ordinateur de traiter plus rapidement. (Bien sûr, cela assume un soutien suffisant dans le matériel pour exploiter le parallélisme.) Un compilateur décent serait capable de mieux faire (au moins pour un degré supérieur) en reconnaissant que le calcul XPWR peut être parallélisé - par exemple, calculer x ^ 2 dans la première itération, x x ^ 2 et x ^ 2 * x ^ 2 (en parallèle) dans la seconde, x ^ 3 * x ^ 2 et x ^ 4 * x ^ 2 dans la troisième, etc. XPWR est partiellement un * nom dépendance. Le livre semble inexact.
Je sais que je suis un peu en retard à la fête, mais le livre est absolument juste. Comme vous pouvez vérifier pour vous-même en timing le code, CPE est en effet 5, la deuxième réponse est donc fausse.
Mais le premier est également faux. Il dit que les mulluls doivent être effectués en même temps, ce qui n'est pas du tout possible dans l'architecture Nehalem (et je soupçonne, la plupart des processeurs modernes). N'oubliez pas qu'il n'y a qu'une seule unité FP Mul et une autre unité d'ajout FP (comme indiqué dans le livre, ed. 2011 et ultérieure)
Que se passe-t-il à la place, c'est ceci:
(Les charges sont supposées toujours présentes, juste 1 cycle si dans le cache)
Nous nourrissons d'abord ... après 5 cycles, nous obtiendrons la nouvelle valeur de Bien sûr, c'est facile car nous n'avons besoin que de 3 cycles pour le FP Ajouter pour obtenir le nouveau Donc, il devient évident que le facteur de limitation est le calcul de xpwr * = x dans mul. Immédiatement après que nous nourris xpwr * a [i] (rappelez-vous le pipeline!)
xpwr , et après 6 cycles, nous aurons le résultat de xpwr * a [i] . À ce stade, un nouveau calcul de xpwr * = x sera à l'étape 1 du mul. Nous n'avons donc que 4 cycles de plus dans lesquels faire le reste des OP si nous ne voulons pas être restreints par eux.
résultat .
xpwr . Ce qui signifie que, dans la recherche du chemin critique (tout ce qui est), nous devons examiner spécifiquement le chemin des anciennes valeurs à la nouvelle. Dans ce cas, le trajet pour résultat est uniquement composé d'un FP Ajouter! (C'est ce qui m'a jeté au début)
C'est la bonne réponse. Par exemple, supposons que ceci: Ajout entier: 1 cycle latence, 1 cycle Double FP Addition: 3 cycles Latence, 1 cycle Double PF Multiplication: 5 cycles Latence, 1 cycle de latence Charge: 4 Cycles Latence, 1 cycle de cycle.
A1: Le chemin critique est le plus long dans le graphique de flux de données selon le livre, qui doit être sur une ligne droite et a un effet sur un registre unique, plutôt que d'ajouter 'mul' et d'ajouter ', dont les résultats ne sont que des opérandes intermédiaires pour les opérations suivantes.
À propos de cette question, vous allez tout faire si continue de lire le reste. Surtout, la comparaison du graphique de flux de données de Combina7 et de la combinaison des5 peuvent être utiles.
A2: Si A1 est compris, question2 est claire, la réponse dans le livre est raisonnable.
Il semble qu'un chemin consiste en seulement les bords reliant le même registre de la boucle. Avec cette définition, il y a deux chemins dans le flux de données, le chemin de
xprw qui n'a quemul et le chemin du coderésultat qui aAjouter . Donc, le chemin critique est celui dexprw .