BRANCH TARGET BUFFER COLUMN PREDICTOR

A processor receives a first instruction with a first instruction address within a first instruction stream. The processor selects a row of a branch target buffer and a row of a one-dimensional array based on the first instruction address. The processor reads information in the current row of the one-dimensional array, where the current row of one-dimensional array includes a first target address and a column of the row of the branch target buffer expected to contain a second target address. The processor receives a second instruction within a second instruction stream, which includes a second instruction address equal to the first target address. The processor reads information included in the row of the branch target buffer, where the information included the row of the branch target buffer includes the second target address. The processor encounters a branch including a third target address within the first instruction stream.

BACKGROUND OF THE INVENTION

The present invention relates generally to the field of microprocessor design and more particularly to branch prediction.

Traditionally, branch prediction is used to steer the flow of instructions down a processor pipeline along the most likely path of code to be executed within a program. Branch prediction uses historical information to predict whether or not a given branch will be taken or not taken, such as predicting which portion of code included in an IF-THEN-ELSE structure will be executed based on which portion of code was executed in the past. The branch that is expected to be the first taken branch is then fetched and speculatively executed. If it is later determined that the prediction was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the instruction proceeding the branch with the correct branch path, incurring a delay between the branch and the next instruction to be executed.

SUMMARY

Embodiments of the invention disclose a method, computer program product, and computer system for predicting a branch in an instruction stream. A processor receives a first instruction within a first instruction stream, where the first instruction includes at least a first instruction address. The processor selects a current row of a branch target buffer and a corresponding current row of a one-dimensional array based, at least in part, on the first instruction address. The processor reads information included in the current row of the one-dimensional array, where the current row of one-dimensional array includes at least a first target address of a first prediction and a column of the current row of the branch target buffer expected to contain a second target address of a second prediction. The processor receives a second instruction within a second instruction stream, where the second instruction includes a second instruction address and the second instruction address is equal to the first target address. The processor reads information included in the current row of the branch target buffer, where the information included in at least one column of the current row of the branch target buffer includes at least the second target address of the second prediction. The processor encounters a branch present within the first instruction stream, where the encountered branch includes at least a third target address.

DETAILED DESCRIPTION

The present invention will now be described in detail with reference to the Figures.FIG. 1is a functional block diagram illustrating a computer system, generally designated100, in accordance with one embodiment of the present invention.

In general, embodiments of the present invention provide a branch target buffer column predictor (CPRED) used to predict the presence, column, and target of a branch indicated by a given row of a branch target buffer, and an approach to predict the presence and target of a branch using a branch target buffer column predictor.

FIG. 1depicts computer system100, which is an example of a system that includes the branch target buffer column predictor of embodiments of the present invention. Computer system100includes communications fabric102, which provides communications between computer processor(s)104, memory106, persistent storage108, communications unit110, input/output (I/O) interface(s)112, cache116, branch target buffer (BTB)310, and branch target buffer column predictor (CPRED)320. Communications fabric102can be implemented with any architecture designed for passing data and/or control information between processors (such as microprocessors, communications and network processors, etc.), system memory, peripheral devices, and any other hardware components within a system. For example, communications fabric102can be implemented with one or more buses.

Memory106and persistent storage108are computer readable storage media. In this embodiment, memory106includes random access memory (RAM). In general, memory106can include any suitable volatile or non-volatile computer readable storage media. Cache116is a fast memory that enhances the performance of processors104by holding recently accessed data and data near accessed data from memory106.

Program instructions and data used to practice embodiments of the present invention may be stored in persistent storage108for execution by one or more of the respective processors104via cache116and one or more memories of memory106. In an embodiment, persistent storage108includes a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, persistent storage108can include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer readable storage media that is capable of storing program instructions or digital information.

Communications unit110, in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit110includes one or more network interface cards. Communications unit110may provide communications through the use of either or both physical and wireless communications links. Program instructions and data used to practice embodiments of the present invention may be downloaded to persistent storage108through communications unit110.

I/O interface(s)112allows for input and output of data with other devices that may be connected to each computer system. For example, I/O interface112may provide a connection to external devices118such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices118can also include portable computer readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention can be stored on such portable computer readable storage media and can be loaded onto persistent storage108via I/O interface(s)112. I/O interface(s)112also connect to a display120.

