System, apparatus and method for controlling allocations into a branch prediction circuit of a processor

In one embodiment, a branch prediction circuit includes: a first bimodal predictor having a first plurality of entries each to store first prediction information for a corresponding branch instruction; a global predictor having a plurality of global entries each to store global prediction information for a corresponding branch instruction; a second bimodal predictor having a second plurality of entries each to store second prediction information for a corresponding branch instruction; a monitoring table having a plurality of monitoring entries each to store a counter value based on the second prediction information for a corresponding branch instruction; and a control circuit to allocate a global entry within the global predictor based at least in part on the counter value of a monitoring entry of the monitoring table for a corresponding branch instruction. Other embodiments are described and claimed.

TECHNICAL FIELD

Embodiments relate to performing branch prediction in a processor.

BACKGROUND

Branch prediction is used to enhance performance in wide, super-scalar processors. Conventional branch predictors use both local and global branch history components. The local predictor makes a direction prediction for a branch instruction (using an instruction pointer (IP) of the instruction) based only on the IPs behavior in the recent past. The global predictor, on the other hand, makes a direction prediction for the branch instruction based on the behavior of all the recently executed branch instructions in the program. However, these different predictors contend for resources.

DETAILED DESCRIPTION

In various embodiments, a branch predictor of a processor or other system on chip (SoC) may be implemented with multiple independent branch predictors. These independent branch predictors include a local predictor and one or more global predictors. With these two predictors, a prediction may be provided for every branch in the program. That is, the local predictor, implemented as a bimodal predictor, provides a prediction for every branch instruction, while the global predictors provide a prediction only if there is a global entry (g-entry) corresponding to the branch instruction.

Still further, techniques are provided to use an additional branch prediction structure, referred to herein as a shadow or replica local branch predictor, to aid in determination of when it is appropriate (or not) to allocate resources of the global predictor for a particular branch instruction. Embodiments may dynamically (using an online mechanism) identify instruction pointers (IPs) to filter and offload onto the local predictor. By “offloading” predictions, it is meant that for certain branch instructions, no allocation is made into the global predictor. That is, a typical scenario is for there to be contention for resources of the global branch predictor. Using information from this shadow local branch predictor and an additional history or monitoring structure, conservative decisions may be made to limit allocations into the global branch predictor. By providing an online technique to identify branch IPs that perform sufficiently well with predictions solely from the local branch predictor, global predictor allocations for such branch IPs is reduced.

Referring now toFIG. 1, shown is a block diagram of a prediction circuit in accordance with an embodiment of the present invention. More specifically, prediction circuit100is a branch predictor having multiple independent prediction circuits or units. As such, prediction circuit100is implemented as a hybrid predictor that includes both local and global predictors. Further, additional prediction structures may be provided to direct more predictions to be made using a local predictor, rather than a global predictor, offloading consumption of resources of the global predictor. This may enhance performance, as in embodiments a global predictor may consume greater storage and computation resources than a local predictor. With an embodiment, more prediction decisions can be made by leveraging information from the local predictor only, reducing resource contention in the global predictor.

As illustrated inFIG. 1, prediction circuit100includes a local predictor120. In the embodiment shown, local predictor120may be implemented as a bimodal predictor. In an embodiment, bimodal predictor120may include a plurality of entries each associated with a given instruction address (namely an instruction pointer (IP) address) and having a corresponding count value associated therewith. In an embodiment, local bimodal predictor120may be implemented as an extension of a target array (TA). In this embodiment, each bimodal entry includes a 2-bit counter. In turn, each of the entries of the TA may be extended with a bit to store the bimodal prediction (namely the most significant bit (MSB) of the bimodal counter). In an embodiment, the lower bits of the bimodal predictor entries may be tracked in a separate, IP-indexed, structure. In a particular embodiment bimodal predictor120may be an IP-hashed structure that maps into a set of counters in which a most significant bit (MSB) provides the direction prediction.

In addition, a set of global predictors130is present. In embodiments, global predictors130may provide for global predictions, namely predictions based on multiple recently executed branch instructions. Global predictors130may be implemented as a set of tables. Although the scope of the present invention is not limited in this regard, in embodiments there may be a plurality of such global tables, e.g., global tables g0-g6. Of course different numbers of global tables may be provided in other embodiments. Each such global table may be associated with a different granularity or range of history of branch instructions, such that the first global table (e.g., g0) is associated with a shortest history duration, which as an example may be on the order of between 5 and 15 branches. The higher global tables may be associated with longer history periods, e.g., ranging from approximately 100 to 200 branches.

As further shown, an additional predictor110is present within prediction circuit100. More specifically, predictor110may be implemented as a shadow bimodal predictor. In embodiments, shadow bimodal predictor110may be used in determining when it is appropriate to allocate an entry within global predictors130for a given branch instruction. Shadow bimodal predictor110may be implemented similarly to bimodal predictor120. In a particular embodiment, shadow bimodal predictor110may be implemented similarly as local predictor120, with the TA entries extended with a shadow bimodal prediction bit, and a separate, IP-indexed structure for the lower bits of the shadow predictor. In embodiments, shadow predictor110may be used to help identify and learn the branch instructions that see an improvement in performance by using predictions solely from bimodal predictor120.

