KR20240124412A - Conditional instruction prediction - Google Patents

Abstract

The processor can include bias prediction circuitry and instruction prediction circuitry for providing respective predictions for conditional instructions. The bias prediction circuitry can provide a bias prediction of whether the condition of the conditional instruction is biased true or biased false. The instruction prediction circuitry can provide an instruction prediction of whether the condition of the conditional instruction is false true. In response to a bias prediction that the condition of the conditional instruction is biased true or biased false, the processor can speculatively process the conditional instruction using the bias prediction from the bias prediction circuitry. Otherwise, the processor can speculatively process the conditional instruction using the instruction prediction from the instruction prediction circuitry.

Description

Conditional instruction prediction

Embodiments described herein relate to a processor, and more particularly, to a processor including circuitry for predicting results of conditional instructions and/or processing the conditional instructions in accordance with the predictions.

Computing systems typically include one or more processors that function as central processing units (CPUs). The CPUs execute control software (e.g., an operating system) that controls the operation of various peripherals. The CPUs may also execute applications that provide user functionality in the system. Sometimes, a processor may implement an instruction pipeline comprising multiple stages, where instructions are divided into a series of steps that are individually executed in corresponding stages of the pipeline. As a result, the instruction pipeline may execute multiple instructions in parallel. To improve efficiency, the processor may additionally implement conditional instruction prediction circuitry (also called a "conditional instruction predictor") that can predict the conditions of conditional instructions. Based on the predictions, the processor may speculatively fetch instructions from target addresses for execution. However, if a conditional instruction is mispredicted, the speculative work may be abandoned, and the processor may have to re-fetch instructions from the correct target addresses for execution. Therefore, the accuracy of predictions of conditional instructions can play a significant role in the performance of processors, and therefore it is desirable to have techniques for improving prediction accuracy. In addition, as the width and depth of execution pipelines increase, a processor may process a large number of conditional instructions and/or mispredictions in one cycle. Therefore, it is also desirable to have techniques for improving the efficiency of conditional instruction processing in processors.

The detailed description below refers to the accompanying drawings, which are now briefly described.
FIG. 1 is a block diagram of one embodiment of a portion of a processor including a bias prediction circuit and an instruction prediction circuit.
FIG. 2a illustrates one embodiment of a bias table of a bias prediction circuit.
FIG. 2b illustrates one embodiment of a basic table of an instruction prediction circuit.
FIG. 3a is a block diagram of one embodiment of the operations of a bias prediction circuit.
FIG. 3b is a block diagram of one embodiment of the operations of the instruction prediction circuit.
FIG. 4 is a flowchart illustrating one embodiment of the operations of a processor including a bias prediction circuit and an instruction prediction circuit.
FIG. 5 is a block diagram of one embodiment of a portion of a processor including an instruction distribution circuit and a plurality of execution pipelines.
FIG. 6 is a flow diagram illustrating one embodiment of the operations of a processor including an instruction distribution circuit and a plurality of execution pipelines.
FIG. 7 is a block diagram of another embodiment of a portion of a processor including an instruction distribution circuit and a plurality of execution pipelines.
FIG. 8 is a flow diagram illustrating another embodiment of the operations of a processor including an instruction distribution circuit and a plurality of execution pipelines.
FIG. 9 is a block diagram of one embodiment of the processor illustrated in FIGS. 1 through 8, including a bias prediction circuit, an instruction prediction circuit, and/or an instruction distribution circuit.
FIG. 10 is a block diagram of one embodiment of a system on a chip (SOC) that may include one or more processors illustrated in FIG. 9.
FIG. 11 is a block diagram of one embodiment of a system used in various situations.
Figure 12 is a block diagram of a computer-accessible storage medium.
While the embodiments described herein may take various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereof are not intended to limit the embodiments to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the appended claims. The headings used herein are for organizational purposes only and are not intended to be used to limit the scope of the description.

Referring now to FIG. 1, a block diagram of one embodiment of a portion of a processor (30) including a bias prediction circuit (156) and an instruction prediction circuit (160) is illustrated. In the illustrated embodiment, the bias prediction circuit (156) and the instruction prediction circuit (160) may be implemented as part of the fetch and decode circuit (100) of the processor (30). Alternatively, in some other embodiments, the bias prediction circuit (156) and/or the instruction prediction circuit (160) may be implemented as separate component(s) from the fetch and decode circuit (100).

As shown in FIG. 1, in the illustrated embodiment, the fetch and decode circuit (100) may implement a pipeline having multiple stages. For example, to process an instruction, the fetch and decode circuit (100) may first load the instruction from memory or cache (12) into an instruction cache (Icache) (102) (hereinafter referred to as the “prefetch” stage) using the prefetch circuit (150). Next, the instruction may be fetched from the Icache (102) by the fetch circuit (152) into a decoder (154) for decoding (hereinafter referred to as the “fetch” stage). The decoder (154) may decode the instruction, convert it into operation(s) and/or micro-operation(s) (hereinafter referred to as the “decode” stage), and send the operation(s) and/or micro-operation(s) to the execution pipeline (164) for execution. Note that sometimes, when the Icache (102) stores an instruction that was previously loaded from memory or cache (12) into the Icache (102), the instruction may already be present in the Icache (102). In that case, the prefetch stage may be avoided and the instruction may be fetched directly from the Icache (102) for execution. In the illustrated embodiment, the execution pipeline (164) may be implemented using execution units (112) (e.g., integer, floating point, and/or vector execution units) and associated reservation stations (110) as described in FIG. 9 . Also, for illustrative purposes, FIG. 1 may not necessarily depict all components of the processor (30). For example, sometimes the fetch and decode circuitry (100) may not necessarily be directly coupled to the execution pipeline (112). Instead, there may be one or more other components in between. For example, sometimes the processor (30) may include a map-dispatch-rename (MDR) unit (106) between the fetch and decode circuitry (100) and the execution pipeline (112), which may map the operation(s) and/or micro-operation(s) to speculative resources (e.g., physical registers) to allow out-of-order and/or speculative execution, and may dispatch the operation(s) and/or micro-operation(s) to standby stations (110).

The execution of code containing a conditional instruction may depend on the condition of the conditional instruction. When the condition of the conditional instruction is true, a first instruction from a first target address may be loaded, fetched, and executed. Conversely, when the condition of the conditional instruction is false, a second instruction from a second target address may be loaded, fetched, and executed. For illustrative purposes, below is example code containing a conditional instruction:

In this example, the conditional instruction simply involves a comparison between the values of two variables, "a" and "b". If the condition of the conditional instruction is true (i.e., the value of "a" is greater than the value of "b"), a first instruction from the first target address may be executed, assigning the value of variable "x" to 1. Conversely, if the condition of the conditional instruction is false (i.e., the value of "a" is less than or equal to the value of "b"), a second instruction from the second target address may be executed, assigning the value of variable "x" to 2.

In the illustrated embodiment, the fetch and decode circuit (100) may speculatively process conditional instructions. For example, the fetch and decode circuit (100) may predict the condition of a conditional instruction prior to (actual) execution of the conditional instruction, and based on the prediction, may speculatively determine a target address from which a subsequent instruction may be fetched for execution. As described above, the target address may reside in memory or cache (12), or Icache (102). Also, as illustrated in the example described above, the subsequent instruction may or may not be immediately following the conditional instruction. To improve efficiency, the fetch and decode circuit (100) may additionally use a bias prediction circuit (156) having a bias table (158) to provide a biased prediction of whether a conditional instruction is biased true or biased false. When a conditional instruction is predicted to be biased true or biased false, the fetch and decode circuit (100) can process the conditional instruction using the bias prediction from the bias prediction circuit (156). Conversely, when the conditional instruction is predicted not to be biased true or biased false, the fetch and decode circuit (100) can use the instruction prediction circuit (160) having one or more table(s) (162) to provide another prediction of whether the condition of the conditional instruction is true or false, e.g., an instruction prediction, and can speculatively process the conditional instruction using the instruction prediction.

In the illustrated example, the bias prediction circuitry (156) and the instruction prediction circuitry (160) may perform their respective predictions at different stages of the processing of a conditional instruction in the fetch and decode circuitry (100). For example, in the illustrated embodiment, the bias prediction circuitry may provide a bias prediction for a conditional instruction at the prefetch stage, when the conditional instruction is loaded from memory or cache (12) into the Icache (102). In contrast, in the illustrated embodiment, the instruction prediction circuitry (160) may provide the instruction prediction at a relatively “later” stage, such as at the fetch stage, when the conditional instruction is fetched from the Icache (102) into the decoder (154). It should be noted that the above is provided as an example only for illustrative purposes. In some embodiments, the bias prediction circuitry (156) and the instruction prediction circuitry (160) may provide their respective predictions at substantially the same time, for example, both at the prefetch stage, the fetch stage, and so on.

Sometimes, when a conditional instruction is predicted to be biased true or biased false, the fetch and decode circuit (100) may simply cause the conditional instruction to "bypass" the instruction prediction circuit (160). In other words, the instruction prediction circuit (160) may not necessarily provide a second prediction, such as an instruction prediction. Alternatively, sometimes the fetch and decode circuit (100) may still provide an instruction prediction using the instruction prediction circuit (160). However, when a conditional instruction is predicted to be biased true or biased false, the fetch and decode circuit (100) may ignore the instruction prediction from the instruction prediction circuit (160) and instead use the bias prediction from the bias prediction circuit (156) to speculatively process the conditional instruction as described above.

In the illustrated embodiment, the bias prediction from the bias prediction circuit (156) and the instruction prediction from the instruction prediction circuit (160) may indicate different properties of the conditional instruction. Furthermore, they may be generated in different manners, as described in FIGS. 2-3 . In the illustrated embodiment, the bias prediction from the bias prediction circuit (156) may indicate whether the conditional instruction is predicted to be biased (e.g., biased true or biased false). A conditional instruction being biased refers to a scenario where the condition of the conditional instruction is always true or always false. For example, if the condition is always true, the condition of the conditional instruction is considered biased true. Conversely, if it is always false, the condition is considered biased false. Referring again to biased prediction, when the condition of a conditional instruction is predicted to be biased true (or biased false), this means that the condition of the conditional instruction is predicted to always be true (or always false), and thus the conditional instruction is expected to always behave in one way (or the other). In contrast, the instruction prediction from the instruction prediction circuitry (160) can indicate whether the condition of the conditional instruction is predicted to be true or false. However, unlike biased prediction, the instruction prediction may not necessarily indicate whether the conditional instruction is biased true or biased false, or in other words, always true or always false.

Note that both bias prediction and instruction prediction are merely predictions. Therefore, either one may be in error. In the illustrated embodiment, the quality of the predictions may be determined after the conditional instruction has been executed, for example, by the execution pipeline (164). Considering the exemplary code described above, when the values of the operands (e.g., variables "a" and "b") are obtained and an operator (e.g., a comparator ">") is applied to the operands, the processor (30) may determine whether the condition of the conditional instruction is actually true or false, and accordingly evaluate whether the bias prediction and/or the instruction prediction is correct. In the illustrated embodiment, the bias prediction circuit (156) and/or the instruction prediction circuit (160) may be updated based on the evaluation of the conditional instruction. For example, when the bias prediction and/or the instruction prediction is a prediction error, the bias table (158) of the bias prediction circuit (156) and/or the table(s) (162) of the instruction prediction circuit (160) may be updated.

When a misprediction occurs, the processor (30) may have to discard the speculative work and retrieve another instruction from the correct target address for execution. For example, the execution pipeline (164) may discard the instruction in the execution pipe that was speculatively fetched, and the fetch and decode circuit (100) may have to redirect the prefetch circuit (150) and/or the fetch circuit (152) to obtain an instruction from the correct target address for execution (also called a refetch). Sometimes, this may cause additional delays in the operations of the processor (30). However, in practice, most conditional instructions may be biased instructions. Therefore, despite the above penalty caused by misprediction, the use of additional bias prediction circuitry may still increase the overall efficiency of the processor (30). In particular, if the processor (30) allows predictively-biased conditional instructions to “bypass” the instruction prediction circuitry (160), this can significantly reduce the overall workload and improve the efficiency of the processor (30).

