PatentDe  


Dokumentenidentifikation DE102005001679A1 27.07.2006
Titel Mikroprozessor-Einrichtung, und Branch-Prediktions-Verfahren
Anmelder Infineon Technologies AG, 81669 München, DE
Erfinder Hastie, Neil, Glos, GB;
Donohoe, Graham, Bristol, GB
Vertreter Bosch, Graf von Stosch, Jehle Patentanwaltsgesellschaft mbH, 80639 München
DE-Anmeldedatum 13.01.2005
DE-Aktenzeichen 102005001679
Offenlegungstag 27.07.2006
Veröffentlichungstag im Patentblatt 27.07.2006
IPC-Hauptklasse G06F 9/32(2006.01)A, F, I, 20051017, B, H, DE
IPC-Nebenklasse G06F 9/38(2006.01)A, L, I, 20051017, B, H, DE   G06F 9/46(2006.01)A, L, I, 20051017, B, H, DE   G06F 9/22(2006.01)A, L, I, 20051017, B, H, DE   G06F 9/42(2006.01)A, L, I, 20051017, B, H, DE   
Zusammenfassung Die Erfindung betrifft eine Mikroprozessor-Einrichtung (11) und ein Branch-Prediktions-Verfahren, welches die Schritte aufweist:
- Ermitteln, zu welcher von mehreren vorbestimmten Branch-Klassen ein jeweils abzuarbeitender Branch-Befehl zugeordnet ist; und
- Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird oder nicht, abhängig von der ermittelten Branch-Klasse.
Vorteilhaft wird zum Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird oder nicht, jeweils eine der ermittelten Branch-Klasse zugeordnete, adaptive Branch-Prediktions-Einrichtung (1a, 1b, 1c, 1d) verwendet.

Beschreibung[de]

Die Erfindung betrifft eine Mikroprozessor-Einrichtung, und ein Branch-Prediktions-Verfahren, insbesondere zur Verwendung in einer Mikroprozessor-Einrichtung.

Bei herkömmlichen Mikroprozessor-Einrichtungen werden entsprechende Maschinenbefehle aus einem Hauptspeicher ausgelesen, und dann von einem Interpreter verarbeitet, insbesondere in eine Sequenz ausführbarer Micro-Operationen übersetzt.

Um die Leistungsfähigkeit von Mikroprozessor-Einrichtungen zu erhöhen, können diese eine sog. „Pipeline-"Struktur aufweisen: Dabei können ein oder mehrere Arbeitsvorgänge, z.B. der Arbeitsvorgang „Maschinenbefehl interpretieren" in mehrere Teil-Schritte unterteilt werden (z.B. in die Teil-Schritte „Instruction Fetch", und/oder „Instruction Decoding", und/oder „Address Generation", und/oder „Operand Fetch", und/oder „Execute", und/oder „Store Result", und/oder „Update Program Counter", etc., etc.), wobei jeder Teil-Schritt von einer separaten Verarbeitungseinheit („Stufe") abgearbeitet wird.

Die einzelnen Verarbeitungseinheiten bzw. Stufen können über entsprechende Latches, Daten- und Steuerpfade so miteinander verbunden sein, dass ein paralleles, sequentielles Abarbeiten mehrerer, verschiedener Maschinenbefehle möglich ist (wobei zu einem bestimmten Zeitpunkt jede Stufe parallel an jeweils verschiedenen Befehlen arbeitet).

Beispielsweise kann eine „Instruction Fetch" Stufe fortwährend sequentiell hintereinanderliegend abgespeicherte Maschinenbefehle aus dem Hauptspeicher laden. In einer „Instruction Decoding" Stufe wird ein entsprechender, von der „Instruction Fetch" Stufe übernommener Befehl decodiert, während die „Instruction Fetch" Stufe bereits den nächsten Befehl aus dem Speicher in den Prozessor transferiert. Eine „Adress Generation" Stufe erhält den Befehlsteil und entsprechende zur Adressierung notwendige Steuerinformationen (z.B. die Adressierungsart) von der „Instruction Decoding" Stufe, und berechnet die Operandenadressen, die an eine „Operand Fetch" Stufe weitergegeben werden (während – parallel – die „Instruction Fetch" Stufe bereits einen weiteren Maschinenbefehl aus dem Hauptspeicher lädt, und in der „Instruction Decoding" Stufe der zuletzt durch die „Instruction Fetch" Stufe geladene Befehl decodiert wird, usw., usw.).

Das Pipelining-Konzept bedingt eine besondere Architektur, die so ausgelegt sein muss, dass die einzelnen Stufen auch tatsächlich parallel an verschiedenen Befehlen arbeiten können, und sich dabei möglichst wenig gegenseitig beeinflussen.

