CN102567137B

CN102567137B - System and method for restoring contents of RAT (register alias table) by using ROB (reorder buffer) when branch prediction fails

Info

Publication number: CN102567137B
Application number: CN 201010607215
Authority: CN
Inventors: 杨思博
Original assignee: BEIJING GUORUI ZHONGSHU TECHNOLOGY CO LTD
Current assignee: BEIJING GUORUI ZHONGSHU TECHNOLOGY CO LTD
Priority date: 2010-12-27
Filing date: 2010-12-27
Publication date: 2013-09-25
Anticipated expiration: 2030-12-27
Also published as: CN102567137A

Abstract

The invention relates to a system and method for restoring contents of an RAT (register alias table) by using an ROB (reorder buffer) when branch prediction fails. The system for restoring the contents of the RAT by using the ROB when the branch prediction fails, provided by the invention, comprises a timing device which is used for generating an update signal for instructing the RAT to perform update operation and mapping relation restoring modules corresponding to each table item in the RAT, wherein each mapping relation restoring module comprises a comparator corresponding to each ROB item, an intra-group looking-up device corresponding to each group of the ROB items, an inter-group multiple selection device for multiple groups of the ROB items, a looking-up device in special groups, aglobal looking-up device and an RAT item restoring device. According to the system provided by the invention, the RAT can be effectively restored. The invention further provides the method for restoring the contents of the RAT by using the ROB when the branch prediction fails.

Description

When failing, branch prediction use ROB to recover the system and method for RAT content

Technical field

The present invention relates to the micro-processor architecture technical field, be particularly related to a kind of resequencing buffer (ReOrder Buffer that when branch prediction is failed, uses, abbreviate ROB as) recover the system of register alias table (Register Alias Table abbreviates RAT as) content.

Background technology

Modern micro-processor architecture has adopted superscale (Super Scale) technology mostly, improves the program execution performance by the method for carrying out many instructions at one-period simultaneously.Want in one-period, can carry out many instructions, just need to solve the relativity problem between instruction.It is relevant relevant with data that the correlativity of instruction is divided into control.Wherein data are relevant is divided into not only read-after-write (RAW) relevant (but also claiming that true data is relevant), writeafterread (WAR) relevant (claim not only spurious correlation) relevant with write after write (WAW) (but also claiming structurally associated) three kinds.Register renaming (Register Renaming) technology is by being mapped to same logic register the mode of a plurality of physical registers, the operating writeafterread of the program that solved (WAR) has improved the concurrency of instruction greatly with to write (WAW) data relevant.

In general, the physical register that is used in rename for the logic register branch is by register alias table RAT(Register Alias Table) realize.Kept the up-to-date mapping relations of current time logic register and physical register among the RAT, RAT comes addressing with the logic register address, and the data (that is the content of RAT list item) of its storage are logic register corresponding physical register addresss.In other words, any time in the microprocessor operation, a logic register is arranged to the mapping relations of physical register, and RAT is exactly the module of preserving these mapping relations.By using logic register address search RAT just can know to be which physical register represents this logic register, to use this logic register will from this physical register, read data as the instruction of source operand current; Be used for preserving this target operand and use this logic register can obtain the physical register of a free time as the instruction of target operand, to revise the corresponding list item of this logic register in RAT simultaneously, change its corresponding physical register address into idle physical register address that this instruction obtains, instruction after this instruction will be read from amended physical register address if read this logic register.

In order to guarantee that microprocessor can return accurately unusually, the order that adopts the microprocessor of out of order execution technique to use resequencing buffer ROB (ReOrder Buffer) to carry out according to instruction is preserved the information of the instruction of carrying out, and the order that complete instruction is carried out according to instruction is submitted to.So-called submission is that expression confirms that the instruction before instruction and this instruction is all complete, and the microprocessor of out of order execution is in agreement in presentation stage with the execution result of the programming model that order is carried out.Resequencing buffer ROB recovers instruction a kind of hardware configuration of order originally for the out of order back of carrying out, to reach the purpose that instruction results is submitted in proper order.Can regard resequencing buffer as a storehouse FIFO who comprises head pointer and tail pointer.When every instruction enters streamline, according to program at first the order all in resequencing buffer, occupied row clauses and subclauses successively, wait the instruction be finished, submit instruction successively to according to the order of first-in first-out.When interruption or abnormal behaviour take place, also can recover original execution sequence.

Register renaming has two kinds of main implementations, and a kind of is that physical register is divided into two kinds in architecture register and rename register.Wherein architecture register and logic register are one to one, expression be the state that the back logic register is submitted in instruction to; Rename register and logic register can be many-to-one mapping relations, the execution result of temporarily holding instruction before instruction is submitted to.The target logic register of instruction is assigned with a rename register when register renaming, and complete back target operand can be write back in the architecture register from the rename register, and the rename register can be released.In this manner, though each logic register and its corresponding RAT list item can corresponding a plurality of rename registers, but have only an architecture register corresponding with it, when microprocessor resetted, the content of each RAT list item just was reset the address of the architecture register corresponding with it.Another kind of implementation is physical register not to be divided into regularly architecture register and rename register, and adds the mapping relations that an architecture register mapping table is preserved physical register and architecture register outside RAT again.Instruction is assigned with a free time when register renaming physical register is used for preserving target operand, and this physical register address can be written into architecture register mapping table and be confirmed to be architecture register when submitting to.The physical register that is considered to architecture register can not be used for register renaming and be replaced out architecture register mapping table up to it by other physical register, and this moment, this physical register became the rename register of a free time again.In this manner, each logic register can be set up corresponding relation with any one physical register when microprocessor moves, but each logic register still has a corresponding physical register as its acquiescence architecture register, when microprocessor resetted, the content of each RAT list item just was reset the address of the acquiescence architecture register corresponding with logic register.

These two kinds of implementations hereinafter also can be mentioned, and in order to explain simplification, above-mentioned first kind of mode called rename implementation A, and above-mentioned the 2nd kind of mode called rename implementation B.