In an illustrated embodiment, the bias prediction circuitry (156) may provide bias predictions for conditional instructions using a bias table (158). FIG. 2A illustrates an exemplary bias table (158). In the figure, the bias table (158) may be organized into one or more entries, each of which may be identified by a corresponding index and may include a corresponding value. In the illustrated embodiment, the indices of the bias table (158) may be associated with addresses of conditional instructions. For example, the indices may be generated by hashing the addresses of the conditional instructions using a hash function. In the context of hashing, the addresses of the conditional instructions may be considered "keys" and the values within the entries may be considered "values", the two of which may be associated with each other via the indices (and the hash function). Accordingly, for a given conditional instruction, the bias prediction circuit (156) can identify a value (e.g., a “value”) in a corresponding entry of the bias table (158) based on the address (e.g., a “key”) of the conditional instruction, and then provide a bias prediction for the conditional instruction based on the value identified in the bias table (158). For example, when the bias prediction circuit (156) receives a conditional instruction, the bias prediction circuit (156) can obtain the address of the conditional instruction, for example, from a program counter (PC). The bias prediction circuit (156) can determine an index based on the address of the conditional instruction, for example, using a hash function. The bias prediction circuit (156) can then search the bias table (158) using the index to find an entry matching the index, identify a value in the entry, and use the value to determine a bias prediction for the conditional instruction. Note that sometimes the indexes in the bias table (158) may suffer from hashing collisions, for example, different addresses of different conditional instructions may hash to the same index. In other words, different keys may correspond to the same value in the bias table (158). Sometimes, hashing collisions may lead to misprediction for conditional instructions.

In the illustrated embodiment, in FIG. 2a, the values in the bias table (158) may be 2-bit values that indicate different predictions of the biasability of a conditional instruction. For example, a value of "00" may indicate that no conditional instruction corresponding to an entry in this value has been previously encountered by the bias prediction circuitry (156). A value of "01" may indicate that the condition of the conditional instruction is biased false. A value of "10" may indicate that the condition of the conditional instruction is biased true. And, a value of "11" may indicate that a conditional instruction corresponding to an entry in this value has been previously encountered by the bias prediction circuitry (156), but the condition of the conditional instruction was not biased (e.g., neither biased true nor biased false). It is noted that the bias table (158) of FIG. 2a is provided as an example only for illustrative purposes. In some embodiments, values within the bias table (158) may have fewer or more bits. For example, sometimes values may have more than two bits to provide a particular level of hysteresis.

In the illustrated embodiment, the instruction prediction circuitry (160) may also use one or more table(s) (162) to predict the instruction prediction of a conditional instruction. However, unlike the bias prediction circuitry (156), at least some of the table(s) (162) may be heavily correlated with previous prediction history (e.g., by the instruction prediction circuitry (160)) and/or evaluation history of the conditional instructions. Furthermore, sometimes the history may include not only the history of a particular conditional instruction, but also the history of other conditional instructions in the same code. For example, sometimes the instruction prediction circuitry (162) may be a tagged GEometric length predictor (also referred to as a TAGE predictor) comprising a base predictor (T ₀ ) and a set of (partially) tagged predictors (T _i (1 ≤ i ≤ M)). A base predictor (T ₀ ) may provide a base prediction using a base table (162(0)). In an illustrated embodiment, the indices of the base table (162(0)) may be generated by hashing the addresses of the conditional instructions. In contrast, the tagged predictors (T _i ) (1 ≤ i ≤ M) may each have a table (162( i )) (1 ≤ i ≤ M), the indices of which may be generated by hashing (a) the addresses of the conditional instructions and (b) the previous prediction and/or evaluation history of the conditional instructions. The history may be considered a geometric series. For example, the addresses of the conditional instructions may be concatenated with the history, and then the two may be hashed together to generate the indices. The tables (162( i )) of different tagged predictors (T _i ) (1 ≤ i ≤ M) may be associated with different history lengths. For example, the higher the order of the tagged predictor (e.g., the larger i ), the longer the history may be used to generate indexes to the tables (162( i )) of the tagged predictors (T _i ) (1 ≤ i ≤ M). Accordingly, the tagged predictors (T _i ) (1 ≤ i ≤ M) may provide their own predictions for conditional instructions using their respective tables (162( i )) (1 ≤ i ≤ M). Sometimes, the hashing functions for the bias table (158) of the bias prediction circuit (156) and the base table (162(0)) of the instruction prediction circuit (160) may be different. Also, sometimes the hashing functions for the different tables (162( i )) of the different predictors (T _i ) (0 ≤ i ≤ M) may also be different. Additionally, the aforementioned hashing functions can be implemented based on any suitable hashing functions including exclusive or (or XOR) operations.

In the illustrated embodiment, for a given conditional instruction, to provide an instruction prediction, the instruction prediction circuit (160) may determine indices for each of the (M+1) predictors (0 ≤ i ≤ M) based on the address and history (for the tagged predictors only) of the conditional instruction, identify the matching predictor with the longest history (e.g., highest order), and use the prediction from the matched predictor as the (final) instruction prediction for the conditional instruction. From the above description, it can be seen that the instruction prediction circuit (160) may be more complex than the bias prediction circuit (156) and thus may take more time to predict. Therefore, using additional bias prediction circuitry (156) to allow predictively-biased conditional instructions to "bypass" the instruction prediction circuit (160) may reduce the overall workload and improve the efficiency of the processor (30).

FIG. 2b illustrates an exemplary base table (162(0)) of the instruction prediction circuit (160). For illustrative purposes, the base table (162(0)) is also provided as an example to illustrate tables (162( i )) of tagged predictors (T _i ) (1 ≤ i ≤ M). In the illustrated embodiment, the tables (162( i )) of tagged predictors (T _i ) (1 ≤ i ≤ M) may be similar to the base table (162(0)), for example, may also provide a value at each entry, but may additionally include additional information, such as a history-related geometric series. Additionally, the base table (162(0)) may also illustrate a distinction between the bias prediction circuit (156) and the instruction prediction circuit (160). As shown in FIG. 2B , in the illustrated embodiment, the values in the base table (162 (0)) may be 2-bit values. For example, a value of "00" may indicate that the condition of the conditional instruction is strongly false. A value of "01" may indicate that the condition of the conditional instruction is weakly false. A value of "10" may indicate that the condition of the conditional instruction is weakly true. A value of "11" may indicate that the condition of the conditional instruction is strongly true. Thus, the values in the table (162 (0)) of the instruction prediction circuit (160) may not necessarily indicate the bias of the conditional instruction, but may only indicate whether it is true or false with a particular relative degree of certainty. For example, a value of "00" may indicate that the conditional instruction is predictively more likely to be false than a value of "01". Similarly, a value of "11" may indicate that the conditional instruction is predictively more likely to be true than a value of "10". Note that the base table (162(0)) of FIG. 2b is provided only as an example for illustrative purposes. In some embodiments, the values in the base table (162(0)) and/or the tables (162( i )) of tagged predictors (T _i ) (1 ≤ i ≤ M) may have fewer or more bits.

Referring now to FIGS. 3A and 3B , state machines of the bias prediction circuit (156) and the instruction prediction circuit (160) are depicted to illustrate the operations of their respective prediction circuits. As shown in FIG. 3A , circles (302, 304, 306, 308) may correspond to four possible predictions in the bias table (158) of the bias prediction circuit (156) of FIG. 2A . Similarly, in FIG. 3B , circles (312, 314, 316, 318) may correspond to four possible predictions in the table(s) (162) of the instruction prediction circuit (160) of FIG. 2B . Additionally, edges connecting the circles in the respective tables may represent changes in values upon update.

Referring again to FIG. 3A , in the illustrated embodiment, the value "00" may be designed as an initial state or default value for conditional instructions. For example, at startup, the value for a conditional instruction in the bias table (158) may be set to the default value "00". When a conditional instruction is first loaded from memory or cache (12) into Icache (102), assuming that there is no hash collision yet for the conditional instruction, this may be the first time that the bias prediction circuit (156) encounters a conditional instruction corresponding to an entry of the conditional instruction in the bias table (158). Accordingly, the value for the conditional instruction in the bias table (158) may be "00" (e.g., corresponding to circle (302)). Since the value "00" does not indicate that the condition of the conditional instruction is biased true or biased false, the fetch and decode circuit (100) may additionally provide a second prediction, e.g., instruction prediction, for the conditional instruction using the instruction prediction circuit (160). As described above, the instruction prediction circuit (160) may provide instruction prediction using the table(s) (162). In the illustrated embodiment, similarly, the processor (30) may designate one of four possible states as an initial state or default value for the conditional instruction. For purposes of illustration, the initial state or default value for the conditional instruction is assumed to be "10" (e.g., corresponding to circle (316)), indicating that the condition is predicted to be weakly true. Based on the instruction prediction from the instruction prediction circuit (160), the fetch and decode circuit (100) may determine a target address from which a subsequent instruction may be speculatively obtained for execution. Consider the exemplary code described above that includes the conditional instruction "if (a > b)". Since the conditional instruction is predicted to be “weakly true,” the fetch and decode circuit (100) can speculatively obtain the subsequent instruction “x = 1” for execution.

After execution of the instruction, for example, in the execution pipeline (164), the condition of the conditional instruction may actually be determined, and the bias prediction from the bias prediction circuit (156) and the instruction prediction from the instruction prediction circuit (160) may be evaluated based on the results of the execution of the conditional instruction. In the illustrated embodiment, the bias table (158) of the bias prediction circuit (156) and/or the table(s) (162) of the instruction prediction circuit (160) may be updated based on the evaluation. For example, when the evaluation finds that the condition of the conditional instruction is actually true, this means that the previous bias prediction from the bias prediction circuit (156) (which was an initial state or default value of "00") was a prediction error. Accordingly, in the bias table (158), the value for the conditional instruction may change from "00" (e.g., an initial state) to "10" (e.g., a biased true). In FIG. 3a, this is illustrated by the change from circle (302) (e.g., corresponding to "00") to circle (306) (e.g., corresponding to "10"). In contrast, the evaluation of the conditional instruction may determine that the previous instruction prediction from the instruction prediction circuitry (160) was not a misprediction. Accordingly, in the table(s) (162), the value(s) for the conditional instruction may change from "10" (e.g., weakly true) to "11" (e.g., strongly true), indicating that the instruction prediction circuitry (160) is rewarded. In FIG. 3b, this is illustrated by the change from circle (316) (e.g., corresponding to "10") to circle (318) (e.g., corresponding to "11").

Conversely, when the evaluation of a conditional instruction reveals that the condition of the conditional instruction is actually false, this indicates that the previous bias prediction from the bias prediction circuitry (156) was a misprediction. Accordingly, in the bias table (158), the value for the conditional instruction may change from "00" (e.g., initial state) to "01" (e.g., biased false). In FIG. 3A , this is illustrated by the change from circle (302) (e.g., corresponding to "00") to circle (304) (e.g., corresponding to "01"). Additionally, the evaluation of the conditional instruction may indicate that the previous instruction prediction from the instruction prediction circuitry (160) was also a misprediction. Accordingly, in the table(s) (162), the value(s) for the conditional instruction may change from "10" (e.g., weakly true) to "01" (e.g., weakly true), indicating that the instruction prediction circuitry (160) is penalized. In Figure 3b, this is illustrated by a change from circle (316) (corresponding, for example, to “10”) to circle (314) (corresponding, for example, to “01”).

As shown in FIG. 3a, once updated to a value “10” (e.g., biased true) or “01” (e.g., biased false), the value of the conditional instruction in the bias table (158) may remain at “10” or “01” until a misprediction occurs. In other words, once the value for a conditional instruction in the bias table (158) is updated from an initial state, the bias prediction circuit (156) may refrain from changing it to another value until a misprediction occurs. From an operational standpoint, this means that the bias prediction circuit (158) may unconditionally predict the condition of the conditional instruction in the same manner until evaluation of the conditional instruction indicates that the bias prediction is a misprediction. When such a misprediction occurs, the value of the conditional instruction in the bias table (158) may be updated from “10” or “01” to “11” (e.g., unbiased). In FIG. 3a, this is illustrated by a change from circle (304) (e.g., corresponding to "01") or circle (306) (e.g., corresponding to "10") to circle (308) (e.g., corresponding to "11"). Additionally, once updated to the value "11", the value of the conditional instruction in the bias table (158) may remain at "11" (e.g., unbiased) until the prediction circuitry (156) resets the value to its initial state or default value "00".

As illustrated in FIG. 3b, the value(s) of the conditional instructions in the table(s) (162) may change from one value to another upon update, depending on whether the instruction prediction circuit (160) is rewarded or penalized. For example, when the evaluation of the conditional instruction determines that the instruction prediction from the instruction prediction circuit (160) is not a misprediction, the instruction prediction circuit (160) may be rewarded and change the value(s) of the conditional instructions in the table(s) (162) from a relatively weaker prediction to a relatively stronger prediction (e.g., from weakly true to strongly true, or from weakly false to strongly false), or may remain at the relatively stronger prediction (e.g., strongly true or strongly false). Conversely, when the evaluation of a conditional instruction indicates that the instruction prediction from the instruction prediction circuitry (160) is a misprediction, the instruction prediction circuitry (160) may be penalized to change the value(s) of the conditional instruction in the table(s) (162) from a relatively stronger prediction to a relatively weaker prediction (e.g., from strongly true to weakly true, or from strongly false to weakly false), or even from a relatively weaker prediction to the opposite relatively weaker prediction (e.g., from weakly true or weakly false, or vice versa). Note that in the illustrated embodiment, the values for the conditional instructions in the table(s) (162) may not change from one relatively stronger prediction to the opposite relatively stronger prediction (e.g., from strongly true to strongly false, or vice versa). Thus, the table(s) (162) may be considered to have a certain level of hysteresis.

