JP-7854891-B2 - Computer implementation method for updating metadata prediction tables, computer program product for updating metadata prediction tables, and system for updating metadata prediction tables (metadata prediction table update using a re-prediction pipeline).

JP7854891B2JP 7854891 B2JP7854891 B2JP 7854891B2JP-7854891-B2

Inventors

カフニー、レイモンド、ジェームス
コルーラ、ベンジャミン、アダム
ボナンノ、ジェームス
プラスキー、ロバート、ブライアン
マリー、トーマス、エドワード
アムゴトゥ、スマン

Assignees

インターナショナル・ビジネス・マシーンズ・コーポレーション

Dates

Publication Date: 20260507
Application Date: 20220726
Priority Date: 20210909

Claims (13)

A computer implementation method for updating a metadata prediction table, wherein the computer implementation method is The metadata prediction table establishes a prediction of how the set of instructions will be resolved, Identifying that the aforementioned set of instructions has been completed, Upon completion of the set of instructions , it is determined whether the set of instructions resolved the prediction in one of a plurality of predetermined forms, When it is determined that the set of instructions has been resolved in one of the plurality of predetermined formats , and it is assumed that an update to the metadata prediction table is necessary based on the prediction of the set of instructions, if the prediction update queue (PUQ), which stores data representing the set of instructions and the prediction, contains data representing the set of instructions resolved in one of the plurality of predetermined formats, then it is determined that the metadata prediction table is a candidate for update. Computer implementation methods, including those mentioned above.
Determining that the set of instructions resolved in one of the plurality of predetermined forms includes determining that the set of instructions resolved to the wrong target, in the wrong direction, or as a surprise. The computer implementation method according to claim 1.
The determination that the metadata prediction table is a candidate for update is, Observe that the metadata prediction table is a candidate for update, and confirm that the metadata prediction table is indeed a candidate for update. The computer implementation method according to claim 1, including the method described in claim 1.
When the metadata prediction table is in a predetermined state, The observation includes assuming that an update is needed when the prediction is established in the metadata prediction table and the set of instructions is resolved as expected, and writing data representing the set of instructions and the prediction as an entry to one of the PUQs, The confirmation occurs upon completion of the set of instructions and includes comparing the data of the completed instructions with data representing a set of previous instructions that was written as a previous entry to one of the PUQs; determining whether there is a match between the data representing the set of instructions and the data representing the set of previous instructions in one of the PUQs; invalidating the entry if a match is found; and confirming that the metadata prediction table should be updated. The computer implementation method according to claim 3.
When the metadata prediction table should be modified to account for erroneous instances, The observation occurs upon completion of the first and second instances of the set of instructions and includes writing the data representing the first instance of the set of instructions and the prediction to one of the PUQs, respectively. The verification occurs upon completion of a second instance of the set of instructions and includes comparing second data representing the second instance of the set of instructions with data representing a previous set of instructions written as a previous entry in one of the PUQs ; determining whether there is a match between the second data and the data representing the previous set of instructions in one of the PUQs; invalidating the entry if there is a match; and confirming that the metadata prediction table should be modified to account for erroneous branch instances. The computer implementation method according to claim 3.
The aforementioned decision is, A weak predictive update queue (WeakPUQ) tracks a set of instructions that need to be updated upon completion based on the assumed correctness of the aforementioned prediction, A false branch PUQ (BrWrgPUQ) tracks a set of instructions that need updating based on how multiple instances of the aforementioned set of instructions complete, The computer implementation method according to claim 1, made possible by the above.
This further includes updating the metadata prediction table which is a candidate for update, and the update is: Upon completion of the aforementioned set of instructions, characteristic data is read from the metadata prediction table, This involves comparing the aforementioned characteristic data with knowledge of how the aforementioned set of instructions was resolved, Based on the results of the comparison, a decision is made as to whether or not to update the metadata prediction table. The computer implementation method according to claim 1, including the method described in claim 1.
A system for updating a metadata prediction table, wherein the system is Memory containing computer-readable instructions, The system includes one or more processors for executing the computer-readable instructions, and the computer-readable instructions control the one or more processors, The metadata prediction table establishes a prediction of how the set of instructions will be resolved, Identifying that the aforementioned set of instructions has been completed, Upon completion of the set of instructions , it is determined whether the set of instructions resolved the prediction in one of a plurality of predetermined forms, When it is determined that the set of instructions has been resolved in one of the plurality of predetermined formats , and it is assumed that an update to the metadata prediction table is necessary based on the prediction of the set of instructions, if the prediction update queue (PUQ), which stores data representing the set of instructions and the prediction, contains data representing the set of instructions resolved in one of the plurality of predetermined formats, then it is determined that the metadata prediction table is a candidate for update. Perform an action that includes system.
Determining that the set of instructions resolved in one of the plurality of predetermined forms includes determining that the set of instructions resolved to the wrong target, in the wrong direction, or as a surprise. The system according to claim 8 .
The determination that the metadata prediction table is a candidate for update is, This includes observing that the metadata prediction table is a candidate for update and confirming that the metadata prediction table is indeed a candidate for update, When the metadata prediction table is in a predetermined state, The observation includes assuming that an update is needed when the prediction is established in the metadata prediction table and the set of instructions is resolved as expected, and writing data representing the set of instructions and the prediction as an entry to one of the PUQs, The confirmation occurs upon completion of the set of instructions and includes comparing the data of the completed instructions with data representing a set of previous instructions that was written as a previous entry to one of the PUQs; determining whether there is a match between the data representing the set of instructions and the data representing the set of previous instructions in one of the PUQs; invalidating the entry if a match is found; and confirming that the metadata prediction table should be updated. The system according to claim 8 .
The determination that the metadata prediction table is a candidate for update is, This includes observing that the metadata prediction table is a candidate for update and confirming that the metadata prediction table is indeed a candidate for update, When the metadata prediction table should be modified to account for erroneous instances, The observation occurs upon completion of the first and second instances of the set of instructions and includes writing the data representing the first instance of the set of instructions and the prediction to one of the PUQs, respectively. The verification occurs upon completion of a second instance of the set of instructions and includes comparing second data representing the second instance of the set of instructions with data representing a previous set of instructions written as a previous entry in one of the PUQs ; determining whether there is a match between the second data and the data representing the previous set of instructions in one of the PUQs; invalidating the entry if there is a match; and confirming that the metadata prediction table should be modified to account for erroneous branch instances. The system according to claim 8 .
The aforementioned decision is, A weak predictive update queue (WeakPUQ) tracks a set of instructions that need to be updated upon completion based on the assumed correctness of the aforementioned prediction, A false branch PUQ (BrWrgPUQ) tracks a set of instructions that need updating based on how multiple instances of the aforementioned set of instructions complete, The system according to claim 8 , made possible by the above.
This further includes updating the metadata prediction table which is a candidate for update, and the update is: Upon completion of the aforementioned set of instructions, characteristic data is read from the metadata prediction table, This involves comparing the aforementioned characteristic data with knowledge of how the aforementioned set of instructions was resolved, Based on the results of the comparison, a decision is made as to whether or not to update the metadata prediction table. The system according to claim 8 , including the above.

