DE112004002877T5

DE112004002877T5 - TLB-correlated branch predictor and method of use

Info

Publication number: DE112004002877T5
Application number: DE112004002877T
Authority: DE
Inventors: Chunrong Lai
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2004-06-02
Filing date: 2004-06-02
Publication date: 2007-05-03
Also published as: WO2005119428A1; CN1961285B; CN1961285A; JP2008501166A; JP4533432B2

Abstract

Verzweigungsvorhersager, umfassend:
eine Verzweigungsvorhersageschaltung zum Vorhersagen eines Verzweigungsergebnisses in einer Ausführungsanweisung in einem Prozessor, unter Verwendung einer Eingabe von einem translation look-aside Puffer.Branch predictor, comprising:
a branch prediction circuit for predicting a branch result in an execution instruction in a processor using an input from a translation look-aside buffer.

Description

Technisches Gebiettechnical area

Ausführungsformen der vorliegenden Erfindung betreffen Hochleistungsprozessoren und insbesondere einen Anweisungsverzweigungsvorhersager unter Verwendung einer translation look-aside Puffer (auch Adreßumsetzerpuffereingabe) und eines globalen Spung- oder Verzweigungsverlaufs mit dynamischer Länge.embodiments The present invention relates to high performance processors and In particular, an instruction branch predictor using a translation look-aside buffer (also address translator buffer input) and a global spur or branch history with dynamic Length.

Stand der TechnikState of technology

Die genaue Sprung- oder Verzweigungsvorhersage ist immer wichtiger geworden, um die potenzielle Leistung eines superskalaren, Out-of-Order-Prozessors zu erfüllen, da sich sowohl die Ausgabegeschwindigkeit von Verzweigungsanweisungen als auch die Leitungstiefe von Anweisungen erhöht haben. Einige Verzweigungsvorhersager aus dem Stand der Technik sind entweder als Verzweigungsvorhersager ohne einen globalen Verlauf oder als Zwei-Ebenen-Verzweigungsvorhersager mit einem globalen Verlauf implementiert.The accurate branch or branch prediction has become increasingly important the potential performance of a superscalar, out-of-order processor to fulfill, as both the output speed of branch instructions as well as the guidance depth of instructions. Some branch predicators The prior art are either branch prediction without a global history or as a two-level branch predictor with a global one History implemented.

In einigen Verzweigungsvorhersagern besteht der globale Verlauf aus m kürzlichen Verzweigungen und wird in einem globalen in-Bit Schieberegister implementiert, in dem jedes Bit aufzeichnet, ob die Verzweigung genommen wurde oder nicht. Leider zeichnet das globale Schieberegister nur einen globalen Verlauf fester Länge auf. Jüngste Forschungen haben jedoch ergeben, daß verschiedene Anweisungen von verschiedenen Programmen eine bessere Vorhersagegenauigkeit erfahren können, indem unterschiedliche Längen des globalen Verlaufs eingesetzt werden.In Some branch forecasters pass the global history m recently Branches and gets into a global in-bit shift register implemented, in which each bit records whether the branching was taken or not. Unfortunately, the global shift register draws only a global history of fixed length. However, recent research has show that different Instructions from different programs provide better predictive accuracy can learn by different lengths the global history.

1 ist ein Blockschaltdiagramm eines Verzweigungsvorhersagers, der aus dem Stand der Technik bekannt ist. In 1 enthält ein m-Bit-Verlaufsschieberegister 110 eine Einfach-Bit-Schiebeeingabe und eine Einfach-Bit-Schiebeausgabe, wobei die Einfach-Bit-Schiebeeingabe verwendet wird, um eine Anzeige darüber zu empfangen, daß eine Verzweigung für eine bestimmte Anweisung genommen worden ist, und eine „0" wird verwendet, um anzuzeigen, daß die Verzweigung nicht genommen worden ist. Das Verlaufsschieberegister 110 wird verwendet, um einen globalen Verzweigungsvorhersageverlauf fester Länge (d.h. m-Bit-Länge) zu speichern, um den signifikantesten Bitwert auszuschieben, d.h. den ersten Bitwert, und um den gesamten zu speichernden globalen m-Bit-Verzweigungsvorhersageverlaufswert auszugeben. 1 Figure 4 is a block diagram of a branch predictor known in the art. In 1 contains an m-bit history shift register 110 a single-bit shift input and a single-bit shift output, where the single-bit shift input is used to receive an indication that a branch has been taken for a particular instruction, and a "0" is used to indicate that the branch has not been taken 110 is used to store a fixed length global branch prediction history (ie, m-bit length) to shift out the most significant bit value, ie, the first bit value, and to output the entire global m-bit branch prediction history value to be stored.

In 1 ist ein Verlaufsschieberegister 110 mit einem EXKLUSIV-ODER-Gate 120 gekoppelt, und das Verlaufsschieberegister 110 gibt einen im Verlaufsschieberegister 110 gespeicherten globalen in-Bit-Verzweigungsvorhersageverlaufwert an eine erste Eingabe des EXKLUSIV-ODER-Gates 120 aus. Das EXKLUSIV-ODER-Gate 120 ist auch mit einem Verzweigungsadressenregister 130 gekoppelt, das m-Bit Verzweigungsadressen an eine zweite Eingabe des EXKLUSIV-ODER-Gates 120 ausgibt. Das EXKLUSIV-ODER-Gate 120 gibt einen globalen m-Bit-Verlauf an eine Musterverlaufstabelle 140 aus, wenn die eingegebene in-Bit-Verzweigungsadresse von dem Verzweigungsadressenregister 130 mit dem eingegebenen globalen in-Bit-Verlauf von dem Verlaufsschieberegister 110 übereinstimmt. Es sei darauf hingewiesen, daß die m-Bit-Verzweigungsadresse von dem Verzweigungsadressenregister 130 verschoben, erweitert oder geschnitten werden kann, bevor sie ausgegeben wird, um der Anzahl von Bits, die von dem Verlaufsschieberegister 110 ausgegeben werden, zu entsprechen. Dadurch ist die Anzahl von Bits in dem m-Bit-Verzweigungsadressenbitstring, der von dem Verzweigungsadressenregister 130 ausgegeben wird, an die Bits des eingegebenen globalen Vorhersagewerts von dem Verlaufsschieberegister 110 angepaßt, obwohl die Länge des globalen Verzweigungsvorhersageverlaufswerts variieren kann.In 1 is a history shift register 110 with an EXCLUSIVE-OR gate 120 coupled, and the history shift register 110 gives one in the history shift register 110 stored global in-bit branch prediction history value to a first input of the EXCLUSIVE-OR gate 120 out. The EXCLUSIVE-OR gate 120 is also with a branch address register 130 coupled, the m-bit branch addresses to a second input of the EXCLUSIVE-OR gate 120 outputs. The EXCLUSIVE-OR gate 120 Gives a global m-bit history to a pattern history table 140 when the inputted in-bit branch address from the branch address register 130 with the entered global in-bit history from the history shift register 110 matches. It should be noted that the m-bit branch address is from the branch address register 130 can be moved, expanded or cut before it is output to the number of bits allocated by the history shift register 110 to be output. This is the number of bits in the m-bit branch address bit string that is from the branch address register 130 to the bits of the input global prediction value from the history shift register 110 although the length of the global branch prediction history value may vary.

