CN101604235B - A Method for Embedded Processor Branch Prediction - Google Patents

Abstract

The invention relates to a method for branch prediction of an embedded processor. The method of the present invention is based on the improvement of the reverse branch prediction mechanism, specifically improving the storage management strategy and index control of the reverse branch prediction mechanism, so that it does not need to clear the original records immediately when it encounters a complex nested cycle, and can make full use of The storage space keeps different nested loop structures and precisely selects the corresponding branch records for prediction. The present invention proposes a dynamic branch prediction mechanism based on the global index method by improving the branch prediction method of the reverse branch prediction mechanism and combining the customized branch target buffer for the specific application environment of the embedded processor. The structure of reverse branch prediction mechanism is improved, and the precise prediction of reverse branch instructions in loop logic is realized.

Description

A Method for Embedded Processor Branch Prediction

technical field

The invention belongs to the technical field of computers and relates to a reverse branch prediction method of a microprocessor.

Background technique

As we all know, branch prediction technology has always been an important method to improve the performance of general-purpose processors. The essence of branch prediction is to overcome instruction control correlation, improve instruction parallelism, and improve processor performance. Both academia and industry have done a lot of research and practice in this regard. Most of the current general-purpose processors use deep pipelines and wide launch mechanisms, and branch prediction is the key supporting technology for both. People are still not satisfied with current processors relying on deep pipelines to increase the main frequency, but at the same time, it should be noted that without a certain depth of pipelines, the processor frequency cannot be too high, and there will be no high performance. At present, the pipeline of general processors jumps between 10 and 30. Yale Pat predicts that wide emission will become the main solution for single-chip integration of 1 billion transistors, and wide emission is also one of the important means to improve the performance of single-chip processors. Recently, Intel's new processor Conroe has increased from the original Pentium's three launches to four launches, making the processor performance increase by 30%. Branch prediction technology is not only used in high-performance general-purpose processors, but also widely used in embedded processors.

Contents of the invention

The object of the present invention is to provide a branch prediction method with low hardware complexity, which can effectively improve the prediction accuracy and improve the performance loss caused by branch instructions in pipeline execution.

The method of the present invention is based on the improvement of the reverse branch prediction mechanism, specifically improving the storage management strategy and index control of the reverse branch prediction mechanism, so that it does not need to clear the original records immediately when it encounters a complex nested cycle, and can make full use of The storage space keeps different nested loop structures and precisely selects the corresponding branch records for prediction.

The inventive method is specifically realized like this:

Step (1). The computer extracts the instruction, and compares the extracted instruction with the record pointed to by the head pointer of the memory stack in the mechanism, and performs operations respectively:

a. If the extracted instruction is an instruction recorded in the improved reverse branch prediction mechanism, send the destination address of the predicted branch instruction as the address of the next instruction to grab the instruction.

b. If the extracted instruction is not an instruction recorded in the improved reverse branch prediction mechanism, the improved reverse branch prediction mechanism does not perform any specific action, and the pipeline executes normally.

Step (2). The instructions extracted in step (1) are processed, specifically:

c. If the extracted instruction is a reverse jump instruction that has been executed in the past, and has produced the effect of predicting the branch in step a, when the instruction matches the instruction that has been recorded in the improved reverse branch prediction mechanism, it means that the improved reverse The prediction to the branch prediction mechanism is correct; if the instruction does not match the instructions recorded in the improved reverse branch prediction mechanism, it means that the prediction is wrong, clear the instructions captured by the improved reverse branch prediction mechanism, and resume the pipeline capture correct instruction address.

d. If the instruction is not the currently predicted reverse branch instruction recorded in the improved reverse branch prediction mechanism, when the execution instruction is decoded and judged as a branch instruction, if the branch instruction is a reverse branch instruction and a jump occurs, judge Whether the destination address of the jump and the jump record corresponding to the outermost nested record index in the improved reverse branch prediction mechanism form a nest. For nested loops, both of them update their corresponding improved reverse branch prediction mechanism space records during the instruction execution phase; otherwise, they are not processed.

Step (3). Execute the command according to the judgment result of step (2). At this time, the index adjustment of the storage gear is performed, which is divided into the following parts:

e. When the reverse branch instruction recorded by the improved reverse branch prediction mechanism is executed again, it is predicted that the jump does occur, and the improved reverse branch prediction mechanism predicts correctly at this time. If there are no other branch instructions to change the program flow, The storage position returns to the innermost layer of the nested loop constructed by the improved reverse branch prediction mechanism; the improved reverse branch prediction mechanism will judge the innermost layer of the nested loop by comparing the jump address of the branch with the original record Afterwards, change the read data index stack head pointer of the read prediction address to make it point to the innermost layer of the nested loop, and keep the rest of the index unchanged.

f. When the reverse branch instruction recorded by the improved reverse branch prediction mechanism is executed again, and its jump is predicted but the jump does not occur because it does not meet the execution conditions, the improved reverse branch prediction mechanism reads the predicted address and reads The head pointer of the data index stack points to the next storage position (that is, points to the next cycle circle) for prediction, and the other indexes remain unchanged.

g. When the instruction passes through the process of the instruction decoding stage, it is confirmed that the instruction is a reverse branch instruction that does not exist in the recording gear of the improved reverse branch prediction mechanism and jumps, and it is found that the instruction is the same as the improved reverse branch instruction through address comparison. The instruction stored in the branch prediction mechanism gear constitutes a nested loop. At this time, if the improved reverse branch prediction mechanism has not been stored in the end gear and a loop occurs, the branch instruction is stored continuously according to the stack tail pointer of the data write index. Into the gear of the improved reverse branch prediction mechanism, and adjust the stack head pointer of the read data indicator to the innermost layer of the nest structure, the current pointer points to the newly created branch gear, and the stack end of the written data indicator The pointer adjusts one notch down.

h. When the instruction passes through the process of the instruction decoding stage, it is confirmed that this instruction is a reverse branch instruction that does not exist in the recording gear of the improved reverse branch prediction mechanism and jumps, and it is found that the instruction is the same as the improved reverse branch instruction through address comparison. The instructions stored in the branch prediction mechanism gear form a nested loop. At this time, if the improved reverse branch prediction mechanism has been stored to the end gear and a cycle occurs, the improved reverse branch prediction mechanism will overwrite the original record from the first gear .

i. If the instruction is a pre-branch instruction and the jump address does not exceed the PC range of the reverse branch stored in the improved reverse branch prediction mechanism, the improved reverse branch prediction after comparing each storage position with the pre-jump address The mechanism will control the head and tail of the stack, and adjust any pointer to the corresponding address.

j. If the instruction is a pre-branch instruction or other non-branch instruction whose jump address exceeds the PC range of the reverse branch stored in the improved reverse branch prediction mechanism, since such behavior will not cause changes to the program flow, the improved The reverse branch prediction mechanism will remain unchanged.

The present invention proposes a dynamic branch prediction mechanism based on the global index method by improving the branch prediction method of the reverse branch prediction mechanism and combining the customized branch target buffer for the specific application environment of the embedded processor. The structure of reverse branch prediction mechanism is improved, and the precise prediction of reverse branch instructions in loop logic is realized.

Description of drawings

Fig. 1 is a large-scale nested loop diagram comprising sub-process calls in the present invention;

Fig. 2 is a diagram of a large-scale nested cycle formed by six groups of six-direction branches in the present invention.

Detailed ways

A method for branch prediction of an embedded processor according to the present invention will be further described below in conjunction with the accompanying drawings and examples.

The specific steps of a method for embedded processor branch prediction are:

Step (1). The computer extracts the instruction, and compares the instruction extracted with the record indicated by the head pointer of the memory stack in the improved reverse branch prediction mechanism, and operates respectively:

a. If the extracted instruction is an instruction recorded in the improved reverse branch prediction mechanism, send the destination address of the predicted branch instruction as the address of the next instruction to grab the instruction.

b. If the fetched instruction is not an instruction recorded in the mechanism, the reverse branch prediction mechanism does not perform specific actions, and the pipeline executes normally.

Step (2). The instructions extracted in step (1) are processed, specifically:

c. If the extracted instruction is a reverse jump instruction that has been executed in the past, and has produced the effect of predicting the branch in step a, when the instruction matches the instruction that has been recorded in the improved reverse branch prediction mechanism, it means that the improved reverse The prediction to the branch prediction mechanism is correct; if it does not match, it means that the prediction is wrong, and the instructions captured by the improved reverse branch prediction mechanism are cleared, and the pipeline is restored to capture the correct instruction address.

