Patent Description:
Processing units use branch prediction to predict the outcome of a branch instruction so that the processing unit can begin speculatively executing instructions following the predicted branch before the processing unit has evaluated the branch instruction. To predict the outcome of the branching instruction the processing unit uses information in a branch prediction structure, such as indirect branch predictors that redirect the flow of the program to an arbitrary instruction, a return address stack that includes return addresses for subroutines executing on the processing unit, conditional branch predictors that predict the direction (taken or not taken) of a conditional branch, and a branch target buffer that includes information predicting the location, type, and target addresses of branching instructions.

Some implementations of branch prediction structures use a branch history of results of branching instructions executed by processes that were previously, or are currently, executing on the processing unit. For example, if a branching instruction previously directed the program flow to a first address <NUM>% of the time and a second address <NUM>% of the time, a corresponding entry in the branch prediction structure predicts that the branching instruction will direct the program flow to the first address, thereby allowing the process to speculatively execute instructions along the branch beginning at the first address without waiting for evaluation of the branching instruction. If the predicted branch turns out to be incorrect when the branching instruction is evaluated, speculative execution along the incorrectly predicted branch is suspended and the state of the processing unit is rolled back to the state at the branching instruction to begin executing along the correct branch. More specifically, both the branch prediction unit and the fetch unit are rolled back to process from the correct target of the branch, or the address after the branch if the branch was not taken. <CIT> discloses a dynamic throttling mechanism based on confidence values attributed to in flight branches.

BRIEF DESCRIPTION OF THE DRAWINGS.

Speculative execution leads to wasted work by a processor when a branch predictor incorrectly predicts the sequence of instructions to be fetched. Such wasted work wastes power due to processing the instructions following the predicted branch. Incorrect branch prediction also wastes processing bandwidth when a core is running in multi-thread mode in which the pipeline and resources are shared.

In various branch prediction pipelines, a branch predictor at the front end of a prediction pipeline predicts every cycle an address from which instructions should be fetched. It is unknown for a number of cycles whether the predictions being made are correct. As long as the predictions are correct, it is computationally efficient to keep the prediction pipeline full. However, when predictions are made incorrectly, the prediction pipeline needs to be flushed which results in a performance penalty associated with the flushing. Another penalty of having made the wrong predictions is that not only are resources wasted in executing instructions that are along the wrong path, but other threads running on the same system are penalized as the incorrectly predicted paths consume resources that other threads could have otherwise used. For example, in a single thread mode, there is no current solution addressing the wasted work caused by redirects. In multi-thread mode, competitive sharing of computing resources is based on fairness criteria assuming that each thread is executing instructions on the correct path and does not account for potential misprediction from different threads.

To reduce the amount of wasted work in order to save power and to improve multi-thread performance, <FIG> describe a system and method for performing branch confidence throttling. In one embodiment, a processor includes a branch predictor having one or more branch target buffer (BTB) tables and a branch prediction pipeline including a throttle unit and an uncertainty accumulator. The processor assigns an uncertainty value for each of a plurality of branch predictions generated by the branch predictor. The uncertainty accumulator adds the uncertainty value for each of the plurality of branch predictions to an accumulated uncertainty counter associated with the uncertainty accumulator. The throttle unit throttles operations of the branch prediction pipeline based on the accumulated uncertainty counter, slowing down threads that are less likely to be on the correct path, and by doing so, saves power by not executing instructions that are likely to be flushed.

<FIG> is a block diagram of a processor <NUM> implementing branch confidence throttling in accordance with some embodiments. The processor <NUM> includes a memory <NUM>, an instruction cache <NUM>, an instruction fetch unit <NUM>, a branch predictor <NUM>, one or more branch target buffer (BTB) tables <NUM>, and a processing pipeline <NUM>. In various embodiments, the processing system is included within a computer processor or otherwise distributed within a computer system. The memory <NUM> includes any type of volatile or nonvolatile memory, such as cache memory, for storing instructions and data. The instruction cache <NUM> accesses instructions from memory <NUM> and stores the instructions to be fetched. In various embodiments, the memory <NUM> and instruction cache <NUM> includes multiple cache levels. Further, the processor <NUM> also includes a data cache (not shown).

In <FIG>, simplified examples of the instruction fetch unit <NUM> and the processing pipeline <NUM> are depicted for ease of illustration. The branch predictor <NUM> of the instruction fetch unit <NUM> generates branch target addresses that are stored or provided to the one or more BTB tables (also commonly referred to as BT buffers and BTBs) <NUM>. The branch predictor <NUM> is implemented, at least in part, within the instruction fetch unit <NUM> of a processor (e.g., processor <NUM> of <FIG>). While BTB tables <NUM> are shown internal to the branch predictor <NUM> in <FIG>, the BTB tables <NUM> may or may not be located in the processor <NUM> proximate to certain elements of the instruction fetch unit <NUM> or the branch predictor <NUM>. In some embodiments, the processor <NUM> further includes multiple instruction fetch units <NUM> and processing pipelines <NUM>. The processing pipeline <NUM> includes a decode unit <NUM>, an issue unit <NUM>, an execution stage <NUM>, and a write-back unit <NUM>.

