ENFORCING CONSISTENCY ACROSS REDUNDANT TAGGED GEOMETRIC (TAGE) BRANCH HISTORIES

Enforcing consistency across redundant tagged geometric (TAGE) branch histories, including: determining, by a TAGE branch predictor, whether a predefined interval has occurred; and storing, in a retirement branch history, in response to the predefined interval occurring, a copy of a global branch history.

BACKGROUND

Some implementations of tagged geometric (TAGE) branch predictors use redundant instances of branch histories, one for generating predictions and one for training the branch predictor. These redundant histories are maintained as duplicate copies of each other but are used at different points in the branch prediction pipeline. As these redundant instances of the branch history should be duplicate copies of each other, cohesion between the redundant instances of the branch history should be maintained to ensure proper performance.

DETAILED DESCRIPTION

Some implementations of tagged geometric (TAGE) branch predictors use redundant instances of branch histories. For example, a first instance of branch history is used for generating predictions, while a second instance of branch history is used to train the TAGE branch predictor on retirement of a branch instruction. These redundant instances should maintain cohesion to ensure proper performance. In some circumstances, due to various errors, bugs, and the like, a variance is introduced between these redundant representations. Such a variance introduces the possibility of errors in branch prediction, performance degradation, and the like.

The present specification sets forth various implementations for enforcing consistency across redundant TAGE branch histories. In some embodiments, a method for enforcing consistency across redundant TAGE branch histories includes. The method also includes determining, by a TAGE branch predictor, whether a predefined interval has occurred. The method further includes storing, in a retirement branch history, in response to the predefined interval occurring, a copy of a global branch history.

In some embodiments, the method further includes updating, in response to retirement of a branch instruction, one or more TAGE tables based on the retirement branch history storing the copy of the global branch history. In some embodiments, the method further includes updating the retirement branch history based on a prediction for the branch instruction. In some embodiments, the prediction is based on the global branch history as copied into the retirement branch history. In some embodiments, the predefined interval includes a number of prediction cycles. In some embodiments, the predefined interval includes a time interval. In some embodiments, the global branch history and the retirement branch history are each implemented as a circular buffer.

The present specification also describes various implementations for a TAGE branch predictor for enforcing consistency across redundant TAGE branch histories. Such a TAGE branch predictor includes: a global branch history and a retirement branch history. The TAGE branch predictor performs steps including: determining whether a predefined interval has occurred, and storing, in the retirement branch history, in response to the predefined interval occurring, a copy of the global branch history.

In some embodiments, the steps further include updating, in response to retirement of a branch instruction, one or more TAGE tables based on the retirement branch history storing the copy of the global branch history. In some embodiments, the steps further include updating the retirement branch history based on a prediction for the branch instruction. In some embodiments, the prediction is based on the global branch history as copied into the retirement branch history. In some embodiments, the predefined interval includes a number of prediction cycles. In some embodiments, the predefined interval includes a time interval. In some embodiments, the global branch history and the retirement branch history are each implemented as a circular buffer.

Also described in this specification are various implementations of an apparatus for enforcing consistency across redundant TAGE branch histories. Such an apparatus includes computer memory and a processor operatively coupled to the computer memory. The processor includes a TAGE branch predictor. The TAGE branch predictor performs steps including: determining whether a predefined interval has occurred, and storing, in a retirement branch history, in response to the predefined interval occurring, a copy of a global branch history.

In some embodiments, the steps further include updating, in response to retirement of a branch instruction, one or more TAGE tables based on the retirement branch history storing the copy of the global branch history. In some embodiments, the steps further include updating the retirement branch history based on a prediction for the branch instruction. In some embodiments, the prediction is based on the global branch history as copied into the retirement branch history. In some embodiments, the predefined interval includes a number of prediction cycles. In some embodiments, the predefined interval includes a time interval.