Modern microprocessor has also used branch prediction (Branch Predict) technology simultaneously and has inferred (Speculation Execution) technology of execution, make the instruction of not determining branch to be loaded and to carry out by microprocessor in advance, the control that solves instruction thus is relevant.But this has produced a problem: if the branch prediction mistake, infer that then the instruction of carrying out also will be cancelled, the physical register that distributes for them when register renaming will be retracted, and therefore the mapping relations of the logic register of preserving in RAT and physical register will be restored to the state of the instruction of inferring execution error before carrying out.

A kind of simple method is that branch instruction arrival presentation stage judges whether prediction is correct again by the time, because representing the state of microprocessor, the submission of instruction confirms, if find the branch prediction mistake of instruction this moment, can directly cancel all instructions of carrying out in the instruction.For first kind of above-mentioned register renaming implementation, i.e. rename mode A, RAT will be restored to the state after microprocessor resets, and namely all list items of RAT all are to point to and they architecture registers one to one.And for second kind of above-mentioned register renaming implementation, i.e. rename mode B directly copies the content of architecture register mapping table the recovery that just can realize among the RAT RAT.The realization of this method is very simple, but in the microprocessor of out of order execution, submit to and may need a lot of cycles from the instruction instruction that is finished, if the correction to the branch prediction mistake is placed on presentation stage to be carried out, during this period of time, microprocessor is always in the address value from mistake before then arriving submission after the branch instruction execution, and these instructions will be cancelled, this is equivalent to be wasted during this period of time, has reduced performance of processors.

The method of recovery RAT commonly used is for each fundamental block an independent RAT to be set, instruction address in the fundamental block is continuous, and branch instruction is that the last item of fundamental block instructs (if microprocessor has the Tapped Delay groove, the instruction that postpones so in the groove is exactly the interior the last item instruction of fundamental block), instruction at the destination address place of branch instruction (no matter whether branch takes place) is in the different fundamental blocks with this branch instruction, and RAT also can switch when fundamental block switched.Kept a RAT for each fundamental block in the microprocessor like this, when microprocessor is found the branch prediction mistake, can switch back the corresponding RAT of that branch instruction target place fundamental block of prediction error, the mapping relations of logic register with regard to the branch instruction that turned back to prediction error (for some architecture, also comprising the instruction that postpones in the groove) by the state after the rename.

This method need arrange a plurality of RAT, and will carry out the switching of RAT to a branch instruction whenever, and also will switch during prediction error.RAT is made up of timing unit, clock need be arranged and constantly be in energising (power on) state, has increased power consumption.And when register renaming, need select to use the result of which RAT and which RAT the state after the rename be write back among the sequential expense when also having increased rename.

Summary of the invention

The object of the invention is to overcome the deficiency on power consumption and sequential of prior art, the free time utilization is started working to the rename unit again from discovery branch prediction mistake, according to the information of having preserved among the ROB, uses pure combinational logic to recover RAT.Owing to only when the branch prediction mistake, work, and in most of the cases branch prediction success ratio of Modern microprocessor very high (greater than 95%), pure combinational logic does not have clock signal again, so can reduce dynamic power consumption.And owing to do not need extra preservation information, this part circuit can be in the shutdown state when not working, so also can reduce quiescent dissipation.Because have only a RAT, when operating, rename do not need to select according to fundamental block, therefore on sequential, also improve.

According to a first aspect of the invention, a kind of system that uses resequencing buffer ROB to recover register alias table RAT content when branch prediction is failed is provided, all ROB items are divided into a plurality of groups according to its address, the ROB item that each group comprises the ROB item of predetermined number and described predetermined number does not have between mutually overlapping, and described system comprises:

Upgrade the timing device of the update signal of operation for generation of indication RAT;

Mapping relations corresponding to each list item among the RAT are recovered module, and wherein each mapping relations recovery module comprises:

Correspond respectively to the comparer of each ROB item, the target logic address that is kept in each ROB item is compared and export the two comparative result that whether equates of indication with the corresponding logic register of this mapping relations recovery corresponding RAT list item of module address, and the target logic address that wherein is kept in each ROB item equates with the target logic register address of the corresponding instruction of this ROB item;

Search device in the group corresponding to each group of ROB item, it receives comparative result of the corresponding comparer output of ROB item in each group, searches and export lookup result in these comparative results;

Be used for multi-selection device between a plurality of groups group of ROB item, group for the ROB tail item place of selecting the ROB item, described ROB tail item is that the corresponding ROB item of branch instruction that makes a mistake is (for the microprocessor that the Tapped Delay groove is arranged, be the instruction that postpones in the groove), and export the comparative result of the comparer in the group of group at this ROB tail item place;

Search device in the specific group, receive the comparative result of the output of multi-selection device between described group, and based on the comparative result of multi-selection device output between described group the comparative result of the comparer in the group of described ROB tail item place is searched, and the output lookup result;

The global search device, be used in described group, searching the final lookup result of lookup result output of searching device output in the lookup result of device output and the described specific group, whether described final lookup result indication also has its target logic address and this mapping relations to recover the ROB item that the corresponding logic register of the corresponding RAT list item of module address equates in ROB, and the address of the ROB item of the instruction that equates with described target logic address corresponding to its target register address that should be performed the latest in its target logic address and these ROB items that the corresponding logic register of this mapping relations recovery corresponding RAT list item of module address equates;

RAT list item recovery device receives the final lookup result of global search device output, exports these mapping relations and recovers the content that physical register address that the corresponding RAT list item of module preserves should be resumed.

According to system of the present invention, wherein in the process that described ROB item is divided into groups, address of the ROB item in each group is adjacent, and in all ROB items each all and only in a group.

According to system of the present invention, when the count value of the counter in the described timing device reaches predetermined value, this timing device sends update signal and recovers module output with indication RAT according to the corresponding mapping relations of its each list item and upgrade the original physical register address of being preserved of each RAT list item, and the timing of wherein said timing device is no more than when generation branch prediction mistake microprocessor reloads instruction from new address time.

According to system of the present invention, whether the target logic address that the comparative result of wherein said comparer output indicates the corresponding ROB item of this comparer to store is recovered the corresponding logic register of the corresponding RAT list item of module address with the mapping relations at this comparer place and is equated, if the corresponding ROB item of this comparer is cancelled, then comparative result is designated as unequal.

