Zweigprädiktor

Nicht zu verwechseln mit Branchenprädikation.

Im Rechnerarchitektur, a Zweigprädiktor[1][2][3][4][5] ist ein Digitaler Schaltung Das versucht zu erraten, in welchem ​​Weg a Zweig (z. B. an Wenn - dann Struktur) wird gehen, bevor dies definitiv bekannt ist. Der Zweck des Zweigprädiktors besteht darin, den Fluss in der zu verbessern Anweisung Pipeline. Zweigprädiktoren spielen eine entscheidende Rolle bei der hohen Erreichung Leistung in vielen modernen Pipeline Mikroprozessor Architekturen wie x86.

Beispiel einer 4-stufigen Pipeline. Die farbigen Kisten repräsentieren Anweisungen unabhängig voneinander.

Zwei-Wege-Verzweigungen werden normalerweise mit a implementiert bedingter Sprung Anweisung. Ein bedingter Sprung kann entweder "nicht genommen" werden und die Ausführung mit dem ersten Codezweig fortsetzen, der unmittelbar nach dem bedingten Sprung folgt, oder er kann "genommen" und an einen anderen Ort im Programmspeicher springen, an dem der zweite Zweig des Codes ist gelagert. Es ist nicht sicher bekannt, ob ein bedingter Sprung angenommen oder nicht genommen wird, bis die Bedingung berechnet wurde und der bedingte Sprung die Ausführungsstufe in der Befehlspipeline überschritten hat (siehe Abb. 1).

Ohne Branchvorhersage müsste der Prozessor warten, bis die bedingte Sprunganweisung die Ausführungsstufe überschritten hat, bevor die nächste Anweisung in die Pipeline in die Fetch -Stufe eingeben kann. Der Zweig -Prädiktor versucht, diese Zeitverschwendung zu vermeiden, indem versucht wird, zu erraten, ob der bedingte Sprung am wahrscheinlichsten genommen wird oder nicht. Der Zweig, der als am wahrscheinlichsten angesehen wird, wird dann abgerufen und spekulativ ausgeführt. Wenn später festgestellt wird, dass die Vermutung falsch war, werden die spekulativ ausgeführten oder teilweise ausgeführten Anweisungen verworfen und die Pipeline beginnt mit dem richtigen Zweig, was eine Verzögerung entspricht.

Die Zeit, die im Fall von a verschwendet wird Zweig -Fehlverguss entspricht der Anzahl der Stufen in der Pipeline von der Fetch -Stufe zur Ausführungsstufe. Moderne Mikroprozessoren haben in der Regel ziemlich lange Pipelines Taktzyklen. Infolgedessen erhöht eine längere Pipeline die Notwendigkeit eines fortschrittlicheren Branch -Prädiktors.[6]

Wenn zum ersten Mal eine bedingte Sprunganweisung auftritt, gibt es nicht viele Informationen, auf die eine Vorhersage stützt. Der Zweigprädiktor hält jedoch Aufzeichnungen darüber, ob Zweige genommen werden oder nicht. Wenn es auf einen bedingten Sprung trifft, der mehrmals gesehen wurde, kann es die Vorhersage auf die Geschichte stützen. Der Zweig -Prädiktor kann beispielsweise erkennen, dass der bedingte Sprung häufiger als nicht jedes zweite Mal eingenommen wird.

Die Vorhersage der Zweig ist nicht dasselbe wie Zweigzielvorhersage. Die Vorhersage der Zweigversuche versucht zu erraten, ob ein bedingter Sprung unternommen wird oder nicht. Die Vorhersage von Zweigzielen versucht, das Ziel eines bedingten oder bedingungslosen Sprungs zu erraten, bevor er durch Decodieren und Ausführen der Anweisung selbst berechnet wird. Die Vorhersage der Verzweigungen und die Vorhersage der Zweigziel werden häufig zu derselben Schaltung kombiniert.

Implementierung

Statische Zweigvorhersage

Die statische Vorhersage ist die einfachste Zweige -Vorhersage -Technik, da sie sich nicht auf Informationen über die dynamische Geschichte des Codeausführens beruht. Stattdessen prognostiziert es das Ergebnis eines Zweigs, der ausschließlich auf dem Zweiganweis basiert.[7]

Die frühen Implementierungen von Sparc und MIPS (Zwei der ersten Werbespots RISC Architekturen) verwendeten eine statische Zweig-Vorhersage von Einzelanleitung: Sie sagen immer voraus, dass ein bedingter Sprung nicht durchgeführt wird, sodass sie immer die nächste sequentielle Anweisung abrufen. Nur wenn der Zweig oder der Sprung bewertet und als genommen festgestellt wird, wird der Befehlszeiger auf eine nicht-sequentielle Adresse eingestellt.

Beide CPUs bewerten Zweige in der Decodes -Phase und haben einen einzelnen Zyklusanweisungen. Infolgedessen ist das Wiederauftreten des Zweigziels zwei Zyklen lang, und die Maschine holt die Anweisung immer unmittelbar nach einem genommenen Zweig ab. Beide Architekturen definieren Zweigverzögerungsschlitze Um diese abgerufenen Anweisungen zu nutzen.