Processor(s)104include BTB310and CPRED320which are sets of hardware logic components capable of storing predictions for the location of branches in an instruction stream.

FIG. 2is a flowchart, generally depicted200, depicting the operational steps used in the utilization of the branch target buffer column predictor of the invention (CPRED320), in accordance with an embodiment of the invention. It should be appreciated that the process described inFIG. 2describes the operation of CPRED320in embodiments where the predictions drawn from CPRED320are verified by the predictions later drawn from BTB310. In other embodiments where the predictions drawn from CPRED320differ from the predictions drawn from BTB310, the information stored in CPRED320is updated using the process described in greater detail with respect toFIG. 4. The structure and usage of CPRED320and BTB310are described in greater detail with respect toFIG. 3.

In step205, a microprocessor such as processor(s)104receives a stream of instructions describing one or more operations which the microprocessor is to perform, and identifies the address of the first instruction present in the instruction stream. In some embodiments, one or more branches may be present in the instruction stream at various locations. In general, a branch represents a possible break in the sequential instruction stream which describes a new location within the instruction stream where processing is to jump to. In some embodiments, two-way branching is implemented within a high level programming language with a conditional jump instruction such as an if-then-else structure. In these embodiments, a conditional jump can either be “not taken” and continue execution with the set of instructions which follow immediately after the conditional jump in the instruction stream, or it can be a “taken” branch and jump to a different place in instruction stream where the second branch of instructions are stored. In general, a branch such as a two-way branch is predicted using information stored in BTB310and CPRED320to be either a “taken” branch or a “not taken” branch before the instruction or set of instructions containing the branch is executed by the microprocessor. It should be appreciated by one skilled in the art that instructions will be structured differently in various embodiments of the invention where different architectures and instruction sets are used by microprocessors such as processor(s)104.

In step210, CPRED320is indexed to the row corresponding to the address of the first instruction received in the instruction stream and the information included in the current row of CPRED320is read. In various embodiments, depending on the width of the address space, various numbers of unique instruction addresses may be present, and as a result different numbers of rows may be required for CPRED320in various embodiments of the invention. Generally, only a subset of bits of the instruction address for a given instruction are used to identify the row number in CPRED320which contains branch prediction data for the given instruction. For example, in an embodiment where 32-bit instruction addresses are used (including bits0through31), each instruction address is split into an L-tag made up of the first 17 bits of the instruction address (bits0through16), an index made up of the next 10 bits of the instruction address (bits17through26), and an R-tag made up of the final 5 bits of the instruction address (bits27through31). In this embodiment, because only the ten bits of the instruction address used as the index are used to determine the row in CPRED320in which the branch prediction data is stored for that instruction, CPRED320includes 1024 (210) rows. Further, in some embodiments CPRED320is designed to contain the same number of rows as BTB310and be indexed based on the same 10 bits of the instruction address as BTB310. In other embodiments, BTB310and CPRED320use different numbers of bits to determine which row in the respective tables contain the branch prediction information for that instruction. In these embodiments, it is possible for BTB310and CPRED320to have different numbers of rows while still allowing for the invention to operate correctly.

In decision step215, the data contained in the row of CPRED320corresponding to the current instruction is read to determine if a branch is expected for the current instruction. It should be appreciated that one row of CPRED320can correspond to a large number of instruction addresses in embodiments where aliasing is used, and that in these embodiments multiple instruction addresses will correspond to the same row in CPRED320. In one embodiment, the first bit of data stored in the current row of CPRED230contains a binary indication of whether or not a taken prediction is present in the corresponding row of BTB310. In this embodiment, the determination of whether or not a taken prediction is present in the corresponding row of BTB310is made using this single bit of data alone. In this embodiment, if the first bit of data is a zero indicating that there is not taken prediction present in the corresponding row of BTB310(decision step215, no branch), then processor(s)104determines if more instructions are present in the instruction stream in decision step225. If the first bit of data is a one indicating that there is a taken prediction present in the corresponding row of BTB310(decision step215, yes branch), then processor(s)104identifies the target address of the first taken branch indicated by the current row of CPRED320in step220.