According to system of the present invention, whether search device in wherein said group has the comparative result of the corresponding comparer of ROB item to be designated as equal according to the ROB item address in its corresponding group by the sequential search that maximum in the group is decremented to minimum in the group, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, the signal of success is searched in signal and the indication of the position of that ROB item in group that the output indication is found at first, otherwise failure signal is searched in the output indication.

According to system of the present invention, multi-selection device is selected the group at ROB tail item place according to amended ROB tail pointer between wherein said group from existing ROB grouping.

According to system of the present invention, in not having the microprocessor of branch delay slot, amended ROB tail pointer points to the corresponding ROB item of branch instruction of prediction error; In the microprocessor of branch delay slot was arranged, amended ROB tail pointer pointed to the corresponding ROB item of instruction that postpones in the groove.

According to system of the present invention, search the output result of multi-selection device between device reception group in the wherein said specific group, and be starting point with described ROB tail item, whether there is the comparative result of the corresponding comparer of ROB item to be designated as equal according to the descending sequential search in ROB item address, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, then output indicates signal and the indication of the position of that ROB item in group of finding at first to search the signal of success, otherwise failure signal is searched in the output indication, wherein will can not searched greater than the comparative result of the comparer of the ROB item of ROB tail item address corresponding to its address.

According to system of the present invention, wherein said global search device is at first searched successful signal whether according to the indication of searching the output of device in the described specific group and is judged that searching the comparative result whether device found comparer in the specific group is designated as equal ROB item, if find, just the signal of success is searched as output and output expression in the address of searching the ROB item that device finds in the specific group, be designated as equal ROB item if search the comparative result that device do not find comparer in the specific group, then according to instructing the direction that enters ROB successively, the next one of judging selected group of multi-selection device between group is organized and is searched the comparative result whether device found comparer in corresponding group and be designated as equal ROB item, if find, the signal of success is searched as output and output indication in the address of searching the ROB item that device finds in this group, if do not find, continue to judge the result who searches device in the next group, till being recycled to the ROB group that multi-selection device finds between group, whether the global search device was searched and was searched device in the group of the selected ROB group of multi-selection device between group and find the comparer comparative result to be designated as equal ROB item this moment, if find, the signal of success is searched as output and output indication in the address of this ROB item, otherwise failure signal is searched in global search device output indication, and finishes to search.

According to system of the present invention, if wherein the signal of success is searched in the output indication of global search device, then described RAT list item recovery device adds one and this position is made as ' 1 ' content to be resumed as the physical register address of being preserved in this RAT list item again with the front, ROB item address of described global search device output; If failure signal is searched in the output indication of global search device, then RAT list item recovery device just with the corresponding RAT list item of this mapping relations recovery module the address of the corresponding architecture register content that be resumed as the physical register address of preserving in this RAT list item.

According to system of the present invention, the structure that wherein said each mapping relations are recovered module is identical.

According to system of the present invention, search the difference of searching device in device and the specific group in wherein said group and be, search in the group device search to as if fixing, and irrelevant with amended ROB tail pointer; And search the group at the ROB tail item place of searching to as if from all existing ROB groups, being selected according to amended ROB tail pointer by multi-selection device between group of device in the specific group, and be starting point with ROB tail item when searching, its address can not searched greater than the ROB item of the address of ROB tail item.

In the present invention, the employed target logic of the corresponding comparer of each ROB item address also is present among the ROB in the microprocessor that adopts recovery RAT method commonly used, is used for when instruction is submitted to register renaming being confirmed.The present invention just is used for RAT again with these information and recovers, and does not have additionally to preserve these contents for ROB increases new hardware.

According to a further aspect in the invention, a kind of method of using resequencing buffer ROB to recover register alias table RAT content when branch prediction is failed is provided, all ROB items are divided into a plurality of groups according to its address, the ROB item that each group comprises the ROB item of predetermined number and described predetermined number does not have between mutually overlapping, said method comprising the steps of:

(I) be provided for producing the update signal that indication RAT upgrades operation;

(II) the target logic address of preserving in each ROB item is compared with the corresponding logic register of the RAT list item address that will be resumed and defeated indication the two whether equate go out comparative result, the target logic address that wherein is kept in each ROB item equates with the target logic register address of the corresponding instruction of each ROB item;

(III) to each group of ROB item, the corresponding comparative result of each ROB item in this group is searched, and the output lookup result;

(IV) select the group at the ROB tail item place in the ROB item, described ROB tail item is the corresponding ROB item of branch instruction that makes a mistake, and exports the corresponding comparative result of each ROB item in the group of group at this ROB tail item place;

(V) based on the corresponding comparative result of each ROB item in the group of the group at described ROB tail item place, the comparative result of the comparer in the group of described ROB tail item place is searched, and the output lookup result;

(VI) based on the final lookup result of the output of the lookup result in the lookup result in the step (III) and the step (V), the ROB item whether described final lookup result indication also has its target logic address to equate with the corresponding logic register of the RAT list item address that will be resumed in ROB, and the address of the ROB item of the instruction that in its target logic address and these ROB items that the corresponding logic register of the RAT list item address that will be resumed equates, equates with described target logic address corresponding to its target register address that should be performed the latest;

(VII) based on the final lookup result in the step (VI), upgrade the content that physical register address that RAT list item that the update signal output of operation will be resumed preserves should be resumed according to the indication RAT in the step (I).

The method according to this invention, wherein in the process that described ROB item is divided into groups, address of the ROB item in each group is adjacent, and in all ROB items each all and only in a group.

The method according to this invention, wherein use timing device to provide indication RAT to upgrade the update signal of operation, when the count value of the counter in the described timing device reaches predetermined value, this timing device sends update signal and upgrades the original physical register address of being preserved of each RAT list item with the output that indication RAT recovers module according to the corresponding mapping relations of its each list item, and the timing of wherein said timing device is no more than when generation branch prediction mistake microprocessor reloads instruction from new address time.

The method according to this invention, wherein step (II) further comprises the signal whether output indication ROB item the target logic address of storing and the corresponding logic register of the RAT list item address that will be resumed equate, if the ROB item is cancelled, then output indication comparative result is unequal signal.