The following disclosure provides many different implementations, or examples, for implementing different features of the provided subject matter. Specific examples of components and arrangements are described below to simplify the present disclosure. These are, of course, merely examples and are not intended to be limiting. For example, the formation of a first feature over or on a second feature in the description that follows include implementations in which the first and second features are formed in direct contact, and also include implementations in which additional features be formed between the first and second features, such that the first and second features are not in direct contact. Further, spatially relative terms, such as “beneath,” “below,” “lower,” “above,” “upper,” “back,” “front,” “top,” “bottom,” and the like, are used herein for ease of description to describe one element or feature's relationship to another element(s) or feature(s) as illustrated in the figures. Similarly, terms such as “front surface” and “back surface” or “top surface” and “back surface” are used herein to more easily identify various components, and identify that those components are, for example, on opposing sides of another component. The spatially relative terms are intended to encompass different orientations of the device in use or operation in addition to the orientation depicted in the figures.

FIG.1is a block diagram of an apparatus100including an example tagged geometric (TAGE) branch predictor102for enforcing consistency across redundant TAGE branch histories. The apparatus102can be implemented as a variety of computing devices, including personal computers, mobile devices, servers, systems-on-a-chip (SoCs), hardware accelerators, and the like. The apparatus100is a processor104such as a central processing unit (CPU) or other processor104as can be appreciated. The apparatus100also includes memory106operatively coupled to the processor104. The memory106includes, for example, volatile memory such as random access memory (RAM), non-volatile memory, disk-based storage, or combinations thereof.

The processor104includes a TAGE branch predictor102for enforcing consistency across redundant TAGE branch histories according to some implementations described in further detail below. The TAGE branch predictor102performs a branch prediction on instructions provided to the processor104for execution (e.g., instructions loaded from memory106). The TAGE branch predictor102uses a TAGE algorithm to perform branch prediction as will be described in further detail below.

FIG.2is a block diagram of a non-limiting example tagged geometric (TAGE) branch predictor such as the TAGE branch predictor102ofFIG.1. The example TAGE branch predictor200ofFIG.2can be implemented in a variety of processors, cores, and other computer hardware components as can be appreciated. The TAGE branch predictor200uses a TAGE branch prediction algorithm as would be appreciated by one skilled in the art to generate, for a given branch instruction, a prediction202. The prediction202is a prediction of whether or not a branch in the branch instruction will be taken. In other words, the prediction202is a prediction of whether or not a particular condition that will trigger a conditional branch will be satisfied.

The history used by the TAGE branch predictor200is shown as the global branch history206. The global branch history206is a data structure or portion of memory including a plurality of entries each indicating whether a branch was taken or not taken. As an example, each entry is a single bit, with a “1” indicating a taken branch and a “0” indicating a non-taken branch. For a global branch history206with N entries, the global branch history206then stores the N-most recent branch decisions. In some implementations, the global branch history206includes a path history. A register value for a path history is shifted for all branch types so long as their direction is taken, typically shift by two or three bits at a time. Instead of shifting in the direction of a branch at the lowest position, a portion of the address of the last byte in the instruction is XORed into the register, allowing some overlap with the previous values at the low position.

As the global branch history206is of limited size, after the global branch history206is full, an oldest entry should be removed when a newest entry is added. In existing solutions, prediction branch histories206are stored using an N-bit shift register. When a new entry is added to the global branch history206, the entire register is shifted by a single bit and a bit is stored at the new head of the register. The amount of power required to perform this bit shift increases as the size of the shift register increases. Accordingly, a large global branch history206using a shift register would require a large amount of power to shift the register for each update to the global branch history206.

To address this concern, in some implementations, the global branch history206is instead implemented using an array402as shown inFIG.4. The array402is implemented, for example, as a latch array, a flip-flop array, as an allocated portion of static random access memory (SRAM), and the like. Each entry in the array402is a single bit. Instead of shifting entries as with a shift register, the global branch history206maintains a head pointer404identifying a newest entry in the array402and a tail pointer406identifying an oldest entry in the array402. In other words, the global branch history206is implemented as a circular buffer. AlthoughFIG.4shows the head pointer404identifying entry Hn-2and the tail pointer406identifying entry H0, one skilled in the art will appreciate that this is only for illustrative purposes and that the particular entries identified by the head pointer404and tail pointer406will change as the global branch history206is updated.

Consider an example where the head pointer404identifies entry Hn-2and the tail pointer406identifies entry H0, with entry Hn-1currently unused. An update to the global branch history206will then cause a value to be stored at entry Hn-1and the head pointer404to be updated to identify the entry Hn-1. The array402is now full, with all entries storing a value for the global branch history206. Another update will require an oldest value to be removed from the array402. Accordingly, in response to another update, the tail pointer406will be updated to identify entry Hi, the head pointer404will be updated to identify entry H0, and the value for the update will then be stored at entry H0. Additional updates will continue to cause the head pointer404and tail pointer406to be updated, with the value for the latest update to be stored at the entry identified by the updated head pointer404.

