JPH038023A - Branch predicting algorithm - Google Patents

Abstract

PURPOSE:To increase a branch predicting condition and to improve the rate of success for predicting a branch by providing more than three kinds of branch status for a branch predicting algorithm and increasing the history of the branch. CONSTITUTION:The branch is expressed by T and a negative branch is expressed by N. For example, in the case of NTNT, the branch and negative branch are repeated. In such a case, since it can be predicted that the branch and negative branch are repeated in following operation, such a state is predicted as N. The case of TNTN is samely predicted as T. Next, in the case of NNNT, concerning a branch instruction after arithmetic calculation, since the instruction is defined to execute the branch only when a digit flows over, such a state is predicted as N. In the case of TTTN, when a counter is not 0, such a state can be predicted as T and in the case of NNTN, such a state can be predicted as N similary as the case of NNNT. When it is failed to predict NTTN and TNNT, NTTN is transited to TTNN. Accordingly, the next state can be predicted as N and accuracy for predicting is improved in the following operation. Samely, since TNNT is transited to NNTT, the next state is predicted as T and the accuracy for predicting the following branch is improved.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a launch prediction algorithm for a launch target buffer (BTB) that predicts whether or not a launch instruction in an electronic computer will launch.

[Conventional technology]

Figures 3 and 4 show the past 2
FIG. 2 is a diagram illustrating a launch prediction algorithm that executes a launch prediction of a launch instruction based on the branch status data of the first instruction.

Next, the operation will be explained.

First, before explaining this algorithm, we will use Fig. 5 to refer to the launch target buffer (hereinafter referred to as "plant target buffer").

(referred to as BTB) will be explained.

This BTB is a cache memory that stores the branch destination address of a branch instruction under pipeline control.

Normal cache memory basically uses address play,
It consists of an address comparison circuit and a data array, but E
TE is almost the same address array.

It consists of an address comparison circuit, a plant prediction circuit, and a data array. The only difference is that a plant prediction circuit has been added. The address array of the BTB stores the plant instruction address.

The data array stores the plant destination address and the plant status indicating the past plant history. The plant status is the data (“NT” “TN” “NN” ”.

“TT”).

The plant prediction circuit is activated under the following conditions.

When the address in the address array matches the memory requested address (at the time of BTEbtt).

Read plant status from data array.

Predict whether or not the plant command will plant.

If you want to plant, access the cache memory using the data array's plant destination address.

If the branch instruction is not executed, the branch instruction address is directly sent to the cache memory, and if the branch instruction is executed, it becomes clear whether or not the branch prediction was correct. At this point, the plant status section of the BTB's data array is updated.

The present invention relates to a launch prediction algorithm for predicting whether or not a branch instruction in a launch prediction circuit will launch.

In FIG. 3, FIG. 1, and FIG. 5, the plant status is 2 bits. The launch history of the Tsumeshi launch prediction is data regarding the latest two times.

Next, a conventional plant prediction algorithm will be explained using FIG.

This is because the plant status is 2 bits.

There are four states. “TT“TN” “NT””N
It is N'. Regarding “TT” “NN”, past 2
Since the planch situation in the first round is the same, it can be predicted that the same will happen in the ninth time. Therefore, the plant status is “T”.
If T'', it is predicted to be T'' and a toe plank is predicted. Further, if the plant status is "NN-, @N" is predicted, and it is predicted that the plant will not plant.

If the plant status is @TN“”NT-.

It is difficult to predict what will happen next. Both "N" and "T" can be predicted, but in the case of FIG. 3, the result will be the same as when there is one plant status. I predict that the situation will be similar to the last time's situation next time. Also.

The difference between FIG. 4 and FIG. 3 is that 1T# is predicted in the case of "@TN". In this way, two branch statuses are used to perform the branch prediction of the branch instruction.

[Problem to be solved by the invention]

Since there are only two plant statuses in the conventional plant prediction algorithm using two plant statuses, if the situation between the previous plant history and the previous one is different (“NT”, “TN”), the plant prediction is successful. There were 9 problems with low rates.

This invention has been made to solve the above-mentioned problems, and the object is to obtain a launch prediction algorithm that increases the success rate of the launch prediction.

[Failure to solve the problem]

The plant prediction algorithm according to the present invention is as follows.

The conditions for predicting a launch are established by setting the number of launch statuses to three or more and increasing the launch history.

[Effect] The plant prediction algorithm in this invention is as follows.

Since the branch prediction of the branch instruction is performed based on three or more past branch histories, the success rate of the branch prediction is further increased.

〔Example〕

The plant prediction algorithm of the present invention is shown in FIG.

Those surrounded by 16 circles indicate 4 past plant histories. The left side is the oldest. For example, “NTTN
=f is @N'! >Ul- is also old (', -T"7>E is the second oldest, "T" is the third oldest, and "N" is the previous plant history.

The arrows represent state transitions, and after the launch command is executed, if a launch occurs, the state transitions to the state shown by "↓", and if the plant does not launch, the state changes to the state shown by "N". Also, regarding the plant history surrounded by 16 circles,
It shows how to predict planches. For example, in the case of "TTTT", it is predicted that the next time it will be "T" (it is predicted that the next time) will be "T".