Eine fortgeschrittenere Form der statischen Vorhersage setzt voraus, dass rückständige Zweige genommen werden und dass Vorwärtsäste dies nicht tun. Eine Rückwärtszweig ist eine, die eine Zieladresse hat, die niedriger ist als seine eigene Adresse. Diese Technik kann bei der Vorhersagegenauigkeit von Schleifen helfen, die normalerweise nach hinten zeigende Zweige sind und häufiger eingenommen werden.

Einige Prozessoren ermöglichen die Einfügung von Zweigvorhersagen in den Code, um festzustellen, ob die statische Vorhersage aufgenommen werden sollte oder nicht. Der Intel Pentium 4 Akzeptiert Zweigvorhersage Hinweise, aber dieses Merkmal wurde in späteren Intel -Prozessoren aufgegeben.[8]

Die statische Vorhersage wird bei einigen Prozessoren mit dynamischer Verzweigungsvorhersage als Fall-Back-Technik verwendet, wenn dynamische Prädiktoren nicht über ausreichende Informationen verfügen. Sowohl die Motorola MPC7450 (G4E) und der Intel Pentium 4 Verwenden Sie diese Technik als Fall-Back.[9]

In der statischen Vorhersage werden alle Entscheidungen vor der Ausführung des Programms zum Kompilierenzeitpunkt getroffen.[10]

Dynamische Zweigvorhersage

Dynamische Zweigvorhersage[2] Verwendet Informationen über Taken oder nicht genommene Zweige, die zur Laufzeit gesammelt wurden, um das Ergebnis eines Zweigs vorherzusagen.[1]

Zufällige Zweigvorhersage

Die Verwendung eines zufälligen oder Pseudorandombits (eine reine Vermutung) würde jedem Zweig eine korrekte Vorhersagerate von 50% garantieren, die durch Neubeständigkeit nicht verbessert (oder verschlechtert) werden kann. (Mit der einfachsten statischen Vorhersage von "Annahme nehmen", Compiler Kann Anweisungen neu ordnen, um besser als 50% korrekte Vorhersage zu erhalten.) Außerdem würde es das Timing [viel] nicht deterministisch machen.

Nächste Zeilenvorhersage

Etwas Superscalar -Prozessoren (MIPS R8000, Alpha 21264, und Alpha 21464 (EV8)) Abrufen Sie jede Anweisungslinie mit einem Zeiger auf die nächste Zeile. Dieser nächste Prädiktorgriff Zweigzielvorhersage sowie Ast -Richtungs -Vorhersage.

Wenn ein Next-Line-Prädiktor auf ausgerichtete Gruppen von 2, 4 oder 8 Anweisungen zeigt, ist das Zweigziel normalerweise nicht die erste Anweisung, und so werden die abgerufenen anfänglichen Anweisungen verschwendet. Unter der Annahme, dass ein Einfachheit halber eine einheitliche Verteilung der Zweigziele, werden 0,5, 1,5 und 3,5 abgerufene Anweisungen verworfen.

Da der Zweig selbst im Allgemeinen nicht die letzte Anweisung in einer ausgerichteten Gruppe ist, Anweisungen nach dem Einnahmezweig (oder dessen Verspätungsschlitz) wird verworfen. Wieder einmal werden 0,5, 1,5 und 3,5 Anweisungen abgerufen.

Die weggeworfenen Anweisungen an den Zweig- und Zielleitungen summieren sich zu einem nahezu vollständigen Abrufzyklus, selbst für einen Einzelzyklus-Next-Line-Prädiktor.

Ein-Level-Zweigvorhersage

Sättigungsschalter

Ein 1-Bit-Sättigungsschalter (im Wesentlichen a Flip Flops) zeichnet das letzte Ergebnis des Zweigs auf. Dies ist die einfachste Version des dynamischen Zweig -Prädiktors möglich, obwohl er nicht sehr genau ist.

Ein 2-Bit Sättigungsschalter[11] ist ein Zustandsmaschine mit vier Staaten:

Abbildung 2: Zustandsdiagramm des 2-Bit-Sättigungszählers
  • Stark nicht genommen
  • Schwach nicht genommen
  • Schwach genommen
  • Stark genommen

Wenn ein Zweig bewertet wird, wird die entsprechende Statusmaschine aktualisiert. Zweige, die als nicht genommen bewertet wurden, verändern den Staat in Richtung starker Nichtnutzung, und Zweige, die als genommen bewertet wurden, verändern den Staat in Richtung starker Einnahme. Der Vorteil des Zwei-Bit-Zählerschemas gegenüber einem Ein-Bit-Schema besteht darin, dass ein bedingter Sprung zweimal von dem abweichen muss, was es in der Vergangenheit am meisten getan hat, bevor sich die Vorhersage ändert. Zum Beispiel wird ein bedingter Sprung in der Schlaufeschleife eher einmal als zweimal falsch geprägt.