In various embodiments, the entire instruction fetch unit <NUM> and / or the branch predictor <NUM> is also part of the processing pipeline <NUM>. The processing pipeline <NUM> can also include other features, such as error checking and handling logic, one or more parallel paths through the processing pipeline <NUM>, and other features known in the art. While a forward path through the processing system <NUM> is depicted in <FIG>, other feedback and signaling paths may be included between elements of the processor <NUM>.

The instruction fetch unit <NUM> fetches instructions from the instruction cache <NUM> for further processing by the decode unit <NUM>. In one embodiment, the instruction fetch unit <NUM> includes the branch predictor <NUM> and also includes other branch prediction logic (not shown). Alternatively, in other embodiments, the branch predictor <NUM> is located separately from the instruction fetch unit <NUM>. The branch predictor <NUM> is an example of a processing circuit to implement branch confidence throttling, as discussed in more detail below.

The decode unit <NUM> decodes instructions and passes the decoded instructions, portions of instructions, or other decoded data to the issue unit <NUM>. The issue unit <NUM> analyzes the instructions or other data and transmits the decoded instructions, portions of instructions, or other data to one or more execution units <NUM> based on the analysis. The one or more execution units <NUM> include execution units such as fixed-point execution units, floating-point execution units, load/store execution units, vector execution units, and the like for executing the instructions. The write-back unit <NUM> writes results of instruction execution back to a destination resource (not shown). The destination resource may be any type of resource, including registers, cache memory, other memory, I/O circuitry to communicate with other devices, other processing circuits, or any other type of destination for executed instructions or data.

The branch predictor <NUM> includes a branch prediction pipeline <NUM> that performs prediction by comparing an instruction address against previously executed instruction addresses that have been stored in the BTB tables <NUM>. In this type of architecture, many instructions can be "in flight"; that is, in various stages of execution, simultaneously. The operation of the branch prediction pipeline <NUM> is presented in greater detail below with regard to <FIG> and <FIG>. Each stage within the branch prediction pipeline <NUM> generally occurs in order. To achieve high performance, one new instruction enters the branch prediction pipeline <NUM> every cycle, and each instruction in the pipeline moves to a new stage. Each stage takes inputs and produces outputs, which are stored in an output buffer associated with the stage. One stage's output buffer is typically the next stage's input buffer. Such an arrangement permits all the stages to work in parallel and therefore yields a greater throughput than if each instruction had to pass through the entire branch prediction pipeline <NUM> before the next instruction can enter the pipeline. When the branch prediction pipeline <NUM> is delayed or has to be cleared, latency is created in the processing of each instruction in the pipeline.

Prediction usually saves time in processing because successful prediction allows the processor <NUM> to skip execution of steps for acquiring a target address. The processor <NUM> saves time by looking up an address for a next step of execution in the BTB tables <NUM>. For example, in some embodiments, the BTBs <NUM> store branch addresses, target addresses, and history data to predict the branch direction (e.g., taken, not taken). Branch address information is stored in order to identify which BTB entry to use for a prediction (e.g., the entry whose branch address is equal to or closest following the search address). The target address is used to initiate instruction fetching for the target of a predicted taken branch. The history data, taken/not-taken, is used to predict the branch's direction as either taken or not-taken based on previous outcomes of the branch. In other embodiments, direction prediction information may come from additional (e.g., hierarchical) structures accessed in parallel with the BTBs <NUM>.

The branch prediction pipeline <NUM> includes a throttle unit <NUM>, a plurality of prediction pipeline stages BPO-BP3 (e.g., BP0 <NUM>, BP1 <NUM>, BP2 <NUM>, BP3 <NUM>), a BTB lookup <NUM>, a conditional predictor <NUM>, and an uncertainty accumulator <NUM>. In terms of pipelining, such as in the branch prediction pipeline <NUM> of <FIG>, one or more of the BTB tables <NUM> is read for every prediction flow unless the read is suppressed for power savings. According to some embodiments, a first BTB read is initiated in a first stage designated BP0. Subsequent stages are designated as BP1, BP2, and so forth as stages in the branch prediction pipeline <NUM>. It will be appreciated that in <FIG> and in other figures that the illustrated pipelines are simplified in order to provide a clear example and to avoid unnecessarily obscuring the embodiment(s) of the invention being presented in the figures. For example, an illustrated pipeline stage may represent multiple actual pipeline stages or where two or more illustrated pipeline stages can be executed concurrently they may be combined into the same pipeline stage in a particular implementation or embodiment. It will also be understood that while the function of a particular pipeline stage may be explained with reference to a particular portion of a particular thread, a pipeline actually works to perform such functions on many such portions of one or more threads concurrently.

