Updating metadata prediction tables using a reprediction pipeline

Aspects of the invention include a computer-implemented method of updating metadata prediction tables. The computer-implemented method includes establishing, in the metadata prediction tables, a prediction of how a set of instructions will resolve and identifying that the set of instructions is completed. The computer-implemented method also includes determining, upon completion of the set of instructions, whether prediction update queues (PUQs) associated with the set of instructions indicate that the set of instructions resolved in one of a plurality of prescribed manners relative to the prediction and deciding that the metadata predictions tables are candidates to be updated based on the PUQs indicating that the set of instructions resolved in one of the plurality of prescribed manners.

The present invention generally relates to prediction pipelines and more specifically, to a method of updating metadata prediction tables using a reprediction pipeline.

An instruction pipeline in a computer processor improves instruction execution throughput by processing instructions using a number of pipeline stages, where multiple stages can act on different instructions of an instruction stream in parallel. A conditional branch instruction in an instruction stream may result in a pipeline stall if the processor waits until the conditional branch instruction is resolved in an execution stage in the pipeline before fetching a next instruction in an instruction fetching stage for the pipeline. A branch predictor can attempt to guess whether a conditional branch will be taken or not and can also include branch target prediction, which attempts to guess a target of a taken conditional or unconditional branch before it is computed by decoding and executing the instruction itself. A branch target may be a computed address based on an offset and/or an indirect reference through a register.

A branch target buffer (BTB) can be used to predict the target of a predicted taken branch instruction based on the address of the branch instruction. Predicting the target of the branch instruction can prevent pipeline stalls by not waiting for the branch instruction to reach the execution stage of the pipeline to compute the branch target address. By performing branch target prediction, the branch's target instruction decode may be performed in the same cycle or the cycle after the branch instruction instead of having multiple bubble/empty cycles between the branch instruction and the target of the predicted taken branch instruction. Other branch prediction components that may be included in the BTB or implemented separately include a branch history table (BHT) and a pattern history table (PHT). A branch history table can predict the direction of a branch (taken vs. not taken) as a function of the branch address. A pattern history table can assist with direction prediction of a branch as a function of the pattern of branches encountered leading up to the given branch which is to be predicted.

SUMMARY

Embodiments of the present invention are directed to a computer-implemented method of updating metadata prediction tables.

A non-limiting example includes establishing, in the metadata prediction tables, a prediction of how a set of instructions will resolve and identifying that the set of instructions is completed. The computer-implemented method also includes determining, upon completion of the set of instructions, whether prediction update queues (PUQs) associated with the set of instructions indicate that the set of instructions resolved in one of a plurality of prescribed manners relative to the prediction and deciding that the metadata predictions tables are candidates to be updated based on the PUQs indicating that the set of instructions resolved in one of the plurality of prescribed manners.

DETAILED DESCRIPTION

One or more embodiments of the present invention provide for an accurate and efficient method of determining whether any of the predictive structures that combined to create a prediction for a branch need to be updated. A set of structures are created to help to decide whether a specific execution pipeline pass of a branch needs to make an update to the branch's predictive structure. The use of the structures as well as a read-before-write model of completion time updates removes the need for a large portion of logic that tracks and applies speculative updates; hence reducing the latency of the critical prediction time pipeline for steering the instruction fetch and decode streams.

Branch data, such as a direction and a target address for example, is important to the performance of a general-purpose computing machine (e.g., mainframe machine) because it allows for predictive structures to get ahead of a current instruction to prepare the machine for where it will need to go in the future. As these predictive structures encounter a branch, they store the outcome of the completion of the branch in multiple different structures. This is so that when the branch is predicted again the machine can use the results of the previous execution of the branch to more accurately determine what the branch will do in the future. As such, being able to accurately update the data in these structures will allow the machine to increase performance in this area.

In addition, branches are very common instructions in a computing machine. Since branches are common, it is important to have a way to decide if a branch needs to make updates to its metadata or not. Previously, this has been done by saving the data from when the branch was predicted until when it completed. But this is costly in terms of silicon area and sometimes power usage especially when this data is transported since prediction and completion can be many cycles apart. For example, ages of the speculative entries in relation to update mechanisms were tracked in an attempt to predict whether a branch would need to be updated based on assuming that the prediction was correct and then tracking information of the branch through the pipeline.