Description

This invention relates to a prediction pipeline in general, and more specifically, to a method for updating a metadata prediction table using a re-prediction pipeline. A computer processor's instruction pipeline improves instruction execution throughput by processing instructions using multiple pipeline stages, and these stages can act in parallel on different instructions in the instruction stream. A conditional branch instruction in the instruction stream can cause pipeline stall if the processor waits for the conditional branch instruction to resolve in the pipeline's execution stage before fetching the next instruction in the pipeline's instruction fetch stage. A branch predictor can attempt to guess whether a conditional branch will branch, and may include a branch target predictor that attempts to guess the target of a conditional or unconditional branch before it is computed by decoding and executing the instruction itself. The branch target may be an address computed based on an offset or indirect reference via a register, or both. A branch target buffer (BTB) can be used to predict the target of a predicted branch instruction based on the address of the branch instruction. Predicting the target of a branch instruction prevents pipeline stalling by not waiting for the branch instruction to reach the pipeline execution stage in order to calculate the branch target address. By performing branch target prediction, decoding of the branch target instruction can be performed in the same cycle or in a subsequent cycle, instead of having multiple bubble/empty cycles between the branch instruction and the target of the predicted 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). The branch history table can predict the direction of a branch (whether to branch or not) as a function of the branch address. The pattern history table can assist in predicting the direction of a branch as a function of the branch patterns leading up to the predicted branch. Figure 1 shows a system for performing a computer implementation method for chip design according to one or more embodiments of the present invention.Figure 2 is a schematic diagram of a branch prediction update system according to one or more embodiments of the present invention.Figure 3 is a schematic diagram illustrating the operation of a weak predictive update queue (WeakPUQ) according to one or more embodiments of the present invention.Figure 4 is a schematic diagram illustrating the operation of a mis-branching PUQ (BrWrgPUQ) according to one or more embodiments of the present invention.Figure 5 is a flowchart showing the operation of WeakPUQ and BrWrgPUQ according to one or more embodiments of the present invention.Figure 6 is a flowchart showing the operation of the re-prediction pipeline according to one or more embodiments of the present invention.Figure 7A is a flowchart showing a computer implementation method for updating a metadata prediction table according to one or more embodiments of the present invention.Figure 7B is a flowchart showing a computer implementation method for updating a metadata prediction table according to one or more further embodiments of the present invention.Figure 8 is a schematic diagram of a computer system for performing a branch prediction update method according to one or more embodiments of the present invention.Figure 9 is a flowchart of a method for manufacturing an integrated circuit according to an exemplary embodiment of the present invention. The diagrams shown herein are illustrative. Many variations are possible in the diagrams or the operations described therein without departing from the spirit of the invention. For example, actions can be performed in a different order, or actions can be added, deleted, or modified. Furthermore, the term “combined” and its variations indicate the presence of a communication path between two elements, and do not imply a direct connection between elements without intervening elements/connections. All these variations are considered part of the specification. One or more embodiments of the present invention provide an accurate and efficient method for determining whether any of the predictive structures combined to create a branch prediction need to be updated. A set of structures is created that helps determine whether a particular execution pipeline path of a branch requires an update to the branch's predictive structure. Using this structure and a read-before-write model of completion time updates eliminates much of the need for logic to track and apply speculative updates, reducing latency in the critical predictive time pipeline that controls instruction fetch and decode streams. For example, branch data such as direction and target address is crucial for the performance of general-purpose computers (such as mainframe machines). This is b