Additionally, as described above, when the condition of the conditional instruction is predicted to be biased true or biased false, for example, when the value for the conditional instruction in the bias table (158) is "10" or "01", the fetch and decode circuit (100) can speculatively process the conditional instruction using the bias prediction from the bias prediction (156). Conversely, when the condition of the conditional instruction is predicted not to be biased true or biased false, for example, when the value for the conditional instruction in the bias table (158) is "00" or "11", the fetch and decode circuit (100) can speculatively process the conditional instruction using the instruction prediction from the instruction prediction circuit (160).

In the illustrated embodiment, the bias table (158) and/or the table(s) (162) may be implemented using one or more of the registered ones. Additionally, the fetch and decode circuit (100) may encode a bias prediction from the bias prediction circuit (156) and/or an instruction prediction from the instruction prediction circuit (160) in an instruction line that includes a conditional instruction. For example, the fetch and decode circuit (100) may append a value (e.g., a 2-bit value) for a conditional instruction from the bias table (158) and/or the table(s) (162) to the machine code of the instruction line that includes the conditional instruction, either forward, backward, or in the middle. Alternatively, the fetch and decode circuit (100) may recode the machine code of the instruction line that includes the conditional instruction to embed the prediction(s) for the conditional instruction. For example, the fetch and decode circuit (100) may change the values of one or more bits of the machine code. Accordingly, when an instruction with an attached value is received at the Icache (102) and/or the decoder (154), the Icache (102) and/or the decoder (154) may recognize the prediction(s) of the conditional instruction and speculatively process the conditional instruction based on the prediction(s) as described above.

In the illustrated embodiment, when a conditional instruction is predicted to be biased true or biased false, the fetch and decode circuit (100) may sometimes cause the conditional instruction to "bypass" the instruction prediction circuit (160). In the illustrated embodiment, to implement the "bypass," the fetch and decode circuit (100) may recode the conditional instruction into a non-conditional instruction. As a result, the instruction prediction circuit (160) may treat the conditional instruction as a non-conditional instruction and may not necessarily provide an instruction prediction for the recoded conditional instruction.

As described above, the bias prediction circuit (156) and/or the instruction prediction circuit (160) may mispredict conditional instructions. As a result, the bias prediction circuit (156) and/or the instruction prediction circuit (160) may become saturated. For example, when code is executed by the processor (30) for a relatively long period of time, the bias prediction circuit (156) may experience sufficient misprediction for one or more conditional instructions in the code. As a result, the values for the conditional instructions in the bias table (158) may change to the value "11". As described above, once the values change to "11", they may remain at "11" until reset. Accordingly, to address saturation, in the illustrated embodiment, the bias prediction circuit (156) and/or the instruction prediction circuit (160) may each detect the occurrence of saturation and, in response, reset the bias table (158) and/or the table(s) (162). For example, the bias prediction circuit (156) may monitor the number of values "11" within the bias table (158). When it reaches a specified threshold, e.g., a specified percentage, the bias prediction circuit (156) may determine that the bias table (158) is saturated. As a result, the bias prediction circuit (156) may reset these values "11" to the initial state "00". Occasionally, the bias prediction circuit (156) may also reset other values within the bias table (158), e.g., the entire bias table (158), to the initial state "00".

Referring now to FIG. 4, a flow diagram illustrating one embodiment of the operations of a processor (30) including a bias prediction circuit (156) and an instruction prediction circuit (160) is depicted. In the illustrated embodiment, a conditional instruction may be received at the fetch and decode circuit (100), as indicated at block (402). As described above, the conditional instruction may be loaded from memory or cache (12) into the Icache (102), or fetched from the Icache (102) into the decoder (154). The fetch and decode circuit (100) may provide a bias prediction of whether the condition of the conditional instruction is biased true or biased false using the bias prediction circuit (156), as indicated at block (404). In the illustrated embodiment, the bias prediction circuit (156) may perform the bias prediction using a bias table (158), as indicated at block (404). As described above, when the condition of a conditional instruction is predicted to be biased true or biased false, it indicates that the bias prediction circuit (156) predicts that the condition of the conditional instruction is always true or always false.

When the bias prediction from the bias prediction circuit (156) predicts that the condition of the conditional instruction is neither biased true nor biased false, the fetch and decode circuit (100) may provide an instruction prediction of whether the condition of the conditional instruction is true or false using the instruction prediction circuit (160), as indicated at block (406). As described above, in the illustrated embodiment, the instruction prediction circuit (160) may be a TAGE predictor having a total of ( M +1) predictors, such as a base predictor (T ₀ ) having a base table (162 ( 0 )) and one or more additional (partially) tagged predictors (T _i ) having their own tables (162 ( i )) (1 ≤ i ≤ M). The tables (162 ( i )) of the tagged predictors (T _i ) (1 ≤ i ≤ M) may be associated with a history-related geometric series of their respective history lengths.

As described above, in the illustrated embodiment, when the bias prediction circuit (156) predicts that the condition of the conditional instruction is biased true or biased false, the fetch and decode circuit (156) may cause the conditional instruction to "bypass" the instruction prediction circuit (160). As a result, the operations at block (406) may be avoided. For example, the fetch and decode circuit (100) may recode the conditional instruction into a non-conditional instruction. Furthermore, as described above, in the illustrated embodiment, the bias prediction from the bias prediction circuit (156) and the instruction prediction from the instruction prediction circuit (160) may be provided as different stages of processing the conditional instruction in the fetch and decode circuit. For example, the bias prediction circuit (156) may provide bias prediction at the prefetch stage when a conditional instruction is loaded from memory or cache (12) into the Icache (102), while the instruction prediction circuit (160) may perform instruction prediction at the fetch stage when a conditional instruction is fetched from the Icache (102) into the decoder (154).

In the illustrated embodiment, the fetch and decode circuit (100) can speculatively determine a target address for a conditional instruction using either a bias prediction from the bias prediction circuit (156) or an instruction prediction from the instruction prediction circuit (160), as indicated at block (408). For example, the fetch and decode circuit (100) can speculatively determine a target address of a conditional instruction from which a subsequent instruction can be fetched for execution based on either a bias prediction from the bias prediction circuit (156) or an instruction prediction from the instruction prediction circuit (160).

In the illustrated embodiment, the fetch and decode circuit (100) may send a conditional instruction to the execution pipeline (164) for execution, as indicated at block (410). Additionally, the fetch and decode circuit (100) may receive an evaluation of the conditional instruction based on the result of execution of the conditional instruction, as indicated at block (412). As described above, execution of the conditional instruction may determine whether the condition of the conditional instruction is actually true or false, and thus whether a previous bias prediction from the bias prediction circuit (156) and/or a previous instruction prediction from the instruction prediction circuit (160) was a misprediction.

In the illustrated embodiment, the bias prediction circuitry (156) and/or the instruction prediction circuitry (160) update their bias table (158) and table(s) (162), respectively, based on the evaluation of the conditional instruction, as indicated in blocks (414, 416). As described above in FIGS. 2 and 3 , the update of the bias table (158) may change the value for the conditional instruction from an initial state such as "00" to "01" (e.g., indicating biased false) or "10" (e.g., indicating biased true) when the evaluation indicates that the condition of the conditional instruction is actually true or false, respectively, or may change the value from "01" or "10" to "11" (e.g., indicating unbiased) when the evaluation indicates that a previous biased true or biased false prediction was actually a prediction error. In contrast, the instruction prediction circuit (160) may update the value(s) for the conditional instruction in the table(s) (162( i )) of the base and tagged predictors (T i ) (0 ≤ i ≤ M) from a relatively weaker prediction to a relatively stronger prediction (e.g., from weakly true "10" to strongly true "11", or from weakly false "01" to strongly false "00"), or may keep the value at the relatively stronger prediction (e.g., strongly true "11" or strongly false "00"), when the evaluation verifies that the instruction prediction from the instruction prediction circuit (160) is not a misprediction; Alternatively, when the evaluation indicates that the instruction prediction from the instruction prediction circuit (160) is a misprediction, it may be updated from a relatively stronger prediction to a relatively weaker prediction (e.g., from a strongly true "11" to a weakly true "10", or from a strongly false "00" to a weakly false "01"), or from a relatively weaker prediction to the opposite relatively weaker prediction (e.g., from a weakly true "10" or a weakly false "01", or vice versa).

Referring now to FIG. 5 , a block diagram of one embodiment of a portion of a processor (30) including an instruction distribution circuit (520) and execution pipelines (504, 506) is illustrated. In FIG. 5 , the instruction distribution circuit (520) may receive a conditional instruction associated with a prediction from the fetch and decode circuit (100) and may distribute the conditional instruction to one of a plurality of execution pipelines, such as 504 and 506, depending on a confidence level of the prediction of the conditional instruction. When the conditional instruction is determined to have a relatively high confidence level, the instruction distribution circuit may distribute the conditional instruction to a first execution pipeline (504). Conversely, when the conditional instruction is determined to have a relatively low confidence level, the instruction distribution circuit may distribute the conditional instruction to a second execution pipeline (506). One difference between the execution pipelines (504, 506) may be that when a conditional instruction is mispredicted, the execution pipeline (506), rather than the execution pipeline (504), may have the ability to redirect the fetch and decode (100) to obtain the instruction from the correct target address for execution (also called a refetch).

Therefore, when the execution pipeline (504) detects a misprediction for a conditional instruction, the execution pipeline (504) may need to use the execution pipeline (506) to direct a refetch of the instruction from the correct target address for execution. For example, the execution pipeline (504) may create a bubble in the execution pipeline (506) and then insert the conditional instruction into the bubble for execution by the execution pipeline (506). Once the execution pipeline (506) executes the conditional instruction and determines that the conditional instruction was also mispredicted, the execution pipeline (506) may redirect the fetch and decode (100) to refetch the instruction from the correct target address for execution. For example, the execution pipeline (506), rather than the execution pipeline (504), may have a communication path to the fetch and decode circuitry (100), through which the execution pipeline (506) may instruct the fetch and decode circuitry (100) to perform a re-fetch. Given that the conditional instruction has already been executed in the execution pipeline (504), the second execution of the conditional instruction in the execution pipeline (506) may also be considered a re-execution or re-play of the conditional instruction. Additionally, in the illustrated embodiment, the execution pipeline (506) may also use a bubble to execute one or more non-conditional instructions along with the mispredicted conditional instruction. For example, the execution pipeline (506) may execute one or more non-conditional instructions in the same cycle as the mispredicted conditional instruction generated by the bubble.

In the illustrated embodiment, when it detects a mispredicted conditional instruction, the execution pipeline (504) may not necessarily write back the results to any registers or memory until the instruction from the correct target address has been successfully executed by the execution pipeline (504). This ensures that only the correct results are written to the registers or memory. However, this may also delay the retirement of the execution pipeline (504), thus causing additional delay in the execution pipeline (404). In contrast, when a mispredicted conditional instruction is initially distributed to the execution pipeline (506), the execution pipeline (506) can detect the misprediction and cause the fetch and decode circuit (100) to obtain execution from the correct target address for execution, thereby causing minimal delay to execution. Therefore, due to the different latencies in processing the mispredicted conditional instructions, the execution pipeline (504) may be considered a "slow" execution pipeline, while the execution pipeline (506) may be considered a "fast" execution pipeline. Sometimes, the execution pipelines (504, 506) may include the same stages or the same number of stages. In other words, for non-mispredicted conditional instructions, the execution pipelines (504, 506) may not necessarily have different latencies, and the different latencies may only exist for mispredicted conditional instructions, since the execution pipeline (504) lacks the ability to directly direct the fetch and decode circuit (100) for refetting. Alternatively, sometimes the execution pipeline (504) may have more stages or a greater number of stages than the execution pipeline (506). As a result, the execution pipeline (504) may always have a greater latency than the execution pipeline (506), regardless of whether conditional instructions are mispredicted.

In the illustrated embodiment, the prediction of the conditional instruction used by the instruction distribution circuit (502) to dispense the conditional instruction may be (a) a bias prediction from the bias prediction circuit (156) or (b) an instruction prediction from the instruction prediction circuit (160). For example, as described above, when the bias prediction circuit (156) provides a bias prediction that the condition of the conditional instruction is biased true or biased false, the fetch and decode circuit (100) may use the bias prediction to speculatively process the conditional instruction. In that case, the instruction distribution circuit (502) may use the bias prediction from the bias prediction circuit (156) to determine the dispensing of the conditional instruction. Conversely, when the bias prediction circuit (156) predicts that the condition of the conditional instruction is not biased true or biased false, the fetch and decode circuit (100) may use the instruction prediction from the instruction prediction circuit (160) to speculatively process the conditional instruction. In that case, the instruction distribution circuit (502) can determine the distribution of the conditional instruction using the instruction prediction from the instruction prediction circuit (160). In other words, the prediction of the conditional instruction disclosed in the present specification can be a prediction of a conditional instruction on which the fetch and decode circuit (100) speculatively processes the conditional instruction based thereon.

