JP3764019B2 - Branch prediction method, arithmetic device, and calculation device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a branch prediction method, an arithmetic device, and a calculation device, and more particularly to a branch prediction method, an arithmetic device, and a calculation device that are used when branch prediction is performed according to a branch instruction.
[0002]
In recent years, microprocessors using a pipeline system have become the mainstream in order to increase processing speed. Further, in the microprocessor, when a branch instruction is generated for speeding up the processing, a method of predicting the branch direction according to the degree of branching and advancing the processing is employed.
[0003]
When branch prediction is applied to the pipeline method, when a branch prediction is missed, a pipeline bubble that does not participate in the current processing is generated in each slot of the pipeline, and the performance is significantly reduced. Pipeline bubbles greatly affect the overall performance of the microprocessor as the operating frequency of the microprocessor increases.
[0004]
Therefore, various branch prediction methods have been proposed aiming at a high branch prediction hit rate. Among them, the two-stage branch prediction method is the most effective branch prediction method at present.
[0005]
In this two-stage branch prediction method, it is necessary to detect a plurality of branch misses before the branch prediction table is updated in the correct direction. In particular, in a superscalar processor, the number of branch prediction errors increases as multiple instructions are executed simultaneously, and the impact on performance degradation increases. Therefore, a method that can easily reflect the result of profiling in branch prediction is desired.
[0006]
[Prior art]
FIG. 1 is a block diagram showing an example of a conventional computing device.
[0007]
The computing device 1 includes an arithmetic device 2, a main memory 3, a hard disk drive 4, an input device 5, a display device 6, and a bus 7.
[0008]
The arithmetic device 2 performs data arithmetic. The main memory 3 is used as a working storage area of the arithmetic device 2, and temporarily stores data to be calculated, instructions, calculation results, and the like. The hard disk drive 4 stores programs and data executed by the arithmetic device 2. The input device 5 includes a keyboard, a mouse, and the like, and is used for program execution instructions and data input. The display device 6 displays the calculation result in the calculation device 2 and the like. The bus 7 connects the arithmetic device 2, the main memory 3, the hard disk drive 4, the input device 5, and the display device 6.
[0009]
FIG. 2 is a block diagram showing an example of a conventional arithmetic device.
[0010]
The conventional arithmetic device 2 includes a cache memory 11, an instruction fetch unit 12, an instruction decode unit 13, an arithmetic unit 14, a multiplexer 13, a reorder buffer 14, a control unit 15, and a branch prediction unit 16.
[0011]
The cache memory 11 holds instructions and data from the main storage unit. The instruction fetch unit 12 sequentially fetches information stored in the cache memory 11. The instruction fetched by the instruction fetch unit 12 is supplied to the instruction decode unit 13.
[0012]
The instruction decoding unit 13 decodes the instruction. The instruction from the instruction decoding unit 13 is supplied to the arithmetic unit 14. The arithmetic unit 14 executes the instruction from the instruction decoding unit 13. The calculation unit 14 includes an integer calculation unit 19, a floating point calculation unit 20, and a functional unit 21. The integer arithmetic unit 19 performs integer arithmetic. The floating point arithmetic unit 20 performs floating point arithmetic. The functional unit 21 realizes other preset functions. The calculation result executed by the calculation unit 14 is supplied to the multiplexer 15. The multiplexer 15 supplies the operation result of any one of the integer arithmetic unit 19, the floating point arithmetic unit 20, and the functional unit 21 to the cache memory 11. In addition, the calculation unit 5 outputs a reorder request.
[0013]
The reorder buffer 16 holds a reorder request from the calculation unit 14. The reorder request held in the reorder buffer 16 is supplied to the control unit 17. The control unit 17 controls the cache memory 11, the instruction fetch unit 12, the instruction decoding unit 13, the arithmetic unit 14, the multiplexer 15, and the reorder buffer 16, and controls the execution of instructions. The branch prediction unit 18 performs branch prediction according to the instruction code.
[0014]
FIG. 3 is a block diagram of a branch prediction unit as an example of a conventional arithmetic device.
[0015]
The branch prediction unit 18 includes a branch history register 22, an index synthesis circuit 23, a branch prediction table unit 24, a multiplexer 25, and a branch prediction control unit 26.
[0016]
The branch history register 22 stores a history of hits or misses in branch prediction in order of time.
[0017]
FIG. 4 shows a block diagram of a branch history register data as an example of a conventional arithmetic unit.
[0018]
The branch history register 22 is composed of a predetermined number of bit strings. Each bit of the bit string corresponds to past branch prediction. A value corresponding to the branch prediction result is stored in each bit of the branch history register 22.
[0019]
The value corresponding to the branch prediction result is “1” when the branch is successful, and is “0” when the branch is unsuccessful. The bit string held in the branch history register 22 is supplied to the index synthesis circuit 23.
[0020]
The index synthesis circuit 23 synthesizes the program count value from the control unit 17 and the branch history value from the branch history register 22. The branch prediction table unit 24 is referred to according to the synthesis result in the index synthesis circuit 23.
[0021]
The branch prediction table unit 24 includes n branch prediction tables 24-1 to 24-n. The branch prediction tables 24-1 to 24-n are selected according to the program count value. The branch prediction data is selected from the selected branch prediction table 24-x according to the value of the branch history register 22. Here, the branch prediction table 24-x is a desired branch prediction table among the branch prediction tables 24-1 to 24-n.
[0022]
FIG. 5 is a data configuration diagram of a branch prediction table as an example of a conventional arithmetic device.
[0023]
In the branch prediction table 24-x, a combined value of the program count value ax from the control unit 17 and the branch history value bm from the branch history register 22 is used as an address, and branch prediction data c corresponding to the address is stored. .
[0024]
The branch prediction data c is 2-bit data and indicates four branch prediction states. The branch prediction data c is SNT (Strongly not Taken) state when “00”, WNT (Weakly Not Taken) state when “01”, WT (Weakly Taken) state, ST (Strongly Taken) state when “10”. Indicates.
[0025]
The SNT state indicates a state where no branching occurs, the WNT state indicates a state where branching is performed little, the WT state indicates a state where some branching occurs, and ST indicates a state where branching is predicted.
[0026]
The branch prediction table unit 24 uses the index synthesis circuit 23 as an address, and reads the branch prediction data c. The branch prediction data c read from the branch prediction table unit 24 is supplied to the control unit 17. The control unit 17 speculatively executes a branch instruction according to the branch prediction data c from the branch prediction control unit 18.
[0027]
FIG. 6 shows an operation explanatory diagram of an example of a conventional arithmetic device.
[0028]
In FIG. 6, when a branch prediction error occurs in the SNT state, the branch prediction error is reflected in the branch history value. Branch prediction data is determined based on the branch history value, and “00” indicating the SNT state is output as branch prediction data.
[0029]
When the branch prediction hits in the SNT state, the branch prediction hit is reflected in the branch history value. When the branch prediction hits in the SNT state, the probability that the branch prediction hits has improved, so that “01” indicating the WNT state is output as branch prediction data for the branch prediction data.
[0030]
When the branch prediction is missed in the WNT state, the branch prediction data is returned to “00” indicating the SNT state. When the branch prediction hits in the WNT state, the probability that the branch prediction hits is further improved, so that the branch prediction data is changed to “10” indicating the WT state. When the branch prediction is missed in the WT state, the branch prediction data is changed to “01” indicating the WNT state.
[0031]
Furthermore, if the branch prediction misses in the WT state, the branch prediction data is returned to the WNT state. When the branch prediction hits in the WT state, the branch prediction data is changed to “11” indicating the ST state.
[0032]
As described above, the branch prediction data c is changed according to the branch history value. Further, the branch prediction tables 15-1 to 15-n are switched according to the program count value, thereby enabling branch prediction control according to the program position.
[0033]
[Problems to be solved by the invention]
However, in the conventional branch prediction method, since the predicted branch data is determined by the branch history and the program count value, there is a problem that accurate branch prediction cannot be performed unless the branch prediction result is accumulated in the branch history. there were.
[0034]
The present invention has been made in view of the above points, and an object thereof is to provide an arithmetic device, a branch prediction method, and a calculation device that can perform accurate branch prediction.
[0035]
[Means for Solving the Problems]
The present invention provides a branch prediction table that stores branch prediction data in an arithmetic unit that determines branch prediction data indicating a branch prediction state according to a branch prediction result, and performs branch prediction according to the branch prediction data. A branch prediction history table, a branch prediction auxiliary table holding branch prediction auxiliary data corresponding to the branch prediction history, a branch direction transition table holding the branch prediction update data, and branch prediction. A control unit for controlling, the control unit reads branch prediction auxiliary data from the branch prediction auxiliary table based on a branch prediction history held in the register, and the branch based on the branch prediction auxiliary data Read the branch prediction update data from the direction transition table, and update the branch prediction table based on the branch prediction update data And wherein the door.
[0036]
According to the present invention, optimal branch prediction data can be obtained according to the success or failure of branch prediction, so that accurate branch prediction is possible, and the direction of branch prediction is weighted according to the branch prediction history. And accurate branch prediction can be performed quickly.
[0042]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 7 shows a block diagram of an embodiment of the present invention. In the figure, the same components as in FIG. Further, the configuration of the entire computing device is the same as that shown in FIG.
[0043]
The arithmetic device 100 of the present embodiment is different from the arithmetic device of FIG. 1 in the configuration of the branch prediction unit 101.
[0044]
FIG. 8 is a block diagram of a branch prediction unit according to an embodiment of the present invention. In the figure, the same components as those in FIG.
[0045]
The branch prediction unit 101 includes a branch prediction correction circuit 102 in addition to the branch history register 22, the index synthesis circuit 23, the branch prediction table unit 24, the multiplexer 25, and the branch prediction control unit 26. The branch prediction correction circuit 102 includes a profile information table 103, a branch prediction auxiliary table unit 104, a branch direction transition table unit 105, and multiplexers 106 and 107.
[0046]
The profile information table 103 stores profile information. Profile information is information for controlling the update of the branch prediction auxiliary table portion 10 4. In the profile information, when the corresponding bit is set to “1”, the branch prediction auxiliary data output from the branch prediction auxiliary table unit 103 is fixed, and when the corresponding bit is set to “0”, allowing update branch prediction auxiliary data of the branch prediction auxiliary table portion 104 or al. The branch prediction auxiliary table unit 104 holds branch prediction auxiliary data.
[0047]
FIG. 9 shows a data configuration diagram of the branch prediction auxiliary table part of one embodiment of the present invention.
[0048]
The branch prediction auxiliary table unit 104 includes m branch prediction auxiliary tables 104-1 to 104-m. The branch auxiliary table 103-x is composed of an n-bit bit string. The bit string is composed of two bit fields, r field and s field. In the r field, a history of hit / miss of past branch prediction is stored. In the s field, a value for selecting the branch direction transition table unit 104 is stored. The branch prediction auxiliary table unit 104 outputs data (r, s) by the entry from the branch prediction control unit 26. The output of the branch prediction auxiliary table unit 104 is supplied to the branch prediction control unit 26 via the multiplexer 106.
[0049]
The branch direction transition table unit 105 includes 2n = m branch direction transition tables 105-1 to 105-m. The branch direction transition tables 105-1 to 105-m output branch prediction update data using the branch prediction data from the branch prediction control unit 26 as an entry. The branch prediction update data is composed of “00”, “01”, “10”, and “11” similarly to the branch prediction data. The branch prediction update data “00” indicates the SNT state similarly to the branch prediction data. The branch prediction update data “01” indicates the WNT state in the same manner as the branch prediction data. The branch prediction update data “10” indicates the WT state similarly to the branch prediction data. The branch prediction update data “11” indicates the ST state similarly to the branch prediction data.
[0050]
FIG. 10 is a data configuration diagram of a branch direction transition table according to an embodiment of the present invention.
[0051]
The branch direction transition table 105-x is selected from the m branch direction transition tables 105-1 to 105-m according to the value of the s field. In the selected branch direction transition table 105-x, branch prediction data “00”, “01”, “10”, and “11” are entries. In the branch direction transition table 105-x, a 4-bit bit string is set for each branch prediction data “00”, “01”, “10”, and “11”. In the bit string, the first bit corresponds to the branch prediction update data “00”, the second bit corresponds to the branch prediction update data “01”, and the third bit corresponds to the branch prediction update data “10”. The fourth bit corresponds to the branch prediction update data “11”. Branch prediction update data whose bit value is “1” is output.
[0052]
For example, it is assumed that the branch direction transition table 105-x is selected from the branch direction transition tables 105-1 to 105-m by the s field value. Further, it is assumed that the branch prediction data at this time is “01”.
[0053]
In FIG. 10, the bit string of the transition entry “01” in the branch direction transition table 105-x is “0010”. In the bit string “0010”, the third bit is “1”. The third bit of the bit string corresponds to branch prediction data “10”. Therefore, branch prediction data “10” is output.
[0054]
Note that the bit patterns of the branch direction transition tables 105-1 to 105-m are a bit pattern that is easily changed to the SNT state, a bit pattern that is easily changed to the WNT state or the WN state, and a transition to the ST state. It consists of bit patterns that are easy to perform. Transition weighting is performed by this bit pattern. A branch direction transition table is selected heuristically from the branch direction transition tables 105-1 to 105-m according to the branch history. For example, when there are many “Taken” in the branch history, the branch direction transition table in which the threshold in the ST state and WT state directions is low and the threshold in the SNT state and WNT state directions is set high is selected. When there are many “Not-Takens”, a branch direction transition table in which thresholds in the ST state and WT state directions are high and thresholds in the SNT state and WNT state directions are set low is selected.
[0055]
The multiplexer 107 is supplied with the value of the s field. The multiplexer selectively outputs the output branch prediction data from the branch direction transition table unit 105-x according to the value of the s field.
[0056]
The branch prediction update data selected and output by the multiplexer 107 is supplied to the branch prediction control unit 26. The branch prediction control unit 26 updates the corresponding branch prediction data in the branch history table unit 24 with the branch prediction update data from the multiplexer 107.
[0057]
The updated branch prediction data is supplied to the branch prediction control unit 26 via the multiplexer 25 and used for branch prediction.
[0058]
Further, the branch prediction control unit 26 updates the value of the s field according to the output value of the r field from the branch prediction auxiliary table unit 104. For example, when the ratio of “0” in the value of the r field is greater than a predetermined value, that is, when the number of misses in the branch prediction is greater than the ratio, the value of the corresponding s field is updated. By updating the value of the s field, the branch direction transition table 105-x selected by the branch direction transition table unit 105 is switched . Branch prediction control unit 26 controls the control unit 17 in accordance with the branch prediction data, updates the branch prediction data.
[0059]
FIG. 11 shows an operation flowchart of the branch predicting unit of the embodiment of the present invention.
[0060]
In step S1, it is determined from the branch prediction result from the control unit 17 whether the branch prediction has hit or missed. If it is determined in step S1 that the branch prediction result is a hit, step S6 is executed. In step S6 , the branch history register 22 is updated according to the branch prediction result .
[0061]
If it is determined in step S1 that the branch prediction result is a mistake, step S2 is executed.
[0062]
Step S2 refers to the branch history register. In step S3, it is determined from the reference result of the branch history register whether or not the branch prediction validity rate is equal to or higher than a predetermined validity rate. The correct rate is calculated from the ratio of the bits of “1” in all the bits of the branch history register.
[0063]
In step S3, it is determined whether or not this ratio is equal to or greater than a predetermined value. If it is determined in step S3 that the correct rate is greater than or equal to a predetermined value, the process is terminated. In step S3, when the validity rate is equal to or less than a predetermined value, step S4 is executed.
[0064]
In step S4, an optimum transition entry is selected. In step S4, first, the branch prediction auxiliary table is referred to according to the bit pattern of the branch history register, and the branch prediction auxiliary value corresponding to the bit pattern is acquired. Next, the branch direction transition table is referred to according to the branch prediction auxiliary value, and the optimum transition entry is acquired.
[0065]
In step S5, the optimum transition entry acquired in step S4 is output as branch prediction update data.
[0066]
In step S6 , the branch prediction table unit 24 is updated with the branch prediction update data output in step S5.
[0067]
FIG. 12 is an operation explanatory diagram of one embodiment of the present invention.
[0068]
According to the above operation, the probability of transition from SNT state to WNT state, WNT state to SNT state, WNT state to WT state, WT state to WNT state, WT state to ST state, ST state to WT state can be freely set Can be set.
[0069]
For example, as shown in FIG. 12, the probability of transition from the SNT state to the WNT state is 50%, the probability of transition from the WNT state to the SNT state is 10%, the probability of transition from the WNT state to the WT state is 40%, The probability of transition from the WT state to the WNT state can be set to 20%, and the probability of transition from the WT state to the ST state to ST state to the WT state can be set to 70%. In the transition state of FIG. 12, for example, if the branch prediction hits in the SNT state, the state transitions to the WNT state with a probability of 50 percent.
[0070]
As described above, according to the present embodiment, since a branch direction transition table that reduces branch misses can be used, pipeline bubbles due to branch prediction mistakes in the pipeline processor can be reduced. Therefore, the effective processing performance of the microprocessor can be improved.
[0071]
This example includes the following inventions.
[0072]
6. The branch prediction data correction unit according to claim 5, wherein the branch prediction data correction means selects a predetermined branch prediction change table from a plurality of branch prediction change tables weighted in advance according to the success / failure history of the branch prediction, and the selected branch prediction update An arithmetic unit comprising: reading branch prediction update data corresponding to the branch prediction data from a table and making the branch prediction data.
[0073]
7. The branch prediction data acquisition unit according to claim 5, wherein the branch prediction data correction unit acquires branch prediction data according to the branch instruction from a branch prediction table storing the branch prediction data, and the branch prediction. Branch prediction auxiliary data acquisition means for acquiring branch prediction auxiliary data according to data, and a branch prediction update table corresponding to the branch prediction auxiliary data from a plurality of stored branch prediction update tables having different weights in the direction of transition A branch prediction update table selection unit that selects and outputs branch prediction update data according to the branch prediction data; and a branch prediction table that updates the branch prediction table according to branch prediction update data from the branch prediction update table And an updating means.
[0074]
8. The arithmetic unit according to claim 5, wherein the branch prediction data correction unit sets a weight of a transition direction of the branch prediction data according to preset profile information.
[0075]
【The invention's effect】
As described above , according to the present invention, optimal branch prediction data can be obtained according to the success or failure of branch prediction, so that accurate branch prediction is possible, and the direction of branch prediction according to the branch prediction history. Can be weighted, and accurate branch prediction can be performed quickly.
[Brief description of the drawings]
FIG. 1 is a block configuration diagram of an example of a conventional computing device.
FIG. 2 is a block configuration diagram of an example of a conventional arithmetic device.
FIG. 3 is a block configuration diagram of a branch prediction unit of an example of a conventional arithmetic device.
FIG. 4 is a data configuration diagram of a branch history register as an example of a conventional arithmetic device.
FIG. 5 is a data configuration diagram of a branch prediction table unit of an example of a conventional arithmetic device.
FIG. 6 is an operation explanatory diagram of an example of a conventional arithmetic device.
FIG. 7 is a block diagram of an embodiment of the present invention.
FIG. 8 is a block configuration diagram of a branch prediction unit according to an embodiment of the present invention.
FIG. 9 is a data configuration diagram of a branch prediction auxiliary table unit according to an embodiment of the present invention.
FIG. 10 is a data configuration diagram of a branch direction transition table according to an embodiment of the present invention.
FIG. 11 is an operation flowchart of a branch prediction unit according to an embodiment of the present invention.
FIG. 12 is an operation explanatory diagram of an embodiment of the present invention.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 Computation device 2 Arithmetic device 3 Main memory 4 Hard disk drive 5 Input device 6 Display device 7 Bus 11 Cache memory 12 Instruction fetch unit 13 Instruction decode unit 14 Calculation unit 15 Multiplexer 16 Reorder buffer 17 Control unit 22 Branch history register 23 Index composition circuit 24 branch prediction table unit 25 multiplexer 26 branch prediction control unit 100 arithmetic unit 101 branch prediction unit 102 branch prediction correction circuit 103 profile information table 104 branch prediction auxiliary table unit 105 branch direction transition table units 106 and 107 multiplexers