A drawback of the previous solutions is that when a single branch is executed several times in quick succession there is often no way to communicate from dependent passes of the branch that a prior branch has already updated the predictive structures. In the previous solutions, the update mechanism was determined based on the prediction time information and how the branch completes. Since the previous solution does not factor in any updates that happened between the time the branch was predicted versus when it completes, those updates are excessive and potentially inaccurate. An example of how an inaccurate update is made would be if there were multiple instances of a branch that made updates to the strength of a branch, causing it to go from an initially weak state to a strong state, but the final instance of the branch gets a branch wrong. This branch wrong would not see the updated strong state and instead sees the outdated, and incorrect, weak state from the initial prediction and make the incorrect update based on seeing the stale weak state.

Another drawback is that the methods for determining if a branch needs to make an update are typically imprecise. In those cases, there is extra power consumed for writing the array and/or having updates that are unnecessary slow down the pipeline from making the updates that are necessary.

An additional drawback of the previous solutions is that the branch data from the prediction time was stored and carried through to completion time. This was so that as the branch resolved the prediction time information was available to decide what the update should be. This was costly as there is a lot of information that needed to be kept around for every branch. In many cases there is not a need for an update so that tracking is useless.

One or more embodiments of the present invention address one or more of the above-described shortcomings of the prior art by providing for creation of a set of side structures or prediction update queues (PUQs) that act as funnels to determine if a branch needs to go through an update pipeline based on the way the branch was predicted and how the branch completed. There are a finite number of reasons why a branch might need to go through to the update logic at completion time. Several of these reasons can be detected at completion time through minimal data tracking in conjunction with the result of the branch execution. These reasons will always need an update to occur for that branch and thus are always passed through to have the update occur. For the remaining reasons the PUQs are split up by reason and when a branch completes it is checked against each of the PUQs. A match against either of the PUQs indicates that the branch needs to head through to the update pipeline. The update pipeline will be repredicting the branch at completion time through reading the data from the predictive structures out and going through the same predictive mechanisms in conjunction with the result from the completion of the branch to determine the correct state to update to. By going through the same process of how a branch is predicted and knowing how the branch completed, the update pipeline can determine the correct updates without having to carry around a lot of data through the overall pipeline from prediction to completion.

The present invention thus reduces logical complexity during the prediction pipeline and potentially the silicon area needed to track extra information through the pipeline. Also, the PUQ structures reduce the amount of data needed to be tracked through the execution pipeline. The PUQ structures only need to match the IA of a given branch to indicate that branch needs to go through the update pipeline regardless of how the branch completes. In addition, the PUQ's allow for maintaining branch information for branches that are going to need an update.

Using the reprediction pipeline, it is no longer necessary to store all of the prediction time information in a side structure to track through the pipeline. Since the data will go through a process of repredicting the branch at completion and knowing how the branch completed the pipeline knows what updates are needed. Thus, almost all the data tracking from prediction time through to completion can be removed which potentially reduces overall silicon area and power usage by the core.

FIG.1is a block diagram of a system100to perform a computer-implemented method of updating branch prediction according to embodiments of the invention. The system100includes processing circuitry110used to generate the design that is ultimately fabricated into an integrated circuit120. The steps involved in the fabrication of the integrated circuit120are well-known and briefly described herein. Once the physical layout is finalized, according to embodiments of the invention, to facilitate optimization of the routing plan, the finalized physical layout is provided to a foundry. Masks are generated for each layer of the integrated circuit based on the finalized physical layout. Then, the wafer is processed in the sequence of the mask order. The processing includes photolithography and etch. This is further discussed with reference toFIG.9.