As will be appreciated by one skilled in the art, updating a global branch history206implemented using an array402, head pointer404and tail pointer404only requires modification of a single entry in the array402and updates to the head pointer404and, if the array402is full, the tail pointer404. This provides considerable power savings when compared to shifting a shift register of sufficiently large size.

An entry for a given TAGE table204a-nis identified using an index208a-n. An index208a-nis calculated as a function of the program counter (PC)210(e.g., identifying the address of the branch instruction subject to prediction) and a portion of the global branch history206, with each TAGE table204a-nhaving its corresponding index208a-ncalculated using portions of the global branch history206of geometrically increasing length. For example, the PC210, or a subset of the bits of the PC210, are combined with the bits of the global branch history206used for the given index208a-nusing a hash function, an exclusive-OR (XOR) function, or other function. Although the following discussion will use the term “hashing” when combining the PC210with bits from the global branch history206, it is understood that this encompasses the use of XOR functions or other aggregate functions usable in combining the PC210with portions of the global branch history206to generate an index208a-n.

As the number of global branch history 206 bits used for a given TAGE table204a-n(hereinafter referred to as “history bits”) increases, the number of history bits used will exceed the number of bits needed to index a TAGE table204a-n(e.g., to identify a particular entry in the TAGE table204a). For example, a TAGE table204a-nwith 2024 entries only needs ten bits to identify any of the entries. Accordingly, before hashing the PC210with the history bits, in some implementations the used history bits are “folded” on themselves to generate a folded branch history212a-n.

The history bits are “folded” by subdividing the history bits into portions of equal length (e.g., corresponding to the number of bits needed to identify an entry in the TAGE table204a-n) and then applying an XOR function to combine each of the portions into a single portion. Assuming N history bits used for a given TAGE table204a-nand assuming M bits are needed to identify an entry in the TAGE table204a-n, the N history bits are divided into N/M portions of M bits and XOR-ed together to create a single folded branch history212a-nof M bits. For example, assume that a given TAGE table204a-nwith 1024 entries (therefore needing 10 bits to index) uses 500 bits of the global branch history206. These 500 bits are divided into fifty 10-bit portions. These fifty portions are then XOR-ed together to create a single 10-bit folded branch history212a-nfrom which an index208a-nis generated. Where the history bits are not evenly dividable by the number of bits used for indexing, in some implementations, the history bits are padded (e.g., with one or more zeroes) until the history bits are of a length that is a factor of the number of bits used for indexing.

In some implementations, a folded branch history212a-nfor each TAGE table204a-nis calculated from the global branch history206each time a branch prediction is to be performed. However, this requires significant computational and time resources, and would require a large number of XOR gates in order to be implemented in hardware as the size of the global branch history206grows. Instead, in some implementations, the TAGE branch predictor200includes allocated portions of memory to logically store the folded branch history212a-nfor each TAGE table204a-n. When the global branch history206is updated, instead of recalculating the folded branch history212a-nfor each TAGE table204a-n, the stored folded branch histories212a-nare modified to reflect the update (e.g., by shifting or rotating the folded branch history212a-n, modifying one or more bits in the shifted value, accessing particular bits in the global branch history206to calculate particular bits in the folded branch history212a-n, etc.). Thus, the folded branch history212a-nfor each TAGE table204a-nis maintained without the need to fully recalculate each folded branch history212a-non an update to the global branch history206.

In addition to the TAGE tables204a-n, the TAGE branch predictor200also maintains a base predictor214. The base predictor214is a table of counters indexed using the PC210that will provide a default prediction202if no entries in the TAGE tables204a-nmatch the calculated indexes208a-n.