Das ursprüngliche, nicht-mmx Intel Pentium Der Prozessor verwendet einen Sättigungszähler, jedoch mit einer unvollkommenen Implementierung.[8]

Auf der Spezifikation'89 Benchmarks, sehr große bimodale Prädiktoren mit 93,5% korrekt, sobald jeder Zweig auf einen einzigartigen Zähler kartiert.[12]: 3

Die Predictor -Tabelle wird mit der Anweisung indiziert die Anschrift Bits, so dass der Prozessor eine Vorhersage für jede Anweisung holen kann, bevor der Anweisungen dekodiert wird.

Zwei-Ebenen-Prädiktor

Der zweistufige Zweig-Prädiktor, der auch als Korrelationsbasis-Zweigprädiktor bezeichnet wird, verwendet eine zweidimensionale Tabelle von Zählern, auch als "Musterverlauf Tabelle" bezeichnet. Die Tabelleneinträge sind zwei-Bit-Zähler.

Zweistufiger adaptiver Prädiktor

Abbildung 3: Zweistufiger adaptiver Zweig-Prädiktor. Jeder Eintrag in der Musterverlaufstabelle stellt einen 2-Bit-Sättigungszähler des in Abbildung 2 gezeigten Typs dar.[13]

Wenn ein wenn Die Erklärung wird dreimal ausgeführt, die Entscheidung, die über die dritte Ausführung getroffen wurde, könnte davon abhängen, ob die beiden vorherigen getroffen wurden oder nicht. In solchen Szenarien funktioniert ein zweistufiger adaptiver Prädiktor effizienter als ein Sättigungszähler. Bedingte Sprünge, die jedes zweite Mal unternommen werden oder ein anderes regelmäßig wiederkehrendes Muster haben, werden durch den Sättigungsschalter nicht gut vorhergesagt. Ein zweistufiger adaptiver Prädiktor erinnert sich an die Geschichte der letzten N-Vorkommen des Asts und verwendet einen Sättigungszähler für jedes der möglichen 2n Geschichtsmuster. Diese Methode ist in Abbildung 3 dargestellt.

Betrachten Sie das Beispiel von n = 2. Dies bedeutet, dass die letzten beiden Ereignisse des Zweigs in einem Zwei-Bit gespeichert sind Schieberegister. Dieses Branch -History -Register kann vier verschiedene verschiedene haben binär Werte 00, 01, 10 und 11, wobei Null "nicht genommen" und eine "genommen" bedeutet. Eine Muster -Verlaufstabelle enthält vier Einträge pro Zweig, eines für jedes der 22= 4 mögliche Verzweigungsverläufe und jeder Eintrag in der Tabelle enthält einen Zwei-Bit-Sättigungsschalter desselben Typs wie in Abbildung 2 für jeden Zweig. Das Branch -History -Register wird verwendet, um auszuwählen, welche der vier Sättigungszähler verwendet werden sollen. Wenn die Geschichte 00 ist, wird der erste Zähler verwendet; Wenn die Geschichte 11 ist, wird der letzte der vier Zähler verwendet.

Nehmen wir zum Beispiel an, dass jedes dritte Mal ein bedingter Sprung unternommen wird. Die Zweigsequenz ist 001001001 ... in diesem Fall wird die Eintragsnummer 00 in der Musterverlaufstabelle an "stark genommen" angezeigt, was darauf hinweist, dass nach zwei Nullen eins kommt. Die Eintrittsnummer 01 geht an den Zustand "stark nicht genommen", was nach 01 auf Null kommt. Gleiches gilt für die Eingangsnummer 10, während die Eintragsnummer 11 nie verwendet wird, da es nie zwei aufeinanderfolgende gibt.

Die allgemeine Regel für einen zweistufigen adaptiven Prädiktor mit einer N-Bit Teilsequenzen sind anders.[8]

Der Vorteil des zweistufigen adaptiven Prädiktors besteht darin, dass er schnell lernen kann, ein willkürliches sich wiederholendes Muster vorherzusagen. Diese Methode wurde von T.-Y. Yeh und Yale Patt Bei der Universität von Michigan.[14] Seit der ersten Veröffentlichung im Jahr 1991 ist diese Methode sehr beliebt geworden. Varianten dieser Vorhersagemethode werden in den meisten modernen Mikroprozessoren verwendet.

Zweistufiger neuronaler Prädiktor

Ein zweistufiger Zweig-Prädiktor, bei dem die zweite Ebene durch a ersetzt wird neurales Netzwerk wurde vorgeschlagen.[15]

Lokale Branchenvorhersage

Ein lokaler Zweigprädiktor verfügt über einen separaten Verlaufspuffer für jeden bedingten Sprunganweis. Es kann einen zweistufigen adaptiven Prädiktor verwenden. Der Verlaufspuffer ist für jeden bedingten Sprunganweisung getrennt, während die Musterverlaufs -Tabelle auch getrennt sein kann oder zwischen allen bedingten Sprüngen geteilt werden kann.