In 1 besteht die Musterverlaufstabelle 140 aus 2^m Einträgen, wobei jeder Eintrag in der Tabelle einen „lokalen Verlauf" enthält. Die lokale Verlaufsinformation wird allgemein in einem 2-Bit-gesättigten Verzweigungsvorhersager gespeichert. Der ausgegebene globale m-Bit-Verlauf von dem EXKLUSIV-ODER-Gate 120 wird verwendet, um einen Eintrag von der Musterverlaufstabelle 140 auszuwählen, der dann verwendet wird, um die Vorhersage auszuführen. Durch diesen Aufbau wird ein fester Vorhersageeintrag verwendet, um die gültige Verlaufsinformation zu speichern, wobei die verschiedenen Verzweigungsanweisungen miteinander korreliert werden.In 1 exists the pattern history table 140 from 2 ^m entries, each entry in the table contains a "local history". The local history information is generally stored in a 2-bit saturated branch predictor. The output global m-bit history of the EXCLUSIVE-OR gate 120 is used to make an entry from the pattern history table 140 which is then used to perform the prediction. By this construction, a fixed prediction entry is used to store the valid history information, with the various branch instructions correlated with each other.

In 1 führt ein 2-Bit-Vorhersager einen 2-Bit-Zähler. Wenn auf ihn zugegriffen wird, wird er eine Verzweigungsvorhersage basierend auf seinem Inhalt ausgeben. Beispielsweise wird er für eine Verzweigung ein „genommen" vorhersagen, wenn „10" der 2-Bit-Inhalt des Vorhersagers ist (d.h. der Musterverlaufstabelleneintrag), der dieser Verzweigung zugeordnet ist. Etwas später wird der Inhalt aktualisiert, nachdem die wirkliche Richtung bekannt ist. Beispielsweise wird „10" zu „11" aktualisiert, wenn die Verzweigung „genommen" wird, und zu „01" aktualisiert, wenn die Verzweigung „nicht genommen" wird. Wenn der 2-Bit-Zählerwert größer oder gleich der Hälfte seines Maximalwerts ist, also 2^2-1 = 2, wird von der Verzweigung allgemein vorhergesagt, daß sie nicht genommen wird. Wenn der 2-Bit-Zählerwert weniger als 2 ist, wird von der Verzweigung dagegen vorhergesagt, daß sie nicht genommen wird. Anders ausgedrückt, wenn der 2-Bit-Zähler entweder „10" (d.h. 2) oder „11" (d.h. 3) ist, wird die Verzweigung als genommen vorhergesagt und wenn der 2-Bit-Zähler entweder „00" (d.h. 0) oder „01" (d.h. 1) enthält, wird die Verzweigung als nicht genommen vorhergesagt.In 1 a 2-bit predictor performs a 2-bit counter. If accessed, it will issue a branch prediction based on its content. For example, it will predict a "taken" for a branch if "10" is the 2-bit content of the predictor (ie, the pattern history table entry) associated with that branch. Somewhat later, the content is updated after the real direction is known. For example, "10" is updated to "11" when the branch is "taken", and updated to "01" if the branch is "not taken". If the 2-bit counter value is greater than or equal to half of its maximum value, that is, 2 ^2-1 = 2, the branch is generally predicted to not be taken. On the other hand, if the 2-bit counter value is less than 2, the branch is predicted not to be taken. In other words, if the 2-bit counter is either "10" (ie 2) or "11" (ie 3), the branch is predicted taken and if the 2-bit counter is either "00" (ie 0) or "01" (ie 1), the branch is predicted not taken.

Während der lokale Verlauf bedeutet, daß die Ausgabe einer Verzweigung von ihrem eigenen Verlauf abhängt, bedeutet der globale Verlauf, daß die Ausgabe einer Verzweigung von den Verläufen anderer Verzweigungen abhängt. Wenn die erste Verzweigung in dem unten dargestellten Kurzcodebeispiel „genommen" ausgibt, dann wird die zweite Verzweigung ebenfalls „genommen" ausgeben. Dann wird ein unabhängiger 2-Bit-Verzweigungsvorhersager (der Musterverlaufeintrag mit globalem Verlauf ist entsprechend der Verzweigung d==0 genommen) verwendet, um diese Information mit dem globalen Verlauf und dem 2-Ebenen-Verzweigungsvorhersageschema zu halten.During the local history means that the Output of a branch depends on its own history means the global course that the Output of a branch from the courses of other branches depends. If the first branch in the short code example shown below outputs "taken", then then issue the second branch "taken", then become an independent 2-bit branch predictor (The pattern history entry with global history is corresponding taken from the branch d == 0) used this information with the global history and the 2-level branch prediction scheme to keep.

Da das globale Verlaufsregister 110 in 1 für alle Fälle nur einen globalen Verlauf mit fester Länge aufzeichnet, ist die Genauigkeit der Verzweigungsvorhersagen basierend auf dem globalen Verlauf fester Länge leider nicht gut genug. Verzweigungsvorhersagen, die auf dem globalen Verlauf fester Länge beruhen, unterscheiden zum Beispiel nicht immer genau die vorherigen Verzweigungsanweisungen, die mit den aktuellen Verzweigungsanweisungen korreliert waren. Analog werden mittels des globalen Verlaufs fester Länge nicht nur andere Verzweigungsanweisungen, die nicht korreliert sind, nicht immer genau vorhergesagt, sondern die Korrelationen bestehen in einigen Zusammenhängen und in anderen Zusammenhängen, wo sie bestehen sollten, bestehen sie nicht. Zum Beispiel, wenn der Speicheroperand X, Y in dem Codebeispiel unten aufgrund von Datenlokalität benachbarte Werte aufweist. Der Verzweigungsvorhersager kann wie oben beschrieben ausgeführt werden. Das Verhältnis wird jedoch mit dem Verlust an Datenlokalität gebrochen.Because the global history register 110 in 1 Unfortunately, the accuracy of the branch predictions based on the fixed-length global history is not good enough in all cases. For example, branch predictions based on the fixed-length global history do not always differ exactly from the previous branch statements that correlated with the current branch instructions. Similarly, using the fixed length global history, not only are other branch instructions that are uncorrelated not always accurately predicted, but the correlations exist in some contexts and they do not exist in other contexts where they should exist. For example, if the memory operand X, Y in the code example below has adjacent values due to data locality. The branch predictor may be executed as described above. However, the ratio is broken with the loss of data locality.

Dieser Fall zeigt, daß die globalen Korrelationen manchmal nicht nur auf dem globalen Verlauf oder der Verzweigungsadresse beruhen, sondern auch auf der Datenlokalität. Der Verlust an Datenlokalität, wie in dem obigen Beispiel gezeigt, kann auftreten, wenn in der zweiten Anweisung d gleich X gesetzt wird und d wird in der dritten Anweisung bestimmt, nicht gleich Y zu sein. Dadurch können die d=Y Bedingungsanweisungen nicht ausgeführt werden. Dies kann auch den globalen Verlauf verletzen. Daher ist es wünschenswert, einen Verzweigungsvorhersager zu haben, der die oben genannten Mängel vermeiden würde.This Case shows that the sometimes global correlations not only on the global history or the branch address, but also on the data locality. The loss at data locality, as shown in the above example, can occur when in the second instruction d is set equal to X and d becomes in the third Instruction determines not to be equal to Y This allows the d = Y conditional statements are not executed. This can too violate the global course. Therefore, it is desirable to have a branch predictor to have that would avoid the above shortcomings.