The method according to this invention, wherein step (III) comprises further whether the address according to the interior ROB item of each group of ROB item has the corresponding comparative result of ROB item to be designated as equal by the sequential search that maximum in the group is decremented to minimum in the group, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the corresponding comparative result of a plurality of ROB items to be designated as equal, the signal of success is searched in signal and the indication of the position of that ROB item in group that the output indication is found at first, otherwise failure signal is searched in the output indication.

The method according to this invention, wherein step (IV) further comprises according to amended ROB tail pointer, selects the group at ROB tail item place from existing ROB grouping.

The method according to this invention, wherein said amended ROB tail pointer points to described ROB tail item, when the branch prediction mistake, according to branch's formation the ROB tail pointer is made amendment, in not having the microprocessor of branch delay slot, amended ROB tail pointer points to the corresponding ROB item of branch instruction of prediction error; In the microprocessor of branch delay slot was arranged, amended ROB tail pointer pointed to the corresponding ROB item of instruction that postpones in the groove.

The method according to this invention, wherein step (V) comprises that further with described ROB tail item be starting point, whether there is the comparative result of the corresponding comparer of ROB item to be designated as equal in the group according to descending sequential search ROB tail item place, ROB item address, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, then output indicates signal and the indication of the position of that ROB item in group of finding at first to search the signal of success, and wherein its address will can not searched greater than the corresponding comparative result of ROB item of ROB tail item address.

The method according to this invention, wherein step (VI) further comprises according to the indication of output in step (V) searching whether whether successful signal is judged has been found the corresponding comparative result of ROB item to be designated as equal ROB item in step (V), if find, just with this corresponding address of ROB item as output, if in step (V), do not find the corresponding comparative result of ROB item to be designated as equal ROB item, then according to instructing the direction that enters ROB successively, whether judge in the next one group of group at ROB tail item place has found the comparative result of ROB item correspondence to be designated as equal ROB item, if find, the signal of success is searched as output and output indication in that corresponding address of ROB item of finding at first in this group, if do not find, continue to judge that next group has not found the comparative result of ROB item correspondence to be designated as equal ROB item, till the group that is recycled to ROB tail item place, judge in the group of ROB tail item place whether found the comparative result of ROB item correspondence to be designated as equal ROB item this moment, if find, the signal of success is searched as output and output indication in the address of that ROB item of finding at first in this group, otherwise failure signal is searched in the output indication, and finishes to search.

The method according to this invention, if wherein the signal of success is searched in output indication in step (VI), then the front, ROB item address that will export in step (VI) is adding one and this is made as ' 1 ' content to be resumed as the physical register address of being preserved in this RAT list item; If failure signal is searched in output indication in step (VI), then with this RAT list item the address of the corresponding architecture register content that be resumed as the physical register address of preserving in this RAT list item.

The method according to this invention, wherein the difference of step (III) and step (V) is, in step (III) search to as if fixing, and irrelevant with amended ROB tail pointer; And the group at the ROB tail item place of searching to as if from all existing ROB groups, selecting according to amended ROB tail pointer in step (V), and when searching, be starting point with ROB tail item, its address can not searched greater than the ROB item of the address of ROB tail item.

The present invention has following advantage:

1. the present invention does not increase other sequential logic except timing device, but has utilized the original information of ROB.Owing to only when branch prediction fail, just work, when not working, the input of institute can be fixed (such as with ' 0 ' and all signals do and operate), perhaps power supply is turned off, thus the reduction power consumption.

2. the time that microprocessor reloaded instruction when the present invention utilized the branch prediction mistake from new address carries out RAT and recovers, and does not have visible time overhead.And owing to have only a RAT, therefore steering logic is fairly simple when register renaming, and the sequential expense is little.

Description of drawings

Fig. 1 is ROB and the RAT synoptic diagram of embodiments of the invention.

Fig. 2 is the overall construction drawing of embodiments of the invention.

Fig. 3 is that the mapping relations described in the embodiments of the invention are recovered module diagram.

Fig. 4 is the ROB view after the cancellation instruction when the branch prediction mistake takes place according to the embodiment of the invention.

Fig. 5 is the ROB view after the cancellation instruction when the branch prediction mistake takes place according to the embodiment of the invention.

Fig. 6 is for using resequencing buffer ROB to recover the process flow diagram of the method for register alias table RAT content when branch prediction is failed according to of the present invention.

Embodiment

Below in conjunction with the drawings and specific embodiments the present invention is described in further detail:

In the present embodiment, microprocessor has 32 logic registers (Logical Register abbreviates LR later on as), and numbering is respectively LR0～LR31.Wherein LR0 is read-only register, and its value perseverance is 0, in actual applications, does not need LR0 is done rename operation, so actual what will carry out the rename operation is these 31 logic registers of LR1～LR31.RAT comprises 31 list items, corresponds respectively to the address of these 31 logic registers of LR1～LR31, and the content of list item is the address of these 31 corresponding physical registers of logic register of current LR1～LR31.

Present embodiment adopts rename implementation A, architecture register (Architectural Register, abbreviate AR later on as) there are 31, be numbered AR1～AR31, correspond respectively to these 31 logic registers of LR1～LR31, and rename register (Rename Register, be called for short later on RR) corresponding one by one with the ROB item, ROB has 32, and relative have 32 rename registers, be numbered RR0～RR31, correspond respectively to these 32 ROB items of ROB0～ROB31.The physical register address has 6, wherein most significant digit represents that this physical register belongs to architecture register or rename register, when most significant digit is 0, represent that this physical register is architecture register, and when most significant digit is 1, represent that this register is the rename register, 5 of the back of physical register address are the numbering of this physical register in architecture register group or rename register group.Specifically, physical register address 000001～011111 corresponds respectively to architecture register AR1～AR31, physical register address 100000～111111 corresponds respectively to rename register RR0～RR31, and because logic register LR0 does not have the corresponding physical register, so physical register address 000000 is address blank, do not correspond to any physical register.In the ROB item, there is a special zone to preserve the corresponding logic register of the target operand address of the instruction in this ROB item, the logic register address has 5, wherein 00001～11111 distinguishes corresponding LR1～LR31, because the value perseverance of LR0 is 0, so LR0 is nonsensical as target operand, therefore the logic register address 00000 that is kept in the ROB item also is an address blank, represent that instruction in this can not write back object run and count in the physical register, when microprocessor resets, logic register address in all ROB items all is set as 00000, and when the instruction in the ROB item was cancelled or is submitted, this logic register address also was set as 00000.