To generate a prediction202for a given branch instruction, the TAGE branch predictor200calculates, for each TAGE table204a-n, a tag216a-n. Each tag216a-nis calculated as a function (e.g., by hashing, XOR-ing, and the like) of the PC210and the bits of the global branch history206used by the corresponding TAGE table204a-n. Though the indexes208a-nand tags216a-nare both generated as a function of the PC210, the particular functions used to calculate the indexes208a-nand tags216a-nare different. For example, in some implementations, tags216a-nand indexes208a-nare of different lengths. Accordingly, in some implementations, a tag216a-nfor a given TAGE table204a-nis calculated by folding the bits of the global branch history206used by that TAGE table204a-nusing portions having a number of bits equal to the number of bits used in a given tag216a-n.

For each TAGE table204a-n, where an entry is found at the corresponding index208a-n, a counter302value is provided to a corresponding multiplexer (MUX)218a-n, shown inFIG.2as Ctr_a, Ctr_n. Moreover, where an entry is found at the corresponding index208a-n, a tag304for the entry (shown as Tag_a, Tag_n) is compared to the calculated tag216a-n. The result of the comparison is provided as a selector signal to the corresponding MUX218a-n. Thus, where the tag304for the entry is equal to the calculated tag216a-n, the MUX218a-noutputs the counter302output by the MUX218a-n. Where the tag304for the entry is not equal to the calculated tag216a-n, or no entry is found, the MUX218a-nprovides, as output, an input received from a preceding MUX218a-nor, in the case of the first MUX218a, an input from the base predictor214. The output of the last MUX218nthen serves as the prediction202. The global branch history206is updated to reflect the result of the prediction202(e.g., a new entry is added to indicate whether it is predicted that the branch will or will not be taken).

After retirement of a branch instruction through the execution pipeline, the TAGE tables204a-nare updated depending on whether the prediction202was correct. For example, where the prediction202was correct, the TAGE table204a-nentries used to generate the prediction202are updated by incrementing a counter302for a taken branch or decrementing a counter302for a non-taken branch. Additionally, in some embodiments, a useful bit306for the entry is set to protect it from being overwritten by other training. As another example, where the prediction202was incorrect, the TAGE table204a-nentries used to generate the prediction are updated by decrementing a counter302for a non-taken branch or decrementing a counter302for a taken branch. Additionally, for TAGE tables204a-nwhere no entry was found (e.g., that use longer history) new entries are allocated.

To identify the TAGE table204a-nentries to update, the indexes208a-nare recalculated using the address of the branch instruction being retired and the particular history bits for the TAGE table204a-n. In some embodiments, the TAGE branch predictor200maintains a second copy of the global branch history206hereinafter referred to as the retirement branch history220. The retirement branch history220is implemented, for example, as a circular buffer. Although the retirement branch history220is described as using a circular buffer, it is understood that, in some embodiments, the global branch history206and retirement branch history220are implemented using other approaches, such as shift register or another approach. For example, the global branch history206is updated when a prediction202is generated, with a new entry in the global branch history206reflecting the predicted branch (e.g., whether it is predicted that the branch will or will not be taken). The retirement branch history220is used to calculate indexes208a-nfor identifying the TAGE table204a-nentries to be updated based on whether the prediction202was correct. The retirement branch history220is then updated on retirement of a branch instruction to reflect the prediction202for the retired branch instruction.

In order to correctly identify the TAGE table204a-nentries to be updated, the global branch history206and the retirement branch history220should maintain cohesion. That is, the state of the global branch history206used to generate a prediction202for a given branch instruction should match the state of the retirement branch history220when the branch instruction is retired. In some circumstances, due to various errors, bugs, and the like, a variance is introduced between the global branch history206and the retirement branch history220. Such a variance introduces the possibility of errors in branch prediction, performance degradation, and the like. Where large circular buffers are used for the global branch history206and retirement branch history220, the variances introduced have the potential of staying for long periods of time, prolonging the performance degradation.

To address this concern, the TAGE branch predictor200periodically forces coherency between the global branch history206and the retirement branch history220by storing, in the retirement branch history220, a copy of the global branch history206. In some embodiments, the predefined interval is a number of prediction cycles. In other words, every Nth branch instruction for which a prediction202is to be generated, the global branch history206is copied into the retirement branch history220. In some embodiments, the predefined interval is a time interval or a number of clock cycles. In some embodiments, the predefined interval is a predefined number of instructions executed. One skilled in the art will appreciate that various intervals or criteria are usable in triggering the copying of the global branch history206into the retirement branch history220.