Das Intel Pentium mmx, Pentium II, und Pentium III Haben Sie lokale Zweigprädiktoren mit einer lokalen 4-Bit-Geschichte und einer lokalen Musterverlauf Tabelle mit 16 Einträgen für jeden bedingten Sprung.

Auf der Spezifikation'89 Benchmarks, sehr große lokale Prädiktoren mit 97,1% korrekt.[12]: 6

Globale Branchenvorhersage

Ein globaler Branch -Prädiktor führt für jeden bedingten Sprung keinen separaten Verlauf. Stattdessen hält es eine gemeinsame Geschichte aller bedingten Sprünge. Der Vorteil einer gemeinsamen Geschichte ist, dass alle alle Korrelation Zwischen verschiedenen bedingten Sprüngen ist Teil der Vorhersagen. Der Nachteil ist, dass die Geschichte durch irrelevante Informationen verdünnt wird, wenn die verschiedenen bedingten Sprünge nicht korreliert sind und der Verlaufspuffer möglicherweise keine Teile aus demselben Zweig enthalten, wenn sich viele andere Zweige dazwischen befinden. Es kann einen zweistufigen adaptiven Prädiktor verwenden.

Dieses Schema ist besser als das Sättigungsschema nur für große Tischgrößen, und es ist selten so gut wie die lokale Vorhersage. Der Verlaufspuffer muss länger sein, um eine gute Vorhersage zu machen. Die Größe des Musterverlaufs ist wächst exponentiell mit der Größe des Verlaufspuffers. Daher muss die große Mustergeschichte Tabelle unter allen bedingten Sprüngen geteilt werden.

Ein zweistufiger adaptiver Prädiktor mit global gemeinsamer Verlaufs- und Mustergeschichte Tabelle wird als "GSHare" -Predictor bezeichnet, wenn es sich Xors die globale Geschichte und der Zweig -PC und "gselektieren", wenn es sich verkettet Sie. Die globale Zweigvorhersage wird in verwendet AMD Prozessoren und in Intel Pentium m, Kern, Kern 2, und Silvermont-basierend Atom Prozessoren.

Legierter Zweigvorhersage

Ein legierter Zweig -Prädiktor[16] kombiniert die lokalen und globalen Vorhersageprinzipien von Verkettung Lokale und globale Zweighistorien, möglicherweise mit einigen Teilen aus der Programm zähler auch. Tests zeigen, dass die Über Nano Der Prozessor kann diese Technik verwenden.[8]

Stimmen Sie Prädiktor zu

Ein vereinbarter Prädiktor ist ein zweistufiger adaptiver Prädiktor mit global gemeinsamer Verlaufs- und Musterverlauf Tabelle und ein zusätzlicher lokaler Sättigungsschalter. Die Ausgänge der lokalen und der globalen Prädiktoren sind miteinander XAD, um die endgültige Vorhersage zu ergeben. Ziel ist es, die Einwände in der Musterverlaufstabelle zu reduzieren, in der zwei Zweige mit entgegengesetzter Vorhersage den gleichen Eintrag in der Musterverlauf Tabelle haben.[17]

Hybridprädiktor

Ein Hybridprädiktor, auch kombinierter Prädiktor bezeichnet, implementiert mehr als einen Vorhersagemechanismus. Die endgültige Vorhersage basiert entweder auf einem Meta-Prädictor, der sich erinnert, welcher der Prädiktoren in der Vergangenheit die besten Vorhersagen gemacht hat, oder eine Mehrheitsstimmenfunktion, die auf einer ungeraden Anzahl verschiedener Prädiktoren basiert.

Scott McFarling schlug die kombinierte Branch -Vorhersage in seiner Arbeit von 1993 vor.[12]

Auf den Spec'89 -Benchmarks ist ein solcher Prädiktor ungefähr so ​​gut wie der lokale Prädiktor.

Prädiktoren wie GSHARE verwenden mehrere Tabelleneinträge, um das Verhalten eines bestimmten Zweigs zu verfolgen. Diese Multiplikation von Einträgen macht es viel wahrscheinlicher, dass zwei Zweige denselben Tabelleneintrag (eine Situation, die als Aliasing genannt) abgebildet wird, was wiederum viel wahrscheinlicher ist, dass die Vorhersagegenauigkeit für diese Zweige leiden wird. Sobald Sie mehrere Prädiktoren haben, ist es vorteilhaft zu arrangieren, dass jeder Prädiktor unterschiedliche Aliasingmuster hat, so dass es wahrscheinlicher ist, dass mindestens ein Prädiktor kein Aliasing hat. Kombinierte Prädiktoren mit unterschiedlichen Indizierungsfunktionen für die verschiedenen Prädiktoren werden aufgerufen gskew Prädiktoren und sind analog zu verzerrte assoziative Caches verwendet für Daten und Anweisungen.