In step220, processor(s)104identifies the target address of the first taken branch prediction indicated in the current row of CPRED320. In one embodiment, a single 17-bit binary number is contained in each row of CPRED320. In this embodiment, the first bit of data present in a row “K” of CPRED320is a binary indicator which indicates whether or not a valid prediction for a taken branch is expected to be present in any of the columns present in row “K” of BTB310. In this embodiment, because there are six columns present in BTB310, six bits of additional data are used to indicate whether the first taken prediction is present in each of the six columns present in the row “K” of BTB310. In general, the “nth” digit of these six digits indicates that the “nth” column of row “K” of BTB310will contain the first taken branch prediction. It should be appreciated that only one of the “n” digits can have a value of one at a given time. In this embodiment, the final 10 bits of data are used to store a portion of the predicted target address of the first taken branch predicted to be stored in the row “K” of BTB310. It should be appreciated that the number of bits of the target address stored in each row of CPRED320varies in different embodiments of the invention. In some embodiments, an additional structure such as a changing target buffer (CTB) may be used to predict the target address for the first taken prediction indicated by one or more rows of CPRED320. In these embodiments, the target address of the first taken prediction may be omitted, and the indication of the column of row “K” of BTB310is used to more easily identify the target address of the first taken prediction using the additional structure such as the CTB. In general, the indication of which column of row “K” of BTB310contains the first taken prediction is used in embodiments where additional structures such as a CTB are used, or embodiments where the first taken branch is a branch of a certain type such as MCENTRY, MCEND, EX, or EXRL.

It should be appreciated that a prediction is drawn from BTB310simultaneously while a prediction is drawn from CPRED320, and that the re-indexing performed using the prediction drawn from CPRED320is valid until confirmed or disputed by the prediction drawn from BTB310, as described in greater detail with respect toFIG. 4. Additionally, it should be appreciated that CPRED320does not provide a prediction of the full target address of the first taken branch, but predicts only a subset of the bits of the target address of the first taken branch. In general, the prediction of the full target address is retrieved from BTB310using the indication of the column of row “K” of BTB310expected to contain the first taken prediction included in CPRED310. In the depicted embodiment, a prediction of a taken branch is drawn by examining the first bit of the 17-bit number included in the current row of CPRED320to determine if a valid prediction is present, and if a valid prediction is present, then examining the last 10 bits of the 17-bit number included in the current row of CPRED320to determine a portion of the target address of the predicted branch used to re-index BTB310and CPRED320to the rows corresponding to the target address of the predicted first taken branch. It should be appreciated that the last 10 bits of the 17-bit number included in the current row of CPRED320represent a subset of the bits of the target address of the predicted branch. In various embodiments, the bits of data included in CPRED320are the bits of data used to re-index CPRED320to the target address of the prediction. In embodiments where more or fewer bits of data are used to re-index CPRED320, the length of the number included in a given row of CPRED320will differ from the 17 bits of data described in the current embodiment. Once the target address of the first taken branch prediction is identified, processor(s)104re-indexes CPRED320and BTB310to the rows corresponding to the target address for the first taken branch prediction. Once CPRED320and BTB310are re-indexed, processor(s)104re-starts the process of searching BTB310and CPRED320for branch predictions at the new target address in step210.

In decision step225, processor(s)104determines if more instructions are present in the instruction stream. In general, determining that more instructions are present is accomplished by receiving a request for a search restart from the main branch predictor using the next sequential instruction address. If no request for restarts is received (decision step225, no branch), then branch prediction search ends. If a request for a restart is received with an instruction address following the previous instruction address (decision step225, yes branch), then processor104continues searching the next sequential rows of BTB310and CPRED320for predictions of the presence of branches in step230. In the depicted embodiment, step230includes incrementing the index of the current rows of BTB310and CPRED320and starting a new search by reading the data included in the new current rows of BTB310and CPRED320. In general, the indexes of BTB310and CPRED320are incremented because the next row in BTB310and CPRED320contains branch prediction information for the next sequential set of instructions present in the instruction stream.