The view of Fig. 1 ROB that is present embodiment when the branch prediction failure does not take place and RAT, wherein the left side is the logic register address among the ROB, the right side is the content of RAT.ROB12～ROB20 is effective ROB item, and RAT1～RAT31 has represented the mapping relations of LR1～LR31 and physical register respectively.Be example with LR6, the target logic register address of ROB12 and ROB16 all is LR6, and what then keep among the RAT6 is that the up-to-date mapping relations of LR6 are that RR14(represents the corresponding physical register of ROB14).And be not exactly the address of the corresponding architecture register of this logic register by the content of the corresponding RAT list item of the logic register that instruction used in the ROB formation, be exactly AR5 such as the content of RAT5.And do not have the ROB item at the instruction place of target logic register, such as the ROB item that is not used at present outside ROB18 and the ROB formation, such as ROB11, their logic register address all is 00000.

In the present embodiment, mapping relations are recovered module and according to the address of ROB item ROB are divided into 8 groups, the 0th group of corresponding to ROB the 0th～3, and its address is 00000～00011; The 1st group of corresponding to ROB the 4th～7, its address is 00100～00111; The 2nd group of corresponding to ROB the 8th～11, its address is 01000～01011; The 3rd group of corresponding to ROB the 12nd～15, its address is 01100～01111; The 4th group of corresponding to ROB the 16th～19, its address is 10000～10011; The 5th group of corresponding to ROB the 20th～23, its address is 10100～10111; The 6th group of corresponding to ROB the 24th～27, its address is 11000～11011; The 7th group of corresponding to ROB the 28th～31, its address is 11100～11111.Can see that from top description the 4th～2 of ROB item address is exactly the numbering of group, and the 1st～0 of ROB item address can be used as numbering in the group.Such as ROB7, the address is 00111, the 4～2, and to be 001, the 1～0 be 11, namely the 1st group the 3rd.And ROB29, the address is 11101, the 4～2, and to be 111, the 1～0 be 01, namely the 7th group the 1st.From above-mentioned packet mode as can be seen, the address of ROB item in each group is adjacent, and in all ROB items each all and only in a group.

Fig. 2 is that the course of work of present embodiment when branch prediction is failed is (simple in order to represent, all mapping relations of not drawing among Fig. 2 are recovered the relation of module and ROB item, but writing back the address, the logic register of all ROB items all to enter into all mapping relations recovery modules), after the branch prediction mistake is judged in branch's formation, revise ROB tail item to the corresponding ROB item of the branch instruction that makes a mistake, and timing device is started working and each mapping relations are recovered module and started working simultaneously, each mapping relations is recovered module and is obtained the logic register address that they will write back from each ROB item, through after the operation of certain hour, export the update content of each RAT list item, when timer reaches predetermined value (during periodicity before this value is not more than the rename stage that the instruction of new address of failing from branch prediction enters streamline, the delay of present embodiment is hidden, can not influence performance), send update signal, each list item among the RAT recovers the mapping relations of the content update Cheng Yuqi correspondence of oneself output of module separately.

Fig. 3 is the inner structure that mapping relations are recovered module, and the structure of recovering module corresponding to each mapping relations of each RAT item is identical, and it is example that these mapping relations of sentencing the RAT7 correspondence are recovered module, and each mapping relations is recovered module by forming with the lower part:

Comparer corresponding to each ROB item, be used for judging that whether logic register address that this ROB item will write back recover the corresponding corresponding logic register of the RAT list item address of module equal (be exactly LR7 at Fig. 3) with these mapping relations, if equate, output ' 1 ', otherwise output ' 0 '.If the corresponding ROB item of this comparer is cancelled, then comparative result output ' 0 '.

Divide into groups at the ROB item, each group has that to search device in the group corresponding with it, search device in the group according to the descending order in ROB item address in the group, check the comparative result of the comparer corresponding with organizing interior ROB item successively, to find to be output as the 1st～0 (i.e. numbering in the group) output of ' 1 ' the corresponding ROB item of comparer address at first, to search into function signal simultaneously and be made as ' 1 ', and be illustrated in to have found in the group and be output as ' 1 ' comparer.Traveled through all ROB items in the group and still do not find and be output as ' 1 ' comparer if search device in the group, then will search into function signal and be made as ' 0 ', failure is searched in expression.

At ROB grouping, find the group at ROB tail item place according to amended ROB tail pointer, as is known, when the branch prediction mistake took place, the ROB tail pointer was resumed the next item down of the corresponding ROB item of the branch instruction that makes a mistake for sensing.According to the present invention, this ROB tail pointer is revised as the corresponding ROB item of the branch instruction that its sensing is made a mistake (namely, ROB tail item), in not having the microprocessor of branch delay slot, amended ROB tail pointer points to the corresponding ROB item of branch instruction of prediction error; In the microprocessor of branch delay slot was arranged, amended ROB tail pointer pointed to the corresponding ROB item of instruction that postpones in the groove.Multi-selection device judges according to the 4th～2 of the scale-of-two ROB address of amended ROB tail pointer ROB tail item pointed ROB tail item is in which group between group, in Fig. 2, ROB tail item is ROB18, and the address is 10010, wherein the 4th～2 is 100, so ROB tail item is just in the 4th group.After multi-selection device is selected the group at ROB tail item place between group, export the comparative result of comparer of ROB item correspondence of this group as oneself output.

The result of multi-selection device between device acceptance group and the 1st～0 of ROB tail item scale-of-two ROB address are searched in special establishment, find the corresponding comparator results of ROB tail item among the result of elder generation according to the 1st～0 multi-selection device between group of ROB tail item address, begin to judge successively according to the descending order in ROB item address the comparative result of comparer from this result, the scope of judging is the 0th from ROB tail item to this group, and numbering can not be judged greater than the comparative result of the ROB item of ROB tail item in the group.First that search in the specific group that device will find is output as the 1st～0 output of ' 1 ' the corresponding ROB item of comparer address, will search into function signal simultaneously and be made as ' 1 ', is illustrated in to have found in the group to be output as ' 1 ' comparer.Found in the group the 0th still not find to be output as ' 1 ' comparer, then will to search into function signal and be made as ' 0 ' if search device in the specific group, failure is searched in expression always.

