Flashcards
4.2.5 Computersysteme II, Sprungvorhersage und spekulative Ausführung
Cards in this deck (96)
- 1Jeder wievielte Maschinenbefehl ist im Schnitt ein bedingter Sprungbefehl?im Schnitt etwa jeder fünfte bis siebte Befehl
- 2Warum wäre ohne Sprungvorhersage bei heutigen (2017) Prozessoren die Leistungseinbuße wesentlich höher als z.B. bei den ersten MIPS-Versionen?Weil heutige Prozessoren bis zu drei bis vier mal mehr Pipeline-Stufen haben
(Superpipelining) - 3Was ist das Ziel der Sprungvorhersagetechniken?Sprungrichtung und Sprungziel schon während der IF-Phase vorherzusagen und ohne Verzögerung ab der darauffolgenden IF-Phase spekulativ auszuführen
- 4Was ist der sogenannte Branch-Target-Buffer? (BTB oder auch Sprungzielpuffer)einem schneller Assoziativspeicher,
aus dem die neue Befehlszähleradresse als auch die Sprungrichtung für die Sprungvorhersage gewonnen werden - 5Wie wird der Branch-Target-Buffer noch genannt?Sprungzieladresscache, bzw.
Branch-Target-Adress-Cache
(BTAC) - 6Welche Informationen enthält ein Eintrag im Sprungzieladresscache?- die Befehlsadresse eines vergangenen Sprungbefehls
- die Zieladresse dieses Sprungs
- ggf. Vorhersagebits "taken" oder "not taken" - 7Wodurch werden die Vorhersagebits im BTB bei statischer und bei dynamischer Sprungvorhersage bestimmt?bei statischer Vorhersage werden diese vom Compiler fest vorgegeben, bei dynamischer Sprungvorhersage über eine Sprungverlaufstabelle ermittelt
- 8Was wird beim Sprungzieladresscache in der IF-Phase miteinander verglichen?Der Wert des Programmcounters (PC) mit den mit den Befehlsadressen der Sprungbefehle
im BTB - 9Was geschieht, wenn bei dem Vergleich des PC mit den Befehlsadressen im BTB ein passender Eintrag gefunden wird?Dann wird die zugehörige Zieladresse als neuer PC benutzt und der Befehl am Sprungziel als nächstes geholt
- 10Was geschieht, wenn bei dem Vergleich des PC mit den Befehlsadressen im BTB kein passender Eintrag gefunden wird?dann wird ein Eintrag erzeugt, sobald das Sprungziel berechnet ist,
und dafür eventuell ein anderer Eintrag überschrieben - 11Warum kann der Vergleich zwischen PC und Befehlsadressen im BTB simultan in einem Takt erfolgen?Weil dieser meist als vollassoziativer Cache-Speicher organisiert ist
- 12Welche Aufgabe haben die Vorhersagebits im BTB?Mit diesen wird bei einem bedingter Sprung eine Vorhersage getroffen, ob der nächste Sprung dieses Sprungbefehls genommen wird.
- 13Was passiert bei einem bedingten Sprung, welcher bereits im BTB vorliegt und als "genommen" markiert ist?dann wird die zugehörige Sprungzieladresse in den PC übertragen und der Befehl von dort geholt
- 14Was sollte geschehen, wenn durch den BTB eine falsche Vorhersage für einen bedingten Sprung eintritt?Dann sollte der Sprung-Zieladress-Cache die Vorhersagebits korrigieren, sobald die Sprungrichtung in der MEM-Stufe bekannt ist
- 15Wann spricht man von einer dynamischen Sprungvorhersagetechnik?Wenn die Hardware die vorhergesagte Sprungrichtung aufgrund der vergangenen Sprungverläufe während der Programmausführung modifiziert
- 16Was kann man tun um den BTB möglichst klein zu halten?die Implementierung so anpassen, dass von den bedingten Sprüngen nur diejenigen gespeichert werden, die als genommen vorhergesagt werden
- 17Was war / ist der sogenannte Branch Target Cache, BTC?Eine Variante des BTAC älterer Prozessoren, die pro Eintrag noch zusätzlich ein paar Befehle am Sprungziel abspeicherte
- 18Was kennzeichnet die statische Sprungvorhersage?eine Vorhersagetechnik, bei der die Hardware jeden bedingten Sprung nach einem festen Muster vorhersagt
und sich die Vorhersage für einen speziellen Sprungbefehl nie ändern kann - 19Welche "Muster" für eine statische Sprungvorhersage gibt es?- Predict always not taken
- Predict always taken
- Predict backward taken, forward not taken - 20Warum ist das Muster "predict always taken" für die statische Sprungvorhersage in der Regel besser als "predict always not taken"?Weil die meisten Programme auf Schleifen basieren und somit alle Rücksprünge bei Schleifen richtig vorhergesagt werden
- 21Welche Idee steckt hinter dem Muster "backward taken, forward not taken" für die statische Sprungvorhersage?Die Idee, dass die Rückwärtssprünge am Ende einer Schleife fast immer genommen und alle anderen vorzugsweise nicht genommen werden
- 22Inwiefern kann der Compiler auf die statische Sprungvorhersage Einfluss nehmen?Entweder direkt durch das Setzen eines Vorhersagebits im Befehl, sofern die ISA das anbietet,
oder durch Umkehren der direkt in der Hardware codierten Sprungvorhersage - 23Welche Techniken kann der Compiler anwenden, um die Genauigkeit der statischen Sprungvorhersage zu erhöhen?- Programmanalyse
- Compilerdirektiven (Programmierer)
- Profiling - 24Wo ist der Unterschied zwischen der Programmanalyse und dem "Profiling", was der Compiler zur statischen Sprungvorhersage durchführen kann?Die Programmanalyse gilt allgemein,
Profiling bezieht sich auf das einzelne Programm, damit kann das voraussichtliche Verhalten jedes Sprungs ermittelt werden - 25Nenne ein Beispiel für ein statisches Sprungvorhersagemuster auf Basis der Programmanalyse."backward taken, forward not taken"
basiert auf der Programmanalyse, dass Rückwärtssprünge bei Schleifen meist genommen werden - 26Welchen Vorteil bieten Compilerdirektiven für die statische Sprungvorhersage? Nenne ein Beispiel in C.Darüber kann der Programmierer sein Wissen über bestimmte Abläufe in die Sprungvorhersage einbringen
Beispiel:
likely (if x != 0).. - 27Welche Compilertechnik zur statischen Sprungvorhersage liefert in der Regel die besten Ergebnisse?Das Profiling
- 28Wie erreicht man für die Sprungvorhersage eine möglichst frühe Bestimmung der Sprungrichtung?durch die direkte Auswertung des Ergebnisses vom vorangegangenen Vergleichsbefehl (Forwarding)
, ohne das dieses Ergebnis zunächst im Registersatz abgelegt werden muss - 29Wie weit kann der Test der Sprungbedingung durch Forwarding vorgezogen werden?bis in die Dekodierstufe
- 30Wovon hängt die Gesamtleistung der Sprungvorhersage in der Regel ab?Von:
- der Genauigkeit der Sprungvorhersage
- den Kosten fürs Zurückrollen bei einer Fehlspekulation - 31Welche Sprungvorhersagetechniken (statisch/dynamisch) sind in der Regel genauer und haben sich deshalb auch weitestgehend in der Praxis durchgesetzt?die dynamischen Sprungvorhersagetechniken
- 32Warum führen die dynamischen Sprungverlaufstechniken in der Regel zu weniger Fehlspekulationen?Weil diese durch Sprungverlaufstabellen
eher die Historie der einzelnen Sprungbefehle bzw. die globale Sprunghistorie berücksichtigen können - 33Warum sind die Kosten für das Rückrollen bei Fehlspekulation in der Regel recht hoch? (15 Takte und mehr)Weil es zum Einen nicht immer möglich ist, Befehle aus internen Puffern zu löschen
und zum Anderen bei größeren Befehlsfenstern nicht alle Befehle auf einmal gelöscht werden können - 34Wo werden bei der dynamischen Sprungvorhersagetechnik die Sprungverläufe gesammelt?In sogenannten Sprungverlaufstabellen
- 35Welche zwei Möglichkeiten gibt es die Sprungverlaufstabellen und den BTB für die dynamische Sprungvorhersage zu implementieren?Entweder als voneinandee getrennte Hardware oder mit Integration der Sprungverlaufstabelle im BTB
- 36Warum bleiben Im Normalfall der Sprungzieladress-Cache und die Sprungverlaufstabelle getrennte Hardware-Einrichtungen?Weil diese unterschiedlich organisiert sind:
- Der BTB ist vollassoziativ
- eine Sprungverlaufstabelle wird nur über einen Teil der branch adress(BA) adressiert und kann mehrere Einträge pro Befehl enthalten (siehe Korrelationsprädiktoren) - 37Welche Bits der Befehlsadresse werden üblicherweise genutzt, um eine Sprungbefehlstabelle zu adressieren?In der Regel die niederwertigsten Bit der Befehlsadresse
- 38Welche Gründe für eine Fehlspekulation kann es bei dynamischer Sprungvorhersage geben?- "Warmlaufphase" bei Programmstart
- der Sprung nimmt eine "unvorhergesehene" Richtung
- Branch Interference, Aliasing in der Sprungverlaufstabelle - 39Nenne ein Beispiel für eine Fehlspekulation bei dynamischer Sprungvorhersage bei der der Sprung eine "unvorhergesehene" Richtung nimmt.Der letzte Schleifendurchlauf kommt in der Regel "unerwartet"
- 40Was versteht man unter der sogenannten "Branch Interference" im Zusammenhang mit dynamischer SprungvorhersageWenn zwei Sprungbefehle in dem zur Adressierung in der Sprungverlaufstabelle verwendeten Bits dasselbe Bitmuster aufweisen..
Dann werden diese auf den gleichen Eintrag abgebildet - 41Warum kann die Sprungverlaufstabelle nicht einfach so groß implementiert werden, dass jeder Sprungbefehl einen eigenen Eintrag in der Sprungverlaufstabelle erhält?Weil dies für beliebig große Programme wegen des beschränkten
Platzes auf dem Prozessor-Chip nicht möglich ist - 42Nenne drei dynamischen Sprungvorhersagetechniken, die in der Praxis angewandt werden.- Ein-Bit-Prädiktoren
- Zwei-Bit-Prädiktoren
- Korrelations-Prädiktoren - 43Was kennzeichnet einen "Ein-Bit-Prädiktor" als dynamische Sprungvorhersagetechnik?Dieser ist die einfachste dynamische Sprungvorhersagetechnik
der für jeden Sprungbefehl die zwei Zustände „genommen“ oder „nicht
genommen“ in einem Bit speichert - 44Wie wird die Sprungverlaufstabelle noch genannt? (engl., ggf. mit Abkürzung)Branch History Table (BHT)
oder auch
Branch Prediction Buffer - 45Was muss bei einem Ein-Bit-Prädiktor mit dem Vorhersagebit bei einer Fehlspekulation geschehen?Dieses muss invertiert werden
- 46Wie kann bei der Implementation eines Ein-Bit-Prädiktors auf eine Sprungverlaufstabelle verzichtet werden?Indem nur
die als „genommen“ vorhergesagten Sprünge in den Sprungzieladress-Cache
eingetragen werden und auf die Vorhersagebits verzichtet wird - 47Nenne ein Beispiel für einen Sprungverlauf eines Befehls, bei dem der Ein-Bit-Prädiktor komplett versagen würde. ("T" für Taken, "N" für Not taken)TNTNTNTNTNT
- 48Was kennzeichnet einen Zwei-Bit-Prädiktor zur dynamischen Sprungvorhersage?Bei diesem werden für die Zustandskodierungen der bedingten
Sprungbefehle zwei Bits pro Vorhersageeintrag in der Sprungverlaufstabelle verwendet - 49Nenne die vier Zustände des Zwei-Bit-Prädiktors zur dynamischen Sprungvorhersage- strongly taken
- weakly taken
- weakly not taken
- strongly not taken - 50Was ist der Vorteil des Zwei-Bit-Prädiktors zur dynamischen Sprungvorhersage?Befindet sich ein Sprungbefehl
in einem „sicheren“ Vorhersagezustand, so sind zwei aufeinander folgende
Fehlspekulationen nötig, um die Vorhersagerichtung umzudrehen - 51Welche zwei Ausprägungen des Zwei-Bit-Prädiktors gibt es?Sättigungszähler
Hysteresezähler - 52Was kennzeichnet den Zwei-Bit-Prädiktor mit Sättigungszähler?Dieser erhöht jedes Mal, wenn der
Sprung genommen wurde, den Zähler und erniedrigt ihn, falls er nicht genommenen
wurde - 53Welches Bit gibt beim Zwei-Bit-Prädiktor mit Sättigungszähler die Sprungrichtung an?Das höchstwertige Bit
- 54Was kennzeichnet den Zwei-Bit-Prädiktor mit Hysteresezähler?dass direkt von einem „unsicheren“ (weakly) Zustand
in den „sicheren“ (strongly) Zustand der entgegengesetzten Richtung gewechselt
wird - 55Bei welchen Programmen funktioniert ein Zwei-Bit-Prädiktor zur dynamischen Sprungvorhersage in der Regel sehr gut?bei numerischen
Programmen, die Schleifen mit vielen Iterationen enthalten - 56Bei welcher Art von Programmen steigt die Anzahl der Fehlspekulationen bei Verwendung eines Zwei-Bit-Prädiktors in der Regel stark an?Bei Programmen bei denen die Schleifen häufig nur wenige Iterationen aufweisen, dafür aber viele if-then- und if-then-else-Konstrukte vorkommen
- 57Welcher dynamische Prädiktor schneidet bei verschachtelten Schleifen in der Regel besser ab, der Ein- oder der Zwei-Bit-Prädiktor?Der Zwei-Bit-Prädiktor
- 58Warum wird der Ansatz des Zwei-Bit-Prädiktors nicht auf mehr Bits ausgeweitet?Weil sich gezeigt hat, dass sich damit kaum Verbesserungen erzielen lassen würden
- 59Welche zwei Möglchkeiten gibt es denn Zwei-Bit-Prädiktor bzgl. des BTAC zu implementieren?Entweder den mit einer extra Sprungverlaufstabelle
oder
integriert im BTAC - 60Welches Problem versucht man durch die sog. Korrelationsprädiktoren zu lösen?dass Sprungbefehle mit anderen Sprungbefehlen (global)
oder auch
mit sich selbst korrelieren können
(local) - 61Was ist die Kernidee der Korrelationsprädiktoren?dass man im Grunde für jeden Sprung mehrere Prädiktoren bereitstellt
Entweder die globale Sprunghistorie als Bitmuster oder für jeden Sprung einzeln (lokal) - 62Welche zwei Funktionseinheiten benötigt man mindestens, um Korrelationsprädiktoren implementieren zu können?mind. :
- ein Branch History Register (BHR)
und
- eine Sprungverlaufstabelle
(Pattern History Table, PHT) - 63Wie funktioniert ein globaler Korrelationsprädiktor grds.?Es gibt ein BHR, in dem der Sprungverlauf der letzten n Sprünge gespeichert ist. Dieses indexiert über das Bitmuster und die letzten 10 Bits einen Eintrag in der Sprungverlaufstabelle. Dort steht dann die Vorhersage zu diesem Bitmuster
- 64Warum nutzt man bei Korrelationpädiktoren nur die letzten 10 Bit der Branch Adress (BA) zum Indexieren der Sprungverlaufstabelle?Um die Sprungverlaufstabelle möglichst klein zu halten.
- 65Was kennzeichnet die Technik der Prädikation (predication)?diese benutzt so genannte prädikative Befehle um einem bedingten Sprungbefehl zu ersetzen und zunächst beide Programmpfade auszuführen und spätestens bei der Rückordnung die fälschlicherweise ausgeführten Befehle zu verwerfen
- 66Wann ist die Prädikationstechnik besonders effektiv?wenn der Sprungausgang völlig irregulär wechselt und damit nicht vorhersagbar ist
- 67Warum ist die Prädikationstechnik besonders effektiv bei völlig irregulär wechselnden und unvorhersehbaren Sprüngen?weil man sich die Kosten für das Rückrollen falsch vorhergesagter Sprungpfade spart, die meist höher sind als die unnötige Ausführung einer der beiden Programmpfade bei Anwendung der Prädikation.
- 68Welche Typen von Prozessoren verwenden häufig die Technik der Prädikation statt der Prädiktion?VLIW-Prozessoren
- 69Welche zwei Architekturerweiterungen sind notwendig, um Prädikation anbieten zu können?Es müssen ein oder mehrere 1-Bit breite Prädikatsregister vorhanden sein und möglichst alle Befehle des Befehlssatzes müssen diese Prädikatsregister im Befehlsformat ansprechen können
- 70Welche Funktion erfüllt das Prädikatsregister bei Verwendung der Technik der Prädikation? (einfachster Fall)dieses erlaubt es dem Compiler, die gültige Befehlsausführung von der Übereinstimmung des Prädikatsbits im Befehl mit dem Bit im Prädikationsregister abhängig zu machen
- 71Von welcher Befehlsart wird das Prädikatsregister bei Einsatz von Prädikation gesetzt?Von einem Vergleichsbefehl
- 72Wenn spricht man von einem "voll prädikativen Befehlssatz"?Wenn alle Befehle eines Befehlssatzes prädikativ sind
- 73Übersetze in Befehle mit Prädikation: if (x ==0) { a=b+c; d=e-f; } g = h • i(Pred = (x==0))
if Pred {a=b+c;}
if Pred {d=e-f;}
g=h*i; - 74Ergänze: Prädikation ermöglicht es bedingte Sprungbefehle ...?aus dem Maschinencode zu eliminieren
- 75Wann sollte Prädikation nicht eingesetzt werden? Warum?Bei sehr gut vorhersagbaren Sprüngen.
Dann führt die Prädikation ständig zu unnötigen Befehlsausführungen und belastet somit die Prozessorressourcen. - 76Welche Technik sollte eher angewandt werden, falls sehr lange Befehlsfolgen von einer Verzweigung abhängen, Prädiktion oder Prädikation?Prädiktion, weil bei Prädikation eventuell sehr viele Befehle prädikativ ausgeführt werden müssten
- 77Wie lange verbleibt ein prädikativer Befehl im Befehlsfenster? (das Prädikationsregister wird als zusätzliches Operandenregister des prädikativen Befehls betrachtet)bis alle Operanden (also auch der Wert des Prädikatsregisters) vorhanden sind.
- 78Wann kann ein prädikativer Befehl frühestens die Ausführungsstufe erreichen? ( wenn das Prädikationsregister als zusätzliches Operandenregister des prädikativen Befehls betrachtet wird)erst wenn die Prädikation entschieden ist,
also der vorangehende Vergleichsbefehl das Prädikatsregister gesetzt hat. - 79Nenne ein Beispiel für eine Architektur die den prädikativen Befehl spekulativ ausführt und das Resultat nur dann gültig macht, wenn das Prädikat zu true ausgewertet wurde.die Intel-IA-64-Architektur
- 80Bei welcher Art von Prozessoren wird die Technik der Prädikation heute (2017) vorwiegend (nur noch) eingesetzt?bei den Digitalen Signalprozessoren und bei leistungsstarken Mikroprozessoren und Mikrocontrollern, die im Bereich der eingebetteten Systeme eingesetzt werden
- 81Nenne zwei Architekturen, die einen voll prädikativen Befehlssatz verwenden.Der Befehlssatz der ARM-Prozessoren ab den 32-Bit-Versionen.
Der IA-64-Befehlssatz
( wobei der Itanium-Prozessor auch Sprungspekulation implementiert) - 82Was ist die sogenannte Grundblocklänge?die Anzahl der Befehle zwischen zwei Sprungbefehlen
- 83Inwiefern beeinflusst Prädikation die Grundblocklänge? Welchen Vorteil hat das?Durch Prädikation wird die Grundblocklänge vergrößert.
Dadurch hat der Compiler mehr Spielraum bei der Optimierung. - 84Was kennzeichnet die Technik der Mehrpfadausführung?Bei dieser werden nach einem bedingten Sprung beide möglichen Ausführungspfade in die Pipeline geladen und ausgeführt
- 85Nenne mindestens einen Unterschied zwischen der Technik der Prädikation und der sog. Mehrpfadausführung.Die Prädikation ersetzt bedingte Sprungbefehle durch prädikative Befehle und benötigt Anpassungen der ISA,
die Mehrpfadausführung nicht - 86Nenne zwei Synonyme für die Mehrpfadausführung. (engl.)Multipath
oder
Eager Execution - 87Wie wird bei der Eager Execution mit Datenabhängigkeiten zwischen den beiden gleichzeitig ausgeführten Befehlspfaden umgegangen?Diese werden durch Techniken der Register-umbenennung
oder -umordnung gelöst - 88Was geschieht bei der Mehrpfadausführung mit dem Befehlspfad der nicht genommen wurde, sobald die Sprungrichtung entschieden ist?Dann werden alle Befehlsresultate und auch noch in der Pipeline befindliche Befehle dieses Pfades wieder gelöscht
- 89Welche Vorteile bietet die Mehrpfadausführung?Diese vermeidet Fehlspekulationen und erhöht die Ausführungsgeschwindigkeit,
Ausserdem kann Sie ohne Einfluss auf die Architektur implementiert werden kann - 90Warum erhöht Mehrpfadausführung grds. die Ausführungsgeschwindigkeit?Weil diese Fehlspekulationen vermeidet und somit der Fehlspekulationsaufwand entfällt
- 91Was ist der Hauptnachteil der Mehrpfadausführung?der dafür nötige Ressourcenverbrauch
- 92Warum muss in der Realtität sehr sorgfältig ausgewählt werden, wann die Mehrpfadausführung genutzt wird und wann nicht?Weil in der Realität die Prozessorressourcen begrenzt sind und dementsprechend nicht bei allen Sprungbefehlen die Mehrpfadausführung genutzt werden kann
- 93Nenne eine Möglichkeit für einen Entscheidungsmechanismus, um zu entscheiden, ob Mehrpfadausführung oder Sprungspekulation angewandt werden soll.die Anwendung einer Zuverlässigkeitsschätzung der Sprungvorhersage
- 94Wie kann man die Verluste in Sachen von Befehlsebenenparallelität eines Prozessors visualisieren?Zum Beispiel durch ein Diagramm mit Befehlsfächern welches vertikal die Prozessorzyklen (Zeitachse) und horizontal die Fächer in der Pipeline (Raumachse) darstellt.
- 95Wann spricht man von horizontalen Verlusten im Zusammenhang mit Befehlsebenenparallelität (Hinweis Visualisierung durch Befehlsfächer)Bei "räumlich verteilten" Verlusten
(horizontale Achse im Befehlsfächerdiagramm) - 96Wann spricht man im Zusammenhang mit Befehlsebenenparallelität von vertikalen Verlusten? (Hinweis Visualisierung durch Befehlsfächer)bei zeitlich verteilten Verlusten
(vertikale Achse im Befehlsfächerdiagramm)
Information
- Description
- Informatik (Computersysteme II) Flashcards on 4.2.5 Computersysteme II, Sprungvorhersage und spekulative Ausführung, created by David Bratschke on 07/03/2018.
- Created by
- David Bratschke
- Views
- 21
- Rating