Da die „Instruction Fetch" Stufe – wie oben erläutert – die Befehle in der Regel sequentiell aus dem Hauptspeicher holt, können bei (bedingten oder unbedingten) Sprung-Befehlen bzw. Branches, und/oder Subroutine Calls irrelevante, momentan nicht auszuführende Befehle in die Pipeline geladen werden, was zu erheblichen Performance-Einbussen führt.

Unbedingte Sprünge (und Subroutine Calls) können durch spezielle Steuermechanismen frühzeitig erkannt werden, woraufhin veranlasst werden kann, dass die „Instruction Fetch" Stufe an der neuen Stelle im Programm fortsetzt, noch bevor durch die „Update Program Counter" Stufe der PC (Program Counter) entsprechend geändert worden ist.

Demgegenüber kann das Ziel von bedingten Sprüngen erst bei der Auswertung der jeweiligen Bedingung, z.B. erst durch die „Execute" Stufe ermittelt werden. Möglicherweise muss dann – entsprechend der jeweiligen Bedingung – der gesamte Inhalt der Pipeline verworfen werden.

Dies kann z.B. dadurch verhindert werden, dass der Pipeline-Mechanismus gestoppt wird, sobald die „Instruction Decoding" Stufe einen bedingten Sprung-Befehl erkennt. Die Pipeline wird erst dann wieder freigegeben, wenn die Zieladresse des Sprungs ermittelt, bzw. der PC aktualisiert wurde. Dieses Vorgehen, das zur einer „Lücke" in der Pipeline, und damit zu einem Performance-Verlust führt, wird als „Interlocking" bezeichnet.

Um die bei einem „Interlocking" auftretenden Performance-Verluste zu verhindern bzw. zu minimieren, können sog. – statische oder dynamische – Branch-Prediktions-Verfahren eingesetzt werden.

Dabei wird versucht, vorherzusagen, ob ein bedingter Sprung wahrscheinlich ausgeführt werden wird (Vorhersage: „taken"), oder nicht (Vorhersage: „not taken").

Ein einfaches Beispiel sind Jump-Operations-Befehle, deren Ziel relativ zum PC angegeben wird (d.h. bei denen eine auf den Program Counter bezogene Adressierung verwendet wird):

Ist bei solchen Sprung-Befehlen das Displacement negativ („Rückwärts-" bzw. „Backward"-Sprung), so kann angenommen werden, dass es sich um ein Schleifenende handelt. Da eine Schleife mit höherer Wahrscheinlichkeit durchlaufen, als verlassen wird, kann als Vorhersage für einen derartigen Sprung-Befehl also angenommen werden, dass der Sprung ausgeführt werden wird (Vorhersage: „taken").

Wird vorhergesagt, dass ein Sprung ausgeführt werden wird, kann veranlasst werden, dass die „Instruction Fetch" Stufe die sequentielle Reihenfolge beim Laden der Maschinenbefehle aus dem Hauptspeicher durchbricht.

Um die Trefferwahrscheinlichkeit der Vorhersagen zu erhöhen, kann eine Tabelle verwendet werden, in der zu möglichst vielen schon einmal ausgeführten Sprüngen in einem Programm die zuletzt berechneten Zieladressen eingetragen werden (sog. Sprungziel-Cache). Die Tabelle wird vom Prozessor verwaltet, und beinhaltet die „Geschichte" der Befehle („Branch History").

Verschiedene statische und dynamische Branch-Prediktions-Verfahren sind z.B. im Buch „Computer Architecture: A Quantitative Approach" von Hennessy und Patterson beschrieben.

Die Erfindung hat zur Aufgabe, eine neuartige Mikroprozessor-Einrichtung, und ein neuartiges Branch-Prediktions-Verfahren zur Verfügung zu stellen, insbesondere ein Branch-Prediktions-Verfahren, bei dem mit relativ geringem Aufwand, insbesondere relativ geringem Hardware-Aufwand eine relativ gute Trefferwahrscheinlichkeit der Vorhersagen erzielt werden kann.

Sie erreicht dieses und weitere Ziele durch die Gegenstände der Ansprüche 1 und 15.

Vorteilhafte Weiterbildungen der Erfindung sind in den Unteransprüchen angegeben.

Gemäß einem ersten Aspekt der Erfindung wird ein Branch-Prediktions-Verfahren zur Verfügung gestellt, welches die Schritte aufweist:

– Ermitteln, zu welcher von mehreren vorbestimmten Branch-Klassen ein jeweils abzuarbeitender Branch-Befehl zugeordnet ist und

– Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird, oder nicht, abhängig von der ermittelten Branch-Klasse.

Vorteilhaft wird zum Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird, oder nicht, jeweils eine der ermittelten Branch-Klasse zugeordnete Branch-Prediktions-Einrichtung verwendet.

Bei einer bevorzugten Ausgestaltung der Erfindung ist die jeweilige der ermittelten Branch-Klasse zugeordnete Branch-Prediktions-Einrichtung eine adaptive Branch-Prediktions-Einrichtung.