Claims (5)

In a calculation device that determines branch prediction data indicating a branch prediction state according to a branch prediction result, and performs branch prediction according to the branch prediction data,
A branch prediction table holding the branch prediction data;
A register for holding the branch prediction history;
A branch prediction auxiliary table holding branch prediction auxiliary data corresponding to the branch prediction history;
A branch direction transition table that holds the branch prediction update data;
A control unit for controlling branch prediction,
The control unit reads branch prediction auxiliary data from the branch prediction auxiliary table based on a branch prediction history held in the register,
Read the branch prediction update data from the branch direction transition table based on the branch prediction auxiliary data,
An arithmetic unit that updates the branch prediction table based on the branch prediction update data. The branch direction transition table includes a plurality of tables storing information with different weights of the transition direction of branch prediction,
The arithmetic unit according to claim 1, wherein the control unit selects a table corresponding to the branch prediction auxiliary data from the plurality of tables. The branch prediction auxiliary table holds n-bit data composed of an r-bit field and an s-bit field ,
The r-bit field stores a history of the branch prediction result,
In the field of s bits, a value for selecting the branch direction transition table is stored.
3. The arithmetic device according to claim 1, wherein the s-bit field is updated according to a value of the r-bit field . In a branch prediction method for determining branch prediction data indicating a branch prediction state according to a branch prediction result, and performing branch prediction according to the branch prediction data,
Acquire branch prediction auxiliary data according to the branch prediction history,
Acquiring branch prediction update data according to the acquired branch prediction auxiliary data;
A branch prediction method, wherein the branch prediction data is updated based on the acquired branch prediction update data. The branch prediction method according to claim 4, wherein the branch prediction update data is acquired from a table weighted according to the branch prediction history.

Images