In one embodiment, a throttling mechanism (e.g., the throttle unit <NUM>) is implemented at the front end of the branch prediction pipeline <NUM> (i.e., the throttle unit <NUM> is positioned at the beginning of the branch prediction pipeline <NUM>). In various embodiments, the throttle unit <NUM> starts prediction flows based on resource availability and arbitrates between multiple independent processes or execution threads running on the processor <NUM>. As illustrated, the BTB lookup <NUM> and the conditional predictor <NUM> stages span over multiple cycles of the branch prediction pipeline <NUM> (i.e., spanning over prediction pipeline stages BP0-BP3).

The conditional predictor <NUM> assigns a confidence level for each branch prediction generated by the branch predictor <NUM> that relates to the probability that the current prediction made at the head of the speculation stream is not going to be flushed. Although described here in the context of conditional predictor <NUM> assigning a confidence level for each of the plurality of branch predictions generated by the branch predictor, those skilled in the art will recognize that various other predictors can be used without departing from the scope of this disclosure. For example, in other embodiments, an indirect predictor (not shown) or a return address predictor (not shown) provides the uncertainty value.

In one embodiment, the conditional predictor <NUM> performs prediction confidence grading and classifies each branch prediction as a high-confidence prediction, a medium-confidence prediction, or a low-confidence prediction. For example, for a tagged geometric length (TAGE) predictor, high-confidence predictions include predictions made with a strong bimodal or saturated <NUM>-bit counter from TAGE tables, and generally have misprediction rates lower than <NUM>%. Medium-confidence predictions include predictions made with a nearly saturated <NUM>-bit counter from TAGE tables, and generally have misprediction rates in the range of <NUM>-<NUM>%. Low-confidence predictions include predictions made with a weak bimodal or weak/nearly-weak <NUM>-bit counter from TAGE tables, and generally have misprediction rates higher than <NUM>%. Additionally, as described in further detail below, for each branch prediction generated by the branch predictor <NUM>, the processor <NUM> assigns an uncertainty value to each prediction.

In other embodiments, various confidence grading systems can be used, including deriving a confidence level from the specific information of each prediction such as the branch type, the age of BTB entry used to predict the branch, the "strength" of the prediction from the conditional or indirect predictor involved in the prediction, or special conditions such as predicting a return with an underflowing return address stack, and so forth as understood by those in the art. In various embodiments, the processor <NUM> assigns the uncertainty value <NUM> for each branch prediction based at least in part on the above-discussed confidence levels assigned by the conditional predictor <NUM> and the number of dynamic branches predicted. For example, in one embodiment, each branch prediction is assigned an uncertainty value by the processor <NUM> ranging from <NUM> to <NUM> based on prediction confidence grading. For example, a high-confidence prediction is assigned an uncertainty value of <NUM>, a medium-confidence prediction is assigned an uncertainty value in the range of <NUM>-<NUM>, and a low confidence prediction is assigned an uncertainty value in the range of <NUM>-<NUM>.

The uncertainty accumulator <NUM> is positioned at the back end of the branch prediction pipeline <NUM> (i.e., the uncertainty accumulator <NUM> is positioned at the end of the branch prediction pipeline <NUM>). The uncertainty accumulator <NUM> adds the uncertainty value <NUM> assigned to each prediction to an accumulated uncertainty counter <NUM> associated with the uncertainty accumulator <NUM>. That is, the uncertainty accumulator <NUM> is incremented at the back end of the branch prediction pipeline <NUM>. Additionally, the uncertainty value assigned to each prediction is subtracted from the accumulated uncertainty counter <NUM> when the corresponding branch prediction is retired or flushed from the branch prediction pipeline <NUM>. That is, the accumulated uncertainty counter <NUM> is decremented when branch predictions are no longer in flight in the processor <NUM>. Thus, the various stages of the branch prediction pipeline <NUM> include assigning an uncertainty value to each prediction and accumulating the uncertainty values across all the predictions that are in flight by adding the uncertainty value of new predictions at the uncertainty accumulator <NUM> stage and subtracting the uncertainty value of predictions that are retired or flushed. In this manner, the uncertainty accumulator <NUM> presents what is in flight-instructions that have been predicted but not yet retired.

Based on whether the accumulated uncertainty counter <NUM> exceeds one or more uncertainty thresholds, the throttle unit <NUM> throttles operations of the branch prediction pipeline <NUM> and makes performance/power tradeoffs based on the confidence that the branch predictor <NUM> is on the correct path. That is, the accumulated uncertainty of in-flight branch predictions is compared against a set of multiple thresholds and an increasingly severe throttling is enforced as the accumulated uncertainty exceeds the different thresholds.