FIG. 3is a block diagram of the components of branch target buffer (BTB)310and branch target buffer column predictor (CPRED)320, in accordance with an embodiment of the invention.

BTB310is a collection of tabulated data including “M” columns and “N” rows of data. In the depicted embodiment, the value of “M” is depicted as being 6, yielding an embodiment where BTB310contains a total of six columns used to store the six most recent predictions for each row present in BTB310. In general, a given cell in BTB310is referred to as BTB(N, M), where “N” is the row number and “M” is the column number. It should be appreciated that the number of rows and columns included in BTB310varies in different embodiments of the invention and that the depicted embodiment of BTB310which included 6 columns and 1024 rows is not meant to be limiting. It should be appreciated by one skilled in the art that various methods for drawing predictions from the information included in BTB310may be used in various embodiments of the invention, and that the invention is not limited to any specific method of drawing predictions from the information included in BTB310. Additionally, the information included in BTB310may be stored or encoded differently in various embodiments of the invention, and the examples provided of how information is stored in BTB310is not meant to be limiting.

CPRED320is a one-dimensional array of data used in conjunction with BTB310by branch prediction logic to predict the column in which the first taken prediction will be present in BTB310for a given row. In some embodiments, CPRED320contains the same number of rows (“N”) as BTB310, with a given row “K” in CPRED320providing information related to the first taken prediction present in the corresponding row “K” of BTB310. In other embodiments, CPRED320contains fewer rows than BTB310, and in these embodiments aliasing is used to apply the column prediction contained in row “K” of CPRED320to multiple rows in BTB310. In general, decreasing the size of CPRED320is desirable in embodiments where reducing the amount of time required to access CPRED320or limiting memory required by CPRED320is important. Additionally, increasing the size of CPRED320is desirable in embodiments where reducing the amount of time required to access CPRED320or limiting memory required by CPRED320is not important, and improving the accuracy of each branch prediction is important. For example, in an embodiment where the address space has a dimension of three bits, BTB310contains eight rows of data to ensure that each possible address corresponds to a unique row in BTB310which can be used to predict the presence of branches in the instruction stream for that address. In this example, it is possible to use only two rows of data for CPRED320and utilize the prediction contained in each row of CPRED320for four rows of BTB310. For example, if BTB310includes rows numbered 1 through 8, then row1of CPRED320is used to provide a column prediction for rows1through4of BTB310while row2of CPRED320is used to provide a column prediction for rows5through8of BTB310.

In general, the data included in each row of CPRED320describes which column in BTB310contains the last taken prediction for the corresponding row in BTB310. In some embodiments, the address of the first taken branch target for a row “K” in BTB310is included in the entry for the corresponding row “K” in CPRED320. The reason for including the address of the first taken branch target is to be able to re-index BTB310and CPRED320to the address of the first taken branch target without having to retrieve the address of the first taken branch target from BTB310.

In various embodiments, BTB310and CPRED320are accessed simultaneously, and a prediction is drawn from both BTB310and CPRED320independently. It should be appreciated by one skilled in the art that in these embodiments, many different methods for drawing predictions from BTB310may be used. Because of the decreased number of cycles required to draw a prediction from CPRED320, the prediction drawn from CPRED320is used as a preliminary prediction until confirmed by the prediction drawn from BTB310. In embodiments where the prediction drawn from BTB310is the same as the prediction drawn from CPRED320, branch prediction logic proceeds to continue retrieving additional predictions for the following instructions in the instruction stream. In embodiments where the prediction drawn from CPRED320differs from the prediction later drawn from BTB310, the prediction drawn from BTB310is assumed to be more reliable and as a result BTB310and CPRED320are both re-indexed to the address of the first taken branch target predicted by BTB310and the column prediction data and address of the new first taken branch target are updated for the corresponding row “K” in CPRED320.

FIG. 4is a flowchart depicting the operational steps required to utilize BTB310and CPRED320in conjunction with each other to draw branch predictions and update the predictions stored in CPRED320in the event that an incorrect prediction is present.