In an embodiment, shadow bimodal predictor110provides a prediction for every branch instruction and a corresponding counter of the predictor may be updated at every branch execution. In contrast, bimodal predictor120and global predictor130may be updated only when a final prediction output decision from the branch predictor originates from the given predictor. Stated another way, only a predictor responsible for a given prediction is updated based on the result of that prediction (either correct or mispredicted).

As further illustrated inFIG. 1, prediction circuit100is implemented as a hybrid prediction structure. As seen, predictions output by local predictor120and global predictors130may be provided to a selection circuit140which, in an embodiment may be implemented as a multiplexer. In embodiments, selection circuit140may output a final prediction decision based on the predictions from these two predictors (when predictions for a corresponding IP are present therein).

Still with reference toFIG. 1, prediction circuit100further includes a monitoring table150and a comparator160. In embodiments herein, comparator160is configured to receive feedback information, e.g., from an execution unit that indicates whether a given prediction output from selection circuit140is correct or not. That is, comparator160receives feedback information that includes indications of correct predictions and mispredictions. Based at least in part on this feedback information and a corresponding prediction from shadow bimodal predictor110, comparator160may cause a probabilistic update to a corresponding entry within monitoring table150associated with a given branch instruction. And, based upon information in a given entry within monitoring table150, an allocation may be made to one or more tables within global predictors130.

In an embodiment, monitoring table (MT)150thus may be used to help keep track of the performance of shadow bimodal predictor110. In an embodiment, each MT entry includes a saturating counter that keeps track of the number of dynamic executions of a corresponding branch instruction since the last misprediction by shadow bimodal predictor110. The resulting count values within these MT entries in turn may be used to indicate whether or not an entry for a given branch instruction is to be allocated (or attempted to be allocated) into one or more tables of global predictor130. If the performance of shadow bimodal predictor110for a given branch instruction has been shown to be above a given threshold, an allocation within global predictor130for that IP may be mitigated by allocating entries probabilistically. In an embodiment, allocations may be prevented only to the g4 and g5 tables, as these tables typically see the most allocation pressure, thus reducing contention for space in these tables.

Understand while shown at this high level in the embodiment ofFIG. 1, many variations and alternatives are possible. Note that in embodiments, the feedback information received from the execution circuit of the processor may further be used to update prediction information in one or more of the predictors. More specifically in an embodiment, this feedback information may be used to update the corresponding predictor that provided the prediction output from selection circuit140. In addition, for every branch execution, shadow bimodal predictor110may be updated.

FIG. 2Ais a block diagram illustrating an in-order pipeline and a register renaming stage, out-of-order issue/execution pipeline according to at least one embodiment of the invention.FIG. 2Bis a block diagram illustrating an in-order architecture core and a register renaming logic, out-of-order issue/execution logic to be included in a processor according to at least one embodiment of the invention. The solid lined boxes inFIG. 2Aillustrate the in-order pipeline, while the dashed lined boxes illustrate the register renaming, out-of-order issue/execution pipeline. Similarly, the solid lined boxes inFIG. 2Billustrate the in-order architecture logic, while the dashed lined boxes illustrate the register renaming logic and out-of-order issue/execution logic.

InFIG. 2A, a processor pipeline200includes a fetch stage202which may include a branch predictor as described herein, a length decode stage204, a decode stage206, an allocation stage208, a renaming stage210, a scheduling (also known as a dispatch or issue) stage212, a register read/memory read stage214, an execute stage216, a write back/memory write stage218, an exception handling stage222, and a commit stage224.

InFIG. 2B, arrows denote a coupling between two or more circuits and the direction of the arrow indicates a direction of data flow between those circuits.FIG. 2Bshows a processor core290including a front end circuit230coupled to an execution engine circuit250, and both are coupled to a memory circuit270.

The core290may be a reduced instruction set computing (RISC) core, a complex instruction set computing (CISC) core, a very long instruction word (VLIW) core, or a hybrid or alternative core type. As yet another option, the core290may be a special-purpose core, such as, for example, a network or communication core, compression engine, graphics core, or the like.

The front end circuit230includes a branch prediction circuit232coupled to an instruction cache circuit234, which is coupled to an instruction translation lookaside buffer (TLB)236, which is coupled to an instruction fetch circuit238, which is coupled to a decode circuit240. Branch prediction circuit232may be implemented as described herein (e.g., as inFIG. 1) including local and global predictors and a shadow predictor to more effectively allocate entries into the global predictor, by leveraging the local predictor when it is determined that good prediction accuracy is achieved with use of the local predictor alone.

Decode circuit240may decode instructions, and generate as an output one or more micro-operations, micro-code entry points, micro-instructions, other instructions, or other control signals, which are decoded from, or which otherwise reflect, or are derived from, the original instructions. The decoder may be implemented using various different mechanisms. Examples of suitable mechanisms include, but are not limited to, look-up tables, hardware implementations, programmable logic arrays (PLAs), microcode read only memories (ROMs), etc. Instruction cache circuit234is further coupled to a level 2 (L2) cache circuit276in the memory circuit270. Decode circuit240is coupled to a rename/allocator circuit252in the execution engine circuit250.