The global search device is according to searching device in 8 groups, and the address of searching device and ROB tail item in 1 specific group finds out the address that is used to recover the ROB item of its content at a certain RAT list item.The global search device is judged the lookup result of searching device in the specific group earlier, if searching the function signal of searching into of device in the specific group is ' 1 ', then piece together searching numbering in the group of searching device output in group # (just the 4th～2 of the address of ROB tail item the) that device searches and the specific group (ROB item address the 1st～0) in the specific group, output as the global search device, simultaneously the function signal of searching into of global search device is made as ' 1 ', if searching the function signal of searching into of device in the specific group is ' 0 ', then the 4th～2 with the address of ROB tail item subtracts 1 back as group #, judge that this organizes whether the function signal of searching into of searching device in corresponding group is ' 1 ', if be ' 1 ', then the group # that will organize and this are organized in the group of searching device output in corresponding group numbering and are pieced together, output as the global search device, simultaneously the function signal of searching into of global search device is made as ' 1 ', if be ' 0 ', then continue this group # is subtracted 1 back as group #, judge that next organizes the function signal of searching into of searching device in corresponding group ... till in finding the group of searching success, searching device or having judged the result who searches device in all groups (search in last estimative group search in device and the specific group device searches be same group), if wherein group # has been 0 and still need continue to search, then group # can be unrolled back 7; If searching the function signal of searching into of device in all groups all is ' 0 ', all not in executing state, the global search device is made as ' 0 ' to its function signal of searching in all instructions that expression this moment writes back this logic register address.The implication of noting splicing is herein arranged according to the order of big-endian for numbering in the group # (just the 4th～2 of the address of ROB tail item the) that will find and the group that finds (ROB item address the 1st～0), for example, if the group # that finds is AAA, and being numbered BB in the group that finds, this spliced result is AAABB.

Based on foregoing description as can be seen, searching the difference of searching device in device and the specific group in of the present invention group is, search in the group device search to as if fixing, and it is irrelevant with amended ROB tail pointer, that is, search device in the group and just search the comparative result that the interior corresponding comparer of ROB item of oneself group is exported; And search the group at the ROB tail item place of searching to as if from all existing ROB groups, being selected according to amended ROB tail pointer by multi-selection device between group of device in the specific group, and be starting point with ROB tail item when searching, its address can not searched greater than the ROB item of the address of ROB tail item.

In the present embodiment, the grouping of ROB is the principle according to even grouping, and 32 ROB items are divided into 8 groups, 4 every group.This group technology has been considered the simple efficient of realization, because can use this moment the not coordination of address of ROB item as numbering in the numbering of group and the group, thus can be by the lookup result that the numbering mode of splicing in the numbering of group and the group is exported at last.But the packet mode of ROB has more than and is limited to this a kind of packet mode, the packet mode of ROB can change as the case may be, also not necessarily each item number of comprising of group all equates, the purpose that ROB is divided into groups is respectively to organize to walk abreast to search to shorten to search the time, concrete packet mode will be seen actual conditions and decide, at the ROB item number seldom or can be used under the chronic situation of searching, even can not divide into groups.Though can not directly use this moment the not coordination of address of ROB item as numbering in the numbering of group and the group, those skilled in the art can expect using similar mode obtain with the present invention the identical result of illustrational embodiment.Such as the group technology that comprises the ROB item that does not wait item number for each group, can carry out unequal grouping according to ROB item address earlier, after this method of the ROB item address that obtains being taked to add and subtract address offset in subsequent treatment obtains numbering in corresponding group # and the group, thereby obtains spliced result at last.For the situation of ROB not being divided into groups, the result's that can directly be found at last according to each ROB item address ROB item address.These class methods are a lot, therefore here do not specifically describe.In a word, the present invention is not limited to 32 ROB items and these 32 ROB items is divided into 8 groups, the embodiment of every group of 4 ROB items, and the ROB item of other number and other packet mode also are adapted to the present invention.This paper uses the ROB with 32 to understand that for example embodiments of the invention are in order better the present invention to be described, to help those skilled in the art to understand the present invention better thus.

RAT list item recovery device is accepted the output of global search device, if the function signal of searching into of global search device is ' 1 ', then RAT list item recovery device then adds the front, ROB item address of global search device output 1 and this position is made as ' 1 ' content to be resumed as the physical register address of preserving in this RAT list item again.As previously mentioned and since first place be ' 1 ' physical register address corresponding to the rename register, therefore the above-mentioned modification of the physical register address of preserving in the RAT list item is just represented that the present corresponding physical register of this RAT list item is the rename register; If the function signal of searching into of global search device is ' 0 ', then RAT list item recovery device just recovers this mapping relations the content that the address of the corresponding architecture register of the corresponding RAT list item of module be resumed as the physical register address of preserving among this RAT, and this expression corresponding physical register of this RAT list item at present is and the corresponding architecture register of the corresponding logic register of this list item.Be example with the situation among above-mentioned Fig. 2, if the function signal of searching into of global search device is ' 1 ', then RAT list item recovery device is then adding 1 and this position is made as ' 1 ' (therefore this address becomes 1XXXXX) with the front, ROB item address (for example XXXXX) of global search device output, then 1XXXXX is revised as in the address of the physical register stored among the RAT7, because the first place of this physical register address is 1, therefore the present corresponding physical register of this RAT list item of expression is the rename register.If the function signal of searching into of global search device is ' 0 ', then RAT list item recovery device just recovers these mapping relations the address of the corresponding architecture register of the corresponding RAT list item of module, as preceding described, though though each logic register and its corresponding RAT list item can corresponding a plurality of rename registers, but have only an architecture register corresponding with it, be exactly AR7 such as the architecture register corresponding with RAT7, be AR7 at any time, although the content of RAT7 is AR7 always not necessarily, will never be other architecture register.Therefore, the content that RAT list item recovery device just should be resumed the address of RAT7 as this RAT list item, the content modification that is about to this RAT list item becomes the address (000111) of AR7, and the expression this moment corresponding physical register of this RAT list item at present is the system register.