In step405, BTB310is indexed to a row “K” corresponding to the current instruction, and hit detection is performed on the row “K” to determine which column (if any) contains a usable branch prediction for that instruction. In general, it takes five clock cycles for a branch prediction to be reported using the information stored in BTB310, and after the first prediction is reported, additional prediction are reported once every four cycles. As a result of this, predictions drawn using the information stored in BTB310alone can be issued every four clock cycles. In this embodiment, due to predictions from CPRED320being drawn faster (once every two clock cycles once the first prediction is reported), BTB310and CPRED320are both re-indexed once predictions are drawn from CPRED320every second clock cycle, and the predictions drawn from BTB310alone are used to verify the predictions drawn from CPRED320two clock cycles earlier. The cycles required for drawing predictions from the information included in BTB310and CPRED320are described in greater detail with respect toFIGS. 5 and 6.

In step410, CPRED320is indexed to a row “K” corresponding to the current instruction and the prediction contained in the row “K” of CPRED320is read. The prediction read from row “K” of CPRED320is used to start a new search using the partial target address read from row “K” of CPRED320. In the depicted embodiment, steps405and410begin simultaneously and occur in parallel when a new instruction is received by processor(s)104. In general, it takes three clock cycles for a prediction to be reported from the data included in CPRED320. In clock cycle0, CPRED320is indexed to the row “K” corresponding to the current instruction. In clock cycle1, the information stored in the row “K” of CPRED320is read by processor(s)104, along with information describing which columns in BTB310is expected to contain the first taken branch. In clock cycle2, the prediction of the first taken branch is reported and both BTB310and CPRED320are re-indexed to the address of the first taken branch predicted by the information in row “K” of CPRED320. Both BTB310and CPRED320are re-indexed at this time to ensure that the branch prediction search for the next target location occurs as soon as possible. It should be appreciated that clock cycle2serves as clock cycle0for the following branch prediction search performed using the information stored in CPRED320.

In decision step415, the prediction reported in step410is compared to the prediction reported in step405to determine if CPRED320predicted the location and target of the first taken branch present in BTB310correctly for the given branch. In one embodiment, the target addresses included in both branch predictions are compared to determine if there is any difference between the prediction reported in step410and the prediction reported in step405. In various embodiments, the prediction drawn from the data included in CPRED320includes only a subset of the bits of the target address of the prediction drawn from the information included in BTB310. In these embodiments, only the bits which are included in both predictions are compared. If the predictions are equal (decision step415, yes branch), then processor(s)104continues with the branch prediction search initiated in step410using the data received from CPRED320in step425. If the predictions received are not equal (decision step415, no branch), then processor(s)104re-indexes CPRED320and BTB310to the first taken branch prediction reported in step405, and starts the branch prediction search over from that point.

In step420, BTB310and CPRED320are re-indexed to the address of the first taken branch predicted in step405. Additionally, the information stored in the row “K” of CPRED320is updated to reflect the prediction reported in step405. In this process, the correct address of the branch target predicted in step405is written to row “K” of CPRED320along with the column of BTB310from which the prediction reported in step405was fetched.

In step425, the search initiated in step410continues based on the prediction drawn from the information included in row “K” of CPRED320. It should be appreciated that the process of continuing the search started in step410includes re-indexing CPRED320to the row corresponding to the target address of each new branch prediction as they are encountered. For example, in the depicted embodiment, a branch prediction included in row “K” of CPRED320includes a target address corresponding to row “L” of CPRED320. After re-indexing CPRED320to row “L”, a prediction with a target address corresponding to row “M” is read. In general, the process of identifying successive predictions is referred to as continuing a search.

FIG. 5is a timing diagram, generally designated500, illustrating successive branch prediction searches performed using BTB310. Each column of timing diagram500present below row550, such as columns531,532,533,534, and535illustrates the current status of each branch prediction search currently being performed by processor104in a given clock cycle, with the clock cycle number indicated by the cell present within row550of that column. Each row of timing diagram500present below row550, such as rows541,542,543,544, and545illustrates the current state of a branch prediction search performed by processor104using BTB310in successive clock cycles. For the search represented by a given row of timing diagram500, the row of BTB310currently being searched is indicated by the cell within column520of that row. Row550indicates the current clock cycle of processor104performing the various branch prediction searches indicated by timing diagram500.