Schleifenprädiktor

A bedingter Sprung das kontrolliert a Schleife wird am besten mit einem speziellen Schleifenprädiktor vorhergesagt. Ein bedingter Sprung in der Unterseite einer Schleife, die sich n-mal wiederholt, wird N-1-mal und dann nicht einmal eingenommen. Wenn der bedingte Sprung oben auf der Schleife platziert wird, wird er nicht n-1-mal genommen und dann einmal genommen. Ein bedingter Sprung, der viele Male in eine Weise und dann einmal in der anderen Richtung geht, wird als Schleifenverhalten erkannt. Ein solcher bedingter Sprung kann leicht mit einem einfachen Zähler vorhergesagt werden. Ein Schleifenprädiktor ist Teil eines Hybridprädiktors, bei dem ein Meta-Vorsprung feststellt, ob der bedingte Sprung das Schleifenverhalten aufweist.

Indirekter Zweig -Prädiktor

Ein Indirekter Sprung Die Anweisung kann zwischen mehr als zwei Zweigen wählen. Einige Prozessoren haben spezielle indirekte Zweigprädiktoren.[18][19] Neuere Prozessoren aus Intel[20] und Amd[21] kann indirekte Zweige vorhersagen, indem ein zweistufiger adaptiver Prädiktor verwendet wird. Diese Art von Anweisung trägt mehr als ein bisschen zum Geschichtspuffer bei. Das ZEC12 und später Z/Architektur Prozessoren von IBM unterstützen a Branchenvorhersage Vorlast Anweisungen, die den Eintrag für den Zweig-Prädiktor für eine bestimmte Anweisung mit einer Zweigzieladresse vorladen können, indem der Inhalt eines allgemeinen Registers zu einem sofortigen Verschiebungswert hinzugefügt wird.[22][23]

Prozessoren ohne diesen Mechanismus prognostizieren einfach einen indirekten Sprung, um zum gleichen Ziel zu gehen wie beim letzten Mal.[8]

Vorhersage der Funktionsrenditen

A Funktion wird normalerweise zu dem Ort zurückkehren, von dem es angerufen wird. Das Anweisung zurückgeben ist ein indirekter Sprung, der seine Zieladresse von der liest Rufen Sie Stack an. Viele Mikroprozessoren haben einen separaten Vorhersagemechanismus für Rückkehranweisungen. Dieser Mechanismus basiert auf einem sogenannten Stapelpuffer zurückgeben, das ist ein lokaler Spiegel des Anrufstapels. Die Größe des Return -Stack -Puffers beträgt normalerweise 4–16 Einträge.[8]

Übergeordnete Zweigvorhersage

Das Abtausch Zwischen schneller Zweigvorhersage und guter Zweigvorhersage wird manchmal durch zwei Zweigprädiktoren behandelt. Der erste Zweig -Prädiktor ist schnell und einfach. Der zweite Zweig -Prädiktor, der langsamer, komplizierter und mit größeren Tabellen ist, wird eine möglicherweise falsche Vorhersage des ersten Prädiktors außer Kraft setzen.

Die Alpha 21264- und Alpha EV8-Mikroprozessoren verwendeten einen schnellen Einzelzyklus-nächsten Prädiktor, um das Wiederauftreten des Zweigziels zu verarbeiten und eine einfache und schnelle Zweigvorhersage zu liefern. Da der Next-Line-Prädiktor so ungenau ist und das Wiederauftreten der Zweigauflösung so lange dauert, haben beide Kerne zwei Zyklus-Sekundärzweig-Prädiktoren, die die Vorhersage des nächsten Zeilenprädiktors auf Kosten eines einzelnen verlorenen Abrufzyklus überschreiben können.

Das Intel Core i7 hat zwei Zweigzielpuffer und möglicherweise zwei oder mehr Zweigprädiktoren.[24]

Vorhersage für neuronale Zweige

Maschinelles Lernen für die Zweigvorhersage mit Lvq und Mehrschichtwahrnehmung, genannt "neuronal Branchenvorhersage ", wurde von Lucian Vintan (vorgeschlagenLucian Blaga Universität Sibiu).[25] Ein Jahr später entwickelte er den Perceptron Branch Predictor.[26] Die Prädiktorforschung der neuronalen Niederlassung wurde von Daniel Jimenez weit weiterentwickelt.[27] In 2001,[27] Der Erste Perzeptron Der Prädiktor wurde vorgestellt, der in Hardware implementiert war. Die erste kommerzielle Umsetzung eines Perceptron Branch -Prädiktors war bei AMDs Piledriver -Mikroarchitektur.[28]

Der Hauptvorteil des neuronalen Prädiktors ist seine Fähigkeit, lange Geschichten zu nutzen und gleichzeitig nur ein lineares Ressourcenwachstum zu erfordern. Klassische Prädiktoren erfordern ein exponentielles Ressourcenwachstum. Jimenez meldet eine globale Verbesserung von 5,7% gegenüber einem Hybridprädiktor im McFarling-Stil.[29] Er verwendete auch eine übergeordnete Hybridprädiktoren von GSHARE/Perceptron.[29]