d. If the instruction is a currently predicted reverse branch instruction that is not recorded in the improved reverse branch prediction mechanism, when the execution instruction is decoded and judged to be a branch instruction, if the branch instruction is a reverse branch instruction and a jump occurs, Judging whether the destination address of the jump and the jump record corresponding to the outermost nested record index in the improved reverse branch prediction mechanism form a nest, if no nest is formed, it means that the improved reverse branch prediction mechanism has been recorded In the nested loop of , both of them update their corresponding improved reverse branch prediction mechanism space records in the instruction execution stage; if it is other cases, it will not be processed.

Step (3). Execute the command according to the judgment result of step (2). At this time, the index adjustment of the storage gear is performed, which is divided into the following parts:

e. When the reverse branch instruction recorded by the improved reverse branch prediction mechanism is executed again, it is predicted that the jump does occur, and the improved reverse branch prediction mechanism predicts correctly at this time. If there are no other branch instructions to change the program flow, The storage position returns to the innermost layer of the nested loop constructed by the improved reverse branch prediction mechanism; the improved reverse branch prediction mechanism will judge the innermost layer of the nested loop by comparing the jump address of the branch with the original record Afterwards, change the read data index stack head pointer of the read prediction address to make it point to the innermost layer of the nested loop, and keep the rest of the index unchanged.

f. When the reverse branch instruction recorded by the improved reverse branch prediction mechanism is executed again, and its jump is predicted but the jump does not occur because it does not meet the execution conditions, the improved reverse branch prediction mechanism reads the predicted address and reads The head pointer of the data index stack points to the next storage position (that is, points to the next cycle circle) for prediction, and the other indexes remain unchanged.

g. When the instruction passes through the process of the instruction decoding stage, it is confirmed that the instruction is a reverse branch instruction that does not exist in the recording gear of the improved reverse branch prediction mechanism and jumps, and it is found that the instruction is the same as the improved reverse branch instruction through address comparison. The instruction stored in the branch prediction mechanism gear constitutes a nested loop. At this time, if the improved reverse branch prediction mechanism has not been stored in the end gear and a loop occurs, the branch instruction needs to be continuously stored according to the stack tail pointer of the data writing index. Into the gear of the improved reverse branch prediction mechanism, and adjust the stack head pointer of the read data indicator to the innermost layer of the nest structure, the current pointer points to the newly created branch gear, and the stack end of the written data indicator The pointer adjusts one notch down.

h. When the instruction passes through the process of the instruction decoding stage, it is confirmed that this instruction is a reverse branch instruction that does not exist in the recording gear of the improved reverse branch prediction mechanism and jumps, and it is found that the instruction is the same as the improved reverse branch instruction through address comparison. The instructions stored in the branch prediction mechanism gear form a nested loop. At this time, if the improved reverse branch prediction mechanism has been stored to the end gear and a cycle occurs, the improved reverse branch prediction mechanism will overwrite the original record from the first gear .

i. If the instruction is a pre-branch instruction and the jump address does not exceed the PC range of the reverse branch stored in the improved reverse branch prediction mechanism, the improved reverse branch prediction after comparing each storage position with the pre-jump address The mechanism will control the head and tail of the stack, and adjust any pointer to the corresponding address.

j. If the instruction is a pre-branch instruction or other non-branch instruction whose jump address exceeds the PC range of the reverse branch stored in the improved reverse branch prediction mechanism, since such behavior will not cause changes to the program flow, the improved The reverse branch prediction mechanism will remain unchanged.

Through simulation evaluation, it can be concluded that the prediction accuracy rates are 89.4% and 90.9% for the large-scale nested circulation in Fig. 1, respectively. Taking Figure 2 as an example, when encountering interference from other complex structures such as calling subroutines, in the three sets of double-layer nested loops of the main program S1, BL S2 will call the subroutine S2 and encounter other nested loop structures. The reverse branch prediction mechanism needs to clear the existing branch records immediately regardless of whether there are available storage slots, resulting in a decrease in performance, resulting in a prediction accuracy rate of 75.7% for the reverse branch prediction mechanism and the improved reverse branch prediction mechanism. % and 90.8%, resulting in a significant difference.

Claims (1)

1. the method for a branch prediction of embedded processor is characterized in that the concrete steps of this method are:

Step (1). computing machine extracts instruction, and the record of internal memory stack owner pointer indication contrasts in the instruction that will extract and the mechanism, operates respectively:

If the instruction of a. extracting is the instruction of writing down in the improved backward branch forecasting mechanism, the destination address of then seeing the predicted branches instruction off grasps the address of instruction as next instruction;

If the instruction of b. extracting is not the instruction of writing down in the improved backward branch forecasting mechanism, then improved backward branch forecasting mechanism is not done specific action, and pipeline is normally carried out;

Step (2). the instruction to step (1) is extracted is handled, specifically:

If the reverse skip instruction of the instruction of c. extracting for carried out in the past; And produced the effect of predicted branches at step a; The instruction of having write down conforms in instruction and improved backward branch forecasting mechanism, then representes improved backward branch forecasting mechanism prediction correctly; If the instruction of having write down does not conform in instruction and improved backward branch forecasting mechanism, then represent prediction error, remove the instruction that improved backward branch forecasting mechanism grasps, and recover the correct instruction address of pipeline extracting;

If d. instruction is not the backward branch instruction that is recorded in the present prediction in the improved backward branch forecasting mechanism; When executing instruction when decoding is judged as branch instruction; If branch instruction is back when branch instruction and generation jump; Judge whether the pairing jump record of outermost layer nido record index constitutes nido in destination address and the improved backward branch forecasting mechanism of its jump; If not constituting nido then representes to have broken away from the nido loop that improved backward branch forecasting mechanism has write down, the record formation of jumping nido does not constitute nido with the record that jumps, and the two all upgrades the improved backward branch forecasting mechanism spatial registration of its correspondence in the execution phase; If be other situation, then do not process;

Step (3). according to the judged result execution command of step (2), store the index adjustment of gear this moment, be divided into the lower part and carry out:

E. the backward branch instruction that has write down when improved backward branch forecasting mechanism is performed again; Predict that its jump jumps really; This moment, improved backward branch forecasting mechanism prediction was correct; If do not have other branch instruction change program circuit, store gear and get back to the constructed nido circulation innermost layer of improved backward branch forecasting mechanism; Improved backward branch forecasting mechanism will be at relatively this branch's jumping address and original record and after judging nido round-robin innermost layer; The sense data index stack owner pointer that predicted address is read in change makes it point to nido round-robin innermost layer, and it is motionless that all the other indexs keep;

F. the backward branch instruction that has write down when improved backward branch forecasting mechanism is performed again; Predict its jump but when not meeting executive condition and do not take place to jump; Improved backward branch forecasting mechanism is read predicted address sense data index stack owner pointer and is pointed to the next gear that stores to predict, it is motionless that all the other indexs then keep;

G. confirm that through the flow process in instruction decode stage this instruction is a backward branch instruction that is not present in the improved backward branch forecasting mechanism record gear and jump takes place when instructing; And find relatively that via the address the stored instruction of this instruction and improved backward branch forecasting mechanism gear constitutes the nido circulation; At this moment; If improved backward branch forecasting mechanism be not stored into terminal gear and had circulated; Then this branch instruction deposits in the improved backward branch forecasting mechanism gear according to the stack tail pointer that data write index continuously; And the stack owner pointer of sense data index is transferred to nido structure innermost layer, current pointer points to branch's gear of new foundations, and the stack tail pointer of the data target that writes is adjusted a gear downwards;

H. confirm that through the flow process in instruction decode stage this instruction is a backward branch instruction that is not present in the improved backward branch forecasting mechanism record gear and jump takes place when instructing; And find relatively that via the address the stored instruction of this instruction and improved backward branch forecasting mechanism gear constitutes the nido circulation; This moment, improved backward branch forecasting mechanism began to cover original record by initial gear if improved backward branch forecasting mechanism has been stored into terminal gear and has circulated;

I. if instruction does not exceed the PC scope of having deposited backward branch in the improved backward branch forecasting mechanism for preposition branch instruction and jumping address; Improved backward branch forecasting mechanism is with the first stack tail of control stack after respectively storing the preposition therewith jumping address of gear, and pointer is adjusted to corresponding address arbitrarily;

J. if instruction exceeds preposition branch instruction or other non-branch instruction of the PC scope of having deposited backward branch in the improved backward branch forecasting mechanism for jumping address; Because this class behavior can not cause change to program circuit, improved backward branch forecasting mechanism will remain unchanged this moment.

Images