According to the present invention, also comprise the timing device (referring to Fig. 2) that upgrades the update signal of operation for generation of indication RAT, in the time of this timing device can being designed to count value when the counter in the described timing device and reaching predetermined value, this timing device sends update signal and recovers the original physical register address of being preserved of module output each RAT list item of renewal with indication RAT according to the corresponding mapping relations of its each list item, the timing of wherein said timing device is no more than when the branch prediction mistake takes place microprocessor reloads instruction from new address time, therefore, there is not visible time overhead.And owing to have only a RAT, therefore steering logic is fairly simple when register renaming, and the sequential expense is little.

Present embodiment is at rename implementation A, but just goes for rename implementation B as long as make an amendment at RAT list item recovery device in fact.The method of revising is: with respect to rename mode A, rename mode B can additionally preserve the corresponding physical register of target logic register address in the ROB item, RAT list item recovery device is read physical address separately from each ROB item, if the function signal of searching into of global search device is ' 1 ', then according to the recovery data of the ROB address selection of the global search device output target physical register address corresponding with it as the RAT list item; If the function signal of searching into of global search device is ' 0 ', then from architecture register mapping table, read the content of corresponding list item as the recovery data of corresponding RAT list item.

Enumerate two concrete examples below and specify working method of the present invention, because each list item of RAT is corresponding to same recovery logic, so following Example only is illustrated with the rejuvenation to a list item among the RAT:

Example 1. as shown in Figure 4, when the branch prediction mistake takes place, also have 4 among the instruction cancellation back ROB at the rename operation of logic register LR15, be in respectively among the 13rd, 17,24,26 of ROB, the head pointer of instruction cancellation back ROB is positioned at the 12nd, and amended tail pointer belongs to mapping relations recovery module to the 0th group of the ROB grouping at the 2nd, so the 0th group also is to deliver to the specific group of searching device in the specific group.4 operations to LR15 lay respectively in the the 3rd, the 4th and the 6th group, and wherein the 6th group comprises two to the operation of LR15.Recover to search in all groups in the module corresponding to the mapping relations of LR15 and search device in device and the specific group and search for operation to LR15 separately, in this example, 3rd, search device in the 4th and the 6th group the group and found operation to LR15, wherein the 6th group that find is the 26th of ROB, because go up from the time, it is newer than on the same group the 24th.The global search device is at first judged the result who searches device in the specific group, search device in the specific group and do not find the ROB item that will write back LR15, next the global search device judges the 7th group result, still do not find, followed by being the 6th group, the 6th group has been found the target logic register address of preserving is the ROB item of LR15, so the global search device also is that the 26th of ROB gives the recovery data that RAT list item recovery device draws the RAT list item corresponding with LR15 as the output of oneself with the 6th group Search Results.

This is a kind of relatively opposite extreme situations for example 2., also be why the reason of searching device in the specific group will be set in the native system, as shown in Figure 5, when the branch prediction mistake takes place, it is empty having only two ROB items after the instruction cancellation, and the piece at amended ROB rear of queue item place has two ROB items to write back LR15, it is respectively the 8th and the 11st, though they belong to a piece, but the two ends of the effective ROB formation in office logically, the 11st is the piece that uses LR15 the earliest, and the 8th is the piece that uses LR15 at last.If make a decision with common group inner encoder, should select the 11st, can be in fact the 8th be only existing up-to-date rename result to LR15.Search device in the specific group owing to be to begin to search from amended ROB rear of queue item, it will be the 8th so search the lookup result of device in the specific group, find under result's the situation and search device in specific group, overall scrambler will preferentially use the result who searches device in the specific group.

With reference to Fig. 6, the method according to this invention has been described.Described method is from being provided for producing the update signal step 601 that indication RAT upgrades operation, in step 602, the target logic address of preserving in each ROB item and the corresponding logic register of the RAT list item address that will be resumed are compared and export the two comparative result that whether equates of indication; Comparative result in step 602 output is provided for step 603 and 604, in step 603, to each group of ROB item, the corresponding comparative result of each ROB item in this group searched, and the output lookup result; In step 604, select the group at the ROB tail item place in the ROB item and export the corresponding comparative result of each ROB item in the group of group at this ROB tail item place; The comparative result of step 604 output is provided for step 605, in step 605, based on the corresponding comparative result of each ROB item in the group of the group at described ROB tail item place, the comparative result of the comparer in the group of described ROB tail item place is searched, and the output lookup result; The lookup result of output is provided for step 606 in step 603 and the step 605, in step 606, based on the lookup result in step 603 and 605, export final lookup result, the ROB item whether described final lookup result indication also has its target logic address to equate with the corresponding logic register of the RAT list item address that will be resumed in ROB, and the address of the ROB item of the instruction that in its target logic address and these ROB items that the corresponding logic register of the RAT list item address that will be resumed equates, equates with described target logic address corresponding to its target register address that should be performed the latest; Final lookup result in the step 606 is provided for step 607, in step 607, based on final lookup result, upgrade the content that physical register address that RAT list item that the update signal output of operation will be resumed preserves should be resumed according to the indication RAT in step 601.

It should be noted that at last: above embodiment is the unrestricted technical scheme of the present invention in order to explanation only, although with reference to above-described embodiment the present invention is had been described in detail, those of ordinary skill in the art is to be understood that: still can make amendment or be equal to replacement the present invention, and not breaking away from any modification or partial replacement of the spirit and scope of the present invention, it all should be encompassed in the middle of the claim scope of the present invention.

Claims

1. system that when branch prediction is failed, uses resequencing buffer ROB to recover register alias table RAT content, all ROB items are divided into a plurality of groups according to its address, the ROB item that each group comprises the ROB item of predetermined number and described predetermined number does not have between mutually overlapping, and described system comprises:

Be used for multi-selection device between a plurality of groups group of ROB item, be used for selecting the group at the ROB tail item place of ROB item, described ROB tail item is the corresponding ROB item of branch instruction that makes a mistake, and exports the comparative result of the comparer in the group of group at this ROB tail item place;