With reference toFIG.2, a system200for updating branch prediction is provided and can be executed or embodied in the computer system800ofFIG.8. As shown inFIG.2, the system200includes a branch target buffer (BTB)201, a pattern history table (PHT)202, a changing target buffer (CTB)203and a perceptron204. The system200further includes prediction logic210, completion logic211, a WeakPUQ220, a branch wrong PUQ (BrWrgPUQ)230, a completion write queue214and a reprediction pipeline240. The prediction logic210is communicative with a predicted bundle unit212and the WeakPUQ220. The completion logic211is communicative with the WeakPUQ220, the BrWrgPUQ230, a completing group unit213and a completion write queue214. The reprediction pipeline240is communicatively interposed between the completion write queue214and the BTB201, PHT202, the CTB203, and the perceptron204.

When a branch is predicted by the BTB201or any of the auxiliary structures (i.e., the PHT202, the CTB203and the perceptron204) that help determine the characteristics of a branch, most notably the direction and target address, the prediction logic210, the completion logic211, the WeakPUQ220and the BrWrgPUQ230cooperatively determine whether that branch is a candidate for update when the branch completes. In particular, the WeakPUQ220and the BrWrgPUQ230determine if a branch needs to be sent for an update and, when, it is determined that a branch needs to be sent for an update, data representative of the branch is written into the completion write queue214.

Surprise branches and branches that are dynamic but get a wrong target or direction will always need to be sent thru the update pipeline. A surprise branch is a branch which is not predicted and learned about as a function of an instruction decode. These types of branches can be identified at completion time by saving a very small amount of data, such as the predicted direction and target. In addition, there are some other types of dynamic branches that can also be identified at completion time and there is not a need for excess information to make the necessary updates. The WeakPUQ220tracks the information and determine that an update is necessary at completion time.

Surprise branches and branches that are dynamic but get a wrong target or direction will always need to be sent through the update pipeline. A surprise branch is a branch which is not predicted and learned about as a function of an instruction decode. These types of branches can be identified at completion time by saving a very small amount of data, such as the predicted direction and target. In addition, there are some other types of dynamic branches that can also be identified at completion time and there is not a need for excess information to make the necessary updates. The WeakPUQ220tracks the information and determine that an update is necessary at completion time.

With reference toFIG.3, an exemplary scenario of an operation of the WeakPUQ220is illustrated. As shown inFIG.3, Branch A, Branch B and Branch C are provided. Branch A is predicted in a weak taken state and is placed into the WeakPUQ220(Point1). Branch A resolves as taken (Point4) and matches in the Weak PUQ220, which means we need an update and so Branch A is updated from weak taken to strong taken (Point7). At Point4the entry that matched Branch A is invalidated in the Weak PUQ200. For Branches B and C the prediction, resolution and update are all for separate instances of the same branch and since there is no matching entry in the Weak PUQ220, since it was invalidated at Point4when Branch A matched against it, when these branches complete (Points5and6respectively) these branches are not sent through to the update pipeline (Points8and9are excessive and do not occur in an implementation with the Weak PUQ200). Thus, only the entry for Branch A goes to the update pipeline.

The BrWrgPUQ230works differently than the WeakPUQ220because the BrWrgPUQ230is designed to go after a different set of branches. The BrWrgPUQ230is designed to go after future instances of branches that are predicted in a strong state, SNT (strongly-not-taken) or ST (strongly-taken), that at completion time resolve with a wrong direction before the update for that branch in a strong state has been processed by the reprediction pipeline240. Since the branch resolves with a wrong direction, that branch will be passed along to the update pipeline and at the same time this branch will be installed into the BrWrgPUQ230. The BrWrgPUQ230is going after branches that have the same IA and were predicted after the initial branch, but before it completed updating, and resolved with a correct direction prediction. For example, a future instance of the same branch that caused an install into the BrWrgPUQ230that completes without a branch wrong and was predicted in a strong state, but matches in the BrWrgPUQ230, will be sent through to the reprediction pipeline240. In this case, those branches would have seen an incorrect state at prediction time, because the update to that state had not occurred yet from the completion of the first instance, and since they resolved in a manner that if predicted weak would cause an update, they would miss this update. But the BrWrgPUQ230is there to catch this case so the branches know to go through the update pipeline. That means that this PUQ has entries created and invalidated at completion time, whereas the Weak PUQ220has entries created at prediction time and invalidated at completion time.