Der Hauptnachteil des Perceptron -Prädiktors ist seine hohe Latenz. Auch nach der Nutzung von Arithmetik-Tricks mit Hochgeschwindigkeit ist die Berechnungslatenz im Vergleich zur Taktperiode vieler moderner Mikroarchitekturen relativ hoch. Um die Vorhersagelatenz zu verringern, schlug Jimenez 2003 die vor, die Schnellweg-neuronaler Prädiktor, wo der Perceptron -Prädiktor seine Gewichte entsprechend dem Pfad des aktuellen Zweigs wählt, und nicht nach dem PC des Zweigs. Viele andere Forscher entwickelten dieses Konzept (A. Seznec, M. Monchiero, D. Tarjan & K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black usw.).

Die meisten der hochmodernen Branch-Prädiktoren verwenden einen Perceptron-Prädiktor (siehe Intel "Meisterschaftsbranchen-Vorhersagewettbewerb"[30]). Intel implementiert diese Idee bereits in einem der IA-64Simulatoren (2003).[31]

Das AMD Ryzen[32][33][34] Multi-Core-Prozessor Infinity Stoff und die Samsung Exynos Der Prozessor umfasst einen Perceptron-basierten neuronalen Zweig-Prädiktor.

Geschichte

Das IBM 7030 StretchVorausgesetzt, alle bedingungslosen Zweige und alle bedingten Zweige, die von den Indexregistern abhing, executiert alle bedingungslosen Zweige. Für andere bedingte Zweige prognostizieren die ersten beiden Produktionsmodelle Untaken; Nachfolgende Modelle wurden geändert, um Vorhersagen basierend auf den aktuellen Werten der Indikatorbits (entsprechend den heutigen Zustandscodes) zu implementieren.[35] Die Stretch -Designer hatten zu Beginn des Projekts in den Zweiganweisungen in den Zweiganweisungen nachgedacht, sich jedoch gegen sie entschieden. Die Wiederherstellung der Fehlverpredungen wurde von der Lookahead-Einheit auf Stretch bereitgestellt, und ein Teil des Rufs von Stretch für weniger als herausragende Leistung wurde auf die Zeit verantwortlich gemacht, die für die Wiederherstellung von Fehlverhalten erforderlich war. Nachfolgende IBM große Computerdesigns verwendeten keine Zweigvorhersage mit spekulativer Ausführung, bis die IBM 3090 1985.

Zwei-Bit-Prädiktoren wurden 1977 von Tom McWilliams und Curt Widdoes für den Lawrence Livermore National Lab S-1 Supercomputer und unabhängig von Jim Smith im Jahr 1979 bei CDC eingeführt.[36]

Mikroprogrammierte Prozessoren, die von den 1960er bis 1980er Jahren und darüber hinaus beliebt waren, nahmen mehrere Zyklen pro Anweisung an und erforderten im Allgemeinen keine Ast -Vorhersage. Zusätzlich zum IBM 3090 gibt es jedoch mehrere andere Beispiele für mikroprogrammierte Konstruktionen, die die Branchenvorhersage enthalten.

Das Burroughs B4900Eine mikroprogrammierte COBOL -Maschine, die um 1982 freigesetzt wurde, wurde pipeliniert und verwendete Zweigvorhersage. Der Status der B4900 Branch Prediction History wird während der Programmausführung in die Anweisungen in den Memory zurückgebracht. Die B4900 implementiert die 4-Staaten-Zweigvorhersage unter Verwendung von 4 semantisch äquivalenten Zweig-Opcodes, um jeden Zweig-Operator-Typ darzustellen. Der verwendete Opcode zeigte die Geschichte dieses bestimmten Zweigunterrichts an. Wenn die Hardware feststellt, dass der Zweig -Vorhersagezustand eines bestimmten Zweigs aktualisiert werden muss, schreibt sie den Opcode mit dem semantisch äquivalenten Opcode um, der die richtige Geschichte angedeutet hat. Dieses Schema erhält eine Trefferquote von 93%. US -Patent 4.435.756 und andere wurden in diesem Schema gewährt.

Das VAX 9000, angekündigt 1989, ist sowohl mikroprogrammiert als auch pipeliniert und führt die Vorhersage der Zweig durch.[37]

Die ersten kommerziellen RISC -Prozessoren, die MIPS R2000 und R3000 und das frühere Sparc Prozessoren, nur triviale "nicht geschlossene" Zweigvorhersage. Da sie Zweigverzögerungsschlitze verwenden, nur einen Anweisungen pro Zyklus abgerufen und in Ordnung ausführen, gibt es keinen Leistungsverlust. Am später R4000 Verwendet die gleiche triviale "nicht geschlossene" Ast-Vorhersage und verliert zwei Zyklen für jeden Zweig, da das Wiederauftreten der Zweigauflösung vier Zyklen lang ist.