Execution engine circuit250includes the rename/allocator circuit252coupled to a retirement circuit254and a set of one or more scheduler circuit(s)256. The scheduler circuit(s)256represents any number of different schedulers, including reservations stations, central instruction window, etc. The scheduler circuit(s)256is coupled to the physical register files258. Each of the physical register files258represents one or more physical register files, different ones of which store one or more different data types, such as scalar integer, scalar floating point, packed integer, packed floating point, vector integer, vector floating point, etc., status (e.g., an instruction pointer that is the address of the next instruction to be executed), etc. The physical register files258are overlapped by the retirement circuit254to illustrate various ways in which register renaming and out-of-order execution may be implemented (e.g., using a reorder buffer(s) and a retirement register file(s), using a future file(s), a history buffer(s), and a retirement register file(s); using a register map and a pool of registers, etc.).

Generally, the architectural registers are visible from the outside of the processor or from a programmer's perspective. The registers are not limited to any known particular type of circuit. Various different types of registers are suitable as long as they are capable of storing and providing data as described herein. Examples of suitable registers include, but are not limited to, dedicated physical registers, dynamically allocated physical registers using register renaming, combinations of dedicated and dynamically allocated physical registers, etc.

The retirement circuit254and the physical register files258are coupled to the execution cluster(s)260. The execution cluster(s)260includes a set of one or more execution circuits262and a set of one or more memory access circuits264. The execution circuit262may perform various operations (e.g., shifts, addition, subtraction, multiplication) and on various types of data (e.g., scalar floating point, packed integer, packed floating point, vector integer, vector floating point). While some embodiments may include a number of execution units dedicated to specific functions or sets of functions, other embodiments may include only one execution unit or multiple execution units that all perform all functions. The scheduler circuit(s)256, physical register files258, and execution cluster(s)260are shown as being possibly plural because certain embodiments create separate pipelines for certain types of data/operations (e.g., a scalar integer pipeline, a scalar floating point/packed integer/packed floating point/vector integer/vector floating point pipeline, and/or a memory access pipeline that each have their own scheduler unit, physical register file(s), and/or execution cluster—and in the case of a separate memory access pipeline, certain embodiments are implemented in which only the execution cluster of this pipeline has the memory access circuit(s)264). It should also be understood that where separate pipelines are used, one or more of these pipelines may be out-of-order issue/execution and the rest in-order. As illustrated, feedback information may be provided from execution engine circuit250to branch prediction circuit232to provide feedback information, indicating whether branch instructions were correctly predicted or mispredicted, so that updating of prediction information can occur as described herein.

The set of memory access circuits264is coupled to the memory circuit270, which includes a data TLB circuit272coupled to a data cache circuit274coupled to a level 2 (L2) cache circuit276. In one exemplary embodiment, the memory access circuits264may include a load unit, a store address unit, and a store data unit, each of which is coupled to the data TLB circuit272in the memory circuit270. The L2 cache circuit276is coupled to one or more other levels of cache and eventually to a main memory.

With reference back toFIG. 2A, by way of example, the exemplary register renaming, out-of-order issue/execution core architecture may implement the pipeline200as follows: 1) the instruction fetch circuit238performs the fetch and length decoding stages202and204; 2) the decode circuit240performs the decode stage206; 3) the rename/allocator circuit252performs the allocation stage208and renaming stage210; 4) the scheduler circuit(s)256performs the schedule stage212; 5) the physical register files258and the memory circuit270perform the register read/memory read stage214; the execution cluster260performs the execute stage216; 6) the memory circuit270and the physical register files258perform the write back/memory write stage218; 7) various circuits may be involved in the exception handling stage222; and 8) the retirement circuit254and the physical register files258perform the commit stage224.

Core290may support one or more instructions sets (e.g., the ×86 instruction set (with some extensions that have been added with newer versions); the MIPS instruction set of MIPS Technologies of Sunnyvale, Calif.; the ARM instruction set (with optional additional extensions such as NEON) of ARM Holdings of Sunnyvale, Calif.); or possible other ISAs. It should be understood that core290may support multithreading (executing two or more parallel sets of operations or threads), and may do so in a variety of ways including time sliced multithreading, simultaneous multithreading (where a single physical core provides a logical core for each of the threads that physical core is simultaneously multithreading), or a combination thereof (e.g., time sliced fetching and decoding and simultaneous multithreading thereafter such as in the Intel® Hyperthreading technology).

FIG. 3is a block diagram of a processor300with integrated memory controller and accelerator functionality according to embodiments. The solid lined boxes inFIG. 3illustrate a processor300with a single core302, a single accelerator308A, a system agent unit310, a set of one or more bus controller units316, while the optional addition of the dashed lined boxes illustrates an alternative processor300with multiple accelerators308B-N, and a set of one or more integrated memory controller unit(s)314in the system agent unit310. At least core302may include a branch prediction circuit as described herein.