Bevorzugt wird beim Ermitteln der dem jeweils abzuarbeitenden Branch-Befehl zugeordneten Branch-Klasse die Befehls-Länge des jeweils abzuarbeitenden Branch-Befehls untersucht.

Vorteilhaft wird – alternativ oder zusätzlich – beim Ermitteln der dem jeweils abzuarbeitenden Branch-Befehl zugeordneten Branch-Klasse die Sprungrichtung des jeweils abzuarbeitenden Branch-Befehls untersucht.

Bei einer bevorzugten Ausgestaltung der Erfindung wird – alternativ oder zusätzlich – beim Ermitteln der dem jeweils abzuarbeitenden Branch-Befehl zugeordneten Branch-Klasse der Befehlstyp des jeweils abzuarbeitenden Branch-Befehls untersucht.

Gemäß einem weiteren Aspekt der Erfindung wird eine Mikroprozessor-Einrichtung zur Verfügung gestellt, mit mehreren, jeweils einer von mehreren vorbestimmten Branch-Klassen zugeordneten Branch-Prediktions-Einrichtungen.

Vorteilhaft sind die Branch-Prediktions-Einrichtungen adaptive Branch-Prediktions-Einrichtungen.

Im folgenden wird die Erfindung anhand eines Ausführungsbeispiels und der beigefügten Zeichnung näher erläutert. In der Zeichnung zeigt:

1 eine schematische, vereinfachte Darstellung eines Mikrocontroller- bzw. Mikroprozessor-Systems gemäß einem Ausführungsbeispiel der vorliegenden Erfindung;

2 eine schematische, beispielhafte Darstellung eines Abschnitts der in 1 gezeigten CPU, zur Veranschaulichung von deren Pipeline-Struktur;

3 eine schematische Darstellung mehrerer – jeweils separat für verschiedene Branch-Klassen verwendete – Branch-Prediktions-Einrichtungen, zur Veranschaulichung des beim Mikrocontroller- bzw. Mikroprozessor-System gemäß dem Ausführungsbeispiel der vorliegenden Erfindung verwendeten Branch-Prediktions-Verfahrens; und

4 eine schematische Darstellung mehrerer beim Branch-Prediktions-Verfahren gemäß dem Ausführungsbeispiel der vorliegenden Erfindung durchgeführter Verfahrens-Schritte.

In 1 ist eine schematische Darstellung eines Mikrocontroller- bzw. Mikroprozessor-Systems 10 gemäß einem Ausführungsbeispiel der Erfindung gezeigt.

Bei dem Mikrocontroller- bzw. Mikroprozessor-System 10 kann es sich z.B. um ein 8 Bit Mikrocontroller- bzw. Mikroprozessor-System 10 handeln, oder um ein beliebiges anderes Mikrocontroller- bzw. Mikroprozessor-System, z.B. ein entsprechendes 16 Bit, 32 Bit oder 64 Bit Mikrocontroller- bzw. Mikroprozessor-System, etc., insbesondere um ein Multithreaded (MT) Mikrocontroller- bzw. Mikroprozessor-System, z.B. um ein TriCore-Prozessor-System der Fa. Infineon.