Die Vorhersage der Branche wurde mit der Einführung von pipelierten Supercalar -Prozessoren wie dem Intel wichtiger Pentium, Dec Alpha 21064, die MIPs R8000, und die IBM -Kraft Serie. Diese Prozessoren verlassen sich alle auf ein Bit oder einfache bimodale Prädiktoren.

DER DEC Alpha 21264 (EV6) verwendet einen von einem kombinierten lokalen Prädiktor und globalen Prädiktor überschriebenen Prädiktor als Nächsteil, bei dem die kombinierte Wahl durch einen bimodalen Prädiktor getroffen wird.[38]

Das AMD K8 hat einen kombinierten bimodalen und globalen Prädiktor, bei dem die kombinierte Wahl ein weiterer bimodaler Prädiktor ist. Dieser Prozessor zwischen den Basis- und Auswahl -Bimodal -Prädiktorzähnen in Bits des L2 -Cache, ansonsten für ECC verwendet. Infolgedessen hat es effektiv sehr große Basis- und Auswahl -Prädiktabellen und Parität als ECC für Anweisungen im L2 -Cache. Das Paritätsdesign ist ausreichend, da jede Anweisung, die einen Paritätsfehler leistet, ungültig und aus dem Speicher ausgestreckt werden kann.

Das Alpha 21464[38] (EV8, spät im Design abgesagt) hatte eine Mindeststrafe von 14 Zyklen. Es sollte einen komplexen, aber schnellen Prädiktor der nächsten Linie verwenden, der durch einen kombinierten bimodalen und mehrheitlich stimmberechtigten Prädiktor überschrieben wurde. Die Mehrheitsabstimmung war zwischen dem bimodalen und zwei GSKEW -Prädiktoren.

2018 ein katastrophaler Sicherheitsanfälligkeit genannt Gespenst wurde von Google veröffentlicht Projekt Null und andere Forscher. Praktisch alle modernen betreffen CPUsDie Sicherheitsanfälligkeit besteht darin, private Daten aus den übrig gebliebenen Daten von Fehlverhaltensdaten zu extrahieren.[39]

Siehe auch