The memory hierarchy includes one or more levels of cache within the core302including a cache unit304, a set or one or more shared cache units306, and external memory (not shown) coupled to the set of integrated memory controller units314. The set of shared cache units306may include one or more mid-level caches, such as level 2 (L2), level 3 (L3), level 4 (L4), or other levels of cache, a last level cache (LLC), and/or combinations thereof. While in one embodiment a ring-based interconnect unit312interconnects the accelerator(s)308, the set of shared cache units306, and the system agent unit310, alternative embodiments may use any number of well-known techniques for interconnecting such units.

The system agent unit310includes those components coordinating and operating core302and accelerator(s)308A-N. The system agent unit310may include for example a power control unit (PCU) and a display unit (not shown). The PCU may be or include logic and components to regulate the power state of the core302and accelerator(s)308A-N. The display unit is for driving one or more externally connected displays.

While a single core embodiment is shown for ease of illustration, understand that multiple cores may be present. Such cores may be homogenous or heterogeneous in terms of architecture and/or instruction set. For example, some of the cores may be in-order while others are out-of-order. As another example, two or more of the cores may be capable of execution the same instruction set, while others may be capable of executing only a subset of that instruction set or a different instruction set.

The processor may be a general-purpose processor, such as a Core™ i3, i5, i7, 2 Duo and Quad, Xeon™, Itanium™, XScale™ or StrongARM™ processor, which are available from Intel Corporation, of Santa Clara, Calif. Alternatively, the processor may be from another company, such as ARM Holdings, Ltd, MIPS, etc. The processor may be a special-purpose processor, such as, for example, a network or communication processor, compression engine, graphics processor, co-processor, embedded processor, or the like. The processor may be implemented on one or more chips. The processor300may be a part of and/or may be implemented on one or more substrates using any of a number of process technologies, such as, for example, BiCMOS, CMOS, or NMOS.

Referring now toFIG. 4, shown is a block diagram of a micro-architecture of a processor core in accordance with one embodiment of the present invention. As shown inFIG. 4, processor core400may be a multi-stage pipelined out-of-order processor.

As seen inFIG. 4, core400includes front end units410, which may be used to fetch instructions to be executed and prepare them for use later in the processor pipeline. For example, front end units410may include a fetch unit401, an instruction cache403, and an instruction decoder405. Front end units410may further include a branch prediction unit404, implemented as described herein. The resulting branch decision information can be provided to fetch unit401to direct the next IP to be fetched to obtain instructions for execution within processor400. As further illustrated, feedback information may be received by branch prediction unit404to indicate whether corresponding branch predictions were correctly predicted or mispredicted. Such information may be provided from corresponding execution units420, described further below. In some implementations, front end units410may further include a trace cache, along with microcode storage as well as a micro-operation storage. Fetch unit401may fetch macro-instructions, e.g., from memory or instruction cache403, and feed them to instruction decoder405to decode them into primitives, i.e., micro-operations for execution by the processor.

Coupled between front end units410and execution units420is an out-of-order (OOO) engine415that may be used to receive the micro-instructions and prepare them for execution. More specifically OOO engine415may include various buffers to re-order micro-instruction flow and allocate various resources needed for execution, as well as to provide renaming of logical registers onto storage locations within various register files such as register file430and extended register file435. Register file430may include separate register files for integer and floating point operations. Extended register file435may provide storage for vector-sized units, e.g., 256 or 512 bits per register. As further illustrated inFIG. 4, core400also includes a set of configuration registers436, which may include various configuration registers to configure modes of operation and execution within core400.

Various resources may be present in execution units420, including, for example, various integer, floating point, and single instruction multiple data (SIMD) logic units, among other specialized hardware. For example, such execution units may include one or more arithmetic logic units (ALUs)422and one or more vector execution units424, among other such execution units.

Results from the execution units may be provided to retirement logic, namely a reorder buffer (ROB)440. More specifically, ROB440may include various arrays and logic to receive information associated with instructions that are executed. This information is then examined by ROB440to determine whether the instructions can be validly retired and result data committed to the architectural state of the processor, or whether one or more exceptions occurred that prevent a proper retirement of the instructions. Of course, ROB440may handle other operations associated with retirement.

As shown inFIG. 4, ROB440is coupled to a cache460which, in one embodiment may be a low level cache (e.g., an L1 cache), although the scope of the present invention is not limited in this regard. As further shown inFIG. 4, execution units420can be directly coupled to cache460. From cache460, data communication may occur with higher level caches, system memory and so forth. While shown with this high level in the embodiment ofFIG. 4, understand the scope of the present invention is not limited in this regard. For example, while the implementation ofFIG. 4is with regard to an out-of-order machine such as of an Intel® x86 ISA, the scope of the present invention is not limited in this regard. That is, other embodiments may be implemented in an in-order processor, a reduced instruction set computing (RISC) processor such as an ARM-based processor, or a processor of another type of ISA that can emulate instructions and operations of a different ISA via an emulation engine and associated logic circuitry.

In one embodiment, the following actions are taken on every branch execution: (1) update the shadow bimodal predictor based on the branch's resolved direction; and (2) update the MT entry counter corresponding to the branch IP. The monitoring table entry counter is set probabilistically if the shadow bimodal predictor was correct, and is reset on a shadow bimodal misprediction.