In one embodiment, the throttle unit <NUM> reduces a prediction rate for a first execution thread based on the accumulated uncertainty counter <NUM> exceeding one or more uncertainty thresholds. For example, when the processor <NUM> is in a single-thread mode and the accumulated uncertainty counter <NUM> exceeds one or more of the uncertainty thresholds, the throttle unit <NUM> instructs the branch predictor <NUM> to skip predictions for one or more cycles in the future. In another embodiment, when the processor <NUM> is in a multi-thread mode and the accumulated uncertainty counter <NUM> exceeds one or more of the uncertainty thresholds, the throttle unit <NUM> instructs the branch predictor <NUM> to allocate processing bandwidth by assigning cycles that would have been used for generating branch predictions from a first execution thread to a second execution thread for one or more cycles in the future.

Throttling causes an execution thread to not issue any prediction in a cycle where it would have otherwise met all the criteria for issuing a prediction, in such a way that it would yield to another execution thread or create a bubble cycle if no other execution thread can take advantage of the yielding (e.g., when the processor <NUM> is operating in single thread mode). For example, in a single-thread mode, throttling enables saving power and in multi-thread mode, throttling enables both power savings and performance improvement by yielding to other execution threads. By assigning uncertainty values to each prediction and selecting the thresholds and associated prediction rate, throttling reduces wasted work with minimum impact to the performance of the execution thread being throttled. The savings in wasted work translate into power savings and/or multi-thread performance benefits.

<FIG> is a diagram of prediction pipeline throttling in a single-thread mode in accordance with some embodiments. Plot <NUM> illustrates the value of an accumulated uncertainty counter associated with a first execution thread (i.e., thread A in this example) as a function of time (measured in cycles) during branch prediction operations. Plot <NUM> illustrates new predictions entering the branch prediction pipeline (such as branch prediction pipeline <NUM> of <FIG>) as a function of time (measured in cycles) during branch prediction operations. The horizontal axes of plots <NUM> and <NUM> indicate the time (in units of cycles) increasing from left to right. The vertical axis of plot <NUM> indicates the value of the accumulated uncertainty counter (in arbitrary units).

As illustrated in plot <NUM>, the new prediction <NUM> at cycle <NUM> and the new prediction <NUM> at cycle <NUM> each result in an increase to the accumulated uncertainty counter. However, the value of the accumulated uncertainty counter is less than a first uncertainty threshold T1. Thus, operations of the branch prediction pipeline proceed as normal with one new prediction entering the branch prediction pipeline <NUM> every cycle, and each instruction already in the pipeline moves to a new stage.

An uncertainty value associated with the new prediction <NUM> entering the branch prediction pipeline <NUM> at cycle <NUM> is added to the accumulated uncertainty counter. After adding the uncertainty value associated with the new prediction <NUM>, the value of the accumulated uncertainty counter increases above the first uncertainty threshold T1. Accordingly, the throttle unit <NUM> of the branch prediction pipeline <NUM> begins throttling of branch prediction pipeline operations at a first level of throttling in the next cycle of execution (i.e., cycle <NUM>). The example of <FIG> assumes that each prediction is made in one cycle so that the uncertainty accumulator <NUM> represents accumulated uncertainty at the front of the pipeline where the throttle unit <NUM> operates.

At cycle <NUM>, the throttle unit <NUM> inserts a stall into the branch prediction pipeline <NUM> by not issuing a new prediction. A new prediction <NUM> enters the branch prediction pipeline <NUM> at cycle <NUM>. Thus, the throttle unit <NUM> throttles branch prediction pipeline operations when the accumulated uncertainty counter increases above the first uncertainty threshold T1 by generating a new prediction every other cycle instead of every cycle. As illustrated in plot <NUM>, the new prediction <NUM> at cycle <NUM> results in an increase to the accumulated uncertainty counter (e.g., due to being another medium-confidence or low-confidence prediction). However, the value of the accumulated uncertainty counter is less than a second uncertainty threshold T2 but greater than the first uncertainty threshold T1. Thus, operations of the branch prediction pipeline proceed at the first level of throttling with one new prediction entering the branch prediction pipeline <NUM> every other cycle, and each instruction already in the pipeline moves to a new stage each cycle.

At cycle <NUM>, the throttle unit <NUM> inserts a stall into the branch prediction pipeline <NUM> by not issuing a new prediction. A new prediction <NUM> enters the branch prediction pipeline <NUM> at cycle <NUM>. An uncertainty value associated with the new prediction <NUM> entering the branch prediction pipeline <NUM> at cycle <NUM> is added to the accumulated uncertainty counter. However, after adding the uncertainty value associated with the new prediction <NUM>, the value of the accumulated uncertainty counter increases above the second uncertainty threshold T2. Accordingly, the throttle unit <NUM> of the branch prediction pipeline <NUM> begins throttling of branch prediction pipeline operations at a second level of throttling in the next cycle of execution (i.e., cycle <NUM>).