In the illustrated embodiment, the confidence level of a prediction can be determined for one or more criteria. For example, when the prediction of a conditional instruction is a biased prediction from the bias prediction circuit (156) (e.g., when the conditional instruction is predicted as biased true or biased false), the instruction distribution circuit (502) can determine that the prediction has a high confidence level. Additionally, when the prediction is an instruction prediction from the instruction prediction circuit (160) (e.g., when the conditional instruction is not predicted as biased true or biased false), the instruction distribution circuit (502) can determine that the prediction has a high confidence level if the instruction prediction is provided by a tagged predictor (T _i ) having a saturated counter or a tagged predictor (T _i ) having a high-order table (e.g., when the instruction prediction circuit (160) is a TAGE predictor). Otherwise, when the prediction of the conditional instruction does not satisfy one or more of the criteria above, the instruction distribution circuit (502) can determine that the prediction has a low confidence level.

When the confidence level is high, the instruction distribution circuit (502) may distribute the conditional instruction to the “slow” execution pipeline (504). Conversely, when the confidence level is low, the instruction distribution circuit (502) may distribute the conditional instruction to the execution pipeline (506) (e.g., the “slow” execution pipeline). From an operational perspective, this means that when a conditional instruction is predicted with a high confidence level, the instruction distribution circuit (502) may estimate that the conditional instruction is less likely to be mispredicted, and thus execution of the conditional instruction in the execution pipeline (504) (e.g., the “slow” execution pipeline) may be less likely to result in a refetch. In contrast, when a conditional instruction is predicted with a low confidence level, the instruction distribution circuit (502) may estimate that the misprediction is more likely to result in a refetch. Thus, the instruction distribution circuit (502) can distribute conditional instructions to the execution pipeline (506) (e.g., a “fast” execution pipeline) to reduce potential delays for refetting.

At times, the instruction distribution circuit (502) may perform load balancing between the execution pipelines (504, 506). For example, the instruction distribution circuit (502) may distribute conditional instructions to the execution pipelines (504, 506) based on occupancies of the execution pipelines rather than on predictions of the conditional instructions. For example, when the execution pipeline (504) is overloaded and the execution pipeline (506) is underoccupied, the instruction distribution circuit (502) may distribute conditional instructions associated with a high confidence level prediction for execution to the execution pipeline (506).

Referring now to FIG. 6, a flow diagram illustrating one embodiment of the operations of a processor (30) including an instruction distribution circuit (502) and different execution pipelines (504, 506) is depicted. In the illustrated embodiment, a conditional instruction associated with a prediction may be received at the instruction distribution circuit (502), as indicated at block (602). As described above, the prediction of the conditional instruction may be (a) a bias prediction from the bias prediction circuit (156) or (b) an instruction prediction from the instruction prediction circuit (160).

In the illustrated embodiment, the instruction distribution circuit (502) may determine a confidence level of the prediction by evaluating the prediction of the conditional instruction against one or more criteria, as indicated at block (604). For example, the instruction distribution circuit (502) may determine whether the prediction is a biased prediction (e.g., biased true or biased false) provided by the bias prediction circuit (156), or an instruction prediction (e.g., true or false) provided by a tagged predictor (T _i ) having a saturated counter or a tagged predictor (T _i ) having a high-order table of the instruction prediction circuit (160) (e.g., when the instruction prediction circuit (160) is a TAGE predictor). If so, the instruction distribution circuit (502) may determine that the conditional instruction has a high confidence level. Otherwise, the instruction distribution circuit (502) may determine that the conditional instruction has a low confidence level.

The instruction distribution circuit (502) may distribute a conditional instruction to one of a plurality of execution pipelines based on a confidence level of the prediction of the conditional instruction for one or more criteria. For example, when the confidence level is high, the instruction distribution circuit (502) may distribute the conditional instruction to the execution pipeline (504) (e.g., a “slow” execution pipeline) for execution, as indicated at block (606). Otherwise, when the confidence level is low, the instruction distribution circuit (502) may distribute the conditional instruction to the execution pipeline (506) (e.g., a “fast” execution pipeline) for execution, as indicated at block (610).

When a conditional instruction is dispatched to the execution pipeline (504), execution of the conditional instruction may determine that a prediction of the conditional instruction is a misprediction, as indicated at block (608). In response, the execution pipeline (504) may cause the mispredicted conditional instruction to be re-executed or replayed in the execution pipeline (506), as indicated at block (610). As described above, in the illustrated embodiment, the execution pipeline (504) may create a bubble in the execution pipeline (506) and insert the mispredicted conditional instruction into the bubble so that it may be executed by the execution pipeline (506). As described above, execution of the conditional instruction in the execution pipeline (506) may determine that the conditional instruction is mispredicted, as indicated at block (612). The execution pipeline (506) may direct the fetch and decode circuit (100) to obtain an instruction from the correct target address of a conditional instruction for execution, as indicated at block (614).

Referring now to FIG. 7, a block diagram of one embodiment of a portion of a processor (30) including an instruction distribution circuit (520) and execution pipelines (504, 506, 708, 710) is illustrated. In the illustrated embodiment, the execution pipeline (708) may be similar to the execution pipeline (504) (e.g., a “slow” execution pipeline) such that the execution pipeline (708) lacks the ability to directly direct the fetch and decode circuit (100) to perform a refetch for a mispredicted conditional instruction. In contrast, the execution pipeline (710) may be similar to the execution pipeline (506) (e.g., a “fast” execution pipeline) such that the execution pipeline (710) can also directly direct the fetch and decode circuit (100) to perform a refetch for a mispredicted conditional instruction. For example, as with execution pipeline (506), execution pipeline (710) may also have a communication path to the fetch and decode circuitry to direct refetting of mispredicted conditional instructions. Thus, in FIG. 7, the processor (30) includes two “slow” execution pipelines (e.g., execution pipelines (504, 708)) and two “fast” execution pipelines (e.g., execution pipelines (507, 710)). Note that FIG. 7 is provided as an example only for illustrative purposes. At times, the processor (30) may include fewer or more “slow” execution pipelines, and/or fewer or more “fast” execution pipelines.

As illustrated in FIG. 7, the instruction distribution circuit (502) can distribute conditional instructions to the execution pipelines (504, 506, 708, 710) based on the confidence levels of the predictions of the conditional instructions. In the illustrated embodiment, the confidence levels of the predictions of the conditional instructions can be determined with respect to one or more criteria, as described above with reference to FIGS. 5 and 6. Accordingly, the instruction distribution circuit (502) can distribute conditional instructions associated with high confidence levels of predictions to the execution pipelines (504, 708) (e.g., “slow” execution pipelines) for execution, and can distribute conditional instructions associated with low confidence levels of predictions to the execution pipelines (506, 710) (e.g., “fast” execution pipelines) for execution.

In the illustrated embodiment, the execution pipelines (504, 506, 708, 710) may operate in parallel, processing one or more conditional instructions at approximately the same time. However, in the illustrated embodiment, only one of the "fast" execution pipelines, such as the execution pipeline (506), may be used to re-execute or replay a mispredicted conditional instruction provided from the "slow" execution pipelines, such as the execution pipelines (504, 708) (to cause a refetch). Thus, when both of the execution pipelines (504, 708) detect a mispredicted conditional instruction, the processor (30) may use the first misprediction selection circuit (712), as illustrated in FIG. 7, to select one of the mispredicted conditional instructions from the execution pipelines (504, 708) for re-execution or replay in the execution pipeline (506).

In the illustrated embodiment, the selection may be performed based on the ages of the two mispredicted conditional instructions in each of the execution pipelines (504, 708). For example, the first misprediction selection circuit (712) may compare the age of the first mispredicted conditional instruction in the execution pipeline (504) to the age of the second mispredicted conditional instruction in the execution pipeline (708) and cause the older of the two conditional instructions to be executed in the execution pipeline (506). The age of the conditional instruction may be obtained in one of a variety of ways. For example, the fetch and decode circuit (100) may assign a number, such as Gnum, to the conditional instruction when the conditional instruction is decoded by the decoder (154). Gnum may be a unique number that is monotonically increasing (or decreasing) for each instruction. Accordingly, a younger instruction may be assigned a smaller Gnum (or a larger Gnum), while an older instruction may be assigned a larger Gnum (or a smaller Gnum). Accordingly, the first misprediction selection circuit (712) may compare the Gnums of two conditional instructions to select the older conditional instruction. Additionally, sometimes the age of a conditional instruction may also be determined based on the order of the conditional instructions within a reorder buffer (ROB) (108) of the processor (30).

When the first misprediction selection circuit (712) makes a selection, the corresponding execution pipeline (e.g., execution pipeline (504)) can create a bubble in the execution pipeline (506) and insert the selected conditional instruction into the bubble so that it can be executed by the execution pipeline (506). Once the execution pipeline (506) executes the conditional instruction and detects that it has been mispredicted, the execution pipeline (506) can instruct the fetch and decode circuit (100) to retrieve the instruction from the correct target address of the mispredicted conditional instruction for execution, as described above. Note that a selection by the first misprediction selection circuit (712) may not necessarily mean that the unselected mispredicted conditional instruction will not be re-executed or replayed by the execution pipeline (506). Instead, it simply means that when both "slow" execution pipelines (504, 708) detect misprediction at about the same time, one of the conditional instructions may be selected to cause a refetch first to resolve the conflict. The other non-selected conditional instruction may then be re-executed or replayed by the execution pipeline (506) to direct another refetch.

However, given that in the illustrated embodiment, multiple execution pipelines, including two "fast" execution pipelines (506, 710), may process instructions in parallel, it is possible that when execution pipeline (506) (e.g., the first "fast" execution pipeline) detects a mispredicted conditional instruction, execution pipeline (710) (e.g., the second "fast" execution pipeline) may also detect a mispredicted conditional instruction at about the same time. This may also create a conflict. As illustrated in FIG. 7 , in that case, the processor (30) may use the second prediction selection circuit (714) to select one of the two mispredicted conditional instructions from the two "fast" execution pipelines (506, 710) for refetch. For example, the second misprediction circuit (714) can compare the age of a first mispredicted conditional instruction in the execution pipeline (506) with the age of a second mispredicted conditional instruction in the execution pipeline (710), select the older of the two conditional instructions, and instruct the fetch and decode circuit (100) to obtain the instruction from the target address for execution.

Referring now to FIG. 8, a flow diagram illustrating one embodiment of the operations of a processor (30) including an instruction distribution circuit (502) and different execution pipelines (504, 506, 708, 710) is depicted. In the illustrated embodiment, a conditional instruction associated with a prediction may be received by the instruction distribution circuit (502), as indicated at block (802). As described above, the prediction of the conditional instruction may be (a) a bias prediction from the bias prediction circuit (156) or (b) an instruction prediction from the instruction prediction circuit (160).

In the illustrated embodiment, the instruction distribution circuit (502) may evaluate the prediction of a conditional instruction against one or more criteria to determine a confidence level of the prediction, as indicated at block (704). The instruction distribution circuit (502) may distribute the conditional instruction to one of the plurality of execution pipelines based on the confidence level of the prediction of the conditional instruction for the one or more criteria. For example, when the confidence level is high, the instruction distribution circuit (502) may distribute the conditional instruction to one of the execution pipelines (504, 708) (e.g., a “slow” execution pipeline) for execution, as indicated at block (806). Otherwise, when the confidence level is low, the instruction distribution circuit (502) may distribute the conditional instruction to one of the execution pipelines (506, 710) (e.g., a “fast” execution pipeline) for execution, as indicated at block (812).

When a conditional instruction is dispatched to one of the execution pipelines (504, 708), execution of the conditional instruction may determine that the prediction of the conditional instruction is a misprediction, as indicated at block (808). However, another one of the execution pipelines (504, 708) may also detect the mispredicted conditional instruction at about the same time. Therefore, to resolve the conflict, the processor (30) may use the first misprediction selection circuit (712), as indicated at block (810), to select one of the two mispredicted conditional instructions from the execution pipelines (504, 708) to be re-executed or replayed by the execution pipeline (506). In the illustrated embodiment, the selection may be performed based on the ages of the two conditional instructions. For example, the first misprediction selection circuit (712) may compare the age of a first mispredicted conditional instruction in the execution pipeline (504) with the age of a second mispredicted conditional instruction in the execution pipeline (708), as indicated in block (812), and cause the older of the two conditional instructions to be executed in the execution pipeline (506).