Kurze Beschreibung der ZeichnungenShort description the drawings

1 ist ein Blockschaltdiagramm eines aus dem Stand der Technik bekannten Verzweigungsvorhersagers. 1 Figure 4 is a block diagram of a branch predictor known in the art.

2 ist ein Blockschaltdiagramm eines mit einem translation look-aside Puffer korrelierten Spung- oder Verzweigungsvorhersagers für einen Prozessor gemäß einer Ausführungsform der vorliegenden Erfindung. 2 FIG. 12 is a block diagram of a translation or spin-off predictor associated with a translation look-aside buffer for a processor in accordance with an embodiment of the present invention. FIG.

3 ist ein Flussdiagramm eines Verfahrens gemäß einer Ausführungsform der vorliegenden Erfindung. 3 FIG. 10 is a flowchart of a method according to an embodiment of the present invention. FIG.

4 ist ein Blockdiagramm eines Computersystems, welches ein oder mehrere Prozessoren und Speicher enthält, zur Verwendung gemäß einer Ausführungsform der vorliegenden Erfindung. 4 FIG. 10 is a block diagram of a computer system including one or more processors and memory for use in accordance with an embodiment of the present invention. FIG.

Ausführliche BeschreibungDetailed description

Ausführungsformen der vorliegenden Erfindung können eine Vorrichtung und ein Verfahren für mit translation look-aside Puffern korrelierte Verzweigungsvorhersage betreffen, welche einen globalen Verlauf, einen mit einem translation look-aside Puffer korrelierten Verzweigungsvorhersager und/oder einen mit einem translation look-aside Puffer korrelierten Zwei-Ebenen-Verzweigungsvorhersager, beide mit und ohne einen Verzweigungsverlauf dynamischer Länge, enthalten können, jedoch nicht darauf beschränkt sind. Gemäß einer Ausführungsform der vorliegenden Erfindung kann ein Prozessor beispielsweise einen korrelierten Verzweigungsvorhersager mit einer Eingabeleitung von einem Adressumsetzer zu einem globalen Verzweigungsverlaufschieberegister enthalten. Die Eingabeleitung, die anzeigen kann, wenn in dem translation look-aside Puffer ein Fehler aufgetreten ist, kann verwendet werden, um das globale Verzweigungsverlaufsschieberegister zu leeren. Da der globale Verzweigungsverlauf, der in dem globalen Verzweigungsverlaufsschieberegister gespeichert ist, durch Datenlokalität gezogen werden kann kann das Leeren des globalen Verzweigungsverlaufsschieberegister bei einem Fehler im translation look-aside Puffer verhindern helfen, daß ein korrupter globaler Verzweigungsverlauf von Nicht-Datenlokalität vermieden wird, der durch in dem translation look-aside Puffer fehlende Daten verursacht wird.embodiments of the present invention a device and a method for translation look-aside Buffers relate to correlated branch prediction, which is a global history, one with a translation look-aside buffer correlated branch predictors and / or one with a translation look-aside buffers correlated two-level branch predictors, both with and however, without a dynamic length branching history not limited to this are. According to one embodiment For example, in the present invention, a processor may be one correlated branch predictors with an input line of an address translator to a global branch history shift register contain. The input line, which can indicate if in the translation look-aside buffer an error has occurred can be used to clear the global branch history shift register. There the global branch history stored in the global branch shift register is, by data locality may be to flush the global branch history shift register help prevent an error in the translation look-aside buffer the existence Corrupt global branching of non-data locality avoided is missing from the data missing in the translation look-aside buffer is caused.

2 ist ein Blockschaltdiagramm eines mit einem translation look-aside Puffer korrelierten Verzweigungsvorhersagers für einen Prozessor gemäß einer Ausführungsform der vorliegenden Erfindung. In 2 kann ein Prozessor 200 ein m-Bit-Verlaufsschieberegister 210 enthalten, das eine erste Einfach-Bit-Schiebeeingabe (die analog zu der Einfach-Bit-Schiebeeingabe in 1 sein kann), eine zweite Einfach-Bit-Schiebeeingabe und eine Einfach-Bit-Schiebeausgabe (die analog zu der Einfach-Bit-Schiebeausgabe in 1 sein kann) enthalten kann, wobei die erste Einfach-Bit-Schiebeeingabe eine Anzeige empfängt, ob die Verzweigung für eine bestimmte Anweisung genommen oder nicht genommen wurde. Das Verlaufsschieberegister 210 kann verwendet werden, um einen globalen Verzweigungsverlauf dynamischer Länge für eine Ausführungsanweisung zu speichern. Im allgemeinen kann das signifikanteste Bit mit einem Wert von 1 verwendet werden, um die gültige Verlaufslänge anzuzeigen, beispielsweise, wenn das signifikanteste Bit 1 in dem fünften Bit eines m-Bit-Schieberegisters ist, kann die Länge des globalen Verlaufs auf m-5 Bits bestimmt werden. Im Ergebnis zeigt der signifikanteste „1"-Wert nicht an, ob eine Verzweigung aufgetreten ist. Gemäß einer Ausführungsform der vorliegenden Erfindung kann ein „1"-Wert als das Aktivierungssignal verwendet werden, um anzuzeigen, daß eine Verzweigung genommen wurde, und eine „0" kann als ein Nicht-Aktivierungssignal verwendet werden, um anzuzeigen, daß die Verzweigung nicht genommen wurde. Das Verlaufsschieberegister 210 kann verwendet werden, um einen globalen Verzweigungsvorhersageverlauf dynamischer Länge mit einer maximalen Länge von m-1 Bits zu speichern, und den signifikantesten Bitwert auszugeben, das heißt den m-1-Bitwert. Daher kann ein „0000...01"-String einen globalen Verlauf der Länge Null anzeigen, was anzeigen kann, daß der globale Verlauf kürzlich von dem Verlaufsschieberegister 210 gelöscht wurde. Analog kann gemäß einer Ausführungsform der vorliegenden Erfindung ein „0000...00"-String als bedeutungslos angesehen werden, da er eine nicht-existente globale Verlaufslänge anzeigen kann, und ein „1X...Y"-String (wobei X und Y jeweils gleich „0" oder „1" sind) kann so aufgefaßt werden, daß er die längstmögliche globale Verlaufslänge, die das Register enthalten kann, enthält, nämlich eine Länge von m-1 Bits. 2 FIG. 10 is a block diagram of a translation predictor associated with a translation look-aside buffer for a processor according to one embodiment of the present invention. FIG. In 2 can be a processor 200 an m-bit history shift register 210 containing a first single-bit shift input (analogous to the single-bit shift input in FIG 1 may be), a second single-bit shift input and a one-bit shift output (analogous to the one-bit shift output in 1 can), the first single-bit shift input receiving an indication as to whether the branch was taken or not taken for a particular instruction. The history shift register 210 can be used to store a dynamic length global branching history for an execution statement. In general, the most significant bit with a value of 1 may be used to indicate the valid history length, for example, if the most significant bit is 1 in the fifth bit of an m-bit shift register, the length of the global history may be m-5 bits be determined. As a result, the most significant "1" value does not indicate whether a branch has occurred According to an embodiment of the present invention, a "1" value may be used as the activation signal to indicate that a branch has been taken and a "1" value. 0 "may be used as a non-activation signal to indicate that the branch has not been taken 210 may be used to store a dynamic length global branch prediction history having a maximum length of m-1 bits and to output the most significant bit value, that is, the m-1 bit value. Therefore, a "0000 ... 01" string may indicate a zero-length global history, which may indicate that the global history is recently from the history shift register 210 was deleted. Similarly, according to one embodiment of the present invention, a "0000 ... 00" string may be considered meaningless, as it may indicate a non-existent global history length, and a "1X ... Y" string (where X and Y each equal to "0" or "1") can be considered to include the longest possible global history length that the register can contain, namely, a length of m-1 bits.