The TAGE branch predictor200uses the global branch history206as copied into the retirement branch history220to generate a prediction202for a given branch instruction as described above. After generating the prediction, the global branch history206is updated to reflect the prediction202. On retirement of the given branch instruction, one or more TAGE tables204a-nare updated based on the retirement branch history220storing the copy of the global branch history206. The retirement branch history220is then updated based on the prediction202for the retired branch instruction as described above.

In some implementations, the TAGE branch predictor200ofFIG.2is implemented in a computer500. For example, the TAGE branch predictor200is implemented in at least one processor502. In addition to at least one processor502, the computer500ofFIG.5includes random access memory (RAM)504which is connected through a high speed memory bus506and bus adapter508to processor502and to other components of the computer500. Stored in RAM504is an operating system510. The operating system510in the example ofFIG.5is shown in RAM504, but many components of such software typically are stored in non-volatile memory also, such as, for example, on data storage512, such as a disk drive.

The computer500ofFIG.5includes disk drive adapter516coupled through expansion bus518and bus adapter508to processor502and other components of the computer500. Disk drive adapter516connects non-volatile data storage to the computer500in the form of data storage512. Such disk drive adapters include Integrated Drive Electronics (‘IDE’) adapters, Small Computer System Interface (SCSI′) adapters, and others as will occur to those of skill in the art. In some implementations, non-volatile computer memory is implemented as an optical disk drive, electrically erasable programmable read-only memory (so-called ‘EEPROM’ or ‘Flash’ memory), RAM drives, and so on, as will occur to those of skill in the art.

The example computer500ofFIG.5includes one or more input/output (′I/O′) adapters520. I/O adapters implement user-oriented input/output through, for example, software drivers and computer hardware for controlling output to display devices such as computer display screens, as well as user input from user input devices522such as keyboards and mice. The example computer500ofFIG.5includes a video adapter524, which is an example of an I/O adapter specially designed for graphic output to a display device526such as a display screen or computer monitor. Video adapter524is connected to processor502through a high speed video bus528, bus adapter508, and the front side bus530, which is also a high speed bus.

The exemplary computer500ofFIG.5includes a communications adapter532for data communications with other computers and for data communications with a data communications network. Such data communications are carried out serially through RS-232 connections, through external buses such as a Universal Serial Bus (‘USB’), through data communications networks such as IP data communications networks, and/or in other ways as will occur to those of skill in the art. Communications adapters532implement the hardware level of data communications through which one computer sends data communications to another computer, directly or through a data communications network. Such communication adapters532include modems for wired dial-up communications, Ethernet (IEEE 802.3) adapters for wired data communications, and 802.11 adapters for wireless data communications.

For further explanation,FIG.6sets forth a flow chart illustrating an example method for enforcing consistency across redundant TAGE branch histories according to some embodiments of the present disclosure. The method ofFIG.6is performed, for example, by a TAGE branch predictor such as the example TAGE branch predictor200ofFIG.2. The method ofFIG.6includes determining602whether a predefined interval has occurred. In some embodiments, determining602whether the predefined interval has occurred is performed in response to beginning a branch prediction cycle. For example, the TAGE branch predictor receives a memory address of a branch instruction for which a prediction is to be generated, thereby beginning the branch prediction cycle. In some embodiments, the predefined interval is a number of prediction cycles. In other words, the predefined interval is deemed to occur every N prediction cycles. In some embodiments, the predefined interval is a time interval or a number of clock cycles. In some embodiments, the predefined interval is a number of fetched instructions. One skilled in the art will appreciate that, in some embodiments, other criteria are used to define the predefined interval.

The method ofFIG.6also includes storing604, in a retirement branch history, in response to the predefined interval occurring, a copy of the global branch history. The global branch history is a data structure or memory allocation that stores a history of generated predictions. In other words, after a prediction is generated, an entry is added to the global branch history indicating whether the prediction predicts that a branch will or will not be taken. The global branch history is also used by the TAGE branch predictor to generate predictions. The retirement branch history also stores a history of generated predictions. In contrast to the global branch history that is updated after generating a prediction, the retirement branch history is updated at retirement of a branch instruction to indicate the prediction for that branch instruction. The retirement branch history is used to train the TAGE branch predictor as will be described in further detail below.