Das Mikrocontroller- bzw. Mikroprozessor-System 10 weist eine oder mehrere, auf einem entsprechenden Mikrochip 15 angeordnete (zentrale) Steuer- bzw. Recheneinheiten 11 auf (Central Processing Units (CPUs), bzw. CPU „Cores").

Die CPU 11 oder die CPUs sind – über einen System-Bus 16 (und ggf. ein oder mehrere weitere Bus-Systeme) – mit einer oder mehreren internen (auf demselben Mikrochip 15, wie die CPU 11 vorgesehenen) Speicher-Einrichtungen 17 verbunden, sowie – z.B. über den System-Bus 16, und eine oder mehrere entsprechende Speicher-Steuereinrichtungen („memory controller") 12 – mit einer oder mehreren externen (auf einem anderen Mikrochip, als die CPU 11 vorgesehenen) Speicher-Einrichtungen 18.

Die Speicher-Einrichtungen 17, 18 können z.B. als Programmspeichereinrichtung, und/oder Datenspeichereinrichtung („Programmspeicher", und „Datenspeicher") fungieren.

Der „Programmspeicher" enthält insbesondere die Folge der von der bzw. den CPUs 11 abzuarbeitenden Befehle, also das Programm (und ggf. zusätzlich entsprechende – von der bzw. den CPUs 11 zu verwendende – Daten-Konstanten).

Der – z.B. von der Speicher-Einrichtung 17 gebildete – Programmspeicher kann z.B. von einem EPROM (Erasable PROM bzw. Löschbaren Festwertspeicher) oder EEPROM (Electrically Erasable PROM bzw. Elektrisch Löschbarer Festwertspeicher) gebildet werden, insbesondere einem Flash-EEPROM-Bauelement.

Dadurch kann erreicht werden, dass das Programm auch bei unterbrochener Stromzufuhr auf der entsprechenden Speicher-Einrichtung gespeichert bleibt.

Für häufig zu ändernde Programme können – alternativ – z.B. auch RAMs (RAM = Random Access Memory bzw. Schreib-Lese-Speicher), insbesondere DRAMs als Programmspeicher verwendet werden, die von einem externen Massenspeicher geladen werden können.

Im o.g. – z.B. von der Speicher-Einrichtung 18 gebildeten – „Datenspeicher" können z.B. die – insbesondere von der bzw. den CPUs 11 beim Abarbeiten des Programms ggf. abzuändernden – Variablen gespeichert sein.

Der Datenspeicher kann z.B. von einem oder mehreren RAM-Bauelementen, insbesondere z.B. einem entsprechenden DRAM-Bauelement (DRAM = Dynamic Random Access Memory), oder SRAM-Bauelement (SRAM = Static Random Access Memory) gebildet werden.

Ein – durch die CPU bzw. den CPU Core 11 abzuarbeitendes – Software-Programm (bzw. mehrere derartige Programme) kann in eine Vielzahl entsprechender Software Tasks (Threads) unterteilt sein.

Dies hat z.B. den Vorteil, dass – insbesondere bei dem hier gezeigten Multithreaded (MT) Mikrocontroller- bzw. Mikroprozessor-System 10 – parallel jeweils mehrere, verschiedenene Tasks gleichzeitig in den CPU Core 11 geladen, und dort abgearbeitet werden können.

Im CPU Core 11 werden – entsprechend wie bei herkömmlichen CPUs – aus einer entsprechenden Speicher-Einrichtung, z.B. der als Hauptspeicher fungierenden Speicher-Einrichtung 17 ausgelesene Befehle, insbesondere Maschinenbefehle, von einem Interpreter verarbeitet, insbesondere in eine Sequenz ausführbarer Micro-Operationen übersetzt.

Wie in 2 schematisch veranschaulicht ist, weist die CPU bzw. Der CPU Core 11 eine „Pipeline-"Struktur auf: Dabei können ein oder mehrere Arbeitsvorgänge, z.B. der Arbeitsvorgang „Maschinenbefehl interpretieren" in mehrere Teil-Schritte unterteilt werden (z.B. in die Teil-Schritte „Instruction Fetch", und/oder „Instruction Decoding", und/oder „Address Generation", und/oder „Operand Fetch", und/oder „Execute", und/oder „Store Result", und/oder „Update Program Counter", etc., etc.), wobei jeder Teil-Schritt von einer separaten, in einer entsprechenden Pipeline 2 angeordneten Verarbeitungseinheit („Stufe") 3a, 3b, 3c, 3d, 3e, 3f, 3g abgearbeitet wird.

Die einzelnen Verarbeitungseinheiten bzw. Stufen 3a, 3b, 3c, 3d, 3e, 3f, 3g der Pipeline 2 können über entsprechende Latches, Daten- und Steuerpfade so miteinander verbunden sein, dass ein paralleles, sequentielles Abarbeiten mehrerer, verschiedener Maschinenbefehle möglich ist (wobei zu einem bestimmten Zeitpunkt jede Stufe 3a, 3b, 3c, 3d, 3e, 3f, 3g parallel an jeweils verschiedenen Befehlen arbeitet).

Beispielsweise kann eine „Instruction Fetch" Stufe 3a – in einem Normalbetrieb der CPU Core 11 (s.u.) – fortwährend sequentiell hintereinanderliegend abgespeicherte Maschinenbefehle aus dem Hauptspeicher laden. In einer „Instruction Decoding" Stufe 3b wird ein entsprechender, von der „Instruction Fetch" Stufe 3c übernommener Befehl decodiert, während die „Instruction Fetch" Stufe 3a bereits den nächsten Befehl aus dem Hauptspeicher lädt. Eine „Adress Generation" Stufe 3c erhält den Befehlsteil und entsprechende zur Adressierung notwendige Steuerinformationen (z.B. die Adressierungsart) von der „Instruction Decoding" Stufe 3b, und berechnet die Operandenadressen, die an eine „Operand Fetch" Stufe 3d weitergegeben werden (während – parallel – die „Instruction Fetch" Stufe 3a ggf. bereits einen weiteren Maschinenbefehl aus dem Hauptspeicher lädt, und in der „Instruction Decoding" Stufe 3b der zuletzt durch die „Instruction Fetch" Stufe 3a geladene Befehl decodiert wird, usw., usw.).

Um zu verhindern, dass von der „Instruction Fetch" Stufe 3a – insbesondere bei (bedingten) Sprung-Befehlen bzw. Branches – irrelevante, (momentan) nicht auszuführende Befehle in die Pipeline 2 geladen werden, bzw. – allgemeiner ausgedrückt – um durch (bedingte) Sprung-Befehle bzw. (conditional) Branches hervorgerufene Performance-Verluste zu minimieren, wird beim vorliegenden Ausführungsbeispiel ein spezielles, im folgenden im Detail erläutertes – gemischt statisch-dynamisches (bzw. „adaptiv-statisches") – Branch-Prediktions-Verfahren eingesetzt.