Row541illustrates a branch prediction search with search address “X” which involves drawing a prediction using the information included in row “X” of BTB310. In the depicted embodiment, the prediction is drawn from the information included in row “X” of BTB310in the fifth cycle of the branch prediction search (B4) (row541, col531). In the depicted embodiment, the five cycles required for each branch prediction search performed using BTB310are B0, B1, B2, B3, and B4. In cycle B0, BTB310is indexed to a starting search address of “X”. In some embodiments the starting search address has additional properties associated with it such as an indication of whether or not the instructions received by processor104are in millicode, the address mode, a thread associated with the instructions received by processor104, or other information stored in BTB310in various embodiment of the invention. In general, cycle B1is an access cycle for BTB310which serves as busy time while information included in row “X” of BTB310is retrieved. In cycle B2, the entries in row “X” are returned from BTB310and hit detection begins. In various embodiments, hit detection includes ordering the entries in row “X” by instruction address space, filtering for duplicate entries, filtering for a millicode branch if the search is not for a millicode instruction or set of millicode instructions, or filtering for other criteria indicated by the entries present in row “X” of BTB310. In some embodiments, hit detection additionally includes discarding any branch with an address earlier than the starting search address and identifying the first entry that is predicted to be taken. Additionally, any entry for a taken branch present after the first taken branch in the instruction space may be discarded, and all of the remaining branch predictions including the first taken branch prediction and a number of not taken branch predictions are reported. In cycle B3, hit detection continues and concludes with an indication of whether or not any of the entries included in row “X” of BTB310contain a valid prediction of a branch which is expected to be encountered in the instruction stream. In cycle B4, the target address of the first taken prediction is reported and a new branch prediction search is initiated with a search address equivalent to the target address of the first taken prediction reported.

In the depicted embodiment, in clock cycle1a branch prediction search with a search address of “X” begins cycle B0(row541, col531). In clock cycle2, the branch prediction search with a search address of “X” advances to cycle B1(row541, col532), while a new branch prediction search with a search address of “X+1” begins cycle B0(row542, col532). It should be appreciated that the index “X+1” represents the next sequential portion of the address space present after “X”, and that correspondingly row “X+1” represents the next row present in BTB310present after row “X”. In clock cycle3, the branch prediction search with a search address of “X” advances to cycle B2(row541, col533), the branch prediction search with a search address of “X+1” advances to cycle B1(row542, col533), and a new branch prediction search is initiated with a search address of “X+2” (row543, col533). In clock cycle4, the branch prediction search with a search address of “X” advances to cycle B3(row541, col534), the branch prediction search with a search address of “X+1” advances to cycle B2(row542, col534), the branch prediction search with a search address of “X+2” advances to cycle B1(row543, col534), and a new branch prediction search is initiated with a search address of “X+3” (row544, col534). In clock cycle5, the branch prediction search with a search address of “X” advances to cycle B4and issues a prediction of a first taken branch with a target address of “Y” (row541, col535). As illustrated in the depicted embodiment of the invention, a new branch prediction search is initiated in clock cycle5with a search address of “Y” (row545, col535). In some embodiments, the searches with search indices “X+1”, “X+2”, and “X+3” are cancelled upon the search with an index of “X” reporting a prediction for a taken branch. However, in the depicted embodiment, these searches continue to advance to the next cycles before being cancelled following clock cycle5.

In general, it should be appreciated that, using BTB310alone, branch prediction logic can identify a taken prediction up to once every four clock cycles.

FIG. 6is a timing diagram, generally designated600, illustrating successive branch prediction searches performed using BTB310and CPRED320. Similarly toFIG. 5, each column of timing diagram600present below row650, such as columns631,632,633,634, and635illustrates the current status of each branch prediction search currently being performed by processor104in a given clock cycle, with the clock cycle number being indicated by the cell present within row650of that column. Each row of timing diagram600present below row650, such as rows641,642, and643illustrates the current state of an individual branch prediction search performed by processor104using BTB310and CPRED320in each clock cycle. For the search represented by a given row of timing diagram600, the row of BTB310and CPRED320currently being searched is indicated by the cell within column620of that row. Row650indicates the current clock cycle of processor104performing the various branch prediction searches indicated by timing diagram600.