In the illustrated embodiment, execution of a conditional instruction in the execution pipeline (506) may determine that the conditional instruction is mispredicted, as indicated by block (814). Additionally, another execution pipeline (710) (e.g., a second “fast” execution pipeline) may also detect the mispredicted conditional instruction at approximately the same time that the execution pipeline (506) detects the mispredicted conditional instruction. Accordingly, the processor (30) may use the second misprediction circuit (714), as indicated by block (816), to select one of the two mispredicted conditional instructions from the execution pipelines (506, 710). Accordingly, the execution pipeline (506 or 710) of the selected mispredicted conditional instruction may instruct the fetch and decode circuit (100) to obtain an instruction from the correct target address of the selected mispredicted conditional instruction for execution, as indicated by block (818).

FIG. 9 is a block diagram of one embodiment of a processor (30) including the bias prediction circuit (156), the instruction prediction circuit (160), and/or the instruction distribution circuit (502) described in FIGS. 1 through 8. It is noted that FIG. 9 is provided as an example only for illustrative purposes. Thus, at times, the processor (30) may include only some, but not all, of the illustrated components. For example, at times, the processor (30) may include the bias prediction circuit (156) and the instruction prediction circuit (160), but not the instruction distribution circuit (502).

In the illustrated embodiment, the processor (30) includes a fetch and decode unit (100) (including an instruction cache or ICache (102)), a map-dispatch-rename (MDR) unit (106) (including a reorder buffer (ROB) (108)), one or more spare stations (110), one or more execution units (112), a register file (114), a data cache (DCache) (104), a load/store unit (LSU) (118), a spare station (RS) for the load/store unit (116), and a core interface unit (CIF) (122). The fetch and decode unit (100) is coupled to the MDR unit (106), which is coupled to the spare stations (110), the spare station (116), and the LSU (118). The spare stations (110) are coupled to the execution units (28). The register file (114) is coupled to the execution units (112) and the LSU (118). The LSU (118) is also coupled to the DCache (104), which is coupled to the CIF (122) and the register file (114). The LSU (118) includes a store queue (120) (STQ (120)) and a load queue (LDQ (124)).

The fetch and decode unit (100) may be configured to fetch instructions for execution by the processor (30) and to decode the instructions into ops for execution. More specifically, the fetch and decode unit (100) may be configured to cache previously fetched instructions from memory (via the CIF (122)) in the ICache (102) and to fetch a speculative path of instructions for the processor (30). As described above, in the illustrated embodiment, the fetch and decode unit (100) may include bias prediction circuitry (156) and instruction prediction circuitry (160) to provide respective predictions for conditional instructions. The fetch and decode unit (100) may implement various prediction structures to predict the fetch path. For example, a next fetch predictor may be used to predict fetch addresses based on previously executed instructions. Various types of branch predictors may be used to verify the next fetch prediction, or may be used to predict the next fetch addresses if the next fetch predictor is not used. The fetch and decode unit (100) may be configured to decode instructions into instruction operations. In some embodiments, a given instruction may be decoded into one or more instruction operations, depending on the complexity of the instruction. In particular, complex instructions may be microcoded in some embodiments. In such embodiments, the microcode routine for the instruction may be coded into instruction operations. In other embodiments, each instruction in the instruction set architecture implemented by the processor (30) may be decoded into a single instruction operation, such that the instruction operation may be essentially synonymous with the instruction (although it may be reshaped by the decoder). The term "instruction operation" may be more succinctly referred to herein as an "operation" or an "op."

The MDR unit (106) may be configured to map ops to speculative resources (e.g., physical registers) to allow out-of-order and/or speculative execution, and may dispatch the ops to the standby stations (110 and 116). As shown in FIG. 9 , in the illustrated embodiment, the MDR unit (106) may include instruction distribution circuitry (502). The ops may be mapped from architectural registers used in corresponding instructions to physical registers of the register file (114). That is, the register file (114) may implement a set of physical registers that may be larger in number than the architectural registers specified by the instruction set architecture implemented by the processor (30). The MDR unit (106) may manage the mapping of the architectural registers to the physical registers. In an embodiment, there may be separate physical registers for different operand types (e.g., integer, media, floating point, etc.). In other embodiments, physical registers may be shared across operand types. The MDR unit (106) may also be responsible for tracking speculative execution and retiring ops or flushing mis-speculated ops. The reorder buffer (108) may be used to track the program order of ops and manage retires/flushes. That is, the reorder buffer (108) may be configured to track multiple instruction operations corresponding to instructions that have been fetched by the processor and not retired by the processor.

The ops can be scheduled for execution when source operands for the ops are ready. In the illustrated embodiment, decentralized scheduling is used, for example, for each of the execution units (28) and the LSU (118) in the standby stations (116 and 110). Other embodiments may implement a centralized scheduler, if desired.

The LSU (118) may be configured to execute load/store memory ops. In general, a memory operation (memory op) may be an instruction operation that specifies an access to memory (although the memory access may be completed in a cache such as DCache (104)). A load memory operation may specify the transfer of data from a memory location to a register, while a store memory operation may specify the transfer of data from a register to a memory location. Load memory operations may be referred to as load memory ops, load ops, or loads; and store memory operations may be referred to as store memory ops, store ops, or stores. In one embodiment, the store ops may be executed as a store address op and a store data op. The store address op may be defined to generate an address of a store, probe a cache for an initial hit/miss determination, and update a store queue with the address and cache information. Thus, the store address op may have address operands as source operands. The store data op may be defined to transfer store data to a store queue. Thus, a store data op may not have address operands as source operands, but may have a store data operand as a source operand. In many cases, the address operands of the storage may be available before the store data operand, and thus the address may be determined and available earlier than the store data. In some embodiments, it may be possible for a store data op to be executed before the corresponding store address op, for example, if the store data operand is provided before one or more of the store address operands. In some embodiments, the store ops may be executed as store address and store data ops, while other embodiments may not implement store address/store data splitting. The remainder of this disclosure will often use store address ops (and store data ops) as examples, although implementations that do not utilize store address/store data optimization are also contemplated. An address generated by execution of a store address op may be referred to as an address corresponding to the store op.

Load/store ops may be received at the standby station (116), which may be configured to monitor the source operands of the operations to determine when they are available, and then issue the operations to the load or store pipelines, respectively. Some of the source operands may be available when the operations are received at the standby station (116), which may be indicated in the data received by the standby station (116) from the MDR unit (106) for the corresponding operation. Other operands may become available through execution of operations by other execution units (112), or even through execution of earlier load ops. The operands may be collected by the standby station (116), or may be read from the register file (114) upon issuance from the standby station (116), as illustrated in FIG. 6 .

In one embodiment, the standby station (116) may be configured to issue load/store ops out of order (from their original order within the code sequence being executed by the processor (30), referred to as “program order”) as operands become available. To ensure that there is space in the LDQ (124) or STQ (120) for older operations to be bypassed by newer operations in the standby station (116), the MDR unit (106) may include circuitry that pre-allocates LDQ (124) or STQ (120) entries to operations being sent to the load/store unit (118). If there is no LDQ entry available for a load being processed by the MDR unit (106), the MDR unit (106) may delay dispatching the load op and subsequent ops in program order until one or more LDQ entries become available. Similarly, if there is no STQ entry available for storage, the MDR unit (106) may delay op dispatch until one or more STQ entries become available. In other embodiments, the standby station (116) may issue operations in program order, and LRQ (46)/STQ (120) allocation may occur upon issuance from the standby station (116).

The LDQ (124) may track loads from initial execution through retirement by the LSU (118). The LDQ (124) may be responsible for ensuring that memory ordering rules are not violated (between loads executed out of order as well as between loads and stores). If a memory ordering violation is detected, the LDQ (124) may signal a reordering for the corresponding load. The reordering may cause the processor (30) to flush the load and subsequent ops into program order and to refetch the corresponding instructions. Speculative state for the load and subsequent ops may be discarded, and the ops may be reprocessed to be refetched and re-executed by the fetch and decode unit (100).

When a load/store address op is issued by the standby station (116), the LSU (118) may be configured to generate an address accessed by the load/store and to translate the address from a valid or virtual address generated from the address operands of the load/store address op to a physical address actually used in the address memory. The LSU (118) may be configured to generate an access to the DCache (104). For load operations that hit in the DCache (104), data may be speculatively forwarded from the DCache (104) to the destination operand of the load operation (e.g., a register in the register file (114)) unless the address hits a preceding operation in the STQ (120) (i.e., an older store in program order) or unless the load is being replayed. The data may also be speculatively scheduled and forwarded to dependent ops in the execution units (112). In these cases, the execution units (112) may bypass the forwarded data instead of the data output from the register file (114). If the store data is available for forwarding for an STQ hit, the data output by the STQ (120) may be forwarded instead of the cache data. Cache misses and STQ hits where data cannot be forwarded may be reasons for replay, and load data may not be forwarded in such cases. The cache hit/miss status from the DCache (104) may be logged in the STQ (120) or LDQ (124) for later processing.

The LSU (118) may implement multiple load pipelines. For example, in one embodiment, three load pipelines (“pipes”) may be implemented, although in other embodiments, more or fewer pipelines may be implemented. Each pipeline may execute different loads independently and in parallel with other loads. That is, the RS (116) may issue any number of loads up to the number of load pipes in the same clock cycle. The LSU (118) may also implement one or more store pipes, and in particular may implement multiple store pipes. However, the number of store pipes need not be the same as the number of load pipes. In one embodiment, for example, two store pipes may be used. The standby station (116) may issue store address ops and store data ops independently and in parallel to the store pipes. The store pipes may be coupled to an STQ (120), which may be configured to maintain store operations that have been executed but not committed.

The CIF (122) may be responsible for communicating with the rest of the system including the processor (30) on behalf of the processor (30). For example, the CIF (122) may be configured to request data for DCache (104) misses and ICache (102) misses. When the data is returned, the CIF (122) may signal a cache fill to the corresponding cache. For DCache fills, the CIF (122) may also notify the LSU (118). The LDQ (124) may attempt to schedule replayed loads that are waiting for a cache fill so that the replayed loads can forward the fill data when the fill data is provided to the DCache (104) (referred to as a fill forward operation). If a replayed load is not successfully replayed during a fill, the replayed load may be subsequently scheduled and replayed through the DCache (104) as a cache hit. CIF (122) may also write back modified cache lines evicted by DCache (104), merge store data to non-cacheable stores, etc. In another example, CIF (122) may communicate interrupt-related signals to the processor (30), e.g., interrupt requests and/or acknowledge/non-acknowledge signals from/to peripheral devices of the system including the processor (30).

The execution units (112) may include any types of execution units in various embodiments. For example, the execution units (112) may include integer, floating point, and/or vector execution units. The integer execution units may be configured to execute integer ops. Generally, an integer op is an op that performs a defined operation (e.g., arithmetic, logical, shift/rotate, etc.) on integer operands. The integers may be numerical values, each of which corresponds to a mathematical integer. The integer execution units may include branch processing hardware to process branch ops, or there may be separate branch execution units. As described above, the execution units (112) and associated spare stations (110) may implement one or more execution pipelines (164, 504, 506, 708, and/or 710) as described in FIGS. 1 through 8.

Floating point execution units can be configured to execute floating point ops. In general, floating point ops can be ops that are defined to operate on floating point operands. A floating point operand is an operand represented by a base raised to an exponent power and multiplied by a mantissa (or significand). The exponent, the sign of the operand, and the mantissa/significand can be explicitly shown in the operand, and the base can be implied (e.g., in an embodiment, the base is 2).

Vector execution units can be configured to execute vector ops. Vector ops can be used, for example, to process media data (e.g., image data such as pixels, audio data, etc.). Media processing can be characterized by performing the same processing on a large amount of data, each of which is a relatively small value (e.g., 8 bits or 16 bits, compared to integers which are 32 bits or 64 bits). Thus, vector ops include single instruction-multiple data (SIMD), or vector operations on operands representing multiple media data.

Thus, each execution unit (112) may include hardware configured to perform the operations defined for the ops that the particular execution unit is defined to handle. The execution units may be generally independent of one another in that each execution unit may be configured to operate on the ops issued to it without dependencies on other execution units. Viewed another way, each execution unit may be an independent pipe executing the ops. Different execution units may have different execution latencies (e.g., different pipe lengths). Additionally, different execution units may have different latencies with respect to the pipeline stage where the bypass occurs, and thus the clock cycles over which speculative scheduling of dependent ops based on a load op occurs may vary based on the type of op and the execution unit (28) that will execute the op.

It is noted that any number and type of execution units (112) may be included in various embodiments, including embodiments having one execution unit, and embodiments having multiple execution units.

A cache line may be a unit of allocation and deallocation within a cache. That is, data within a cache line may be allocated/deallocated to/from the cache as a unit. Cache lines may vary in size (e.g., 32 bytes, 64 bytes, 128 bytes, or larger or smaller cache lines). Different caches may have different cache line sizes. ICache (102) and DCache (104) may each be caches having any desired capacity, cache line size, and configuration. In various embodiments, there may be more additional levels of cache between DCache (104)/ICache (102) and main memory.