At cycles <NUM> and <NUM>, the throttle unit <NUM> inserts a stall into the branch prediction pipeline <NUM> by not issuing a new prediction during either cycle <NUM> or cycle <NUM>. A new prediction <NUM> does not enter the branch prediction pipeline <NUM> until cycle <NUM>. Thus, the throttle unit <NUM> throttles branch prediction pipeline operations when the accumulated uncertainty counter increases above the second uncertainty threshold T2 by generating a new prediction every three cycles. Those skilled in the art will recognize that throttling is described here in the context of issuing new predictions every two cycles (e.g., at the first level of throttling) and every three cycles (e.g., at the second level of throttling), any manner of reducing the rate at which new instructions are introduced into the branch prediction pipeline <NUM> and reducing the amount of power and compute resources dedicated to a given execution thread may be utilized without departing from the scope of this disclosure.

For example, <FIG> is a diagram of prediction pipeline throttling in a multi-thread mode in accordance with some embodiments. As shown in <FIG>, rather than skipping predictions, processing bandwidth is allocated to other execution threads that are able to more effectively utilize execute cycles (e.g., other execution threads having higher confidence levels that prediction is on the correct path).

Plot <NUM> illustrates the value of an accumulated uncertainty counter associated with a first execution thread (i.e., thread A in this example) as a function of time (measured in cycles) during branch prediction operations. Plot <NUM> illustrates new predictions entering the branch prediction pipeline (such as branch prediction pipeline <NUM> of <FIG>) as a function of time (measured in cycles) during branch prediction operations. The horizontal axes of plots <NUM> and <NUM> indicate the time (in units of cycles) increasing from left to right. The vertical axis of plot <NUM> indicates the value of the accumulated uncertainty counter (in arbitrary units).

As illustrated in plot <NUM>, the new prediction <NUM> at cycle <NUM> and the new prediction <NUM> at cycle <NUM> each result in an increase to the accumulated uncertainty counter. However, the value of the accumulated uncertainty counter is less than a first uncertainty threshold T1. Thus, operations of the branch prediction pipeline proceed as normal. In particular, for each cycle of the branch prediction pipeline <NUM> the fetch alternates between one new prediction for a first thread (e.g., thread A) and a second thread (e.g., thread B), expressed as follows: ABABAB, and each instruction already in the pipeline moves to a new stage.

An uncertainty value associated with the new prediction <NUM> entering the branch prediction pipeline <NUM> at cycle <NUM> is added to the accumulated uncertainty counter. After adding the uncertainty value associated with the new prediction <NUM>, the value of the accumulated uncertainty counter increases above the first uncertainty threshold T1. Accordingly, the throttle unit <NUM> of the branch prediction pipeline <NUM> begins throttling of branch prediction pipeline operations for execution thread A at a first level of throttling in the next cycle of execution (i.e., cycle <NUM>). For example, rather than alternating between thread A and thread B, the throttle unit <NUM> selects thread B for processing more often: for example, thread B can be selected for two-thirds of the branch prediction pipeline cycles, expressed as follows: ABBABB.

At cycle <NUM> and cycle <NUM>, the throttle unit <NUM> throttles predictions associated with execution thread A by not issuing a new prediction. Instead, the throttle unit <NUM> instructs the branch predictor <NUM> to assign cycles for generating new branch predictions to thread B and generates new predictions <NUM> and <NUM> for thread B. A new prediction <NUM> enters the branch prediction pipeline <NUM> for thread A at cycle <NUM>. Thus, the throttle unit <NUM> throttles branch prediction pipeline operations when the accumulated uncertainty counter for thread A increases above the first uncertainty threshold T1 by generating a new prediction every third cycle instead of every other cycle. As illustrated in plot <NUM>, the new prediction <NUM> at cycle <NUM> results in an increase to the accumulated uncertainty counter (e.g., due to being another medium-confidence or low-confidence prediction). However, the value of the accumulated uncertainty counter is greater than a second uncertainty threshold T2 but less than the first uncertainty threshold T1. Thus, operations of the branch prediction pipeline proceed at the first level of throttling with one new prediction for thread A entering the branch prediction pipeline <NUM> every third cycle, and each instruction already in the pipeline moves to a new stage each cycle.

A new prediction <NUM> and a new prediction <NUM> for thread B enters the branch prediction pipeline <NUM> at cycles <NUM> and <NUM>, respectively. A new prediction <NUM> for thread A enters the branch prediction pipeline <NUM> at cycle <NUM>. An uncertainty value associated with the new prediction <NUM> entering the branch prediction pipeline <NUM> at cycle <NUM> is added to the accumulated uncertainty counter. However, after adding the uncertainty value associated with the new prediction <NUM>, the value of the accumulated uncertainty counter increases above the second uncertainty threshold T2. Accordingly, the throttle unit <NUM> of the branch prediction pipeline <NUM> begins throttling of branch prediction pipeline operations at a second level of throttling in the next cycle of execution (i.e., cycle <NUM>). For example, at the second level of throttling, the throttle unit <NUM> selects thread B for processing more often: for example, thread B can be selected for <NUM>% of the branch prediction pipeline cycles, expressed as follows: ABBBABBB.