Referring now toFIG. 5, shown is a flow diagram of a method in accordance with an embodiment of the present invention. More specifically, method500is a flow diagram of a method for updating a monitoring table in accordance with an embodiment. As such, method500may be performed by hardware circuitry, software, firmware and/or combinations thereof. In one particular embodiment, method500may be performed at least in part by circuitry within comparator160ofFIG. 1. As seen, method500begins in response to branch execution in an execution circuit of the processor. More specifically, the execution circuit may provide feedback information regarding prediction correctness or misprediction to the comparator (block505). In turn at diamond510the comparator may determine whether the shadow bimodal prediction for this branch execution was correct. In an embodiment, this determination may be made within comparator160ofFIG. 1based on the prediction received from shadow bimodal predictor110, as compared to the feedback information from the execution circuit. If it is determined that the shadow bimodal prediction is correct, control passes to block520.

As illustrated, at block520a counter of the monitoring table entry associated with this branch execution may be updated probabilistically. That is, in embodiments rather than deterministically updating the counter in response to a correct prediction, a probabilistic update to the counter occurs. Although the scope of the present invention is not limited in this regard in an embodiment, this probabilistic counter update may occur once per every 256 attempts. To this end, a comparator or other control circuit may include pseudo-random number generation logic to determine whether to update the counter. Furthermore, while this example uses a probabilistic determination with a ratio of 1:256, understand the scope of the present invention is not limited in this aspect and other probabilities may be used. And in an embodiment in which the monitoring table entries include a saturating counter, the probabilistic update (when it actually occurs) may be by way of setting the counter value to its saturation value (e.g., setting a single bit in the instance of a one-bit saturating counter). This saturating counter may saturate at a maximum value and not wrap around on a further increment. In other cases, the counter may include multiple bits and may be a saturating or non-saturating counter, such that the update is by way of an increment of the counter.

Still with reference toFIG. 5, instead if it is determined that the shadow bimodal prediction is not correct, control passes to block530where the monitoring table counter for the entry associated with the branch execution is reset. Understand while shown at this high level in the embodiment ofFIG. 5, many variations and alternatives are possible. For example, where the monitoring table counter is multi-bit width, instead of resetting the counter, a decrement of the counter value may occur in response to a misprediction by the shadow bimodal predictor.

In an embodiment, the following actions are taken when a determination is made, e.g., in response to a misprediction, that a new g-table entry is to be allocated for a particular branch: (1) if the corresponding MT saturating counter is at its maximum value, then a new g-table entry is not allocated; and (2) if the corresponding MT saturating counter is not at its maximum value, allocation of a g-table entry may be attempted. That is, when the corresponding entry of the monitoring table indicates that the shadow bimodal predictor sufficiently correctly predicts the branch instruction (and thus by replica the local predictor also sufficiently correctly predicts branch direction), future predictions may adequately be made using the local prediction resources only, saving the expense of allocating one or more global prediction entries for the given branch instruction.

Referring now toFIG. 6, shown is a flow diagram of a method in accordance with another embodiment of the present invention. More specifically, method600ofFIG. 6is a method for allocating entries within a global predictor. As such, method600may be performed by hardware circuitry, software, firmware and/or combinations thereof, such as a control circuit, which may be implemented within a comparator (as discussed above), within a monitoring table, within the global predictor or a separate controller (or combinations thereof). As illustrated, method600, which may be performed at least in part by control logic of a monitoring table, begins with a determination of allocation of a new entry within one or more global tables (block605). In embodiments, this determination of a new global table entry may be in response to at least one misprediction by a local or global predictor. In an embodiment, if a g-table gave the prediction and a misprediction occurred, then allocation may be attempted only in the higher g-tables. As seen, control next passes to diamond610to determine whether a counter of the corresponding entry of the monitoring table associated with this (mispredicted) branch instruction is set. If the entry counter is set, control passes to block620where no entry is allocated within entries of the global predictor. That is, while a misprediction may have been incurred due to a misprediction within the local predictor, by way of the strength of the information present in the monitoring table (which in turn is derived based on the shadow bimodal predictor), a new entry is not allocated within the global predictor.

Instead if it is determined that the monitoring table counter for the corresponding entry is not set, control passes to block630where a new entry within one or more global tables may be allocated. Understand while described as an actual allocation, in many embodiments, the actual operation at block330initially may be communication of an allocation signal, e.g., from the monitoring table to the global predictor. In turn the global predictor itself may make a final determination as to whether an entry is to be allocated. Stated another way, an allocation determination may occur within the global predictor, such that an actual allocation may not occur where a victim entry (which may be selected randomly) is determined to include useful prediction information. In one embodiment, each g-table entry has a useful counter to track its usefulness. A g-table entry is deemed useful if it is the g-table entry with the shortest history length that gives the right prediction for that IP instance, and thus may have its useful counter updated. As such, in these embodiments block630instead may proceed by attempting to allocate a new entry within one or more global tables. However, depending upon the determination of control logic within the global predictor, this allocation may or may not successfully complete. Understand while shown at this high level in the embodiment ofFIG. 6, many variations and alternatives are possible.