In 2 kann das Verlaufsschieberegister 210 mit einem EXKLUSIV-ODER-Gate 220 gekoppelt sein, und das Verlaufsschieberegister 210 kam mit einem globalen m-Bit-Verzweigungsvorhersageverlaufwert, der in einem Verlaufsschieberegister 210 gespeichert ist, an eine erste Eingabe des EXKLUSIV-ODER-Gates 220 ausgeben. Das EXKLUSIV-ODER-Gate 220 kann auch mit einem Verzweigungsadressenregister 230 gekoppelt sein, das m-Bit-Verzweigungsadressen an eine zweite Eingabe des EXKLUSIV-ODER-Gate 220 ausgeben kann. Das EXKLUSIV-ODER-Gate 220 kann einen globalen m-Bit-Verlauf an eine Musterverlaufstabelle 240 ausgeben, wenn die eingegebene m-Bit-Verzweigungsadresse von dem Verzweigungsadressenregister 230 mit dem eingegebenen globalen m-Bit-Verlauf von dem Verlaufsschieberegister 210 übereinstimmt. Es sei darauf hingewiesen, daß m-Bit Verzweigungsadressen von dem Verzweigungsadressenregister 230 verschoben, erweitert oder geschnitten werden können, bevor sie ausgegeben werden, um der Anzahl von Bits, die von dem Verlaufsschieberegister 210 ausgegeben werden, zu entsprechen. Dadurch stimmt die Anzahl von Bits in dem m-Bit-Verzweigungsadressenbitstring, der von dem Verzweigungsadressenregister 230 ausgegeben wird, allgemein immer mit den Bits in dem eingegebenen globalen Verzweigungsvorhersagewert von dem Verlaufsschieberegister 210 überein, obwohl die Länge des globalen Verzweigungsvorhersageverlaufswerts variieren kann.In 2 can the history shift register 210 with an EXCLUSIVE-OR gate 220 be coupled, and the history shift register 210 came with a global m-bit branch prediction history value stored in a history shift register 210 is stored to a first input of the EXCLUSIVE-OR gate 220 output. The EXCLUSIVE-OR gate 220 can also use a branch address register 230 be coupled to the m-bit branch address to a second input of the EXCLUSIVE-OR gate 220 can spend. The EXCLUSIVE-OR gate 220 can apply a global m-bit history to a pattern history table 240 when the input m-bit branch address from the branch address register 230 with the entered m-bit global history from the history shift register 210 matches. It should be noted that m-bit branch addresses from the branch address register 230 can be moved, expanded or cut before they are output to the number of bits allocated by the history shift register 210 to be output. This will set the number of bits in the m-bit branch address bit string received from the branch address register 230 generally always with the bits in the input global branch prediction value of History shift register 210 although the length of the global branch prediction history value may vary.

In 2 kann die Musterverlaufstabelle 240 aus 2^m Einträgen bestehen, wobei jeder Eintrag in der Tabelle einen „lokalen Verlauf" enthalten kann. Die lokale Verlaufsinformation kann allgemein in einem 2-Bit gesättigten Verzweigungsvorhersager gespeichert werden. Der ausgegebene globale m-Bit-Verlauf von dem EXKLUSIV-ODER-Gate 220 kann verwendet werden, um einen Eintrag von der Musterverlaufstabelle 240 auszuwählen, der verwendet werden kann, um die Vorhersage auszuführen. Durch diesen Aufbau kann ein fester Vorhersageeintrag verwendet werden, um die gültige Verlaufsinformation zu speichern, wo die verschiedenen Verzweigungsanweisungen miteinander korreliert werden.In 2 can the pattern history table 240 consist of 2 ^m entries, where each entry in the table may contain a "local history." The local history information may generally be stored in a 2-bit saturated branch predictor., The output global m-bit history from the EXCLUSIVE-OR gate 220 can be used to make an entry from the pattern history table 240 which can be used to perform the prediction. By this construction, a fixed prediction entry can be used to store the valid history information where the various branch instructions are correlated with each other.

Allgemein kann in 2 ein Verlaufsschieberegister 210 wie in 1 beschrieben verschoben werden, mit zwei Ausnahmen, nämlich, wenn der globale Verlauf gelöscht werden soll und wenn der globale Verlaufstringwert gleich „1XYZ..." ist, wobei X, Y und Z jeweils gleich „0" oder „1" sein können. Zuerst kann in 2, wenn das Verlaufsschieberegister 210 gelöscht werden soll, der globale Verzweigungsverlaufsstring im Verlaufsschieberegister 210 geleert werden und gleich „0000...01" gesetzt werden. Als zweites kann, wenn das Verlaufsschieberegister 210 einen globalen in-1-Bit-langen Verzweigungsverlauf enthält, was bedeutet, daß „1" in dem signifikantesten Bit des Verlaufsscheiberegisters 210 gespeichert sein kann (d.h. Bit 1), der „1"-Wert, der in Bit 1 gespeichert ist, geführt werden und der Bitwert in Bit 2 ausgeschoben werden.General can be in 2 a history shift register 210 as in 1 with two exceptions, namely, if the global history is to be deleted and if the global history string is equal to "1XYZ ...", where X, Y and Z can be equal to "0" or "1" respectively can in 2 if the history shift register 210 to delete, the global branch history string in the history shift register 210 be emptied and set equal to "0000 ... 01." Second, if the history shift register 210 contains a global one-bit long branch history, meaning that "1" is in the most significant bit of the history slice register 210 may be stored (ie, bit 1), the "1" value stored in bit 1 is passed, and the bit value in bit 2 is shifted out.