With reference toFIG.4, an exemplary scenario of an operation of the BrWrgPUQ230is illustrated. As shown inFIG.4, Branch A is predicted in a strong taken (ST) state. Since it is in a strong taken state, it is not put into the WeakPUQ220. (Point1). Branch A resolves as not taken, which is a wrong direction (Point2) and Branch A goes to the update pipeline to have the branch state updated for that branch. Branch A also creates an entry in the BrWrgPUQ230. After the restart following the branch wrong direction, Branch Aprimeis predicted in a strong state before the update for Branch A has completed (Point3). Branch Aprimehas the same instruction address as Branch A, such as if there is a loop and we see the same branch predicted multiple times. Branch A completes its update process (Point4). When Branch Aprimecompletes correctly with a resolved taken outcome it would normally not automatically know an update is necessary since it was predicted in a strong state and resolved correctly (Point5). Branch Aprimechecks and finds a match in BrWrgPUQ230. This tells Branch Aprimeit needs to go through the update pipeline because it has extra information from the resolution of Branch A. Branch Aprimethen goes through the update pipeline and updates from the WT state back to a ST state (Point6).

With reference toFIG.5, operations of the WeakPUQ220and the BrWrgPUQ230will now be described.

At an initial instance, Branch X is completed501and it is determined whether Branch X resolved with a wrong direction or target502. In an event Branch X resolved with a wrong direction or target, an entry for Branch X is written in the BrWrgPUQ230at503and an attempt is made to write the entry for Branch X into a completion write queue504. If the completion write queue504is full and unable to accept the write for Branch X this data is not installed into the completion write queue. This is followed by awaiting a completion event505and the completion of Branch X at501. In an event Branch X did not resolve with a wrong direction or target, an entry for Branch X is looked for in the WeakPUQ220at506and it is determined if there is a hit in the WeakPUQ220at507. If there is a hit, the entry for Branch X is invalidated from the WeakPUQ220at508whereupon control proceeds to504. Conversely, if there is no hit, the entry for Branch X is looked for in the BrWrgPUQ230at509and it is determined if there is a hit at510. If there is a hit, the entry for Branch X is invalidated from the BrWrgPUQ230at511whereupon control proceeds to504. Conversely, if there is no hit, it is found that no updates are needed for Branch X at512and control proceeds to505.

With reference back toFIG.2, the reprediction pipeline240serves to execute a reprediction for a branch once the branch enters the update pipeline. That is, once a branch is determined that it should go through the update pipeline, the last step before the process completes is to do the update to the branch state. Since most of the data tracking has been removed from the process, the repredicting of the branch is done at completion time. The logic of the reprediction pipeline240reads the data from the arrays and that is where the reprediction pipeline240picks up the branch data instead of from information tracked through the pipeline. With the most current data, it becomes possible to determine the necessary updates for the branch and, once the updates are determined, the logic of the reprediction pipeline240writes the data back to update the arrays.

With reference toFIG.6, an operation of the reprediction pipeline will now be described.

Initially an entry for a next branch is looked for in the completion write queue214at601and it is determined if the entry for the next branch is valid at602. In an event the entry is not valid, control reverts to601. In an event the entry is valid, metadata tables of one or more of the BTB_201, the PHT202, the CTB203and the perceptron204are indexed at603, a hit detect is performed at604and it is determined whether a hit occurred at605. If no hit occurred, it is found that the branch is a surprise at606and it is determined whether a metadata state needs to be updated at607. In an event the metadata state needs to be updated, the updated state is written into the metadata tables at608and control proceeds to601. If a hit occurred, it is determined whether duplicates are found at609and, if duplicates are found, all but one duplicate entry is invalidated at610, a reprediction value is determined at611, the reprediction value is compared with the existing outcome at612and control proceeds to607. If no duplicates are found, control immediately proceeds to611.