At various points, load/store operations are referred to as being younger or older than other load/store operations. If a first operation follows a second operation in program order, the first operation may be younger than the second operation. Similarly, if the first operation precedes a second operation in program order, the first operation may be older than the second operation.

Referring now to FIG. 10 , a block diagram of a system (10) that may include one or more processors (30) is illustrated in one embodiment. In the illustrated embodiment, the system (10) may be implemented as a system on a chip (SOC) (10) coupled to memory (12). As the name implies, the components of the SOC (10) may be integrated on a single semiconductor substrate as an integrated circuit "chip." In some embodiments, the components may be implemented on two or more separate chips within the system. However, the SOC (10) will be used herein as an example. In the illustrated embodiment, the components of the SOC (10) include a plurality of processor clusters (14A-14n), an interrupt controller (20), one or more peripheral components (18) (more briefly, "peripherals"), a memory controller (22), and a communication fabric (27). Components (14A through 14n, 18, 20, and 22) may all be coupled to the communication fabric (27). A memory controller (22) may be coupled to the memory (12) during use. In some embodiments, there may be more than one memory controller coupled to a corresponding memory. The memory address space may be mapped across the memory controllers in any desired manner. In the illustrated embodiment, the processor clusters (14A through 14n) may each include a plurality of processors (P) (30), each of which may further include a respective bias prediction circuit (156), a respective instruction prediction circuit (160), and/or a respective instruction distribution circuit (502) as described in FIGS. 1 through 9 . The processors (30) may form central processing units (CPU(s)) of the SOC (10). In one embodiment, one or more of the processor clusters (14A to 14n) may not be used as CPUs.

As previously mentioned, the processor clusters (14A to 14n) may include one or more processors (30) that may function as the CPU of the SOC (10). The CPU of the system includes processor(s) that execute main control software of the system, such as an operating system. Typically, software executed by the CPU during use may control other components of the system to realize desired functions of the system. The processors may also execute other software, such as application programs. The application programs may provide user functionality and may rely on the operating system for low-level device control, scheduling, memory management, etc. Thus, the processors may also be referred to as application processors.

In general, a processor may include any circuitry and/or microcode configured to execute instructions defined in an instruction set architecture implemented by the processor. Processors may include processor cores implemented on an integrated circuit with other components, such as a system on a chip (SOC (10)) or other levels of integration. Processors may additionally include processor cores and/or microprocessors integrated into discrete microprocessors, multi-chip module implementations, processors implemented as multiple integrated circuits, etc.

A memory controller (22) may typically include circuitry for receiving memory operations from other components of the SOC (10) and accessing memory (12) to complete the memory operations. The memory controller (22) may be configured to access any type of memory (12). For example, the memory (12) may be dynamic RAM (DRAM), such as static random-access memory (SRAM), synchronous DRAM (SDRAM), including double data rate (DDR, DDR2, DDR3, DDR4, etc.) DRAM. Low power/mobile versions of DDR DRAM may be supported (e.g., LPDDR, mDDR, etc.). The memory controller (22) may include queues for memory operations for ordering (and potentially reordering) the operations and presenting the operations to the memory (12). The memory controller (22) may additionally include data buffers for storing write data awaiting a write to memory and read data awaiting a return to the source of a memory operation. In some embodiments, the memory controller (22) may include a memory cache for storing recently accessed memory data. For example, in SOC implementations, the memory cache may reduce power consumption of the SOC by avoiding re-accessing data from memory (12) when it is expected to be accessed again soon. In some cases, the memory cache may also be referred to as a system cache, as opposed to private caches that assist only certain components, such as the L2 cache or caches within processors. Additionally, in some embodiments, the system cache need not be located within the memory controller (22).

Peripherals (18) may be any set of additional hardware functions included in the SOC (10). For example, peripherals (18) may include video peripherals, such as image signal processors configured to process image capture data from a camera or other image sensor, GPUs, video encoders/decoders, scalers, rotators, blenders, display controllers, etc. Peripherals may include audio peripherals, such as microphones, speakers, interfaces to microphones and speakers, audio processors, digital signal processors, mixers, etc. Peripherals may include interface controllers for various interfaces external to the SOC (10), including interfaces such as Universal Serial Bus (USB), Peripheral Component Interconnect (PCI) Express (PCIe), serial and parallel ports, etc. Peripherals may include networking peripherals, such as media access controllers (MACs). Any set of hardware may be included.

The communication fabric (27) may be any communication interconnect and protocol for communicating between components of the SOC (10). The communication fabric (27) may be bus-based, including hierarchical buses with shared bus configurations, cross bar configurations, and bridges. The communication fabric (27) may also be packet-based and hierarchical with bridges, cross bars, point-to-point, or other interconnections.

It is noted that the number of components of the SOC (10) (and the number of subcomponents for the components illustrated in FIG. 4, such as the processors (30) within each processor cluster (14A through 14n)) may vary from embodiment to embodiment. Additionally, the number of processors (30) within one processor cluster (14A through 14n) may be different than the number of processors (30) within another processor cluster (14A through 14n). There may be more or fewer of each component/subcomponent than the number illustrated in FIG. 4.

computer system

Referring now to FIG. 11 , a block diagram of one embodiment of a system (700) is illustrated. In the illustrated embodiment, the system (700) includes at least one instance of a system on a chip (SOC) (10) coupled to one or more peripherals (704) and external memory (702), as described in FIG. 10 . A power supply (PMU) (708) is provided that supplies supply voltages to the SOC (10) as well as one or more supply voltages to the memory (702) and/or the peripherals (154). In some embodiments, more than one instance of the SOC (10) (e.g., SOCs 10A-10q) may be included (and more than one memory (702) may also be included). In one embodiment, the memory (702) may include the memory (12) illustrated in FIGS. 1-10 .

The peripherals (704) may include any desired circuitry depending on the type of system (700). For example, in one embodiment, the system (704) may be a mobile device (e.g., a personal digital assistant (PDA), a smart phone, etc.) and the peripherals (704) may include devices for various types of wireless communications, such as Wi-Fi, Bluetooth, cellular, global positioning system, etc. The peripherals (704) may also include additional storage, including RAM storage, solid state storage, or disk storage. The peripherals (704) may include user interface devices, such as a display screen, including a touch display screen or a multi-touch display screen, a keyboard or other input devices, microphones, speakers, etc. In other embodiments, the system (700) may be any type of computing system (e.g., a desktop personal computer, a laptop, a workstation, a nettop, etc.).

The external memory (702) may include any type of memory. For example, the external memory (702) may be SRAM, dynamic RAM (DRAM) such as synchronous DRAM (SDRAM), double data rate (DDR, DDR2, DDR3, etc.) SDRAM, RAMBUS DRAM, low power versions of DDR DRAM (e.g., LPDDR, mDDR, etc.), etc. The external memory (702) may include one or more memory modules on which memory devices are mounted, such as single in-line memory modules (SIMMs), dual in-line memory modules (DIMMs), etc. Alternatively, the external memory (702) may include one or more memory devices mounted on the SOC (10) in a chip-on-chip or package-on-package implementation.

As illustrated, the system (700) is depicted as having a wide range of applications. For example, the system (700) may be utilized as part of chips, circuitry, components, etc., of a desktop computer (710), a laptop computer (720), a tablet computer (730), a cellular or mobile phone (740), or a television (750) (or a set-top box coupled to a television). Also illustrated is a smartwatch and a health monitoring device (760). In some embodiments, the smartwatch may include a variety of general-purpose computing-related functions. For example, the smartwatch may provide access to email, cell phone services, a user calendar, etc. In various embodiments, the health monitoring device may be a dedicated medical device or may otherwise include dedicated health-related functions. For example, the health monitoring device may monitor a user's vital signs, track a user's proximity to other users for the purposes of epidemiological social distancing, perform contact tracing, provide communication to emergency services in the event of a health crisis, etc. In various embodiments, the smartwatch mentioned above may or may not include some or all of the health monitoring related features. Other wearable devices are also contemplated, such as devices worn around the neck, devices implantable in the human body, glasses designed to provide augmented and/or virtual reality experiences, etc.

The system (700) may additionally be used as part of a cloud-based service(s) (770). For example, the devices and/or other devices previously mentioned may access computing resources in the cloud (i.e., remotely located hardware and/or software resources). Additionally, the system (700) may be utilized in one or more devices in the home other than those previously mentioned. For example, appliances in the home may monitor and detect conditions requiring attention. For example, various devices in the home (e.g., a refrigerator, a cooling system, etc.) may monitor the status of the devices and provide alerts to the homeowner (or, for example, a repair facility) when certain events are detected. Alternatively, a thermostat may monitor the temperature in the home and automate adjustments to the heating/cooling system based on the homeowner's history of responses to various conditions. Also illustrated in FIG. 11 is an application of the system (700) to various modes of transportation. For example, the system (700) may be used in the control and/or entertainment systems of aircraft, trains, buses, rental automobiles, personal automobiles, watercraft ranging from personal boats to cruise ships, scooters (whether rented or owned), etc. In various instances, the system (700) may be used to provide automated guidance (e.g., autonomous vehicles), general system control, etc. Any of these many other embodiments are possible and contemplated. It is noted that the devices and applications illustrated in FIG. 11 are illustrative only and are not intended to be limiting. Other devices are also possible and contemplated.

Computer readable storage medium

Referring now to FIG. 12 , a block diagram of one embodiment of a computer-readable storage medium (800) is illustrated. Generally speaking, a computer-accessible storage medium can include any storage medium that is accessible by a computer during use to provide instructions and/or data to a computer. For example, the computer-accessible storage medium can include magnetic or optical media, such as a disk (either fixed or removable), tape, CD-ROM, DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, or Blu-Ray. The storage medium can additionally include volatile or nonvolatile memory media, such as RAM (e.g., synchronous dynamic RAM (SDRAM), Rambus DRAM (RDRAM), static RAM (SRAM), etc.), ROM, or flash memory. The storage medium can be physically contained within the computer where the storage medium provides the instructions/data. Alternatively, the storage medium can be coupled to the computer. For example, the storage medium may be connected to the computer via a wireless link, such as a network or network-attached storage. The storage medium may be connected via a peripheral interface, such as a Universal Serial Bus (USB). In general, the computer-accessible storage medium (800) may store data in a non-transitory manner, and non-transitory in this context may refer to not transmitting instructions/data over a signal. For example, the non-transitory storage may be volatile (and may lose stored instructions/data in response to a power outage) or non-volatile.

The computer-accessible storage medium (800) of FIG. 12 may store a database (804) representing the SOC (10) described above in FIG. 10. Generally, the database (804) may be a database that can be read by a program and used directly or indirectly to fabricate hardware including the SOC (10). For example, the database may be a behavioral-level description of hardware functionality in a high-level design language (HDL), such as Verilog or VHDL, or a register-transfer level (RTL) description. The description may be read by a synthesis tool that can synthesize the description to generate a netlist including a list of gates from a synthesis library. The netlist includes a set of gates that also represent the functionality of the hardware including the SOC (10). The netlist may then be placed and routed to generate a data set describing geometrical features to be applied to the masks. Subsequently, the masks may be used in various semiconductor fabrication steps to create a semiconductor circuit or circuits corresponding to the SOC (10). Alternatively, the database (804) on the computer accessible storage medium (800) may be a netlist (with or without a synthesis library) or a data set, as desired.

While the computer accessible storage medium (800) stores a representation of the SOC (10), other embodiments may convey a representation of any portion of the SOC (10), including any subset of the components illustrated in FIG. 4, as desired. The database (804) may represent any portion of the above.

***

This disclosure includes references to "an embodiment" or groups of "embodiments" (e.g., "some embodiments" or "various embodiments"). Embodiments are different implementations or instances of the disclosed concepts. References to "an embodiment," "one embodiment," "a particular embodiment," etc. are not necessarily all referring to the same embodiment. Many possible embodiments are contemplated, including modifications or alternatives that fall within the spirit or scope of the disclosure, not just those specifically disclosed.

This disclosure may discuss potential benefits that may arise from the disclosed embodiments. Not all implementations of these embodiments will necessarily exhibit any or all of the potential benefits. Whether or not a particular implementation realizes benefits depends on many factors, some of which are outside the scope of this disclosure. In fact, there are many reasons why an implementation within the scope of the claims may not exhibit some or all of the disclosed benefits. For example, a particular implementation may include other circuitry outside the scope of this disclosure that negates or reduces one or more of the disclosed benefits with respect to one of the disclosed embodiments. Additionally, suboptimal design practices (e.g., implementation techniques or tools) of a particular implementation may also negate or reduce the disclosed benefits. Even assuming a skilled implementation, the realization of benefits may still depend on other factors, such as the environmental conditions in which the implementation is deployed. For example, the inputs provided to a particular implementation may prevent one or more of the problems addressed in this disclosure from occurring in a particular case, and as a result, the benefits of the solution may not be realized. Given the existence of possible factors outside of this disclosure, it is expressly intended that any potential advantages described herein should not be construed as claim limitations that must be satisfied in order to prove infringement. Rather, the identification of these potential advantages is intended to illustrate the type(s) of improvements that designers who have the benefit of the present disclosure may utilize. That these advantages are permissively described (e.g., stating that a particular advantage "may" occur) is not intended to convey doubt as to whether such advantages can actually be realized, but rather to recognize the technical reality that realization of such advantages often depends on additional factors.