Verlaufsschieberegister 210 kann auch mit einem verriegelten Speicher 250, beispielsweise einen Dreistatuspuffer gekoppelt sein, der ein Signal von einem (nicht gezeigten) translation look-aside Puffer („TLB") empfangen kann, das anzeigt, daß in dem TLB ein Fehler aufgetreten ist, und der verriegelte Speicher 250 kann auch einen m-Bit-Eingabeleerwert empfangen und speichern. Der m-Bit-Eingabeleerwert kann alle „0" enthalten, außer an der Position ganz rechts, welche beispielsweise eine „1" sein kann, wobei m=16, ein 16-Bit-Eingabeleerwert kann gleich „0000000000000001" sein. Wenn ein TLB-Fehler auftritt, kann ein Aktivierungssignal, das anzeigt, daß ein TLB-Fehler aufgetreten ist, durch den TLB auf einer TLB-Fehlerleitung 260 bestätigt werden (nicht gezeigt). Wenn das Aktivierungssignal, das anzeigt, daß ein TLB-Fehler aufgetreten ist, den verriegelten Speicher 250 erreicht, kann der m-Bit-Eingabeleerwert, der in dem verriegelten Speicher 250 gespeichert ist, in das Verlaufsschieberegister 210 gelesen werden. Dadurch kann das Verlaufsschieberegister 210 „geleert" werden, so daß der gegenwärtig in dem Verlaufsschieberegister 210 gespeicherte m-Bit-Wert durch einen m-Bit-Wert, beispielsweise „0000000000000001" aus dem verriegelten Speicher 250 überschrieben werden kann.History shift register 210 can also with a locked memory 250 For example, a tri-state buffer may be coupled which may receive a signal from a translation look-aside buffer ("TLB") (not shown) indicating that an error has occurred in the TLB and the latched memory 250 can also receive and store an m-bit input value. The m-bit input raw value may include all "0s" except at the rightmost position, which may be a "1", for example, where m = 16, a 16-bit input value may be equal to "0000000000000001" Error occurs, an enable signal indicating that a TLB error has occurred may be issued by the TLB on a TLB error line 260 confirmed (not shown). If the activation signal indicating that a TLB error has occurred, the latched memory 250 can reach the m-bit input value stored in the latched memory 250 is stored in the history shift register 210 to be read. This allows the history shift register 210 Be "emptied", so that currently in the history shift register 210 stored m-bit value by an m-bit value, for example, "0000000000000001" from the latched memory 250 can be overwritten.

In 2 kann eine Rückkopplungsschaltung 270 mit einer Bit-1-Position und einer Bit-2-Position in dem Verlaufsschieberegister 210 gekoppelt sein. Die Rückkopplungsschleife 270 kann ein UND-Gate 280 enthalten, das mit dem Verlaufsschieberegister 210 gekoppelt ist, um das ausgegebene signifikanteste Bit zu empfangen, und mit einem ODER-Gate 290 gekoppelt sein, das mit der Bit-1- und der Bit-2-Position des Verlaufsschieberegisters 210 gekoppelt sein kann. Die Rückkopplungsschaltung 270 kann verwendet werden, um einen signifikantesten Bitwert von 1 in der m-1-Bit-Position in dem Verlaufsschieberegister zu halten. Insbesondere kann eine erste Eingabe 281 des UND-Gates 280 mit der Ausgabe des Verlaufsschieberegisters 210 gekoppelt sein. Eine zweite Eingabe 283 des UND-Gates 280 kann einen „1"-Wert empfangen, der mit einem Wert der Ausgabe des Verlaufsschieberegisters 210 UND-verknüpft sein kann, um dazu zu führen, daß ein UND-Wert von dem UND-Gate 280 über eine Ausgabe 287 an eine erste Eingabe 291 des ODER-Gates 290 ausgegeben wird. Eine zweite Eingabe des ODER-Gates 290 kann mit der Bit-2-Position in dem Verlaufsschieberegister 210 gekoppelt sein und einen Wert davon empfangen. Eine Ausgabe 297 des ODER-Gates 290 kann mit einem ODER-Wert in der Bit-1-Position des Verlaufsschieberegisters 210 gekoppelt sein und ihn ausgeben. Da die zweite Eingabe 283 des UND-Gates 280 eine eingestellte Eingabe von „1" hat, können nur zwei Eingabekombinationen möglich sein, nämlich (0,1) und (1,1). Unabhängig davon können nur zwei Ausgabewerte von einem UND-Gate 280 möglich sein. Das heißt, eine „1" kann von einem ODER-Gate 280 ausgegeben werden, wenn der Ausgabewert der m-1-Bit-Position in dem Verlaufsschieberegister 210 ebenfalls „1" ist, und eine „0" kann von dem UND-Gate 280 ausgegeben werden, wenn der Ausgabewert der m-1-Bit-Position in dem Verlaufsschieberegister 210 eine „0" ist. Obwohl das ODER-Gate 290 auch nur dieselben zwei möglichen Ausgabewerte haben kann (d.h. „0" oder „1"), können analog die Ergebnisse aus vier möglichen Eingabekombinationen resultieren, nämlich (0,0), (0,1), (1,0) und (1,1), da weder die erste Eingabe 291 noch die zweite Eingabe 293 an das ODER-Gate 290 auf einen einzigen Wert beschränkt sind. Wie in Tabelle 1, einer logischen ODER-Tabelle, zu sehen ist, kann eine „1" als Ergebnis von drei der vier möglichen Eingabewertkombinationen ausgegeben werden. Da das UND-Gate 280 immer eine „1" ausgeben wird, wenn der Bit-1-Wert in dem Verlaufsschieberegister 210 „1" ist, ist daher ersichtlich, daß die Rückkopplungsschaltung 270 den „1"-Wert in der Bit-1-Position führen wird, bis das Verlaufsschieberegister 210 durch einen TLB-Fehler geleert wird.In 2 can be a feedback circuit 270 with a bit 1 position and a bit 2 position in the history shift register 210 be coupled. The feedback loop 270 can be an AND gate 280 included with the history shift register 210 is coupled to receive the most significant bit output and with an OR gate 290 coupled to the bit 1 and bit 2 position of the history shift register 210 can be coupled. The feedback circuit 270 can be used to hold a most significant bit value of 1 in the m-1 bit position in the history shift register. In particular, a first input 281 of the AND gate 280 with the output of the history shift register 210 be coupled. A second input 283 of the AND gate 280 may receive a "1" value that is associated with a value of the history shift register output 210 AND may be linked to cause an AND value from the AND gate 280 about an issue 287 to a first input 291 of the OR gate 290 is issued. A second input of the OR gate 290 can with the bit 2 position in the history shift register 210 be coupled and receive a value thereof. An edition 297 of the OR gate 290 can with an OR value in the bit 1 position of the history shift register 210 be coupled and spend it. Because the second input 283 of the AND gate 280 has a set input of "1", only two input combinations can be possible, namely (0,1) and (1,1), independently of which only two output values from an AND gate can be used 280 to be possible. That is, a "1" may be from an OR gate 280 are output when the output value of the m-1-bit position in the history shift register 210 is also "1", and a "0" may be from the AND gate 280 are output when the output value of the m-1-bit position in the history shift register 210 a "0." Although the OR gate 290 can also have only the same two possible output values (ie "0" or "1"), analogously, the results can result from four possible input combinations, namely (0,0), (0,1), (1,0) and (1 , 1), since neither the first input 291 still the second input 293 to the OR gate 290 are limited to a single value. As can be seen in Table 1, a logical OR table, a "1" can be output as the result of three of the four possible input value combinations 280 will always output a "1" if the bit 1 value in the history shift register 210 Is "1", it can therefore be seen that the feedback circuit 270 will cause the "1" value in the bit 1 position until the history shift register 210 through a TLB error is emptied.

Tabelle 1

Table 1

Ausführungsformen der Erfindung können in einem Out-of-Order-Prozessor implementiert werden, in dem eine Holen/Decodier-Einheit Anweisungen, beispielsweise Makroanweisungen aus einem Speicherplatz holen kann, beispielsweise einem Anweisungscache, und die Anweisungen decodieren kann. Bei einer Complex-Instruction-Set-Computer-(„CISC")-Architektur kann die Holen/Decodier-Einheit eine komplexe Anweisung in eine oder mehrere Mikroanweisungen/Operationen decodieren. In der Regel definieren diese Mikroanweisungen eine Architektur vom Laden/Speichern-Typ, so daß die Mikroanweisungen, die Speicheroperationen involvieren, für andere Architekturen ausgeführt werden können, wie Reduced-Instruction-Set-Computer-(„RISC") oder Very-Large-Instruction-Word-(„VLIW")-Architekturen.embodiments of the invention be implemented in an out-of-order processor in which a Get / Decode unit instructions, such as macro statements from a storage location, such as an instruction cache, and be able to decode the instructions. In a Complex Instruction Set Computer ("CISC") architecture the fetch / decode unit makes a complex statement in one or decode several microinstructions / operations. In general, define these microinstructions have a store / store-type architecture, So that the Microinstructions involving memory operations for others Architectures executed can be such as Reduced Instruction Set Computer ("RISC") or Very Large Instruction Word ("VLIW") architectures.

In einer typischen RISC-Architektur werden Anweisungen nicht in Mikroanweisungen decodiert. Da die vorliegende Erfindung sowohl für RISC-Architekturen als auch für CISC-Architekturen ausgeführt werden kann, wird zwischen Anweisungen und Mikroanweisungen/Operation keine Unterscheidung getroffen, es sei denn, dies wird anders vermerkt, und auf diese wird nur als Anweisungen Bezug genommen.In In a typical RISC architecture, instructions are not translated into microinstructions decoded. Since the present invention is applicable to both RISC architectures as well can be executed for CISC architectures, There is no distinction between instructions and micro instructions / operation unless otherwise noted, and on this is only referred to as instructions.

3 ist ein Flussdiagramm eines Verfahrens gemäß einer Ausführungsform der vorliegenden Erfindung. In 3 kann ein Vorhersageeintrag gewählt werden (310) aus beispielsweise einer Musterverlaufstabelle 240 unter Verwendung einer Eingabe aus dem TLB, und auf der Basis des ausgewählten Vorhersageeintrags und der TLB-Eingabe kann dynamisch vorhergesagt werden, ob eine Verzweigung genommen wird (320). Das Verfahren kann Informationen darüber empfangen (330), ob die Verzweigung wirklich genommen wurde, und der Vorhersageeintrag kann aktualisiert werden (340), beispielsweise in einer Mustervorhersagetabelle aktualisiert werden (340), basierend darauf, ob die Verzweigung wirklich genommen worden ist oder nicht. Ein globaler Verlaufswert, der anzeigt, ob eine Verzweigung wirklich genommen wurde, und die Musterverlaufstabelle 240 können aktualisiert werden (350) beispielsweise in einem Verlaufsschieberegister 210, basierend darauf, ob die Verzweigung wirklich genommen worden ist, und einen Nächste-Verzweigung-Anweisung kann geholt werden (360). Allgemein endet das Verfahren nur, wenn der Prozessor ausgeschaltet wird, oder wenn keine zusätzliche Verarbeitung von Anweisungen ausgeführt werden muss. 3 FIG. 10 is a flowchart of a method according to an embodiment of the present invention. FIG. In 3 a prediction entry can be selected ( 310 ) from, for example, a pattern history table 240 using an input from the TLB, and based on the selected predictive entry and the TLB entry, it can be dynamically predicted whether a branch is taken ( 320 ). The method can receive information about it ( 330 ), whether the branch was really taken, and the prediction entry can be updated ( 340 ), for example in a pattern prediction table ( 340 ), based on whether the branch has really been taken or not. A global history value that indicates whether a branch was actually taken and the pattern history table 240 can be updated ( 350 ), for example, in a history shift register 210 based on whether the branch has actually been taken, and a next branch instruction can be fetched ( 360 ). Generally, the method ends only when the processor is turned off or when no additional processing of instructions needs to be performed.

In einer alternativen Ausführungsform der vorliegenden Erfindung kann das Verfahren in 3, obwohl nicht explizit gezeigt, enden und auf weitere Verzweigungsanweisungen warten, wenn zusätzliche Verzweigungsanweisungen nicht sofort verfügbar sind.In an alternative embodiment of the present invention, the method may be described in 3 although not explicitly shown, end and wait for further branch instructions if additional branch instructions are not immediately available.

Während das Verfahren in 3 eine spezifische Reihenfolge zum Ausführen des Verfahrens enthalten kann, sollte dies nicht so ausgelegt werden, daß Ausführungsformen der vorliegenden Erfindung auf eine solche Reihenfolge beschränkt sind. Tatsächlich werden Ausführungsformen der vorliegenden Erfindung in Betracht gezogen, in denen ein oder alle dieser Elemente in dem Verfahren in jeder Reihenfolge ausgeführt werden können, einschließlich, jedoch nicht beschränkt darauf, daß sie vollkommen oder teilweise parallel ausgeführt werden, beispielsweise in einem Out-of-Order-Prozessor („OOO"). Obwohl zu Darstellungszwecken das Verfahren in 3 vereinfacht wurde, um die Verarbeitung einer Verzweigung zu einer Zeit darzustellen, werden Ausführungsformen der vorliegenden Erfindung in Betracht gezogen, in denen mehrere Verzweigungen simultan verarbeitet werden, beschränkt natürlich auf etwaige bestehende Datenabhängigkeiten.While the procedure in 3 may include a specific order for carrying out the method, it should not be construed that embodiments of the present invention are limited to such an order. Indeed, embodiments of the present invention are contemplated in which any or all of these elements in the process may be performed in any order, including, but not limited to, being performed wholly or partially in parallel, for example, in an out of order manner. Order Processor ("OOO"). Although for illustrative purposes, the method in FIG 3 In order to illustrate the processing of one branch at a time, embodiments of the present invention are contemplated in which multiple branches are processed simultaneously, of course limited to any existing data dependencies.

Der folgende vereinfachte Pseudocodeabschnitt veranschaulicht die Betriebsweise einer Implementation eines TLB-korrelierten globalen Verlaufsverzweigungsvorhersagers gemäß einer Ausführungsform der vorliegenden Erfindung.Of the The following simplified pseudo-code section illustrates the operation an implementation of a TLB-correlated global history branch predictor according to a embodiment of the present invention.

Aus dem obigen Pseudocode ist beispielsweise ersichtlich, daß der Vorhersager eine Anweisung ausführt, um Ergebnisse jeder Verzweigung in der Anweisung vorherzusagen und die Vorhersage mit dem tatsächlichen Ziel, nachdem es bekannt ist, zu aktualisieren. Obwohl das obige Pseudocodebeispiel serielle Ausführung nahelegen kann, ist es lediglich veranschaulichend für das Gesamtkonzept und alternative Ausführungsformen werden in Betracht gezogen, in denen parallele Ausführung und/oder Ausführung ohne Reihenfolge der Verzweigungen auftreten können, abhängig natürlich von zwischengebundenen Datenabhängigkeiten.Out For example, in the above pseudocode, it can be seen that the predictor executes an instruction, to predict results of each branch in the statement and the prediction with the actual Goal, after it is known to update. Although the above Pseudocode example serial execution it is merely illustrative of the overall concept and alternative embodiments are considered in which parallel execution and / or execution without sequence of branches may occur, depending of course on inter-bound ones Data dependencies.

4 ist ein Blockdiagramm eines Computersystems, das einen oder mehrere Prozessoren und Speicher enthalten kann, zur Verwendung gemäß einer Ausführungsform der vorliegenden Erfindung. In 4 kann ein Computersystem 400 einen oder mehrere Prozessoren 410(1)–410(n) enthalten, die mit einem Prozessorbus 420 gekoppelt sind, der an eine Systemlogik 430 gekoppelt sein kann. Jeder dieser einen oder mehreren Prozessoren 410(1)–410(n) kann ein N-Bit-Prozessor sein und einen Decoder (nicht gezeigt) und eine oder mehrere N-Bit-Register (nicht gezeigt) enthalten. Die Systemlogik 430 kann mit einem Systemspeicher 440 über einen Bus 450 gekoppelt sein und mit einem nicht-flüchtigen Speicher 420 und einem oder mehreren Peripheriegeräten 480(1)–480(n) über einen Peripheriebus 460. Bei dem Peripheriebus 460 kann es sich beispielsweise um einen oder mehrere der folgenden handeln: Peripheral Component Interconnect (PCI) Busse, PCI Special Interest Group (SIG) PCI Local Bus Specification, Revision 2.2., veröffentlicht am 18. Dezember 1998; Industriestandardarchitekturbusse (ISA), Erweiterte ISA (EISA) Busse, BCPR Services Inc. EISA Specification, Version 3.12, 1992, veröffentlicht 1992; Universial Serial Bus (USB), USB Specification, Version 1.1, veröffentlicht 23. September 1998, und vergleichbare peripheriefähige Busse. Bei dem nicht-flüchtigen Speicher 470 kann es sich um eine statische Speichereinrichtung, wie beispielsweise einem Read Only Memory (ROM) oder einen Flashspeicher handeln. Zu Peripheriegeräten 480(1)–480(m) kann beispielsweise eine Tastatur, eine Maus oder andere Zeigeeinrichtungen, Massenspeichergeräte, wie Festplattentreiber, Anzeigen und dergleichen handeln. 4 FIG. 10 is a block diagram of a computer system that may include one or more processors and memory for use in accordance with an embodiment of the present invention. In 4 can be a computer system 400 one or more processors 410 (1) - 410 (n) included with a processor bus 420 coupled to a system logic 430 can be coupled. Each of these one or more processors 410 (1) - 410 (n) may be an N-bit processor and may include a decoder (not shown) and one or more N-bit registers (not shown). The system logic 430 can with a system memory 440 over a bus 450 coupled with a non-volatile memory 420 and one or more peripheral devices 480 (1) - 480 (n) via a peripheral bus 460 , In the peripheral bus 460 it may be, for example, one or more of the following: Peripheral Component Interconnect (PCI) buses, PCI Special Interest Group (SIG) PCI Local Bus Specification, Revision 2.2., published December 18, 1998; Industrial Standard Architecture Buses (ISA), Advanced ISA (EISA) buses, BCPR Services Inc. EISA Specification, Version 3.12, 1992, published 1992; Universial Serial Bus (USB), USB Specification, Version 1.1, released September 23, 1998, and comparable peripherally available buses. In the non-volatile memory 470 it may be a static storage device, such as a read only memory (ROM) or a flash memory. To peripheral devices 480 (1) - 480 (m) For example, it may be a keyboard, a mouse, or other pointing devices, mass storage devices such as hard drive drivers, displays, and the like.

Obwohl die vorliegende Erfindung im Detail offenbart worden ist, versteht sich, daß zahlreiche Änderungen, Substitutionen und Veränderungen daran vorgenommen werden können. Außerdem werden Software und Hardware zwar als bestimmte Funktionen steuernd beschrieben, aber solche Funktionen können entweder unter Verwendung Software, Hardware oder einer Kombi nation aus Software und Hardware, wie im Gebiet wohlbekannt, ausgeführt werden. Ebenso kann der Begriff „Anweisung" in den folgenden Ansprüchen eine Anweisung in einer RISC-Architektur oder eine Anweisung in einer CISC-Architektur, sowie Anweisungen, die in anderen Computerarchitekturen verwendet werden, umfassen. Weitere Beispiele lassen sich durch einen Fachmann leicht erstellen und dies kann erfolgen, ohne von der Idee und dem Schutzumfang der vorliegenden Erfindung, wie durch die folgenden Ansprüche definiert, abzuweichen.Even though the present invention has been disclosed in detail that many changes, Substitutions and changes can be made. Furthermore Although software and hardware are controlled as certain functions but such features can be used either Software, hardware or a combination of software and hardware, as is well known in the art. Likewise, the Term "statement" in the following claims an instruction in a RISC architecture or an instruction in a CISC architecture, as well as instructions, which are used in other computer architectures include. Other examples can be easily created by a person skilled in the art and this can be done without departing from the idea and scope of the present invention as defined by the following claims departing.

ZusammenfassungSummary

Ausführungsformen der vorliegenden Erfindung betreffen eine Vorrichtung und ein Verfahren zum Ermöglichen einer effizienten Verzweigungsvorhersage in superskalaren und anderen verzweigungsaktivierten Prozessoren. Gemäß einer Ausführungsform der vorliegenden Erfindung kann ein Verzweigungsvorhersager eine Verzweigungsvorhersageschaltung enthalten, um ein Verzweigungsergebnis in einer Ausführungsanweisung in einem Prozessor unter Verwendung einer Eingabe von einem Adressumsetzerpuffer vorherzusagen.Embodiments of the present invention relate to an apparatus and method for enabling efficient branch prediction in superscalar and other branch-enabled processors. According to one embodiment of the present invention, a branch predictor a branch prediction circuit for predicting a branch result in an execution instruction in a processor using an input from an address translation buffer.

Claims

Branch predictor, comprising: a Branch prediction circuit for predicting a branch result in an execution instruction in a processor, using an input from a translation look-aside buffer.

A branch predictor according to claim 1, wherein said Branch prediction circuit includes: a pattern history table; and a history shift register that matches the pattern history table and is coupled to the translation look-aside buffer, where the History shift registers upon receipt of a miss signal from empties the translation look-aside buffer itself.

A branch predictor according to claim 2, wherein said Branch prediction circuit further comprises: a memory that is coupled to the history shift register, the memory upon receipt of the miss signal from the translation look-aside buffer a reset value passes on to the history shift register.

A branch predictor according to claim 3, wherein said Memory includes a tri-state buffer.

A branch predictor according to claim 3, wherein said Branch prediction circuit further comprises: a feedback loop, coupled to the history shift register, the feedback loop results in a most significant bit value in the history shift register.

A branch predictor according to claim 5, wherein said Feedback loop the most significant bit value is 1.

A branch predictor according to claim 5, wherein a Bit position of a most significant 1 value in the history shift register a length a global branch history that is in the history shift register stored, determined.

A branch predictor according to claim 7, wherein said Length of the global branch history contained in the branch shift register is stored by the bit position of the most significant 1 value is defined.

A branch predictor according to claim 5, wherein said Feedback loop comprising: one AND gate coupled to the history shift register an output bit value of the history shift register and an enable signal to recieve; and an OR gate connected to the AND gate and the History shift register is coupled, wherein the OR gate a first input value from the AND gate and a second input value from the history shift register and receives a new bit value to the history shift register.

A branch predictor according to claim 2, wherein said History shift registers make a global branching dynamic Contains length.

A branch predictor according to claim 2, wherein said Contain shift register m-bit and an m-bit pattern history value to the pattern history table via outputs an EXCLUSIVE-OR gate.

A branch predictor according to claim 11, wherein the EXCLUSIVE-OR gate the m-bit pattern history value and an m-bit address value receives and an m-bit pattern history value to the pattern history table.

A branch predictor, comprising: a branch prediction circuit including an m-bit global branch history; a memory coupled to a translation look-aside buffer and the branch prediction circuit, the switch resetting the branch prediction circuit upon receipt of an indication of an error in the translation look-aside buffer; and a feedback loop coupled to the branch prediction circuit that results in a most significant bit value in the branch prediction circuit when a length of the global branch history is equal to m-1.

A branch predictor according to claim 13, wherein the branch prediction circuit comprises: a pattern history table; one History shift register, which uses the pattern history table and with the translation look-aside buffer is coupled, wherein the History shift register when receiving the error indication from empties the translation look-aside buffer itself; and a branch address store to store addresses for each branch specified in the history shift register.

A branch predictor according to claim 14, wherein the memory is coupled to the history shift register.

A branch predictor according to claim 13, wherein the memory comprises a tri-state buffer.

A branch predictor according to claim 13, wherein the feedback circuit comprising: one AND gate coupled to the history shift register an output bit value of the history shift register and an enable signal to recieve; and an OR gate connected to the AND gate and the History shift register is coupled, wherein the OR gate a receives the first input value from the AND gate and a second input value from the history shift register and a new bit value to the history shift register outputs.

Processor comprising: a translation look-aside Buffer; a branch prediction circuit having a global contains in-bit branch history; one Memory associated with the translation look-aside buffer and the branch prediction circuit wherein the memory is the branch prediction circuit resets upon receipt of an indication of an error in the translation look-aside buffer; and a feedback loop, which is coupled to the branch prediction circuit, wherein the feedback loop a most significant bit value in the branch prediction circuit leads, if a length of the global branching history is equal to m-1.

The processor of claim 18, wherein the branch prediction circuit comprising: a Pattern history table; a history shift register that with the pattern history table and the translation look-aside buffer is coupled, the history shift register being upon receipt of an indication the error empties from the translation look-aside buffer itself; and a branch address memory for storing addresses for every Branch displayed in the history shift register.

The processor of claim 19, wherein the memory comprises is coupled to the history shift register.

The processor of claim 18, wherein the memory is a Includes three status buffer.

The processor of claim 18, wherein the feedback loop comprising: one AND gate coupled to the history shift register an output bit value from the history shift register and an enable signal to recieve; and an OR gate connected to the AND gate and the History shift register is coupled, wherein the OR gate a first input value from the AND gate and a second input value from the history shift register and receives a new bit value to the history shift register.

A computing system, comprising: a memory; a processor coupled to the memory, the processor including: a translation look-aside buffer; a branch prediction circuit having a global m-bit branch history; a memory coupled to the translation look-aside buffer and the branch prediction circuit, the memory including the branch prediction circuit upon receipt of an indication of an error resets buffer in the translation look-aside; and a feedback loop coupled to the branch prediction circuit, wherein the feedback loop results in a most significant bit value in the branch prediction circuit when a length of the global branch history is equal to m-1.

The computing system of claim 23, wherein the branch prediction circuit comprising: a Pattern history table; a history shift register that with the pattern history table and the translation look-aside buffer is coupled, the history shift register being in receipt of the indication an error from the translation look-aside buffer itself empties; and a branch address memory for storing addresses for every Branching displayed in the history shift register.

The computing system of claim 24, wherein the memory is coupled to the history shift register.

Method, comprising: Predict a branch result a variety of execution instructions in a processor using an input from a translation look-aside buffer.

The method of claim 26, wherein the predicting a branch result of the execution instructions in one Processor using an input from a translation look-aside Buffer, comprising: predict of the branching result for each of the plurality of execution instructions; maintain the predicted branch result for each of the plurality of execution instructions; and Empty the global branch history when it receives a Display that in a translation look-aside buffer for data representing one of the multiplicity of execution instructions are assigned, an error has occurred.

The method of claim 27, wherein emptying the global branching history when receiving an ad that is in one translation look-aside buffer an error has occurred, includes: the Replace the global branch history with a predetermined one Blank.

Machine readable medium, on the executable instructions to run stored in a method comprising: Predicting a Branching result of a plurality of execution instructions in one Processor, using an input from a translation look-aside buffer.

The machine-readable medium of claim 29, wherein predicting a branch result of a plurality of execution instructions in a processor, using an input from a translation look-aside buffer, includes: predict of the branching result for each of the plurality of execution instructions; maintain the predicted branch result for each of the plurality of execution instructions; and Empty the global branch history when it receives a Display that in a translation look-aside buffer for data representing one of the multiplicity of execution instructions are assigned, an error has occurred.

The machine-readable medium of claim 30, wherein emptying the global branch history on receipt of a Display that in a translation look-aside buffer encountered an error comprising: Replace the global branch history with a predetermined blank.

A method, comprising: selecting a predictive entry using an input from a translation look-aside buffer; Predicting whether a branch will be taken based on the predictive entry and the input; Receiving information about whether the branch has actually been taken; Update the prediction entry with the information about whether the branching really taken has been; Updating a global history value to indicate whether the branch has actually been made; and Holes of a New Branch Instruction.

The method of claim 32, wherein selecting a Prediction entry using an input from a translation look-aside buffer includes: Select one Prediction entry from a pattern history table using the entry of the translation look-aside buffer.

The method of claim 32, wherein updating of the predictive entry includes: To update the prediction entry in a pattern history table.

The method of claim 32, wherein updating a global history value to indicate if the branching is really has been taken, comprises: To update of the global history value in a global shift register indicate whether the branch has actually been taken.

Machine readable medium with stored on it executable Instructions for execution a method comprising: Select one Prediction entry using an input from a translation look-aside buffer; Predict whether taken a branch will be, based on the predictive entry and the input; Receive of information about it, whether the branch has really been taken; To update the prediction entry with the information about whether the branching is really has been made; Update a global history value to indicate whether the branch has actually been made; and Get a Next Branch instruction.

The machine-readable medium of claim 36, wherein selecting a predictive entry using an entry of one translation look-aside buffer includes: Select the Prediction entry from a pattern history table using the entry of the translation look-aside buffer; To update a global history value to indicate if the branching is really has been made; and Get a Next Branch instruction.

The machine-readable medium of claim 36, wherein Updating the prediction entry includes: Update the Prediction value from the pattern history table.

The machine-readable medium of claim 36, wherein to update a global history value to indicate whether the branch has actually been taken comprises: To update of the global history value in a global shift register Indicating if the junction has actually been taken.