With reference toFIG.7A, a computer-implemented method of updating metadata prediction tables is provided as generally described above. The computer-implemented method includes establishing, in the metadata prediction tables, a prediction of how a set of instructions will resolve (701) and identifying that the set of instructions is completed (702). The computer-implemented method also includes determining, upon completion of the set of instructions, whether prediction update queues (PUQs) associated with the set of instructions indicate that the set of instructions resolved in one of a plurality of prescribed manners relative to the prediction (703) and deciding that the metadata predictions tables are candidates to be updated based on the PUQs indicating that the set of instructions resolved in one of the plurality of prescribed manners (704). In addition, the method can include updating the characteristics of the metadata prediction tables that are candidates to be updated in accordance with results of the deciding (705).

In accordance with one or more embodiments of the present invention, the deciding that the characteristics of the metadata prediction tables are candidates to be updated of operation704can include determining that the set of instructions resolved with a wrong target, with a wrong direction or as a surprise, determining that the characteristics of the metadata prediction tables need to be strengthened or weakened or determining that the set of instructions resolved as a wrong branch. It is to be understood, however, that other embodiments exist and that the deciding that the characteristics of the metadata prediction tables are candidates to be updated of operation704can involve other determinations, conclusions, etc.

In any case, the deciding that the characteristics of the metadata prediction tables are candidates to be updated of operation704is enabled by the capability of the WeakPUQ220to track sets of instructions that will need updates at completion time based on assumed correctness of the prediction and the capability of the BrWrgPUQ230to track sets of instructions that will need updates based on how multiple instances of each of the sets of instructions complete. Thus, the deciding that the characteristics of the metadata prediction tables are candidates to be updated of operation704can further include observing that the characteristics of the metadata prediction tables are candidates to be updated (7041) and confirming that the characteristics of the metadata prediction tables are candidates to be updated is correct (7042).

As an example, for a case in which the characteristics of the metadata prediction tables are in a predefined state (i.e., an unsaturated state) as an update, which encompasses strengthen/weaken updates, the observing of operation7041and the confirming of operation7042will be described below. The observing of operation7041occurs when the prediction is established in the metadata prediction tables and includes assuming that an update will be needed in an event the set of instructions resolves as expected and writing data representing the set of instructions and the prediction into a PUQ, such as the WeakPUQ220, as an entry. The confirming of operation7042occurs upon the completion of the set of instructions and includes comparing the data of a completing instruction with data representing previous sets of instructions written into the PUQ as previous entries. The confirming of operation7042further includes determining whether there is a match between the data representing the set of instructions and the data representing previous sets of instructions in the PUQ, invalidating the entry in an event of a match and confirming that the characteristics of the metadata prediction tables should be updated.

As another example, for a case in which the characteristics of the metadata prediction tables should be changed to account for a branch wrong instance as an update, the observing of operation7041and the confirming of operation7042will be described below. The observing of operation7041occurs upon completion of first and second instances of the set of instructions and includes respectively writing data representing the first instance of the set of instructions and the prediction into a PUQ, such as the BrWrgPUQ230. The confirming of operation7042occurs upon completion of a second instance of the set of instructions and includes comparing the second data with data representing previous sets of instructions written into the PUQ as previous entries, determining whether there is a match between the second data representing the second set of instructions and the data representing previous sets of instructions in the PUQ, invalidating the entry in an event of a match and confirming that the characteristics of the metadata prediction tables should be changed to account for a branch wrong instance.

As used herein, the metadata prediction tables can include one or more selected from the group consisting of the BTB201, the PHT202, the CTB203and the perceptron204.

With reference toFIG.7B, a computer-implemented method of executing the updating of the characteristics of the metadata prediction tables that are candidates to be updated of operation705is provided as an additional set of operations for the method ofFIG.7A. As shown inFIG.7B, the computer-implemented method of executing the updating of the characteristics of the metadata prediction tables that are candidates to be updated of operation705includes reading characteristic data from the metadata prediction tables upon completion of the set of instructions (7054), comparing the characteristic data with knowledge of how the set of instructions resolved (7055) and determining whether to update the characteristics of the metadata prediction tables based on results of the comparing (7056).

