Abstract:
Various embodiments are described relating to processors, branch predictors, branch prediction systems, and computing systems. In an example embodiment, a processor includes a plurality of branch predictors. Each branch predictor is adapted to provide a prediction and an override signal. In the example embodiment, the processor futher includs a branch prediction control circuit. The branch prediction circuit is adapted to generate a branch prediction based on the prediction and the override signal from each predictor.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This subject matter of this application is related to the subject matter of co-pending application, entitled “Hierarchical Processor,” Ser. No. 11/215,833 filed on Aug. 29, 2005, hereby incorporated by reference. 
   BACKGROUND 
   The successful resolution of conditional branches is an important issue in modern microprocessors. When a conditional branch enters an execution pipeline, the instructions following the branch may typically wait for the branch resolution. A common solution to this problem is speculative execution: the branch outcome and/or its target may be dynamically or statically predicted, so the execution may proceed without stalling. However, if a branch is mispredicted, speculatively executed instructions are typically flushed and their results discarded, thus wasting a significant number of processor clock cycles. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram illustrating an instruction pipeline of a processor  100  according to an example embodiment. 
       FIG. 2  illustrates a block diagram of a branch predictor system  114  according to an example embodiment. 
       FIG. 3  is a diagram illustrating a branch predictor  300  that uses a branch target buffer (BTB) according to an example embodiment. 
       FIG. 4  is a diagram of a finite state machine, which may provide the basis of a saturating two-bit counter that may be used for dynamic prediction of a branch outcome, according to an example embodiment. 
       FIG. 5  is a diagram that illustrates another example branch predictor that uses a combination of global history and the branch address (or IP), according to an example embodiment. 
       FIG. 6  illustrates an operational flow  600  representing example operations to select a branch prediction where a predictor may have asserted a positive override signal. 
       FIG. 7  illustrates an operational flow  700  representing example operations to select a branch prediction where a predictor may have asserted a negative override signal. 
       FIG. 8  is a block diagram of a computing system according to an example embodiment. 
   

   DETAILED DESCRIPTION 
   Referring to the Figures in which like numerals indicate like elements,  FIG. 1  is a block diagram illustrating an instruction pipeline of a processor  100  according to an example embodiment. According to an example embodiment, processor  100  may be hierarchical or may include one or more stages that may be multilevel. In an example embodiment, one or more pipeline stages may be grouped into a cluster (or execution cluster). Processor  100  may include multiple parallel clusters, with, for example, one or more stages being replicated in each cluster to provide parallel processing paths. 
   Referring to  FIG. 1 , an instruction pipeline of processor  100  may include a number of pipeline stages (or pipestages). Although not shown, one or more of the pipeline stages may include multiple structures or may be multilevel. Processor  100  may include an instruction fetch unit (IFU)  110  to fetch instructions to be decoded and executed. The instructions fetched may be, for example, architectural instructions, which later in the pipeline may be decoded into one or more micro-operations or micro-ops (uops). 
   Processor  100  may include a branch predictor system (BP)  114  to predict whether a branch instruction will be taken or not. An output from branch predictor system  114  (e.g., taken or not taken) may, for example, cause instruction fetch unit  110  to begin fetching instructions from a branch path (e.g., if a branch instruction is predicted as taken) or to continue fetching instructions along a fall-through path (e.g., if the branch is predicted as not taken). The instruction pointer (IP) (e.g., address) for each fetched instruction may be provided to the branch predictor system  114  to allow the branch predictor system  114  to predict whether a branch instruction will be taken or not taken. 
   Processor  100  may also include an instruction cache (I$)  116  to cache fetched instructions. A level 2 instruction cache (not shown) may also be provided. An instruction decoder (D)  118  may decode each fetched (e.g., architectural) instruction into one or more micro-operations or micro-ops (uops). Processor  100  may include a mapper (or register renamer) (M)  120  to map architectural registers to physical (or virtual) registers. 
   An instruction scheduler (S)  122  may generally schedule micro-ops (uops) for execution, for example, when operands for the instruction are ready and the appropriate execution resources are available. According to an example embodiment, the scheduler may be a single scheduler or may include a multilevel scheduler (or multiple schedulers), such as a level 2 scheduler and a level 1 scheduler (not shown). 
   According to an example embodiment, processor  100  may include a limited set of architectural registers (e.g. eax, ebx, . . . ) that may be seen or accessed by a programmer. Processor  100  may include a larger set of physical registers, shown as the register file (RF) 124 . A register (or entry) in the register file  124  may be allocated for each uop to store the execution result for the micro-op. The register file may also store status information indicating the status of each micro-op. The different status for a uop that may be tracked in its entry in the register file  124  may include, for example: uop is scheduled for execution, uop is executing, uop has completed execution and results are being written back to the register file entry, uop is ready for retirement, and uop is being retired. 
   Processor  100  may include one or more execution units  126  to execute uops. The execution units may include one or more ALU (arithmetic logic unit) execution units and one or more memory load and memory store execution units, for example. A data cache (D$)  128  may be provided to cache data, execution results, etc. Although not show, the processor  100  may include one or more store buffers. An instruction window logic  130  may be provided to handle retirement of uops. 
     FIG. 2  illustrates a block diagram of a branch predictor system  114  according to an example embodiment. Branch predictor system  114  may include one or more branch predictors. According to an example embodiment, branch predictor system  114  may include two or more branch predictors, including branch predictor (BP 1 )  206 , branch predictor (BP 2 )  208 , . . . and branch predictor (BPn)  210 . Although three branch predictors are shown, branch predictor system  114  may include any number of branch predictors. Branch predictors  206  (BP 1 ),  208  (BP 2 ) and  210  (BPn) may be any type of branch predictors, such as dynamic branch predictors, static branch predictors, etc. There are a wide variety of branch prediction mechanisms. 
     FIG. 3  is a diagram illustrating a branch predictor  300  that uses a branch target buffer (BTB)  302 , where the BTB  302  is provided for prediction of branch targets, and an outcome predictor  304  may be provided for prediction of branch outcomes. In this example branch predictor, the branch target buffer (BTB)  302  may be a cache, where a part of the branch address (or instruction pointer or IP for the conditional branch) may be used as a cache index, and the cache data may be, for example, the last target address of that branch. More complex BTBs may hold multiple target addresses, and may include some mechanism to choose which address should be speculatively executed. 
     FIG. 4  is a diagram of a finite state machine, which may provide the basis of a saturating two-bit counter that may be used for dynamic prediction of a branch outcome (branch prediction). The counter may range in states from 00 to 11 (e.g., 00 indicating strongly not taken, 01 indicating weakly taken, 10 indicating weakly taken, and 11 indicating strongly taken). The prediction output by this predictor may be taken/not taken, and may also provide a supplemental output, such as weak or strong. For example, every time a branch is taken, the two-bit counter for that branch (or for that IP or address) is incremented (saturating at 11 ), and every time the branch is not taken, the counter is decremented (saturating at 00). This is an example of a per-IP (instruction pointer) branch predictor that uses a counter (since the counter keeps track of the last branch results for this branch instruction). The counter may be provided as a two-bit cell in a branch prediction table (BPT), with a counter provided for each branch instruction. The BPT may be accessed in different ways, such as using a portion of the IP (branch instruction) address to index to the BPT. This is an example of a local branch predictor since the prediction is based on the local (per-IP) branch history. 
   Other types of branch predictors may rely on global branch history, such as by using a branch history register (BHR), which may be a shift register or other structure that may keep the history of N most recent branch outcomes (e.g., N most recent branch instructions). In general, predictors that use global history may benefit from correlations between subsequent branches in the program execution flow, while local predictors may be based on correlation between subsequent executions of the same branch instruction. 
     FIG. 5  is a diagram that illustrates another example branch predictor  500  that uses a combination of global history (via a BHR  504 ) and the branch address  502  (or IP) to generate an index (using an index function  506 ) into a branch prediction table (BPT)  508  to produce an outcome prediction or branch prediction. These are just a few examples of branch predictors that may be used. There are many other predictors that may be used as well, such as GShare, GSelect, GSkew, etc. 
   Referring to  FIG. 2  again, an instruction fetch unit (IFU)  110  fetches instructions (or uops), and provides the IP (instruction pointer) or address of the instruction to branch predictor system  114  for branch prediction. Also, instructions or uops may be executed further in the pipeline by execution unit  126 , and execution results are provided via line  248  to a structure, such as the IFU  110 . The IFU  110  (or other structure) may generate and provide a global branch history, e.g., via a branch history register. 
   As shown in  FIG. 2 , IFU  110  may provide the instruction pointer or IP of each branch instruction (address) and/or a global branch history (GH) to one or more branch predictors, such as BP 1   206 , BP 2   208 , . . . BPn  210 . The IP or branch address is provided via lines  212 , while the global branch history (GH) may be provided via lines  214 , to each branch predictor. Some predictors may use only the IP address and local history for each branch instruction (e.g., a per-IP predictor), while some predictors may use the global branch history (e.g., a per-history predictor), while other predictors may use a combination of the instruction pointer or branch address and the global history. Yet other predictors may rely on additional information or even different information to make branch predictions. 
   As shown in  FIG. 2 , each branch predictor (e.g.,  206 ,  208 ,  210 ) may generate a number of outputs to a branch prediction (BP) controller  204 . The BP controller  204  may receive information from one or more branch predictors (e.g.,  206 ,  208 ,  210 ) and may generate an overall branch prediction via line  250 . 
   Referring to  FIG. 2 , the outputs from each branch predictor may include, for example, a branch prediction (or prediction), a confidence level and an override signal. The signals output by branch predictors may be different, or may include additional output signals, not shown. Branch predictor  206  (BP 1 ) may output a prediction via line  220 , a confidence level via line  222  and an override signal via line  224 . Branch predictor  208  (BP 2 ) may output a prediction via line  230 , a confidence level via line  232  and an override signal via line  234 . Likewise, branch predictor  210  (BPn) may output a prediction via line  240 , a confidence level via line  242  and an override signal via line  244 . In another embodiment, different predictors may output different types of signals. 
   The prediction output by each predictor (via lines  220 ,  230  and  240  for predictors  206 ,  208  and  210 , respectively) may be the branch prediction for this branch instruction (or IP), e.g., taken or not taken. As noted above, each branch predictor (e.g.,  206 ,  208 ,  210 ) may use a variety of different techniques for branch prediction. In an embodiment, each predictor ( 206 ,  208 ,  210 , etc.) may be a different type of predictor or may use a different technique for branch prediction, although this is merely another example embodiment and is not required. 
   The confidence level output by each predictor (output via lines  222 ,  232  and  242  for predictors  206 ,  208  and  210 , respectively) may, for example, provide a measure of the predictor&#39;s accuracy, e.g., for this branch instruction. It may be based upon, for example, how often this predictor was correct over the last M times it predicted the outcome for this branch instruction. Therefore, the execution results (e.g., indicating whether a branch prediction was correct or not) from execution units  126  may be used to dynamically update the confidence level for each predictor (e.g., for each branch instruction or IP). The confidence level may be different for different branch instructions, and it may change over time (e.g., a dynamic value). Alternatively, the confidence level may be based upon, for example, the global history, e.g., how often this predictor was correct over the last M branch instructions. These are just a few examples of confidence levels, and this disclosure is not limited thereto. Confidence levels may be generated or provided in a number of different ways based on different types of information. In general, the prediction and confidence level for each predictor may be based upon, for example, one or more of: local per-IP branch prediction information (e.g., per-IP branch prediction table), global branch history (e.g., a global branch history register or table), execution results, data kept local to each branch predictor and accumulated over time, and/or other information. 
   In general, according to an example embodiment, an override signal, if asserted, may indicate that the override information may control (and override at least some other signals) in the selection of a prediction, instead of the other signals being used to control the selection of a branch prediction. 
   The override signal output by each predictor (e.g., override signal  224 , override signal  234  and override signal  244  output from branch predictors  206 ,  208  and  210 , respectively) may indicate when the predictor that is asserting the override signal should be trusted, regardless of short term history and/or confidence levels output by the predictors. There may be a variety of conditions that may be detected or measured, which may cause a branch predictor to assert its override signal (also known as a positive override signal). In an example embodiment, where a predictor has asserted its override signal (positive override signal), BP controller  204  may use the prediction from such predictor, without regard to short term history and the confidence levels by the different predictors. 
   In another embodiment, the override signal may actually include two different override signals: a positive override signal that may indicate the predictor asserting the positive override signal should be trusted, regardless of short term history and the signals (e.g., confidence levels) output by other predictors. This positive override signal is described above. 
   However, in addition to a positive override signal, each branch predictor may assert a negative override signal that may indicate that the predictor asserting the negative override signal should not be trusted, e.g., regardless of short term history and confidence levels output by each predictor. There may be a variety of conditions that may be detected or measured, which may cause a branch predictor to assert its negative override signal. Thus, according to an example embodiment, when a predictor asserts its negative override signal, BP controller  204  may ignore (e.g., not select) the prediction from the asserting predictor, even if that predictor outputs the highest confidence level, for instance. 
     FIGS. 6 and 7 , include various examples of operational flows. With respect to these FIGS., discussion and explanation may be provided with respect to the above-described examples of  FIGS. 1 and 2  and/or with respect to other examples and contexts. However, it should be understood that the operational flows may be executed in a number of other environments and contexts, and/or in modified versions of  FIGS. 1 and 2 . Also, although the various operational flows are presented in the sequence(s) illustrated, it should be understood that the various operations may be performed in other orders than those which are illustrated, or may be performed concurrently. In an example embodiment, one or more (or even all) of the operations described in the operational flows of  FIGS. 6 and 7  may be performed, either completely or in part, by BP controller  204  ( FIG. 2 ), although this is not required. These operations may be performed e.g., by BP controller  204 , with assistance of other circuits, which may be shown in the other FIGS., or may not be shown. 
     FIG. 6  illustrates an operational flow  600  representing example operations to select a branch prediction where a predictor may have asserted a positive override signal. After a start operation, the operational flow  600  moves to operation  610 . At operation  610 , it is determined if a positive override signal has been asserted by one of the branch predictors. For example, BP controller  204  may determine if one of branch predictors  206 ,  208  and  210  have asserted their positive override signal. 
   At operation  620 , if a positive override signal has been asserted by one of the branch predictors (e.g.,  206 ,  208 ,  210 ), then the branch prediction from the branch predictor that asserted the override signal is selected, e.g., by BP controller  204 . In an example embodiment, this branch prediction (of the asserting predictor) may be selected regardless of short term history or confidence levels of the predictors. 
   Otherwise, at operation  630 , if no positive override signal has been asserted, then a branch prediction may be selected (e.g., by BP controller  204 ) from the branch predictor having the highest confidence level. 
     FIG. 7  illustrates an operational flow  700  representing example operations to select a branch prediction where a predictor may have asserted a negative override signal. After a start operation, the operational flow  700  moves to operation  710 . At operation  710 , it is determined if a negative override signal has been asserted by one of the branch predictors. 
   At operation  720 , if a negative override signal was asserted by one of the branch predictors, then the prediction from the predictor asserting the negative override signal may be ignored, and the prediction from another predictor having the highest confidence level may be selected. Thus, according to an example embodiment, the prediction from a predictor asserting a negative override signal may be ignored even if the asserting predictor has the highest confidence level. 
   At operation  730 , otherwise, if no negative override signal has been asserted, then a branch prediction may be selected (e.g., by BP controller  204 ) from the branch predictor having the highest confidence level. 
   According to an example embodiment, the branch prediction system  114  may be used in isolation, or may be used in combination with one or more other branch predictors, and/or may be used at any level of a hierarchical or multilevel branch predictor. For example, in a multilevel branch predictor, the latest resolving branch prediction may control or override previous branch predictions. Therefore, in addition to selecting a branch prediction, BP controller  204  may (or may not) terminate a previously selected branch prediction, if such previously selected branch prediction is not the branch prediction selected by controller  204 , for example, although this is not required. Therefore, controller  204  may both select a branch prediction and may also deselect or terminate a previously selected branch prediction, e.g., based on the confidence level, prediction and override signal from each predictor. 
     FIG. 8  is a block diagram of a computing system according to an example embodiment. Computing system  800  may include processor  100  (which may include one or more branch predictors and a BP controller  204 , as described above), a memory  802  to store data and other information, an input/output device  806 , which may be a keyboard, mouse or other I/O device. Computing system  800  may also include a network interface  804 , which may be, for example, an Ethernet network interface, a wireless interface, a wireless LAN (local area network) or WLAN interface, a cellular interface, etc. Computing system  800  may also include other devices that are commonly included in such computing systems. Computing system  800  may include, for example, without limitation, a computer, a personal computer or PC, a laptop, a personal digital assistant (PDA), a cell phone or mobile phone, a wireless device, a WLAN phone, a router or switch, a wireless access point, a network device, etc. 
   While certain features of the described implementations have been illustrated as disclosed herein, many modifications, substitutions, changes and equivalents will now occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the various embodiments.