Broadly speaking, plant instructions can be divided into two types.

(1) Unconditional plant command (always plant) (2)
Conditional plant instruction (plant when conditions are met) The most important aspect of the plant prediction algorithm is how accurately it can predict the plant of the conditional plant instruction (2). For this reason, a plant is predicted by looking at past plant history and determining whether a plant is likely to occur or not based on the history pattern. The basic principle of this determination is that if two or more histories are the same going back up from the latest history, the first history will also be the same. For example, "NTTT" is predicted as @T-, and "NTIJ" is predicted as @T-.
N” is predicted to be “N”.

Note that the most difficult one of the determinations is the branch prediction when two histories reversed from the latest history are different.

The present invention was devised to improve prediction accuracy in this case. for example.

In the case of "-NTNT", the state of launching and not launching is repeated. This is expected to repeat in the future. Therefore, it can be predicted that "N"."TNIJ
“ can be predicted as “T” in the same way. If the algorithm in Figure 3 is used, “T” is predicted in the case of “NT”, and “T” is predicted as “T”.
In the case of "N", it is predicted to be "N", so it can be expected that the 100-chip launch prediction will be unsuccessful.

In Figure 4, in the case of “NT”, “T” is predicted, and “TN”
Since we predict “T” in the case of , the plant prediction is 50
It is expected that the probability will be %.

Next, in the case of "NNNT", 1 regarding the branch instruction etc. involved after arithmetic addition, for example, Over FI Ow:
BOR (Prunch when 9 digits are out of order) It is predicted that this is a plank instruction that only executes when 9 digits are out of order. Therefore, fC is predicted to be "N", but in FIGS. 3 and 4, "NT" is predicted to be "T".

Similarly, in the case of K"TTTN", Branch
C! As in the 0unt (BOT) instruction, the counter is
It can be predicted that the command will be a launch command such as "If not, then launch. Therefore, the ninth instruction is predicted to be °T". Regarding FIGS. 3 and 4, in the case of "TN", "N" is predicted in FIG. 3, and "T" is predicted in FIG. 4.

In the case of "NNTN", it is considered that the history is caused by a plant instruction similar to "NNNT'" explained above.

Therefore, it is predicted to be N''.

-TTNT" is considered to be a launch instruction similar to "TTTN", and can be predicted as "T".

"NTTN" In the case of "TNNT", it can be predicted that it is a regular plant instruction. For example, Branch 0own
It can be predicted like a counter-using instruction such as the t instruction (BOT). Therefore, in the case of "NTTN", it is predicted as °T", and in the case of "TNNT", it is predicted as °N".

Prediction of this “NTTN” is the most difficult, but if the prediction fails, “NTTN” becomes “τTNN”
Since it has transitioned to , it is predicted to be 'N'' in the 9th order, and the prediction accuracy from the 9th time onwards increases.Similarly.

@TNNT” changes to @NNTT”, so the first time is “
T'' is predicted, and the accuracy of plant prediction after the first time also increases.

In this way, using 4 plant statuses, 5
It becomes impossible for a prediction to fail with a probability of 0% or more.

Next, the case of three past plant histories will be explained using FIG.

The past two plant statuses are @NN” or “TT”
", the next status is similarly predicted to be "N" or "T".

Other 'NTN''NNT''TTN',”
TNT' is determined by majority vote. Therefore, NTN″ −NNT′ is predicted to be −N−, and “TTN
``'', ``TNT-'' predicts ``T''.

In addition, in the above embodiment, the plant status is set to 4.
Alternatively, the number is limited to three, but basically any number is acceptable as long as it is three or more.

Further, in the above embodiment, the plant status is expressed by "Y" and "N", but it may be expressed by other methods such as "1" and O" or "Y" and N". moreover.

Regardless of the size of these bits or bytes.

Moreover, the format does not matter, and it does not matter what form it is held in memory.

〔Effect of the invention〕

As described above, according to the present invention, since the plant prediction is performed using three or more pieces of plant history information such as the plant status, there are few uncertainties in the prediction, and highly accurate plant prediction can be performed.

[Brief explanation of drawings]

Figures 1 and 2 are diagrams each explaining a launch prediction algorithm using three or more launch statuses, which is an embodiment of the present invention, and Figures 3 and 4 are diagrams illustrating a conventional launch prediction algorithm using two or more launch statuses. FIG. 5 is a diagram showing a conventional plant prediction algorithm.

Claims (1)

[Claims] In a plant prediction algorithm that uses plant history information to predict whether or not a plant instruction will plant during computer operation, where a plant is represented by "T" and a no-plant is represented by "N", the following applies. A plant prediction algorithm characterized by comprising means (a) means for predicting the next action as "T" when the two latest plant history information of a certain plant instruction are "TT"; (b) (c) means for predicting the next operation as "N" when the two latest plant history information of a certain plant instruction are "NN"; (c) means for predicting the next operation as "N" when the two latest plant history information of a certain plant instruction are "TT"; and "NN", means for predicting the next operation using previous launch history information.