Referring now toFIG. 7, shown is a flow diagram of a method in accordance with another embodiment of the present invention. More specifically, method700shown inFIG. 7is a method for execution of instructions in a processor using a branch predictor as described herein. As such, method700may be performed by various hardware circuitry, firmware and/or software of the processor, including a branch predictor as described herein, execution of circuitry and so forth.

As illustrated, method700begins by receiving a branch instruction in the branch prediction circuit (block710). Based on this branch instruction, local and global predictions for the instruction pointer address associated with this branch instruction may be obtained and provided to a selection circuit (block720). Understand that in embodiments as above, these local predictions may be a local branch predictor implemented as a bimodal predictor and the global predictor may be implemented as one or more global tables. Next at block730a final prediction may be selected based on at least one of these two predictions. In some embodiments, assuming that there is a global prediction for the corresponding branch instruction, the selection circuit may select this global prediction (namely the highest available global component) as the final prediction output. In other cases, other manners of determining a prediction based on both local and global predictions may occur. For example, a majority voting scenario or a weighted average based on the confidence of every predicting component may occur, or so forth. In any event, the resulting final prediction is sent to fetch or other front end circuitry of the processor such that an instruction associated with the direction of prediction can be obtained and provided to execution circuitry of the processor. As such, control next passes to block740where the instruction associated with the prediction direction can be executed. Understand that further operations with regard to the execution, including determining whether the predicted direction was correct may occur. Control next passes to block750where feedback information may be sent (e.g., from an execution circuit) to the branch prediction circuit regarding the prediction. This feedback information indicates whether the corresponding prediction was correct or was a misprediction.

Still with reference toFIG. 7, at block760the shadow predictor and at least one or more of the local and global predictors may be updated based on this feedback information. For example, assuming a correct prediction, the entries of the shadow predictor and the given one of the local and global predictors that provided the prediction may be updated by way of an increment of the counter value of the entries. And similarly, on a misprediction, such entries may be decremented or reset.

Still with reference toFIG. 7, note that the received branch instruction also may trigger the obtaining of a prediction from the shadow predictor (block770). Note that this shadow predictor prediction is not used in generating a final prediction output. Instead, this prediction may be used as a replica to indicate accuracy of the local predictor. As seen, control next passes to diamond780to determine whether the shadow predictor correctly predicted branch direction. If so, control passes to block790where a corresponding entry of a monitoring table of the branch prediction circuit may be updated in a first direction (e.g., the counter of the given entry may be incremented or otherwise set). Instead, upon a misprediction by the shadow predictor, control passes to block785where the entry of the monitoring table may be updated in a second direction (e.g., a decrement or reset of the counter). As discussed above, the value of the counter in entries in the monitoring table may be used to identify when it is appropriate to allocate an entry into the global predictor, such as upon a misprediction event for the local predictor. Understand while shown at this high level in the embodiment ofFIG. 7, many variations and alternatives are possible.

Embodiments may be implemented in many different system types, ranging from small portable devices to large server systems and device types in between. Referring now toFIG. 8, shown is a block diagram of an example system with which embodiments can be used. As seen, system800may be a smartphone or other wireless communicator or any other Internet of Things (IoT) device. A baseband processor805is configured to perform various signal processing with regard to communication signals to be transmitted from or received by the system. In turn, baseband processor805is coupled to an application processor810, which may be a main CPU of the system to execute an OS and other system software, in addition to user applications such as many well-known social media and multimedia applications. Application processor810may further be configured to perform a variety of other computing operations for the device. In embodiments, application processor810may include a branch predictor as described herein. More specifically, the branch predictor may leverage information from a shadow predictor and, based at least in part on a determination of accuracy of predictions made solely using the local branch predictor, constrain allocations into a global predictor as described herein.

In turn, application processor810can couple to a user interface/display820, e.g., a touch screen display. In addition, application processor810may couple to a memory system including a non-volatile memory, namely a flash memory830and a system memory, namely a DRAM835. As further seen, application processor810also couples to a capture device845such as one or more image capture devices that can record video and/or still images.

Still referring toFIG. 8, a universal integrated circuit card (UICC)840comprises a subscriber identity module, which in some embodiments includes a secure storage842to store secure user information. System800may further include a security processor850that may implement a trusted executed environment (TEE), and which may couple to application processor810.

A plurality of sensors825, including one or more multi-axis accelerometers may couple to application processor810to enable input of a variety of sensed information such as motion and other environmental information. In addition, one or more authentication devices895may be used to receive, e.g., user biometric input for use in authentication operations. As further illustrated, a near field communication (NFC) contactless interface860is provided that communicates in a NFC near field via an NFC antenna865. While separate antennae are shown inFIG. 8, understand that in some implementations one antenna or a different set of antennae may be provided to enable various wireless functionality.

A power management integrated circuit (PMIC)815couples to application processor810to perform platform level power management. To this end, PMIC815may issue power management requests to application processor810to enter certain low power states as desired. Furthermore, based on platform constraints, PMIC815may also control the power level of other components of system800.