At cycles <NUM>, <NUM>, and <NUM>, the throttle unit <NUM> throttles predictions associated with execution thread A by not issuing a new prediction. Instead, the throttle unit <NUM> instructs the branch predictor <NUM> to allocate processing bandwidth to execution thread B and generates new predictions <NUM>, <NUM>, and <NUM> for thread B at cycles <NUM>, <NUM>, and <NUM>, respectively. A new prediction for thread A does not enter the branch prediction pipeline <NUM> until cycle <NUM> (not shown). Thus, the throttle unit <NUM> throttles branch prediction pipeline operations for thread A when the accumulated uncertainty counter increases above the second uncertainty threshold T2 by generating a new prediction for thread A every four cycles. Those skilled in the art will recognize that throttling is described here in the context of issuing new predictions every three cycles (e.g., at the first level of throttling) and every four cycles (e.g., at the second level of throttling), any manner of reducing the rate at which new instructions are introduced into the branch prediction pipeline <NUM> and reducing the amount of power and compute resources dedicated to a given execution thread may be utilized without departing from the scope of this disclosure. In other embodiments, the throttling can include differing number of cycles between issuing new predictions. However, the amount of throttling generally increases as the accumulated uncertainty increases.

<FIG> is a block diagram illustrating a method <NUM> for throttling a branch prediction pipeline in accordance with some embodiments. The method <NUM> is implemented in some embodiments of the branch prediction pipeline <NUM> and processor <NUM> shown in <FIG>.

At block <NUM>, the branch predictor <NUM> generates a branch prediction for an execution thread. At block <NUM>, the conditional predictor <NUM> assigns a confidence level for the branch prediction generated by the branch predictor <NUM>. In some embodiments, the conditional predictor <NUM> assigns a confidence level for each branch prediction generated by the branch predictor <NUM> that relates to the probability that the current prediction made at the head of the speculation stream is not going to be flushed. In one embodiment, the conditional predictor <NUM> performs prediction confidence grading and classifies each branch prediction as a high-confidence prediction, a medium-confidence prediction, or a low-confidence prediction.

At block <NUM>, the processor <NUM> assigns an uncertainty value to the branch prediction generated by the branch predictor <NUM>. In some embodiments, the processor <NUM> assigns the uncertainty value for each branch prediction based at least in part on the confidence level assigned by the conditional predictor <NUM> at block <NUM> and a number of dynamic branches predicted.

At block <NUM>, the uncertainty accumulator <NUM> adds the uncertainty value of the branch prediction from block <NUM> to an accumulated uncertainty counter associated with the branch predictor <NUM>. In some embodiments, each different execution thread executing at the processor <NUM> is associated with a separate accumulated uncertainty counter. The uncertainty accumulator <NUM> is incremented at the back end of the branch prediction pipeline <NUM>. Additionally, the uncertainty value assigned to a branch prediction is subtracted from the accumulated uncertainty counter when the corresponding branch prediction is retired or flushed from the branch prediction pipeline <NUM>. That is, the accumulated uncertainty counter is decremented when branch predictions are no longer in flight in the processor <NUM>. In various embodiments, uncertainty values are accumulated in a thread specific counter for all predicted blocks in flight as follows: add uncertainty value at predict time; subtract uncertainty value at retire time; and reset the uncertainty counter on redirects.

Thus, the various stages of the branch prediction pipeline <NUM> include assigning an uncertainty value to each prediction and accumulating the uncertainty values across all the predictions that are in flight by adding the uncertainty value of new predictions at the uncertainty accumulator <NUM> stage and subtracting the uncertainty of predictions that are retired or flushed. The accumulated uncertainty counter provides a measure of confidence as to whether the processor <NUM> is predicting along the correct path.

At block <NUM>, a new cycle of prediction begins and the throttle unit <NUM> determines whether the accumulated uncertainty counter exceeds a first uncertainty threshold. If the throttle unit <NUM> determines that the accumulated uncertainty counter does not exceed a first uncertainty threshold, the method <NUM> returns to block <NUM> for a new cycle of prediction. However, if the throttle unit <NUM> determines that the accumulated uncertainty counter does exceed a first uncertainty threshold, the method <NUM> proceeds to block <NUM>.

At block <NUM>, the throttle unit <NUM> determines whether the processor <NUM> is operating in a single-thread mode or a multi-thread mode for purposes of determining how to throttle operations of the branch prediction pipeline <NUM>. If the throttle unit <NUM> determines that the processor <NUM> is operating in a single-thread mode, the method <NUM> proceeds to block <NUM>. At block <NUM>, the throttle unit <NUM> determines whether the accumulated uncertainty counter exceeds a second uncertainty threshold. If the throttle unit <NUM> determines that the accumulated uncertainty counter exceeds the first uncertainty threshold (from block <NUM>) but does not exceed the second uncertainty threshold, the throttle unit <NUM> skips branch prediction at block <NUM> for a first number of cycles, such as previously discussed in more detail relative to <FIG>. If the throttle unit <NUM> determines that the accumulated uncertainty counter exceeds the first uncertainty threshold (from block <NUM>) and also exceeds the second uncertainty threshold, the throttle unit <NUM> skips branch prediction at block <NUM> for a second number of cycles greater than the first number of cycles, such as previously discussed in more detail relative to <FIG>.