In response to the predefined interval occurring, a copy of the global branch history is copied into the retirement branch history in order to periodically force cohesion between the global branch history and the retirement branch history. For example, entries in the global branch history are each copied into the retirement branch history, thereby overwriting any existing entries in the retirement branch history. Moreover, any pointers (e.g., head and tail pointers) for the retirement branch history are updated to identify the newest and oldest entries, respectively, in the retirement branch history.

The state of the global branch history used to generate a prediction for a given branch instruction (e.g., prior to updating the global branch history to reflect the generated prediction) should match the state of the retirement branch history when the branch instruction is retired (e.g., prior to updating the retirement branch history with the prediction for that branch instruction). In some circumstances, due to various errors, bugs, and the like, a variance is introduced between the global branch history and the retirement branch history. Such a variance introduces the possibility of errors in branch prediction, performance degradation, and the like. Where large circular buffers are used for the global branch history and retirement branch history, the variances introduced have the potential of staying for long periods of time, prolonging the performance degradation. Accordingly, periodically copying the global branch history into the retirement branch history ensures that any variances or differences between the global branch history or the retirement branch history are eliminated.

For further explanation,FIG.7sets forth a flow chart illustrating an example method for enforcing consistency across redundant TAGE branch histories according to some embodiments of the present disclosure. The method ofFIG.7also includes updating702one or more TAGE tables based on the retirement branch history. The one or more TAGE tables are updated on retirement of a branch instruction depending on whether the generated prediction for that branch instruction was correct. For example, where the prediction was correct, the TAGE table entries used to generate the prediction are updated by incrementing a counter for a taken branch or decrementing a counter for a non-taken branch. Additionally, in some embodiments, a useful bit for the entry is set to protect it from being overwritten by other training. As another example, where the prediction was incorrect, the TAGE table entries used to generate the prediction are updated by decrementing a counter for a non-taken branch or decrementing a counter for a taken branch. Additionally, for TAGE tables where no entry was found (e.g., that use longer history) new entries are allocated.

To identify the TAGE table entries to update, the indexes are recalculated using the address of the branch instruction being retired and the particular history bits for the TAGE table as stored in the retirement branch history. In some embodiments, the TAGE branch predictor maintains a second copy of the global branch history hereinafter referred to as the retirement branch history. The retirement branch history is implemented, for example, as a circular buffer. Although the retirement branch history is described as using a circular buffer, it is understood that, in some embodiments, the global branch history and retirement branch history are implemented using other approaches, such as shift register or another approach. For example, the global branch history is updated when a prediction is generated, with a new entry in the global branch history reflecting the predicted branch (e.g., whether it is predicted that the branch will or will not be taken). The retirement branch history is used to calculate indexes for identifying the TAGE table entries to be updated based on whether the prediction was correct.

The method ofFIG.7also includes updating704the retirement branch history based on a prediction for the branch instruction (e.g., the branch instruction being retired). For example, updating704the retirement branch history includes storing, in an entry, an indication of whether the prediction for the retiring branch instruction predicts a taken or not taken branch. In some embodiments, updating704the retirement branch history includes updating a head pointer for the retirement branch history to indicate the newest entry. In some embodiments, where the retirement branch history was full prior to updating, a tail pointer is updated to indicate the oldest entry in the retirement branch history as the previously oldest entry was overwritten or cycled out by the update. One skilled in the art will appreciate that the retirement branch history is updated after updating702the one or more TAGE tables as the particular TAGE table entries to be updated are identified using the retirement branch history. To do so, the retirement branch history must reflect the same state as the global branch history used to select TAGE table entries for generating the prediction. In other words, a pre-update global branch history is used to generate the prediction and then updated based on the prediction. On retirement of the branch instruction, a pre-update retirement branch history is used to index the TAGE tables the for updating, and then the retirement branch history is updated based on the prediction.

In view of the explanations set forth above, readers will recognize that the benefits of enforcing consistency across redundant TAGE branch histories include improved performance of a computing system by ensuring cohesion between redundant branch histories in a branch predictor, reducing performance degradation caused by variances in the redundant representations.

It will be understood from the foregoing description that modifications and changes can be made in various embodiments of the present disclosure. The descriptions in this specification are for purposes of illustration only and are not to be construed in a limiting sense. The scope of the present disclosure is limited only by the language of the following claims.