Dabei wird versucht, vorherzusagen, ob ein bedingter Sprung wahrscheinlich ausgeführt werden wird (Vorhersage: „taken"), oder nicht (Vorhersage: „not taken").

Beim gemischt statisch-dynamischen (bzw. adaptiv-statischen) 8ranch-Prediktions-Verfahren gemäß dem hier dargestellten Ausführungsbeispiel der Erfindung werden die Sprung-Befehle bzw. branches (insbesondere die bedingten Sprung-Befehle (conditional branches)) nach deren jeweiligen statischen Attributen/Charakteristika (oder Kombinationen hieraus) klassifiziert.

Denkbar hierfür ist – insbesondere z.B. bei TriCore-Prozessoren der Fa. Infineon – u.a. die Verwendung der folgenden Charakteristika/Attribute:

  • – Sprungrichtung (vorwärts oder rückwärts);
  • – Befehlslänge (z.B. lang (long) oder kurz (short) (z.B. 32bit (lang), oder 16bit (kurz)));
  • – Befehlstyp (z.B. „Integer", oder „Load/Store");
  • – Befehlsfunktion (z.B. JEQ, JNE, JGT, JLE);
  • – Task bzw. Thread Identifier, etc., etc.

Beim vorliegenden Ausführungsbeispiel werden die bedingten Sprünge (conditional branches) jeweils einer der folgenden fünf Klassen zugeordnet:

Klasse 1:
  • Lange (long) Vorwärts-Integer-Branches
Klasse 2:
  • Kurze (short) Vorwärts-Integer-Branches
Klasse 3:
  • Lange (long) Vorwärts-Load/Store-Branches
Klasse 4:
  • Kurze (short) Vorwärts-Load/Store-Branches
Klasse 5:
  • Rückwärts-Branches

Für jede Klasse wird – wie in 3 für die Klassen 1–4 veranschaulicht ist – jeweils eine separate, adaptive – z.B. in Form einer entsprechenden State-Machine verwirklichte – Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d, etc. verwendet.

Wie aus 1 hervorgeht, weist der CPU Core 11 eine Steuereinrichtung 13 auf, mit der – in einem ersten Schritt – ermittelt wird, zu welcher der o.g. Klassen 1, 2, 3, 4 oder 5 der nächste abzuarbeitende (bedingte) Sprung- bzw. Branch-Befehl gehört (vgl. auch den in 4 gezeigten Verfahrens-Schritt A).

Abhängig von dem Ergebnis dieser Ermittlung wird – in einem zweiten Schritt – unter Verwendung der der jeweils ermittelten Branch-Klasse zugeordneten Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d, etc. ermittelt, ob der Sprung bzw. Branch des nächsten abzuarbeitenden (bedingten) Sprung- bzw. Branch-Befehls wahrscheinlich ausgeführt werden wird, oder nicht (vgl. auch den in 4 gezeigten Verfahrens-Schritt B).

Wird beim o.g. Schritt A ermittelt, dass der nächste abzuarbeitende (bedingte) Sprung- bzw. Branch-Befehl der Branch-Klasse 1 zuzuordnen ist, wird hierzu die in 3 gezeigte erste Branch-Prediktions-Einrichtung 1a verwendet.

Wird demgegenüber beim o.g. Schritt A ermittelt, dass der nächste abzuarbeitende (bedingte) Sprung- bzw. Branch-Befehl der Branch-Klasse 2 zuzuordnen ist, wird zur Ermittlung, ob der nächste, abzuarbeitenden (bedingte) Sprung- bzw. Branch-Befehls wahrscheinlich ausgeführt werden wird, oder nicht die in 3 gezeigte zweite Brauch-Prediktions-Einrichtung 1b verwendet.

Entsprechend wird – falls beim o.g. Schritt A ermittelt wird, dass der nächste abzuarbeitende (bedingte) Sprung- bzw. Branch-Befehl der Brauch-Klasse 3 zuzuordnen ist – zur Ermittlung, ob der nächste, abzuarbeitenden (bedingte) Sprung- bzw. Brauch-Befehls wahrscheinlich ausgeführt werden wird, oder nicht die in 3 gezeigte dritte Branch-Prediktions-Einrichtung 1c verwendet, usw.

Wie sich aus 3 ergibt, ist jede der Brauch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d, etc. symmetrisch aufgebaut, und kann vier verschiedene Zustände einnehmen: Zustand I (predict: „not taken, strong"), Zustand II (predict: „not taken, weak"), Zustand III (predict: „taken, weak"), und Zustand IV (predict: „taken, strong").