If the throttle unit <NUM> determines that the processor <NUM> is operating in a multi-thread mode at block <NUM>, the method <NUM> proceeds to block <NUM>. At block <NUM>, the throttle unit <NUM> determines whether the accumulated uncertainty counter exceeds a second uncertainty threshold. If the throttle unit <NUM> determines that the accumulated uncertainty counter exceeds the first uncertainty threshold (from block <NUM>) but does not exceed the second uncertainty threshold, the throttle unit <NUM> allocates a first number of branch prediction cycles to a different execution thread (block <NUM>), such as previously discussed in more detail relative to <FIG>. If the throttle unit <NUM> determines that the accumulated uncertainty counter exceeds the first uncertainty threshold (from block <NUM>) and also exceeds the second uncertainty threshold, the throttle unit <NUM> allocates a second number of branch prediction cycles greater than the first number of cycles to a different execution thread (block <NUM>), such as previously discussed in more detail relative to <FIG>.

As shown, each of the blocks <NUM>, <NUM>, <NUM>, and <NUM> return to block <NUM> for subsequent new cycles of prediction. Although throttling occurs when the accumulated uncertainty counter increases above the various uncertainty thresholds, branch prediction returns to previous prediction rates if the accumulated uncertainty counter falls back below the uncertainty thresholds. As previously discussed, the uncertainty value for each of the plurality of branch predictions is subtracted from the accumulated uncertainty counter when each of the plurality of branch predictions is retired or flushed from the branch prediction pipeline. The accumulated uncertainty counter starts decreasing as instructions are retired. As instructions retire, if the instructions retire without having seen any redirects, that means that the predictions made were correct. In that case, the prediction is not in flight anymore and so are subtracted from the accumulated uncertainty counter.

Thus, in a single-thread mode, when the accumulated uncertainty counter falls below the second uncertainty threshold, the throttle unit <NUM> instructs the branch predictor <NUM> to skip fewer predictions. Similarly, in a single-thread mode, when the accumulated uncertainty counter falls below the first uncertainty threshold, the throttle unit <NUM> instructs the branch predictor <NUM> to forego throttling and return to generating a new prediction each cycle. In a multi-thread mode, when the accumulated uncertainty counter falls below the second uncertainty threshold, the throttle unit <NUM> instructs the branch predictor <NUM> to allocate less processing bandwidth to the second execution thread and return the processing bandwidth to the first execution thread. Similarly, in a multi-thread mode, when the accumulated uncertainty counter falls below the first uncertainty threshold, processing bandwidth is returned back to the first execution thread which resumes generating a new prediction every other cycle.

In this manner, the branch confidence throttling discussed herein slows down threads that are less likely to be on the correct path, and by doing that, saves power by not executing instructions that are likely to be flushed. The processor yields power and compute resources to another thread that shares the same hardware within a CPU core (e.g., in a multi-thread mode) or can save power by not generating new predictions in a cycle (e.g., in a single-thread mode). Yielded power resources by a thread in a given CPU core can be exploited by threads on other CPU cores within an IC package that can dynamically allocate power across a plurality of CPU cores. In this manner, the branch confidence throttling enables more efficient use of compute resources.

As disclosed herein, in some embodiments a processor includes: a branch predictor including one or more branch target buffer (BTB) tables; a branch prediction pipeline including a throttle unit and an uncertainty accumulator; wherein: the processor is configured to assign an uncertainty value for each of a plurality of branch predictions generated by the branch predictor; the uncertainty accumulator is configured to add the uncertainty value for each of the plurality of branch predictions to an accumulated uncertainty counter associated with the uncertainty accumulator; and the throttle unit is configured to throttle operations of the branch prediction pipeline based on the accumulated uncertainty counter. In one aspect, the uncertainty value for each of the plurality of branch predictions is subtracted from the accumulated uncertainty counter when each of the plurality of branch predictions is retired or flushed from the processor pipeline. In another aspect, the throttle unit is further configured to reduce a prediction rate for a first execution thread based on the accumulated uncertainty counter exceeding one or more uncertainty thresholds.

In one aspect, the throttle unit is further configured to instruct the branch predictor to skip prediction for one or more cycles, when the processor is in a single-thread mode, based on the accumulated uncertainty counter exceeding the one or more uncertainty thresholds. In another aspect, the throttle unit is further configured to instruct the branch predictor to allocate processing bandwidth to a second execution thread for one or more cycles, when the processor is in a multi-thread mode, based on the accumulated uncertainty counter exceeding the one or more uncertainty thresholds. In yet another aspect, the throttle unit is further configured to instruct the branch predictor to return processing bandwidth for the first number of cycles from the second execution thread to the first execution thread in response to the accumulated uncertainty counter falling below the first uncertainty threshold. In still another aspect, the processor includes: a conditional predictor configured to assign a confidence level for each of the plurality of branch predictions generated by the branch predictor, wherein the processor is configured to assign the uncertainty value for each of the plurality of branch predictions based at least in part on the confidence level.