To enable communications to be transmitted and received such as in one or more wireless networks, various circuitry may be coupled between baseband processor805and an antenna890. Specifically, a radio frequency (RF) transceiver870and a wireless local area network (WLAN) transceiver875may be present. In general, RF transceiver870may be used to receive and transmit wireless data and calls according to a given wireless communication protocol such as 3G or 4G wireless communication protocol such as in accordance with a code division multiple access (CDMA), global system for mobile communication (GSM), long term evolution (LTE) or other protocol. In addition a GPS sensor880may be present. Other wireless communications such as receipt or transmission of radio signals, e.g., AM/FM and other signals may also be provided. In addition, via WLAN transceiver875, local wireless communications, such as according to a Bluetooth™ or IEEE 802.11 standard can also be realized.

Referring now toFIG. 9, shown is a block diagram of a system in accordance with another embodiment of the present invention. As shown inFIG. 9, multiprocessor system900is a point-to-point interconnect system such as a server system, and includes a first processor970and a second processor980coupled via a point-to-point interconnect950. As shown inFIG. 9, each of processors970and980may be multicore processors such as SoCs, including first and second processor cores (i.e., processor cores974aand974band processor cores984aand984b), although potentially many more cores may be present in the processors. The various processor cores of processors970and980may include branch predictors as described herein. Such branch predictors may include local and global predictors, as well as at least one shadow or replica predictor to maintain information regarding accuracy of predictions made by the local predictor. Based at least in part on such information, allocations into the global predictor may be constrained or limited, freeing resource allocation within the global predictor, as described herein.

Still referring toFIG. 9, first processor970further includes a memory controller hub (MCH)972and point-to-point (P-P) interfaces976and978. Similarly, second processor980includes a MCH982and P-P interfaces986and988. As shown inFIG. 9, MCH's972and982couple the processors to respective memories, namely a memory932and a memory934, which may be portions of main memory (e.g., a DRAM) locally attached to the respective processors. First processor970and second processor980may be coupled to a chipset990via P-P interconnects952and954, respectively. As shown inFIG. 9, chipset990includes P-P interfaces994and998.

Furthermore, chipset990includes an interface992to couple chipset990with a high performance graphics engine938, by a P-P interconnect939. In turn, chipset990may be coupled to a first bus916via an interface996. As shown inFIG. 9, various input/output (I/O) devices914may be coupled to first bus916, along with a bus bridge918which couples first bus916to a second bus920. Various devices may be coupled to second bus920including, for example, a keyboard/mouse922, communication devices926and a data storage unit928such as a non-volatile storage or other mass storage device. As seen, data storage unit928may include code930, in one embodiment. As further seen, data storage unit928also includes a trusted storage929to store sensitive information to be protected. Further, an audio I/O924may be coupled to second bus920.

FIG. 10is a block diagram illustrating an IP core development system1000that may be used to manufacture an integrated circuit to perform operations according to an embodiment. The IP core development system1000may be used to generate modular, re-usable designs that can be incorporated into a larger design or used to construct an entire integrated circuit (e.g., an SoC integrated circuit). A design facility1030can generate a software simulation1010of an IP core design in a high level programming language (e.g., C/C++). The software simulation1010can be used to design, test, and verify the behavior of the IP core. A register transfer level (RTL) design can then be created or synthesized from the simulation model. The RTL design1015is an abstraction of the behavior of the integrated circuit that models the flow of digital signals between hardware registers, including the associated logic performed using the modeled digital signals. In addition to an RTL design1015, lower-level designs at the logic level or transistor level may also be created, designed, or synthesized. Thus, the particular details of the initial design and simulation may vary.

The RTL design1015or equivalent may be further synthesized by the design facility into a hardware model1020, which may be in a hardware description language (HDL), or some other representation of physical design data. The HDL may be further simulated or tested to verify the IP core design. The IP core design can be stored for delivery to a third party fabrication facility1065using non-volatile memory1040(e.g., hard disk, flash memory, or any non-volatile storage medium). Alternately, the IP core design may be transmitted (e.g., via the Internet) over a wired connection1050or wireless connection1060. The fabrication facility1065may then fabricate an integrated circuit that is based at least in part on the IP core design. The fabricated integrated circuit can be configured to perform operations in accordance with at least one embodiment described herein.

The following examples pertain to further embodiments.

In an example, an apparatus comprises: a first local predictor circuit having a first plurality of entries each to store local prediction information for a corresponding branch instruction; a global predictor circuit having a plurality of global entries each to store global prediction information for a corresponding branch instruction; and a second local predictor circuit having a second plurality of entries each to store second local prediction information for a corresponding branch instruction, wherein an entry of the second local predictor circuit is to be updated in response to every execution of the corresponding branch instruction.

In an example, the apparatus further comprises a comparator to determine whether a first entry of the second plurality of entries of the second local predictor circuit provided a correct prediction for the corresponding branch instruction, based at least in part on feedback information regarding branch execution of the corresponding branch instruction.

In an example, the apparatus further comprises a monitoring table coupled to the comparator, the comparator to probabilistically update the monitoring table based at least in part on the determination.

In an example, the comparator is to probabilistically increment a counter of an entry of the monitoring table in response to a determination of a correct prediction by the second local predictor circuit.

In an example, the apparatus further comprises a control circuit to prevent allocation of an entry in the global predictor circuit for a first branch instruction in response to a misprediction of the first branch instruction by the first local predictor circuit, when a value of an entry of the monitoring table associated with the first branch instruction exceeds a threshold.