Unless otherwise stated, the embodiments are not limiting. That is, the disclosed embodiments are not intended to limit the scope of claims made based on this disclosure, even if only one example is described with respect to a particular feature. The disclosed embodiments are intended to be illustrative, not restrictive, and nothing in this disclosure contains any statement to the contrary. Accordingly, this application is intended to allow claims covering not only the disclosed embodiments, but also such alternatives, modifications, and equivalents as would be apparent to one skilled in the art having the benefit of this disclosure.

For example, the features of the present application may be combined in any suitable manner. Accordingly, new claims may be drafted during the examination of the present application (or an application claiming priority thereto) for any combination of such features. In particular, referring to the appended claims, the features of the dependent claims may be combined with the features of other dependent claims, including claims dependent on other independent claims, where appropriate. Likewise, the features of each independent claim may be combined where appropriate.

Accordingly, although the attached dependent claims may each be written to depend on one another, additional dependencies are contemplated. Any combination of features in a dependency that is consistent with the present disclosure is contemplated and may be claimed in this or another application. In short, the combinations are not limited to those specifically recited in the attached claims.

Where appropriate, claims written in one format or statutory type (e.g., apparatus) are also considered to be intended to support corresponding claims written in another format or statutory type (e.g., method).

***

Because this disclosure is a legal document, various terms and phrases may be subject to administrative and judicial interpretation. It is provided herein that the following paragraphs, in addition to the definitions provided throughout this disclosure, should be used in determining how to interpret claims drafted based on this disclosure.

References to a singular form of an item (i.e., a noun or noun phrase preceded by "a," "an," or "the") are intended to mean "one or more" unless the context clearly dictates otherwise. Thus, references to "an item" in a claim do not exclude additional instances of the item, regardless of the context. A "plurality" of items refers to a set of two or more of the items.

The word "may" is used in this specification in a permissive sense (i.e., having the possibility of doing, being able to do) rather than an obligatory sense (i.e., must).

The terms "comprising" and "including" and their forms are open-ended and mean "including but not limited to."

Where the term "or" is used herein in connection with a list of options, it will generally be understood to be used in an inclusive sense unless the context provides otherwise. Thus, referring to "x or y" is equivalent to "x or y, or both," and thus encompasses 1) x but not y, 2) y but not x, and 3) both x and y. On the other hand, a phrase such as "either x or y, but not both" makes it clear that "or" is being used in an exclusive sense.

References to "w, x, y, or z, or any combination thereof" or "... at least one of w, x, y, and z" are intended to encompass all possibilities relating to a single element, up to the full number of elements in the set. For example, given a set [w, x, y, z], such expressions encompass any single element of the set (e.g., w but not x, y, or z), any two elements (e.g., w and x but not y or z), any three elements (e.g., w, x, and y but not z), and all four elements. Thus, the phrase "... at least one of w, x, y, and z" refers to at least one element of the set [w, x, y, z], and thereby encompasses all possible combinations of that list of elements. Such phrases should not be interpreted as requiring that there be at least one instance of w, at least one instance of x, at least one instance of y, and at least one instance of z.

In this disclosure, various "labels" may precede nouns or noun phrases. Unless otherwise provided by context, different labels used in a feature (e.g., "a first circuit," "a second circuit," "a particular circuit," "a given circuit," etc.) refer to different instances of the feature. Furthermore, the labels "first," "second," and "third" when applied to a feature do not imply any type of order (e.g., spatial, temporal, logical, etc.) unless otherwise specified.

The phrase "based on" is used to describe one or more factors that influence a decision. This term does not exclude the possibility that additional factors may influence the decision. That is, the decision may be based solely on the particular factors, or it may be based on both the particular factors and unspecified other factors. Consider the phrase "determine A based on B." This phrase specifies that B is a factor used in determining A or influencing the determination of A. This phrase does not exclude that the determination of A may be based on some other factor, such as C. This phrase is also intended to encompass embodiments in which A is determined solely on B. As used herein, the phrase "based on" is synonymous with the phrase "based at least in part on."

The phrases "in response to" and "in response to" describe one or more factors that trigger an effect. These phrases do not exclude the possibility that additional factors may act or trigger the effect jointly with or independently of the specified factors. That is, the effect may be responsive only to the factors in question, or may be responsive not only to the specified factors but also to other, unspecified factors. Consider the phrase "performs A in response to B." This phrase specifies that B is a factor that triggers the outcome of A or triggers a particular outcome for A. This phrase does not exclude that performing A may also be responsive to some other factor, such as C. This phrase also does not exclude that performing A may be jointly responsive to B and C. This phrase is also intended to encompass embodiments in which A is performed solely in response to B. As used herein, the phrase "in response to" is synonymous with the phrase "at least partially responsive to." Similarly, the phrase "in response to" is synonymous with the phrase "at least in part in response to."

***

Within this disclosure, different entities (which may be variously referred to as "units," "circuits," other components, etc.) may be described or claimed as being "configured to" perform one or more tasks or operations. This description—[an entity] configured to [perform one or more tasks]—is used herein to refer to a structure (i.e., a physical thing). More specifically, this description is used to indicate that the structure is arranged to perform one or more tasks when in operation. A structure may be said to be "configured" to perform some task even if the structure is not currently in operation. Thus, an entity described or referred to as being "configured to" perform some task refers to a physical thing, such as a device, circuit, system, etc., having a memory and a processor unit that store executable program instructions for implementing the task, etc. This phrase is not used herein to refer to intangible things.

In some instances, various units/circuits/components may be described herein as performing a set of tasks or operations. Such entities are understood to be "configured" to perform such tasks/operations, even if not specifically stated otherwise.

The term "configured" is not intended to mean "configurable." For example, an unprogrammed FPGA would not be considered "configured" to perform a particular function. However, such an unprogrammed FPGA may be "configurable" to perform that function. After proper programming, the FPGA may be said to be "configured" to perform a particular function.

For purposes of United States patent applications based on this disclosure, reference in a claim to a structure being "configured to" perform one or more tasks is expressly intended to exempt 35 U.S.C. §112(f) from application to that claim element. If an applicant desires to invoke Section 112(f) during the prosecution of a United States patent application based on this disclosure, he or she will list claim elements using the "means for" [performing the function] construct.

In this disclosure, different "circuits" may be described. These circuits or "circuitry" constitute hardware including various types of circuit elements, such as combinational logic, clocked storage devices (e.g., flip-flops, registers, latches, etc.), finite state machines, memory (e.g., random-access memory, embedded dynamic random-access memory), programmable logic arrays, etc. The circuitry may be custom designed or taken from standard libraries. In various implementations, the circuitry may include a combination of digital components, analog components, or both, as appropriate. Specific types of circuits may be generally referred to as "units" (e.g., a decode unit, an arithmetic logic unit (ALU), a functional unit, a memory management unit (MMU), etc.). Such units may also be referred to as circuits or circuitry.

Accordingly, the disclosed circuits/units/components and other elements illustrated in the drawings and described herein include hardware elements such as those described in the preceding paragraphs. In many cases, the internal arrangement of hardware elements within a particular circuit can be specified by describing the functionality of that circuit. For example, a particular "decode unit" may be described as performing the function of "processing an opcode of an instruction and routing the instruction to one or more of a plurality of functional units," meaning that the decode unit is "configured" to perform that function. Such a functional specification is sufficient to suggest a set of possible architectures for the circuit to one of ordinary skill in the computer arts.

In various embodiments, as discussed in the preceding paragraphs, the circuits, units, and other elements, arrangements, and operations defined by them, the circuits/units/components, in relation to each other and in the manner in which they interact, form a microarchitectural definition of hardware that is ultimately fabricated in an integrated circuit or programmed into an FPGA to form a physical implementation of the microarchitectural definition. Accordingly, the microarchitectural definition is recognized by those skilled in the art as a structure from which many physical implementations may be derived, all of which fall within the broader structure described by the microarchitectural definition. That is, one skilled in the art, provided with the microarchitectural definition provided in accordance with the present disclosure, can, without undue experimentation and with the application of conventional techniques, implement the structure by coding the description of the circuits/units/components in a hardware description language (HDL), such as Verilog or VHDL. The HDL description is often expressed in a manner that may appear functional. However, to those skilled in the art, such HDL descriptions are the means by which the structure of a circuit, unit, or component is translated into the next level of implementation detail. Such HDL descriptions may take the form of behavioral code (typically non-synthesizable), register transfer language (RTL) code (typically synthesizable, unlike behavioral code), or structural code (e.g., a netlist specifying the logic gates and their connectivity). The HDL description may then be synthesized into a library of cells designed for a given integrated circuit fabrication technology, modified for timing, power, and other reasons, to create masks and ultimately become the final design database that is sent to the foundry to produce the integrated circuit. Some hardware circuits or portions thereof may also be captured as an integrated circuit design, along with the circuit portions that are custom-designed and synthesized with a schematic editor. Integrated circuits may include transistors and other circuit elements (e.g., passive elements such as capacitors, resistors, inductors, etc.), and interconnections between the transistors and the circuit elements. Some embodiments may implement a number of integrated circuits coupled together to implement the hardware circuits and/or in some embodiments discrete elements may be used. Alternatively, the HDL design may be synthesized into and implemented in a programmable logic array, such as a field programmable gate array (FPGA). This separation between the design of a group of circuits and the subsequent low-level implementation of those circuits typically results in a scenario where the circuit or logic designer does not specify a particular set of structures for the low-level implementation, beyond a description of what the circuit is configured to do, as these processes are typically performed at different stages of the circuit implementation process.

The fact that many different low-level combinations of circuit elements can be used to implement the same circuit specification results in many equivalent structures for that circuit. As noted, these low-level circuit implementations can vary depending on variations in manufacturing technology, the foundry chosen to manufacture the integrated circuit, the library of cells available for a particular project, etc. In many cases, the choices made by different design tools or methodologies to generate these different implementations can be arbitrary.

In addition, it is common for a single implementation of a particular functional specification of a circuit for a given embodiment to include a large number of devices (e.g., millions of transistors). Thus, the sheer volume of this information makes it impractical to provide a full description of the low-level structure used to implement a single embodiment, let alone the vast array of equivalent possible implementations. For this reason, the present disclosure describes the structure of the circuit using functional abbreviations commonly employed in the industry.

The following items describe exemplary embodiments consistent with the drawings and the description above.

1. As a processor,

It includes a command distribution circuit, and the command distribution circuit is:

Receiving a first conditional instruction associated with a prediction; and

configured to distribute the first conditional instruction to one of a plurality of execution pipelines for execution based on prediction of the first conditional instruction, the plurality of execution pipelines including a first execution pipeline and a second execution pipeline providing different latencies for processing mispredicted conditional instructions; and

The first execution pipeline is:

In response to receiving the first conditional command,

Execute the first conditional instruction;

determines that the prediction of the first conditional instruction is a prediction error; and

A processor configured to cause execution of a first conditional instruction in a second execution pipeline in response to determining that the prediction of the first conditional instruction is a misprediction.

2. In item 1, the second execution pipeline,

Execute the first conditional instruction;

determines that the prediction of the first conditional instruction is a prediction error; and

A processor configured to, in response to determining that the prediction of the first conditional instruction is a misprediction, cause an instruction to be obtained from the target address of the first conditional instruction for execution.

3. A processor according to item 1, wherein the prediction of the first conditional instruction is associated with a confidence level for one or more criteria, wherein the one or more criteria include at least one of: (a) that the prediction is provided by a bias prediction circuit using a bias table, or (b) that the prediction is provided by an instruction prediction circuit using one or more tables that are at least in part based on a prediction history of conditional instructions.

4. A processor according to item 3, wherein the instruction distribution circuit is configured to distribute the first conditional instruction to the first execution pipeline for execution when the prediction of the first conditional instruction is associated with a high confidence level, or to distribute the first conditional instruction to the second execution pipeline for execution when the prediction of the first conditional instruction is associated with a low confidence level.

5. In item 3,

Third Execution Pipeline - The third execution pipeline is:

Executes a second conditional instruction associated with a high confidence level prediction; and

- configured to determine that the prediction of the second conditional instruction is a prediction error; and

It additionally includes a first prediction error selection circuit, wherein the first prediction error selection circuit comprises:

Before the first conditional instruction is executed in the second execution pipeline, the age of the first conditional instruction from the first execution pipeline is compared with the age of the second conditional instruction from the third execution pipeline;