2. the system as claimed in claim 1, when the count value of the counter in the described timing device reaches predetermined value, this timing device sends update signal and recovers module output with indication RAT according to the corresponding mapping relations of its each list item and upgrade the original physical register address of being preserved of each RAT list item, and the timing of wherein said timing device is no more than when generation branch prediction mistake microprocessor reloads instruction from new address time.

3. the system as claimed in claim 1, whether search device in wherein said group has the comparative result of the corresponding comparer of ROB item to be designated as equal according to the ROB item address in its corresponding group by the sequential search that maximum in the group is decremented to minimum in the group, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, the signal of success is searched in signal and the indication of the position of that ROB item in group that the output indication is found at first, otherwise failure signal is searched in the output indication.

4. the system as claimed in claim 1, search the output result of multi-selection device between device reception group in the wherein said specific group, and be starting point with described ROB tail item, whether there is the comparative result of the corresponding comparer of ROB item to be designated as equal according to the descending sequential search in ROB item address, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, then output indicates signal and the indication of the position of that ROB item in group of finding at first to search the signal of success, otherwise failure signal is searched in the output indication, wherein will can not searched greater than the comparative result of the comparer of the ROB item of ROB tail item address corresponding to its address.

5. system as claimed in claim 4, wherein said global search device is at first searched successful signal whether according to the indication of searching the output of device in the described specific group and is judged that searching the comparative result whether device found comparer in the specific group is designated as equal ROB item, if find, just the signal of success is searched as output and output expression in the address of searching the ROB item that device finds in the specific group, be designated as equal ROB item if search the comparative result that device do not find comparer in the specific group, then according to instructing the direction that enters ROB successively, the next one of judging selected group of multi-selection device between group is organized and is searched the comparative result whether device found comparer in corresponding group and be designated as equal ROB item, if find, the signal of success is searched as output and output indication in the address of searching the ROB item that device finds in this group, if do not find, continue to judge the result who searches device in the next group, till being recycled to the ROB group that multi-selection device finds between group, whether the global search device was searched and was searched device in the group of the selected ROB group of multi-selection device between group and find the comparer comparative result to be designated as equal ROB item this moment, if find, the signal of success is searched as output and output indication in the address of this ROB item, otherwise failure signal is searched in global search device output indication, and finishes to search.

6. system as claimed in claim 5, if wherein the signal of success is searched in the output indication of global search device, then described RAT list item recovery device is adding one and this position is made as ' 1 ' content that be resumed with the physical register address of being preserved in as this RAT list item with the front, ROB item address of described global search device output; If failure signal is searched in the output indication of global search device, then RAT list item recovery device just with the corresponding RAT list item of this mapping relations recovery module the address of the corresponding architecture register content that be resumed as the physical register address of preserving in this RAT list item.

7. method of when branch prediction is failed, using resequencing buffer ROB to recover register alias table RAT content, all ROB items are divided into a plurality of groups according to its address, the ROB item that each group comprises the ROB item of predetermined number and described predetermined number does not have between mutually overlapping, said method comprising the steps of:

(II) the target logic address of preserving in each ROB item and the corresponding logic register of the RAT list item address that will be resumed are compared and export the two comparative result that whether equates of indication, the target logic address that wherein is kept in each ROB item equates with the target logic register address of the corresponding instruction of each ROB item;

8. method as claimed in claim 7, wherein use timing device to provide indication RAT to upgrade the update signal of operation, when the count value of the counter in the described timing device reaches predetermined value, this timing device sends update signal and upgrades the original physical register address of being preserved of each RAT list item with the output that indication RAT recovers module according to the corresponding mapping relations of its each list item, and the timing of wherein said timing device is no more than when generation branch prediction mistake microprocessor reloads instruction from new address time.

9. method as claimed in claim 7, wherein step (III) comprises further whether the address according to the interior ROB item of each group of ROB item has the corresponding comparative result of ROB item to be designated as equal by the sequential search that maximum in the group is decremented to minimum in the group, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the corresponding comparative result of a plurality of ROB items to be designated as equal, the signal of success is searched in signal and the indication of the position of that ROB item in group that the output indication is found at first, otherwise failure signal is searched in the output indication.

10. method as claimed in claim 7, wherein step (V) comprises that further with described ROB tail item be starting point, whether there is the comparative result of the corresponding comparer of ROB item to be designated as equal in the group according to descending sequential search ROB tail item place, ROB item address, if have, then the signal of success is searched in signal and the indication of the position of this ROB item of output indication in group, if there is the comparative result of the corresponding comparer of a plurality of ROB items to be designated as equal, then output indicates signal and the indication of the position of that ROB item in group of finding at first to search the signal of success, and wherein its address will can not searched greater than the corresponding comparative result of ROB item of ROB tail item address.

11. method as claimed in claim 10, wherein step (VI) further comprises according to the indication of output in step (V) searching whether whether successful signal is judged has been found the corresponding comparative result of ROB item to be designated as equal ROB item in step (V), if find, just with this corresponding address of ROB item as output, if in step (V), do not find the corresponding comparative result of ROB item to be designated as equal ROB item, then according to instructing the direction that enters ROB successively, whether judge in the next one group of group at ROB tail item place has found the comparative result of ROB item correspondence to be designated as equal ROB item, if find, the signal of success is searched as output and output indication in that corresponding address of ROB item of finding at first in this group, if do not find, continue to judge that next group has not found the comparative result of ROB item correspondence to be designated as equal ROB item, till the group that is recycled to ROB tail item place, judge in the group of ROB tail item place whether found the comparative result of ROB item correspondence to be designated as equal ROB item this moment, if find, the signal of success is searched as output and output indication in the address of that ROB item of finding at first in this group, otherwise failure signal is searched in the output indication, and finishes to search.

12. method as claimed in claim 11, if wherein the signal of success is searched in output indication in step (VI), then the front, ROB item address that will export in step (VI) is adding one and this is made as ' 1 ' content to be resumed as the physical register address of being preserved in this RAT list item; If failure signal is searched in output indication in step (VI), then with this RAT list item the address of the corresponding architecture register content that be resumed as the physical register address of preserving in this RAT list item.