Alternativ ist auch die Verwendung von asymmetrisch aufgebauten Branch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d denkbar, und/oder von Branch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d mit mehr oder weniger (z.B. zwei, drei oder fünf) Zuständen.

Die Steuereinrichtung 13 überprüft den momentanen Zustand der der ermittelten Branch-Klasse des abzuarbeitenden (bedingten) Sprung- bzw. Branch-Befehls zugeordneten Branch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d (d.h. für einen der Branch-Klasse 1 zugeordneten Branch-Befehl den Zustand der ersten Branch-Prediktions-Einrichtung 1a, für einen der Branch-Klasse 2 zugeordneten Branch-Befehl den Zustand der zweiten Branch-Prediktions-Einrichtung 1b, etc.).

Ist die jeweilige Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d im o.g. Zustand I (predict: „not taken, strong"), oder im o.g. Zustand II (predict: „not taken, weak"), wird als Vorhersage für den abzuarbeitenden Branch-Befehl ermittelt: Sprung bzw. Branch wird wahrscheinlich nicht ausgeführt werden (Vorhersage: „not taken").

Befindet sich demgegenüber die jeweilige Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d im o.g. Zustand III (predict: „taken, weak"), oder IV (predict: „taken, strong"), wird als Vorhersage für den abzuarbeitenden Branch-Befehl ermittelt: Sprung bzw. Branch wird wahrscheinlich ausgeführt werden (Vorhersage: „taken").

Wird vorhergesagt, dass ein Sprung bzw. Branch wahrscheinlich ausgeführt werden wird (Vorhersage: „taken"), kann z.B. veranlasst werden, dass die „Instruction Fetch" Stufe 3a die o.g. – für den Normalbetrieb der CPU Core 11 vorgesehene – sequentielle Reihenfolge beim Laden der Maschinenbefehle aus dem Hauptspeicher durchbricht, bzw. der Pipeline-Mechanismus gestoppt wird, und/oder können entsprechende weitere, herkömmliche, aus dem Stand der Technik für den Fall einer Vorhersage „taken" bekannte Maßnahmen veranlasst werden.

Wird – was erst später, bzw. erst dann ermittelt werden kann, wenn der abzuarbeitende Branch- bzw. Sprung-Befehl die Pipeline 2 durchläuft (insbesondere bei der z.B. durch die „Execute" Stufe 3e vollzogenen Auswertung der Sprung-Bedingung) – festgestellt (z.B. durch die Steuereinrichtung 13, bzw. die „Execute" Stufe 3e), dass i) der Sprung bzw. Branch des abzuarbeitenden Branch- bzw. Sprungbefehls tatsächlich ausgeführt wurde, oder dass ii) der Sprung bzw. Brauch des abzuarbeitenden Brauch- bzw. Sprungbefehls nicht ausgeführt wurde, wird – z.B. durch die Steuereinrichtung 13 – der Zustand der entsprechenden Brauch-Prediktions-Einrichtung 1a, 1b, 1c, 1d (d.h. für einen der Brauch-Klasse 1 zugeordneten Brauch-Befehl der Zustand der ersten Branch-Prediktions-Einrichtung 1a, für einen der Brauch-Klasse 2 zugeordneten Brauch-Befehl der Zustand der zweiten Branch-Prediktions-Einrichtung 1b, etc.) entsprechend wie im folgenden genauer beschrieben aktualisiert (vgl. auch den in 4 gezeigten Verfahrens-Schritt C):

Beim o.g. Fall i), d.h. falls der Sprung bzw. Brauch des abzuarbeitenden Brauch- bzw. Sprungbefehls tatsächlich ausgeführt wurde, wird – wie in 3 gezeigt ist – bei der der ermittelten Brauch-Klasse des abzuarbeitenden (bedingten) Sprung- bzw. Brauch-Befehls zugeordneten Brauch-Prediktions-Einrichtung 1a, 1b, 1c, 1d – nicht jedoch bei den übrigen, nicht der ermittelten Brauch-Klasse des abzuarbeitenden (bedingten) Sprung- bzw. Brauch-Befehls zugeordneten Branch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d – ein durch die mit dem Symbol „T" für „taken" gekennzeichneten Pfeile veranschaulichter Zustands-Wechsel vollzogen (also bei einem vorherigen Zustand I (predict: „not taken, strong") ein Zustands-Wechsel zu einem neuen Zustand II (predict: „not taken, weak") hin, bei einem vorherigen Zustand II (predict: „not taken, weak") ein Zustands-Wechsel zu einem neuen Zustand III (predict: „taken, weak") hin, und bei einem vorherigen Zustand III (predict: „taken, weak") ein Zustands-Wechsel zu einem neuen Zustand IV (predict: „taken, strong") hin (bei einem vorherigen Zustand IV (predict: „taken, strong") verbleibt die entsprechende Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d im selben Zustand IV – vgl. die in 3 jeweils ganz rechts liegenden, mit dem Symbol „T" gekennzeichneten Pfeile)).

Demgegenüber wird beim o.g. Fall ii), d.h. falls der Sprung bzw. Brauch des abzuarbeitenden Brauch- bzw. Sprungbefehls nicht ausgeführt wurde – wie ebenfalls in 3 gezeigt ist – bei der der ermittelten Brauch-Klasse des abzuarbeitenden (bedingten) Sprung- bzw. Brauch-Befehls zugeordneten Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d – nicht jedoch bei den übrigen, nicht der ermittelten Brauch-Klasse des abzuarbeitenden (bedingten) Sprung- bzw. Brauch-Befehls zugeordneten Brauch-Prediktions-Einrichtungen 1a, 1b, 1c, 1d – ein durch die mit dem Symbol „N" für „not taken" gekennzeichneten Pfeile veranschaulichter Zustands-Wechsel vollzogen (also bei einem vorherigen Zustand IV (predict: „taken, strong") ein Zustands-Wechsel zu einem neuen Zustand III (predict: „taken, weak") hin, bei einem vorherigen Zustand III (predict: „taken, weak") ein Zustands-Wechsel zu einem neuen Zustand II (predict: „not taken, weak") hin, und bei einem vorherigen Zustand II (predict: „not taken, weak") ein Zustands-Wechsel zu einem neuen Zustand I (predict: „not taken, strong") hin (bei einem vorherigen Zustand I (predict: „not taken, strong") verbleibt die entsprechende Branch-Prediktions-Einrichtung 1a, 1b, 1c, 1d im selben Zustand I – vgl. die in 3 jeweils ganz links liegenden, mit dem Symbol „N" gekennzeichneten Pfeile)).

Bei dem vorliegenden, u.a. anhand von 4 erläuterten Brauch-Prediktions-Verfahren kann mit relativ geringem Aufwand, insbesondere relativ geringem Hardware-Aufwand eine relativ gute Treffwahrscheinlichkeit der Vorhersagen erzielt werden.

1aBranch-Prediktions-Einrichtung 1bBranch-Prediktions-Einrichtung 1cBranch-Prediktions-Einrichtung 1dBranch-Prediktions-Einrichtung 2Pipeline 3aInstruction Fetch Stufe 3bInstruction Decoding Stufe 3cAddress Generation Stufe 3dOperand Fetch Stufe 3eExecute Stufe 3fStore Result Stufe 3gUpdate Program Counter Stufe 10Mikroprozessor-System 11CPU 12Speicher-Steuereinrichtung 13Steuereinrichtung 15Mikrochip 16System-Bus 17Speicher-Einrichtung 18Speicher-Einrichtung

Anspruch[de]
  1. Branch-Prediktions-Verfahren, insbesondere zur Verwendung in einer Mikroprozessor-Einrichtung (11), welches die Schritte aufweist:

    – Ermitteln, zu welcher von mehreren vorbestimmten Branch-Klassen ein jeweils abzuarbeitender Branch-Befehl zugeordnet ist; und

    – Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird, oder nicht, abhängig von der ermittelten Branch-Klasse.
  2. Verfahren nach Anspruch 1, wobei zum Ermitteln, ob der Branch wahrscheinlich ausgeführt werden wird, oder nicht, jeweils eine der ermittelten Branch-Klasse zugeordnete Branch-Prediktions-Einrichtung (1a, 1b, 1c, 1d) verwendet wird.
  3. Verfahren nach Anspruch 2, wobei die jeweilige der ermittelten Branch-Klasse zugeordnete Branch-Prediktions-Einrichtung (1a, 1b, 1c, 1d) eine adaptive Branch-Prediktions-Einrichtung ist.
  4. Verfahren nach Anspruch 2 oder 3, welches zusätzlich den Schritt aufweist: Aktualisieren des Zustands der der ermittelten Branch-Klasse zugeordneten Branch-Prediktions-Einrichtung (1a, 1b, 1c, 1d), abhängig davon, ob der Branch des jeweils abzuarbeitenden Branch-Befehls ausgeführt wurde, oder nicht.
  5. Verfahren nach einem der vorhergehenden Ansprüche, wobei beim Ermitteln der dem jeweils abzuarbeitenden Brauch-Befehl zugeordneten Brauch-Klasse die Befehls-Länge des jeweils abzuarbeitenden Brauch-Befehls untersucht wird.
  6. Verfahren nach Anspruch 5, wobei beim Untersuchen der Befehls-Länge des jeweils abzuarbeitenden Brauch-Befehls ermittelt wird, ob es sich beim jeweils abzuarbeitenden Branch-Befehl um einen langen, oder kurzen Branch-Befehl handelt.
  7. Verfahren nach Anspruch 6, wobei ermittelt wird, dass es sich beim jeweils abzuarbeitenden Branch-Befehl um einen langen Branch-Befehl handelt, wenn die Befehls-Länge des jeweils abzuarbeitenden Branch-Befehls 32 Bit beträgt.
  8. Verfahren nach Anspruch 6 oder 7, wobei ermittelt wird, dass es sich beim jeweils abzuarbeitenden Branch-Befehl um einen kurzen Branch-Befehl handelt, wenn die Befehls-Länge des jeweils abzuarbeitenden Branch-Befehls 16 Bit beträgt.
  9. Verfahren nach einem der vorhergehenden Ansprüche, wobei beim Ermitteln der dem jeweils abzuarbeitenden Branch-Befehl zugeordneten Branch-Klasse die Sprungrichtung des jeweils abzuarbeitenden Brauch-Befehls untersucht wird.
  10. Verfahren nach Anspruch 9, wobei beim Untersuchen der Sprungrichtung des jeweils abzuarbeitenden Brauch-Befehls ermittelt wird, ob der jeweils abzuarbeitende Brauch-Befehl ein Vorwärts-, oder ein Rückwärts-Brauch ist.
  11. Verfahren nach einem der vorhergehenden Ansprüche, wobei beim Ermitteln der dem jeweils abzuarbeitenden Brauch-Befehl zugeordneten Brauch-Klasse der Befehlstyp des jeweils abzuarbeitenden Brauch-Befehls untersucht wird.
  12. Verfahren nach Anspruch 11, wobei beim Untersuchen des Befehlstyps des jeweils abzuarbeitenden Brauch-Befehls ermittelt wird, ob es sich beim jeweils abzuarbeitenden Brauch-Befehl um einen Integer-, oder einen Load-Store-Branch-Befehl handelt.
  13. Verfahren nach einem der vorhergehenden Ansprüche, wobei beim Ermitteln der dem jeweils abzuarbeitenden Brauch-Befehl zugeordneten Brauch-Klasse die Funktion des jeweils abzuarbeitenden Brauch-Befehls untersucht wird.
  14. Verfahren nach einem der vorhergehenden Ansprüche, wobei beim Ermitteln der dem jeweils abzuarbeitenden Brauch-Befehl zugeordneten Brauch-Klasse der Thread Identifier des jeweils abzuarbeitenden Brauch-Befehls untersucht wird.
  15. Mikroprozessor-Einrichtung (11), mit mehreren, jeweils einer von mehreren vorbestimmten Branch-Klassen zugeordneten Brauch-Prediktions-Einrichtungen (1a, 1b, 1c, 1d).
  16. Mikroprozessor-Einrichtung (11) nach Anspruch 15, mit mehr als zwei, insbesondere mehr als drei oder vier jeweils einer der mehreren vorbestimmten Branch-Klassen zugeordneten Brauch-Prediktions-Einrichtungen (1a, 1b, 1c, 1d).
  17. Mikroprozessor-Einrichtung (11) nach Anspruch 15 oder 16, bei welcher die Brauch-Prediktions-Einrichtungen (1a, 1b, 1c, 1d) adaptive Brauch-Prediktions-Einrichtungen sind.
  18. Mikroprozessor-Einrichtung (11) nach einem der Ansprüche 15 bis 17, mit einer Einrichtung (13) zum Ermitteln, zu welcher der mehreren vorbestimmten Branch-Klassen ein jeweils abzuarbeitender Brauch-Befehl zugeordnet ist.
  19. Mikroprozessor-Einrichtung (11) nach Anspruch 18, bei welcher die Einrichtung (13) zum Ermitteln, zu welcher der mehreren vorbestimmten Branch-Klassen der jeweils abzuarbeitende Brauch-Befehl zugeordnet ist so ausgestaltet und eingerichtet ist, dass diese die Befehls-Länge des jeweils abzuarbeitenden Brauch-Befehls untersucht.
  20. Mikroprozessor-Einrichtung (11) nach Anspruch 18 oder 19, bei welcher die Einrichtung (13) zum Ermitteln, zu welcher der mehreren vorbestimmten Branch-Klassen der jeweils abzuarbeitende Brauch-Befehl zugeordnet ist so ausgestaltet und eingerichtet ist, dass diese die Sprungrichtung des jeweils abzuarbeitenden Branch-Befehls untersucht.
  21. Mikroprozessor-Einrichtung (11) nach einem der Ansprüche 18 bis 20, bei welcher die Einrichtung (13) zum Ermitteln, zu welcher der mehreren vorbestimmten Branch-Klassen der jeweils abzuarbeitende Brauch-Befehl zugeordnet ist so ausgestaltet und eingerichtet ist, dass diese den Befehlstyp des jeweils abzuarbeitenden Brauch-Befehls untersucht.
Es folgen 4 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

  Patente PDF

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com