Row641illustrates a branch prediction search with search address “X” which involves drawing a prediction using the information included in row “X” of BTB310and row “X” of CPRED320. It should be appreciated that in some embodiments, different indexing structures are used for BTB310and CPRED320. In these embodiments, the row “X” of BTB310from which information is read will differ from the row of CPRED320from which information is read. It should additionally be appreciated that the embodiment where BTB310and CPRED320use the same indexing structure serves as an example of one embodiment and is not meant to be limiting. In the depicted embodiment, a prediction is drawn from the information included in row “X” of CPRED320in the third cycle of the branch prediction search (cycle B2), and a prediction is drawn from the information included in row “X” of BTB310in the fifth cycle of the branch prediction search (cycle B4). In the depicted embodiment, the five cycles required for each branch prediction search performed using information included in BTB310are the same five cycles B0through B4as described in greater detail with respect toFIG. 5. In this embodiment, the three cycles required to draw a prediction from the information included in row “X” of CPRED320are B0, B1, and B2. In cycle B0, CPRED320is indexed to a starting search address of “X”. In some embodiments the starting search address has additional properties associated with it such as an indication of whether or not the instructions received by processor104are in millicode, the address mode, a thread associated with the instructions received by processor104, or other information stored in BTB310or CPRED320in various embodiments of the invention. In general, cycle B1is an access cycle for CPRED320which serves as busy time while information included in row “X” of CPRED320is retrieved. In cycle B2, the target address of the first taken prediction is reported and a new branch prediction search is initiated with a search address equivalent to the target address of the first taken prediction reported.

In the depicted embodiment, in clock cycle1a branch prediction search with a search address of “X” begins cycle B0(row641, col631). In clock cycle2, the branch prediction search with a search address of “X” advances to cycle B1(row641, col632), while a new branch prediction search with a search address of “X+1” begins cycle B0(row642, col632). It should be appreciated that the index “X+1” represents the next sequential portion of the address space present after “X”, and that correspondingly row “X+1” represents the next row present in BTB310and CPRED320after row “X”. In clock cycle3, the branch prediction search with a search address of “X” advances to cycle B2and returns a prediction of a first taken branch with a target address of “Y” (row641, col633). As illustrated in the depicted embodiment of the invention, a new branch prediction search is initiated in clock cycle3with a search address of “Y” (row643, col633). In some embodiments, the search with search address “X+1” is cancelled upon the search with an index of “X” reporting a prediction for a taken branch. However, in the depicted embodiment, these searches continue without being cancelled. In clock cycle4, the branch prediction search with a search address of “X” advances to cycle B3(row641, col634), the branch prediction search with a search address of “X+1” advances to cycle B2and returns a prediction of no taken branch (row642, col634), and the branch prediction search with a search address of “Y” advances to cycle B1(row643, col634). In some embodiments, a new branch prediction search with a search address of “Y+1” may begin in clock cycle4, however no additional searches are depicted inFIG. 6. In clock cycle5, the branch prediction search with a search address of “X” advances to cycle B4and reports a prediction of a first taken branch with a target address of “Y” (row641, col635) based on the information contained in BTB310, confirming the prediction reported in clock cycle3using the information contained in CPRED320. Additionally in clock cycle5, the branch prediction search with a search address of “X+1” advances to cycle B3(row642, col635) and the branch prediction search with a search address of “Y” advances to cycle B2and reports a prediction of no taken branch (row643, col635). In embodiments where a branch is predicted in clock cycle5, a new branch prediction search with a search address equal to the target address of the branch prediction in clock cycle5may begin in clock cycle5, however no additional searches are depicted inFIG. 6.

In general, it should be appreciated that, using both BTB310and CPRED320, branch prediction logic can identify a taken branch up to once every two clock cycles. Additionally, it should be appreciated that the use of CPRED320allows for predictions to be reported earlier and allows for the creation of a new search with a search address equivalent to the target address of a taken branch prediction in cycle B2as opposed to cycle B4.