Verweise

  1. ^ a b Malishevsky, Alexey; Beck, Douglas; Schmid, Andreas; Landry, Eric. "Dynamische Zweigvorhersage". Archiviert von das Original Am 2019-07-17. Abgerufen 2017-03-22.
  2. ^ a b Cheng, Chih-Cheg. "Die Pläne und Leistungen dynamischer Zweig -Prädiktoren" (PDF).
  3. ^ Parihar, Raj. "Zweigvorhersagetechniken und Optimierungen" (PDF). Archiviert von das Original (PDF) Am 2017-05-16. Abgerufen 2017-04-02.
  4. ^ Mutlu, Onur (2013-02-11). "18-447 Computerarchitektur Vortrag 11: Zweigvorhersage" (PDF).
  5. ^ Michaud, Pierre; Seznec, André; Uhlig, Richard (September 1996). "Verzerrte Zweigprädiktoren". S2CID 3712157. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  6. ^ Eyerman, S.; Smith, J.E.; Eeckhout, L. (2006). "Charakterisierung der Niederlassung der Niederlassung" Strafe ". 2006 IEEE International Symposium zur Leistungsanalyse von Systemen und Software. IEEE: 48–58. doi:10.1109/ispass.2006.1620789. ISBN 1-4244-0186-0. S2CID 72217.
  7. ^ Shen, John P.; Lipasti, Mikko (2005). Modernes Prozessordesign: Grundlagen von Superscalar -Prozessoren. Boston: McGraw-Hill Hochschulbildung. pp.455. ISBN 0-07-057064-7.
  8. ^ a b c d e f Fog, Agner (2016-12-01). "Die Mikroarchitektur von Intel, AMD und über CPUs" (PDF). p. 36. Abgerufen 2017-03-22.
  9. ^ Das Pentium 4 und das G4E: ein architektonischer Vergleich, ARS Technica
  10. ^ Plusquellic, Jim. "CMSC 611: Erweiterte Computerarchitektur, Kapitel 4 (Teil V)".
  11. ^ "Dynamische Zweigvorhersage". web.engr.oregonstate.edu. Archiviert von das Original Am 2019-07-17. Abgerufen 2017-11-01.
  12. ^ a b c McFarling, Scott (Juni 1993). "Kombination von Zweigprädiktoren" (PDF). Technischer Bericht von Digital Western Research Lab (WRL), TN-36.
  13. ^ "Neuer Algorithmus verbessert die Branchenvorhersage: 27.03.95" (PDF). Carnegie Mellon Universität. Abgerufen 2016-02-02.
  14. ^ Yeh, T.-y.; Patt, Y. N. (1991). "Zwei-Stufe Adaptive Training Branch Prediction". Verfahren des 24. jährlichen Internationalen Symposiums für Mikroarchitektur. Albuquerque, New Mexico, Puerto Rico: ACM. S. 51–61.
  15. ^ Egan, Colin; Steven, Gordon; Quick, P.; Anguera, R.; Vintan, Lucian (Dezember 2003). "Zweistufige Zweigvorhersage mit neuronalen Netzwerken". Journal of Systems Architecture. 49 (12–15): 557–570. doi:10.1016/s1383-7621 (03) 00095-x.
  16. ^ Skadron, K.; Martonosi, M.; Clark, D. W. (Oktober 2000). "Eine Taxonomie von Zweigverpörungen und eine Vorhersage als robuste Lösung für falsche Verfehlungen." Verfahren der Internationalen Konferenz 2000 über parallele Architekturen und Zusammenstellungstechniken. Philadelphia.
  17. ^ Sprangle, e.; et al. (Juni 1997). "Der Vereinbarungprädiktor: Ein Mechanismus zur Verringerung der Eingriffe der negativen Zweighistorie". Verfahren des 24. Internationalen Symposiums über Computerarchitektur. Denver.
  18. ^ "Cortex-A15 MPCORE Technisches Referenzhandbuch, Abschnitt 6.5.3" Indirekter Prädiktor "". Armhoteln.
  19. ^ Driessen, Karel; Hölzle, URS (1997-06-25). "Grenzen der indirekten Zweigvorhersage" (PDF).
  20. ^ Stokes, Jon (2004-02-25). "Ein Blick auf den Centrino -Kern: das Pentium m". S. 2–3.
  21. ^ Kanter, Aaron (2008-10-28). "Leistungsanalyse für Core 2 und K8: Teil 1". p. 5.
  22. ^ "Z/Architekturprinzipien des Betriebs" (PDF). IBM. März 2015. S. 7–40, 7–43. SA22-7832-10.
  23. ^ "IBM Zenterprise BC12 Technischer Leitfaden" (PDF). IBM. Februar 2014. p. 78.
  24. ^ WO 2000/014628, Yeh, Tse-yu & Sharangpani, H. P., "Eine Methode und Apparat für die Zweigvorhersage unter Verwendung einer Zweig-Vorhersagetabelle der zweiten Ebene", veröffentlicht 2000-03-16 
  25. ^ Vintan, Lucian N. (1999). Auf dem Weg zu einem Hochleistungs -Neuralzweigprädiktor (PDF). Proceedings International Journal Conference on Neural Networks (IJCNN). Archiviert von das Original (PDF) Am 2019-07-13. Abgerufen 2010-12-02.
  26. ^ Vintan, Lucian N. (2000). "Auf dem Weg zu einem leistungsstarken dynamischen Zweig -Prädiktor" (PDF). Rumänisches Journal für Informationswissenschaft und Technologie. Bukarest: Rumänische Akademie. 3 (3): 287–301. ISSN 1453-8245.
  27. ^ a b Jimenez, D. A.; Lin, C. (2001). Dynamische Zweigvorhersage mit Perzeptronen. Proceedings des 7. Internationalen Symposiums zur Hochleistungs-Computerarchitektur (HPCA-7). Monterrey, NL, Mexiko. S. 197–296.
  28. ^ Walton, Jarred (2012-05-15). "Die AMD Trinity Review (A10-4600m): Eine neue Hoffnung". Anandtech.
  29. ^ a b Jimenez, Daniel A. (Dezember 2003). Schnellpfadbasierte Vorhersage auf neuronaler Zweig (PDF). Das 36. jährliche IEEE/ACM International Symposium on Microarchitecture (MICRO-36). San Diego, USA. Abgerufen 2018-04-08.
  30. ^ "Meisterschaftsbranche Vorhersage".
  31. ^ Brekelbaum, Edward; Rupley, Jeff; Wilkerson, Chris; Black, Bryan (Dezember 2002). Hierarchische Planungsfenster. Verfahren des 34. Internationalen Symposiums über Mikroarchitektur. Istanbul, Türkei.
  32. ^ James, Dave (2017-12-06). "Amd Ryzen Reviews, Nachrichten, Leistung, Preisgestaltung und Verfügbarkeit". Pcgamesn.
  33. ^ "AMD bringt das Computer mit Ryzen ™ -Prozessoren zu einem neuen Horizont". www.amd.com. Abgerufen 2016-12-14.
  34. ^ "AMDs Zen CPU heißt jetzt Ryzen und könnte tatsächlich Intel herausfordern". ARS Technica UK. Abgerufen 2016-12-14.
  35. ^ IBM Stretch (7030) - aggressive Uniprozessor -Parallelität
  36. ^ S-1 Supercomputer
  37. ^ Mikroarchitektur des VAX 9000
  38. ^ a b Seznec, Felix, Krishnan, Sazeides. Design -Kompromisse für den Alpha EV8 Conditional Branch Predictor
  39. ^ Gibbs, Samuel (2018-01-04). "Meltdown und Gespenst: 'Worst' CPU -Fehler betrifft praktisch alle Computer". der Wächter. Abgerufen 2018-05-18.

Externe Links