In an example, the control circuit is to request allocation of the entry in the global predictor circuit for the first branch instruction in response to the misprediction of the first branch instruction by the first local predictor circuit, when the value of the entry of the monitoring table associated with the first branch instruction is less than the threshold.

In an example, the global predictor circuit is to prevent the allocation of the global entry in response to the allocation request based at least in part on prediction information of a victim entry.

In an example, the probabilistic increment is according to a predetermined ratio.

In an example, the comparator is to reset a counter of an entry of the monitoring table in response to a determination of a misprediction by the second local predictor circuit.

In an example, the apparatus further comprises a target array including a plurality of entries to store target information, wherein at least some of the plurality of entries of the target array are to store at least some counter information of the first plurality of entries of the first local predictor circuit.

In an example, the at least some of the plurality of entries of the target array are to store at least some prediction information of the monitoring table.

In another example, a method comprises: receiving, in a branch predictor of a processor, feedback information regarding execution of a branch instruction from an execution circuit of the processor; upon a determination that the feedback information indicates that an entry of a shadow bimodal predictor of the branch predictor correctly predicted the branch instruction, probabilistically updating a counter of an entry of a monitoring table of the branch predictor, the entry associated with the branch instruction; and allocating a new entry in a global predictor of the branch predictor in response to a misprediction regarding the branch instruction by a local predictor when the counter of the entry of the monitoring table is less than a threshold.

In an example, probabilistically updating the counter comprises probabilistically setting the counter.

In an example, the method further comprises probabilistically updating the counter according to a predetermined ratio.

In an example, the method further comprises decrementing the counter of the monitoring table entry in response to a misprediction regarding the branch instruction by the shadow bimodal predictor.

In an example, the method further comprises preventing allocation of an entry for the branch instruction within the global predictor when the value of the counter of the monitoring table entry exceeds the threshold.

In another example, a computer readable medium including data is to be used by at least one machine to fabricate at least one integrated circuit to perform the method of any one of the above examples.

In another example, an apparatus comprises means for performing the method of any one of the above examples.

In another example, a processor comprises a branch prediction circuit that includes: a first bimodal predictor having a first plurality of entries each to store first prediction information for a corresponding branch instruction; a global predictor having a plurality of global entries each to store global prediction information for a corresponding branch instruction; a second bimodal predictor having a second plurality of entries each to store second prediction information for a corresponding branch instruction; a monitoring table having a plurality of monitoring entries each to store a counter value based on the second prediction information for a corresponding branch instruction; and a control circuit to allocate a global entry within the global predictor based at least in part on the counter value of a monitoring entry of the monitoring table for a corresponding branch instruction. The processor may further include an execution circuit to execute instructions and provide feedback information regarding branch instructions to the branch prediction circuit.

In an example, the processor further comprises a comparator to determine whether a first entry of the second plurality of entries of the second bimodal predictor provided a correct prediction for the corresponding branch instruction, based at least in part on the feedback information.

In an example, the comparator is to probabilistically update a first monitoring entry of the monitoring table based at least in part on the determination.

In an example, the control circuit is to: allocate the global entry within the global predictor for the corresponding branch instruction when a counter value of a first monitoring entry of the monitoring table for the corresponding branch instruction is less than a threshold; and prevent allocation of the global entry within the global predictor for the corresponding branch instruction when the counter value of the first monitoring entry of the monitoring table for the corresponding branch instruction exceeds the threshold.

In an example, an apparatus comprises: first predictor means having a first plurality of entries each to store local prediction information for a corresponding branch instruction; global predictor means having a plurality of global entries each to store global prediction information for a corresponding branch instruction; and second local predictor means having a second plurality of entries each to store second local prediction information for a corresponding branch instruction, wherein an entry of the second local predictor is to be updated in response to every execution of the corresponding branch instruction.

In an example, the apparatus further comprises comparator means for determining whether a first entry of the second plurality of entries of the second predictor means provided a correct prediction for the corresponding branch instruction, based at least in part on feedback information regarding branch execution of the corresponding branch instruction.

In an example, the apparatus further comprises monitoring means for probabilistically maintaining information regarding a determination by the comparator means.

In an example, the apparatus further comprises control means for preventing allocation of an entry in the global predictor means for a first branch instruction in response to a misprediction of the first branch instruction by the first predictor means.

In an example, the control means is to prevent the allocation when the probabilistically maintained information associated with the first branch instruction exceeds a threshold.

Note that the terms “circuit” and “circuitry” are used interchangeably herein. As used herein, these terms and the term “logic” are used to refer to alone or in any combination, analog circuitry, digital circuitry, hard wired circuitry, programmable circuitry, processor circuitry, microcontroller circuitry, hardware logic circuitry, state machine circuitry and/or any other type of physical hardware component. Embodiments may be used in many different types of systems. For example, in one embodiment a communication device can be arranged to perform the various methods and techniques described herein. Of course, the scope of the present invention is not limited to a communication device, and instead other embodiments can be directed to other types of apparatus for processing instructions, or one or more machine readable media including instructions that in response to being executed on a computing device, cause the device to carry out one or more of the methods and techniques described herein.