As disclosed herein, in some embodiments a method includes: assigning an uncertainty value to a branch prediction generated by a branch predictor; adding the uncertainty value of the branch prediction to an accumulated uncertainty counter associated with the branch predictor; and throttling operations of the branch predictor based on the accumulated uncertainty counter exceeding one or more uncertainty thresholds. In one aspect, adding the uncertainty value of the branch prediction further comprises: incrementing the accumulated uncertainty counter at a back end of a branch prediction pipeline of the branch predictor. In another aspect, the method includes subtracting the uncertainty value of the branch prediction from the accumulated uncertainty counter when the branch prediction is retired or flushed from the processor pipeline.

In one aspect, throttling operations of the branch predictor further includes: reducing a prediction rate for a first execution thread based on the accumulated uncertainty counter exceeding the one or more uncertainty thresholds. In another aspect, the method includes skipping, based on the accumulated uncertainty counter exceeding a first uncertainty threshold of the one or more uncertainty thresholds, branch prediction for a first execution thread for a first number of cycles. In yet another aspect, the method includes skipping, based on the accumulated uncertainty counter exceeding a second uncertainty threshold greater than the first uncertainty threshold, branch prediction for the first execution thread for a second number of cycles greater than the first number of cycles.

In one aspect, the method includes allocating, when the branch predictor is operating in a multi-thread mode, processing bandwidth associated with the first number of cycles to a second execution thread. In another aspect, the method includes assigning a confidence level to the branch prediction; and assigning the uncertainty value to the branch prediction based at least in part on the confidence level.

As disclosed herein, in some embodiments a method includes: incrementing, at an uncertainty accumulator of a branch prediction pipeline, an accumulated uncertainty counter of a first execution thread with an uncertainty value; and arbitrating, based at least in part on a determination that the accumulated uncertainty counter exceeds one or more uncertainty thresholds, between a plurality of execution threads. In one aspect, the method includes: allocating, based on the accumulated uncertainty counter exceeding a first uncertainty threshold, processing bandwidth for a first number of cycles from the first execution thread to a second execution thread.

In another aspect, the method includes: allocating, based on the accumulated uncertainty counter exceeding a second uncertainty threshold greater than the first uncertainty threshold, processing bandwidth for a second number of cycles greater than the first number of cycles from the first execution thread to the second execution thread. In still another aspect, the method includes: allocating, based on the accumulated uncertainty counter falling below the first uncertainty threshold, processing bandwidth for the first number of cycles from the second execution thread to the first execution thread. In yet another aspect, the method includes: assigning a confidence level to a branch prediction generated by the branch prediction pipeline; and assigning the uncertainty value to the branch prediction based at least in part on the confidence level.

In some embodiments, the apparatus and techniques described above are implemented in a system including one or more integrated circuit (IC) devices (also referred to as integrated circuit packages or microchips), such as the systems, processors, and BTB tables described above with reference to <FIG>. Electronic design automation (EDA) and computer aided design (CAD) software tools may be used in the design and fabrication of these IC devices. These design tools typically are represented as one or more software programs. The one or more software programs include code executable by a computer system to manipulate the computer system to operate on code representative of circuitry of one or more IC devices so as to perform at least a portion of a process to design or adapt a manufacturing system to fabricate the circuitry. This code can include instructions, data, or a combination of instructions and data. The software instructions representing a design tool or fabrication tool typically are stored in a computer readable storage medium accessible to the computing system. Likewise, the code representative of one or more phases of the design or fabrication of an IC device may be stored in and accessed from the same computer readable storage medium or a different computer readable storage medium.

A computer readable storage medium may include any non-transitory storage medium, or combination of non-transitory storage media, accessible by a computer system during use to provide instructions and/or data to the computer system.

In some embodiments, certain aspects of the techniques described above may be implemented by one or more processors of a processing system executing software. The software includes one or more sets of executable instructions stored or otherwise tangibly embodied on a non-transitory computer readable storage medium.

Not all of the activities or elements described above in the general description are required, that a portion of a specific activity or device may not be required, and that one or more further activities may be performed, or elements included, in addition to those described.

Claim 1:
A processor [<NUM>] comprising:
a branch predictor [<NUM>] including one or more branch target buffer (BTB) tables [<NUM>];
a branch prediction pipeline [<NUM>] including a throttle unit [<NUM>] and an accumulator [<NUM>];
wherein:
the processor is configured to assign a value [<NUM>] for each of a plurality of branch predictions generated by the branch predictor;
the accumulator is configured to add the value for each of the plurality of branch predictions to a counter [<NUM>] associated with the accumulator; and
the throttle unit is configured to throttle operations of the branch prediction pipeline based on the counter and to reduce a prediction rate for a first execution thread for each of a plurality of uncertainty thresholds exceeded by the counter.