A processor configured to cause the first conditional instruction to be executed in a second execution pipeline in response to determining that the first conditional instruction is older than the second conditional instruction.

6. In item 3,

4th Execution Pipeline - The 4th execution pipeline is:

Execute a third conditional instruction associated with a low confidence level prediction; and

- configured to determine that the prediction of the third conditional instruction is a prediction error; and

Second prediction error selection circuit - The second prediction error selection circuit is,

Compare the age of the first conditional instruction from the second execution pipeline with the age of the third conditional instruction from the fourth execution pipeline; and

A processor further comprising: - configured to cause an instruction to be obtained from a target address of an older one of the first and third conditional instructions for execution.

7. In item 1, the second execution pipeline provides lower latency than the first execution pipeline for processing mispredicted conditional instructions, and to provide lower latency, the second execution pipeline is configured to, in response to determining that the prediction of the first conditional instruction is a misprediction, directly direct another circuit of the processor to obtain an instruction from the target address of the first conditional instruction for execution.

8. A processor according to item 1, wherein the second execution pipeline provides lower latency than the first execution pipeline for processing mispredicted conditional instructions, and the second execution pipeline includes fewer stages than the first execution pipeline.

9. In item 1, in order to cause the first conditional instruction to be executed in the second execution pipeline, the first execution pipeline,

Create a bubble in the second execution pipeline; and

A processor configured to cause a first conditional instruction to be inserted into a bubble such that the first conditional instruction can be executed by the second execution pipeline.

10. In item 9, the second execution pipeline,

A processor further configured to execute a non-conditional instruction in the same cycle as a first conditional instruction.

11. As a method,

In an instruction distribution circuit of a processor, a step of receiving a first conditional instruction associated with a prediction;

Distributing a first conditional instruction to one of a plurality of execution pipelines for execution based on a prediction of the first conditional instruction using an instruction distribution circuit, wherein the plurality of execution pipelines include a first execution pipeline and a second execution pipeline providing different latencies for processing mispredicted conditional instructions;

A step of executing a first conditional instruction using a first execution pipeline;

Using the first execution pipeline, determining that the prediction of the first conditional instruction is a prediction error; and

A method comprising: in response to determining that a prediction of a first conditional instruction is a prediction misprediction, causing the first conditional instruction to be executed in a second execution pipeline.

12. In item 11,

A method further comprising the step of causing an instruction to be obtained from a target address of a first conditional instruction for execution using a second execution pipeline.

13. A method according to item 11, wherein the prediction of the first conditional instruction is associated with a confidence level for one or more criteria, wherein the one or more criteria include at least one of: (a) that the prediction is provided by a bias prediction circuit using a bias table, or (b) that the prediction is provided by an instruction prediction circuit using one or more tables that are at least in part based on a prediction history of conditional instructions.

14. In item 13,

A method further comprising the step of distributing a first conditional instruction to a first execution pipeline for execution when a prediction of the first conditional instruction satisfies one or more criteria, or distributing the first conditional instruction to a second execution pipeline for execution when a prediction of the first conditional instruction does not satisfy the one or more criteria.

15. In item 13,

Using a third execution pipeline, executing a second conditional instruction associated with a prediction satisfying the criteria;

An additional step of determining that the prediction of the second conditional instruction is a prediction error is included,

The step that causes the first conditional instruction to be executed in the second execution pipeline is:

A step of comparing the age of the first conditional instruction and the age of the second conditional instruction using a first prediction error selection circuit; and

A method further comprising, in response to determining that the first conditional instruction is older than the second conditional instruction, causing the first conditional instruction to be executed in the second execution pipeline.

16. In item 13,

Using the fourth execution pipeline, executing the third conditional instruction associated with the prediction that does not satisfy the criteria;

A step of determining that the prediction of the third conditional instruction is a prediction error;

A step of comparing the age of the first conditional instruction and the age of the third conditional instruction using a second prediction error selection circuit; and

A method further comprising the step of causing an instruction to be obtained from a target address of an older one of the first and third conditional instructions for execution.

17. In item 13,

In a command distribution circuit, a step of receiving a fourth conditional command associated with a prediction satisfying criteria; and

A method further comprising the step of distributing a fourth conditional instruction to the second execution pipeline for execution based on occupancy of the second execution pipeline.

18. A method according to item 11, wherein the second execution pipeline provides less latency than the first execution pipeline for processing mispredicted conditional instructions, and the second execution pipeline has a communication path for directly instructing an instruction to be fetched from a target address for execution in response to determining that the prediction of the first conditional instruction is a misprediction.

19. As a system,

comprising one or more processors, wherein the one or more processors individually:

It includes a command distribution circuit, and the command distribution circuit is:

Receiving a first conditional instruction associated with a prediction; and

A method is configured to select one of a plurality of execution pipelines to execute a first conditional instruction based on a prediction of the first conditional instruction, wherein the plurality of execution pipelines include a first execution pipeline and a second execution pipeline providing different latencies for processing mispredicted conditional instructions; and

The first execution pipeline is:

In response to receiving the first conditional command,

Execute the first conditional instruction;

determines that the prediction of the first conditional instruction is a prediction error; and

A system configured to cause the first conditional instruction to be executed in a second execution pipeline in response to determining that the prediction of the first conditional instruction is a misprediction.

20. In item 19, the second execution pipeline,

Execute the first conditional instruction;

determines that the prediction of the first conditional instruction is a prediction error; and

A system configured to, in response to determining that a prediction of a first conditional instruction is a misprediction, cause an instruction to be obtained from a target address of the first conditional instruction for execution.

Once the above disclosure is fully understood, various modifications and variations will become apparent to those skilled in the art. It is intended that the following claims be interpreted to encompass all such modifications and variations.

Claims (20)

As a processor,
A fetch and decode circuit is included, wherein the fetch and decode circuit comprises:
A bias prediction circuit configured to provide a bias prediction of whether a condition of a conditional instruction is biased true or biased false, wherein the bias prediction of biased true or biased false indicates that the bias prediction circuit predicts that the condition of the conditional instruction is always true or always false; and
An instruction prediction circuit configured to provide an instruction prediction of whether the condition of the conditional instruction is true or false,
The above fetch and decode circuit,
In response to a bias prediction that the condition of the conditional instruction is biased true or biased false, the bias prediction from the bias prediction circuit is configured to determine a target address of the conditional instruction, and
A processor wherein the bias prediction from the bias prediction circuit and the instruction prediction from the instruction prediction circuit are provided at different stages of processing of the conditional instruction in the fetch and decode circuit. In the first paragraph, to provide the bias prediction, the bias prediction circuit,
Identifying a value in the bias table based on the address of the above conditional instruction; and
A processor configured to provide said bias prediction based on said identified value of said conditional instruction within said bias table. In the second paragraph, the value for the conditional instruction in the bias table is,
A first value indicating that no conditional instruction corresponding to an entry of said value in said bias table has been encountered by said bias prediction circuit;
A second value indicating that the condition of the above conditional instruction is biased false;
a third value indicating that the condition of the above conditional instruction is biased true; and
A fourth value indicating that the condition of the above conditional instruction is unbiased.
A processor, one of multiple values including . In the third aspect, the processor, wherein the value for the conditional instruction in the bias table is set from the first value to the second or third value when (a) execution of the conditional branch indicates that the condition of the conditional instruction is true or false, respectively, or (b) set from the second or third value to the fourth value when the execution of the conditional instruction indicates that the value for the conditional instruction in the bias table mismatches the result of the execution of the conditional instruction. In the first paragraph, the fetch and decode circuit,
A processor further configured to determine the target address of the conditional instruction using the instruction prediction from the instruction prediction circuit, in response to a bias prediction that the condition of the conditional instruction is neither biased true nor biased false. In the first paragraph, the fetch and decode circuit,
A processor further configured to cause the conditional instruction to be recoded into a non-conditional instruction in response to the bias prediction that the condition of the conditional instruction is biased true or biased false. A processor in accordance with claim 1, wherein the bias prediction circuit is configured to provide the bias prediction in a first stage corresponding to loading the conditional instruction into a cache of the processor, and the instruction prediction circuit is configured to provide the instruction prediction in a second stage corresponding to fetching the conditional instruction from the cache. A processor in accordance with claim 1, wherein the instruction prediction circuit comprises at least a first table and a second table, the first table being indexed based on addresses of conditional instructions, and the second table being indexed based on the addresses and a prediction history of the conditional instructions. A processor in accordance with claim 8, wherein the bias table of the bias prediction circuit and the first table of the instruction prediction circuit are indexed based on the addresses of the conditional instructions using different hash functions. In the first paragraph,
A processor further comprising an instruction distribution circuit configured to distribute the conditional instruction to one of the different execution pipelines based on at least one of (a) the bias prediction from the bias prediction circuit or (b) the instruction prediction from the instruction prediction circuit. As a method,
A step of providing a bias prediction of whether a condition of a conditional instruction is biased true or biased false, using a bias prediction circuit of a fetch and decode circuit of a processor, wherein the bias prediction of biased true or biased false indicates that the condition of the conditional instruction is predicted to be always true or always false;
A step of providing an instruction prediction of whether the condition of the conditional instruction is true or false by using the instruction prediction circuit of the above fetch and decode circuit; and
In response to a bias prediction that the condition of the conditional instruction is biased false or biased true, a step of determining a target address of the conditional instruction using the bias prediction from the bias prediction circuit,
A method wherein said bias prediction and said instruction prediction are provided at different stages of processing said conditional instruction using said fetch and decode circuitry. In the 11th paragraph, the step of providing the bias prediction of whether the condition of the conditional instruction is biased true or biased false,
A step of identifying a value in a bias table based on the address of the conditional instruction; and
A method comprising the step of providing the prediction based on the identified value of the conditional instruction within the bias table. In the 12th paragraph, the value for the conditional instruction in the bias table is,
A first value indicating that no conditional instruction corresponding to an entry of said value in said bias table has been encountered by said bias prediction circuit;
A second value indicating that the condition of the above conditional instruction is biased false;
a third value indicating that the condition of the above conditional instruction is biased true; and
A fourth value indicating that the condition of the above conditional instruction is unbiased.
A method, wherein one of a plurality of values including . In Article 13,
A method comprising the step of changing the value for the conditional instruction in the biased table from the first value to the second or third value when (a) execution of the conditional branch indicates that the condition of the conditional instruction is true or false, respectively, or (b) changing the value for the conditional instruction in the biased table from the second or third value to the fourth value when the execution of the conditional instruction indicates that the value mismatches the result of the execution of the conditional instruction. In Article 11,
A step of detecting saturation of the above bias table; and
A method comprising: in response to detecting said saturation of said bias table, changing at least one value in said bias table from said fourth value to said first value. In Article 11,
A method further comprising: determining a target address of the conditional instruction using the instruction prediction from the instruction prediction circuit, in response to a bias prediction that the condition of the conditional instruction is neither biased true nor biased false. A method according to claim 11, wherein the step of providing the bias prediction is performed in a first stage corresponding to loading the conditional instruction into a cache of the processor, and the step of providing the instruction prediction is performed in a second stage corresponding to fetching the conditional instruction from the cache. In the 11th paragraph, the first table includes a value corresponding to the conditional command, and the value in the first table is,
A first value indicating that the condition of the above conditional instruction is strongly false;
A second value indicating that the condition of the above conditional instruction is weakly false;
a third value indicating that the condition of the above conditional instruction is weakly true; and
A fourth value indicating that the above condition of the above conditional command is strongly true.
A method, wherein one of a plurality of values including . As a system,
comprising one or more processors, wherein the one or more processors individually:
A fetch and decode circuit is included, wherein the fetch and decode circuit comprises:
A bias prediction circuit configured to provide a bias prediction of whether a condition of a conditional instruction is biased true or biased false, wherein the bias prediction of biased true or biased false indicates that the bias prediction circuit predicts that the condition of the conditional instruction is always true or always false; and
An instruction prediction circuit configured to provide an instruction prediction of whether the condition of the conditional instruction is true or false,
The above fetch and decode circuit,
In response to a bias prediction that the condition of the conditional instruction is biased true or biased false, the bias prediction from the bias prediction circuit is configured to determine a target address of the conditional instruction, and
The system wherein the bias prediction and the instruction prediction are provided at different stages of processing the conditional instruction in the fetch and decode circuit. In the 19th paragraph, to provide the bias prediction, the bias prediction circuit,
Identifying a value in the bias table based on the address of the above conditional instruction; and
configured to provide the bias prediction based on the identified value of the conditional instruction in the bias table,
The above values for the above conditional instructions in the above bias table are,
A first value indicating that no conditional instruction corresponding to an entry of said value in said bias table has been encountered by said bias prediction circuit;
A second value indicating that the condition of the above conditional instruction is biased false;
a third value indicating that the condition of the above conditional instruction is biased true; and
A fourth value indicating that the condition of the above conditional instruction is unbiased.
A system, one of multiple values including .

Images