As shown inFIG.8, the computer system800has one or more central processing units (CPU(s))801a,801b,801c, etc. (collectively or generically referred to as processor(s)801). The processors801can be a single-core processor, multi-core processor, computing cluster, or any number of other configurations. The processors801, also referred to as processing circuits, are coupled via a system bus802to a system memory803and various other components. The system memory803can include a read only memory (ROM)804and a random access memory (RAM)805. The ROM804is coupled to the system bus802and may include a basic input/output system (BIOS), which controls certain basic functions of the computer system800. The RAM is read-write memory coupled to the system bus802for use by the processors801. The system memory803provides temporary memory space for operations of said instructions during operation. The system memory803can include random access memory (RAM), read only memory, flash memory, or any other suitable memory systems.

The computer system800comprises an input/output (I/O) adapter806and a communications adapter807coupled to the system bus802. The I/O adapter806may be a small computer system interface (SCSI) adapter that communicates with a hard disk808and/or any other similar component. The I/O adapter806and the hard disk808are collectively referred to herein as a mass storage810.

Software811for execution on the computer system800may be stored in the mass storage810. The mass storage810is an example of a tangible storage medium readable by the processors801, where the software811is stored as instructions for execution by the processors801to cause the computer system800to operate, such as is described herein below with respect to the various Figures. Examples of computer program product and the execution of such instruction is discussed herein in more detail. The communications adapter807interconnects the system bus802with a network812, which may be an outside network, enabling the computer system800to communicate with other such systems. In one embodiment, a portion of the system memory803and the mass storage810collectively store an operating system, which may be any appropriate operating system, such as the z/OS or AIX operating system from IBM Corporation, to coordinate the functions of the various components shown inFIG.8.

Additional input/output devices are shown as connected to the system bus802via a display adapter815and an interface adapter816. In one embodiment, the adapters806,807,815, and816may be connected to one or more I/O buses that are connected to the system bus802via an intermediate bus bridge (not shown). A display819(e.g., a screen or a display monitor) is connected to the system bus802by a display adapter815, which may include a graphics controller to improve the performance of graphics intensive applications and a video controller. A keyboard821, a mouse822, a speaker823, etc. can be interconnected to the system bus802via the interface adapter816, which may include, for example, a Super I/O chip integrating multiple device adapters into a single integrated circuit. Suitable I/O buses for connecting peripheral devices such as hard disk controllers, network adapters, and graphics adapters typically include common protocols, such as the Peripheral Component Interconnect (PCI). Thus, as configured inFIG.8, the computer system800includes processing capability in the form of the processors801, and, storage capability including the system memory803and the mass storage810, input means such as the keyboard821and the mouse822, and output capability including the speaker823and the display819.

In some embodiments, the communications adapter807can transmit data using any suitable interface or protocol, such as the internet small computer system interface, among others. The network812may be a cellular network, a radio network, a wide area network (WAN), a local area network (LAN), or the Internet, among others. An external computing device may connect to the computer system800through the network812. In some examples, an external computing device may be an external webserver or a cloud computing node.

It is to be understood that the block diagram ofFIG.8is not intended to indicate that the computer system800is to include all of the components shown inFIG.8. Rather, the computer system800can include any appropriate fewer or additional components not illustrated inFIG.8(e.g., additional memory components, embedded controllers, modules, additional network interfaces, etc.). Further, the embodiments described herein with respect to computer system800may be implemented with any appropriate logic, wherein the logic, as referred to herein, can include any suitable hardware (e.g., a processor, an embedded controller, or an application specific integrated circuit, among others), software (e.g., an application, among others), firmware, or any suitable combination of hardware, software, and firmware, in various embodiments.

FIG.9is a process flow of a method of fabricating an integrated circuit according to exemplary embodiments of the invention. Once the physical design data is obtained, based, in part, on the computer-implemented method of updating branch prediction described herein, the integrated circuit120can be fabricated according to known processes that are generally described with reference toFIG.9. Generally, a wafer with multiple copies of the final design is fabricated and cut (i.e., diced) such that each die is one copy of the integrated circuit120. At block910, the processes include fabricating masks for lithography based on the finalized physical layout. At block920, fabricating the wafer includes using the masks to perform photolithography and etching. Once the wafer is diced, testing and sorting each die is performed, at block930, to filter out any faulty die.