JP5609609B2 - Branch prediction apparatus and processor - Google Patents

Description

  The present invention relates to a branch prediction apparatus and a processor.

  In a conditional branch instruction which is a kind of instruction of a processor, an instruction execution path branches when a branch by a conditional branch instruction is established. Therefore, when the branch by the conditional branch instruction is established, the instruction executed next to the conditional branch instruction is changed to an instruction having an address separated from the conditional branch instruction, not an instruction having an address consecutive to the conditional branch instruction. For this reason, the instruction executed next to the conditional branch instruction is not determined until the conditional branch instruction is executed. That is, the address for fetching (acquiring) an instruction from the instruction memory is not determined until the conditional branch instruction is executed.

  For this reason, the processor cannot access the instruction memory until the conditional branch instruction is executed. For example, in a processor that performs pipeline processing, the occurrence of a period (the number of cycles) during which the instruction memory cannot be accessed causes performance degradation. For this reason, a processor that performs pipeline processing includes, for example, a branch prediction device that predicts the result of a branch instruction. For example, dynamic branch prediction is widely adopted for branch prediction devices.

  In dynamic branch prediction, the execution result of a past conditional branch instruction is stored in a memory, and the execution result stored in the memory is used for branch prediction (see, for example, Patent Document 1 and Patent Document 2). The branch prediction device includes, for example, a direction history memory that stores a branch direction indicating whether or not a branch by a branch instruction is established, and a branch destination history memory that stores a branch destination address when a branch by a branch instruction is established. Have. A branch prediction apparatus mounted on a processor that requires high-speed processing, for example, performs branch prediction before instruction decoding processing is performed.

Japanese Patent Laid-Open No. 11-85516 Japanese Patent No. 3790039

  A branch prediction apparatus that performs branch prediction before instruction decode processing is executed is a branch prediction memory such as a direction history memory each time instruction fetch processing (processing to acquire an instruction from the instruction memory) is executed. To access. This is because it is not known whether the instruction is a branch instruction until the instruction decoding process is performed. For this reason, the branch prediction apparatus accesses the memory for branch prediction even when an instruction other than the branch instruction is executed. At this time, unnecessary power is consumed due to unnecessary access to the branch prediction memory.

  In one aspect of the present invention, a branch prediction apparatus includes a history storage unit that stores a result of a branch instruction, a prediction unit that performs branch prediction with reference to the history storage unit, and a branch instruction corresponding to the branch instruction An interval storage unit that stores the interval of the history, a control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit, a counter that measures the interval of the branch instruction, and the interval And an update unit that updates the contents of the storage unit based on the interval of the branch instruction measured by the counter.

  Unnecessary access to the branch prediction memory can be reduced, and power consumption can be reduced.

2 illustrates an example of a processor in one embodiment. An example of the branch prediction apparatus shown in FIG. 1 is shown. An example of the first update operation of the interval storage unit shown in FIG. 1 is shown. 2 shows an example of the operation of the branch prediction apparatus shown in FIG. An example of a state of an interval storage unit having a data width of 3 bits is shown. 3 shows an example of the operation of the updating unit and the counter shown in FIG. The example of the space | interval memory | storage part in another embodiment is shown. An example of the branch prediction apparatus in another embodiment is shown. FIG. 9 illustrates an example of operations of the updating unit and the counter illustrated in FIG. 8. FIG. 9 shows another example of the operation of the update unit and counter shown in FIG. 1 shows an example of a branch prediction apparatus that performs an update operation at a stage of arithmetic processing. An example of the branch prediction apparatus in another embodiment is shown. 13 illustrates an example of an interval storage unit and a prediction control unit illustrated in FIG. 14 illustrates an example of the operation of the prediction control unit illustrated in FIG. 13. 13 shows an example of the operation of the update unit and counter shown in FIG.

  Hereinafter, embodiments will be described with reference to the drawings.

  FIG. 1 illustrates an example of a processor in one embodiment. For example, the processor performs pipeline processing. The processor includes, for example, a branch prediction device BPRE1 (the portion surrounded by a broken line in the figure), a program counter PC, an instruction memory IMEM, a decoder DEC, a register read unit RPD, an arithmetic logic unit ALU, and pipeline registers PRG1, PRG2, and PRG3. Have. Hereinafter, the arithmetic logic unit ALU is also referred to as ALU.

  For example, the program counter PC outputs a value indicating an address of an instruction executed by the processor (hereinafter also referred to as a PC value) to the instruction memory IMEM and the branch prediction device BPRE1. For example, the value of the program counter PC (PC value) increases every time the processor executes an instruction. Alternatively, the PC value is set to the branch destination address predicted by the branch prediction device BPRE1 when the branch prediction is executed. The PC value is sequentially transferred to the pipeline registers PRG1, PRG2, and PRG3.

  The instruction memory IMEM outputs the instruction at the address indicated by the PC value to the pipeline register PRG1. As a result, the instruction is fetched (acquired) from the instruction memory IMEM. The decoder DEC acquires an instruction (an instruction fetched from the instruction memory IMEM) held in the pipeline register PRG1, and decodes the instruction fetched from the instruction memory IMEM. Then, the decoder DEC outputs the decoding result to the pipeline register PRG2 and the branch prediction device BPRE1. Thereby, for example, the branch prediction apparatus BPRE1 can determine whether or not the instruction fetched from the instruction memory IMEM is a branch instruction.

  For example, the register read unit RDP acquires the decoding result of the decoder DEC from the pipeline register PRG2, and reads out the operand of the instruction from the register based on the decoding result of the decoder DEC. Then, the register read unit RDP outputs the operand read from the register to the pipeline register PRG3. For example, the ALU acquires an operand of an instruction from the pipeline register PRG3, and executes four arithmetic operations, logical operations, and the like. In this way, the processor performs pipeline processing.

  The branch prediction apparatus BPRE1 includes an interval storage unit DMEM1, a prediction unit PRED, a prediction control unit PCNT1, a counter COT, and an update unit UPP1, and predicts the result of a branch instruction. For example, the interval storage unit DMEM1, the prediction unit PRED, and the prediction control unit PCNT1 operate in the same stage as the stage in which the instruction fetch process of the pipeline process (a process of acquiring an instruction from the instruction memory IMEM) is performed. Further, for example, the counter COT and the update unit UPP1 operate in the same stage as the stage in which the pipeline processing decode processing (processing for decoding the instruction) is performed.

  The interval storage unit DMEM1 stores a branch instruction interval (hereinafter also referred to as a branch instruction interval) corresponding to the branch instruction. For example, the interval storage unit DMEM1 stores the branch instruction interval by using a part of the PC value of the branch instruction (for example, the lower bits of the PC value) as an address. Alternatively, the interval storage unit DMEM1 stores the branch instruction interval using a hash value generated from the PC value of the branch instruction as an address.

  The prediction control unit PCNT1 determines the timing for referring to the history storage unit HMEM of the prediction unit PRED based on the branch instruction interval stored in the interval storage unit DMEM1. For example, the prediction control unit PCNT1 has a counter (a counter different from the counter COT in FIG. 1) that counts up each time an instruction fetch process (a process for acquiring an instruction from the instruction memory IMEM) is performed. That is, the counter in the prediction control unit PCNT1 counts up whenever the PC value changes. The prediction control unit PCNT1 resets the counter in the control unit PCNT1 when the branch instruction interval read from the interval storage unit DMEM1 matches the counter value in the prediction control unit PCNT1.

  In addition, the prediction control unit PCNT1 indicates, for example, the reference timing to the history storage unit HMEM when the branch instruction interval read from the interval storage unit DMEM1 matches the counter value in the prediction control unit PCNT1. Is notified to the prediction unit PRED. Further, when the branch instruction interval read from the interval storage unit DMEM1 matches the counter value in the prediction control unit PCNT1, the prediction control unit PCNT1 sets, for example, a branch instruction interval indicating an interval until the next branch instruction. Read from the storage unit DMEM1.

  That is, the interval storage unit DMEM1 is referred to by the prediction control unit PCNT1 when the history storage unit HMEM is referred to by the prediction unit PRED, for example. As described above, the prediction control unit PCNT1 determines the timing for referring to the interval storage unit DMEM1 and the history storage unit HMEM based on the branch instruction interval read from the interval storage unit DMEM1. That is, the prediction control unit PCNT1 predicts whether the instruction is a branch instruction based on the branch instruction interval read from the interval storage unit DMEM1.

  The prediction unit PRED has a history storage unit HMEM that stores the result of the branch instruction. The history storage unit HMEM includes, for example, a direction history memory that stores a branch direction indicating whether or not a branch by a branch instruction is established, and a branch destination history memory that stores a branch destination address when a branch by a branch instruction is established. have. The history storage unit HMEM may be configured without including the branch destination history memory.

  For example, the prediction unit PRED predicts whether or not a branch by a branch instruction is established based on the information on the branch direction stored in the history storage unit HMEM. When the prediction unit PRED predicts that a branch instruction is taken, the prediction unit PRED notifies the program counter PC of the branch destination address stored in the history storage unit HMEM. As a result, the branch destination address is set in the program counter PC. Thus, the prediction unit PRED performs branch prediction with reference to the information stored in the history storage unit HMEM.

  As described above, the timing at which the history storage unit HMEM is referred to is controlled by the prediction control unit PCNT1. For example, the prediction unit PRED refers to the history storage unit HMEM when receiving information from the prediction control unit PCNT1 indicating that it is the reference timing to the history storage unit HMEM. That is, the prediction unit PRED refers to the history storage unit HMEM at the branch instruction interval stored in the interval storage unit DMEM1. Thereby, the prediction unit PRED can reduce unnecessary access to the history storage unit HMEM and the like even when branch prediction is performed before the instruction is decoded. Therefore, in this embodiment, unnecessary access to the history storage unit HMEM and the interval storage unit DMEM1 can be reduced, and power consumption can be reduced.

  The counter COT measures the interval between branch instructions when the program is executed. For example, the counter COT is reset by the updating unit UPP1 when the instruction decoded by the decoder DEC is a branch instruction. That is, the counter COT is reset every time a branch instruction is executed. For example, the counter COT counts up whenever the PC value held in the pipeline register PRG1 changes. That is, the counter COT counts up every time an instruction is fetched from the instruction memory IMEM. The update unit UPP1 updates the contents of the interval storage unit DMEM1 based on the branch instruction interval measured by the counter COT.

  Note that the configuration of the branch prediction device BPRE1 is not limited to this example. For example, the prediction control unit PCNT1 may be configured to be able to stop access to the interval storage unit DMEM1, and may stop access to the interval storage unit DMEM1 during a period in which branch instructions are continuous. In a period in which access to the interval storage unit DMEM1 is stopped, for example, branch prediction is performed for each instruction. Alternatively, the prediction control unit PCNT1 may be provided in the prediction unit PRED, for example.

  Further, the interval storage unit DMEM1 may be provided in the prediction unit PRED. For example, the interval storage unit DMEM1 may be configured by adding a bit for storing the branch instruction interval to the bit width of the direction history memory or the branch destination history memory of the history storage unit HMEM. Alternatively, the interval storage unit DMEM1 may be referred to by the prediction unit PRED. For example, in a configuration in which the prediction unit PRED reads the branch instruction interval from the interval storage unit DMEM1, the prediction unit PRED notifies the prediction control unit PCNT1 of the branch instruction interval read from the interval storage unit DMEM1.

  Further, the counter COT may be provided in the update unit UPP1. Further, for example, in the branch prediction device BPRE1 installed in the processor that performs the branch instruction determination at the stage of the pipeline processing operation (ALU processing), the counter COT and the update unit UPP1 are the same as the operation processing stage. It may be configured to operate on a stage.

  FIG. 2 shows an example of the branch prediction device BPRE1 shown in FIG. In FIG. 2, the update unit UPP1 will be described. Reference numerals PC1 and BRPC in FIG. 2 indicate PC values held in the pipeline register PRG1 and the register REG1, respectively. The instruction INST is, for example, a code indicating an instruction fetched from the instruction memory IMEM.

  The update unit UPP1 includes a register REG1 and an update control unit UCNT1. The register REG1 holds, for example, the PC value of the branch instruction. For example, the register value BRPC (PC value) of the register REG1 is updated every time a branch instruction is executed. The update control unit UCNT1 receives information indicating whether or not the instruction INST is a branch instruction from the decoder DEC and also receives the counter value WCT of the counter COT from the counter COT. When the instruction is a branch instruction, the update control unit UCNT1 resets the counter COT and updates the contents of the interval storage unit DMEM1.

  For example, the update control unit UCNT1 calculates an update target address (lower bits of PC value, hash value, etc.) of the interval storage unit DMEM1 based on the register value BRPC. Then, the update control unit UCNT1 updates the data of the update target address to the counter value WCT (branch instruction interval). For example, when updating the contents of the interval storage unit DMEM1, the update unit UPP1 updates the register value BRPC to the PC value (PC1) held in the pipeline register PRG1. Thereby, the register value BRPC is updated every time a branch instruction is executed.

  FIG. 3 shows an example of the first update operation of the interval storage unit DMEM1 shown in FIG. In FIG. 3, the value of the program counter PC (0x0024 etc.) is shown in hexadecimal. Further, an instruction br surrounded by a thick line in FIG. 3 indicates a branch instruction. The instruction other indicates an instruction other than the branch instruction. In FIG. 3, “◯” indicates that a branch instruction is taken (taken), and “X” indicates that a branch instruction is not taken (not take). “-” In FIG. 3 indicates that a meaningless value (initial value) is written in the register REG1. The initial value of the interval storage unit DMEM1 is set to “0”, for example. This initial value has no particular meaning.

  When the PC value is “0x0028”, the branch instruction br is executed. At this time, the counter value WCT is reset to “0”. The register value BRPC is updated to “0x0028”. Since the branch by the branch instruction br having the PC value “0x0028” is established, the instruction having the PC value “0x0100” is executed next to the branch instruction br. At this time, the counter value WCT is incremented from “0” to “1”.

  When the PC value is “0x0104”, the branch instruction br next to the branch instruction br having the PC value “0x0028” is executed. At this time, the data in the address interval storage unit DMEM1 based on the register value BRPC (“0x0028”) is updated to “1” as the counter value WCT ((a) of FIG. 3). Then, the counter value WCT is reset to “0”, and the register value BRPC is updated from “0x0028” to “0x0104”.

  Since the branch by the branch instruction br having the PC value “0x0104” is not established, the instruction having the PC value “0x0108” is executed next to the branch instruction br. At this time, the counter value WCT is incremented from “0” to “1”. The program is executed in the order of consecutive addresses until the next branch instruction br is executed. During this time, the counter value WCT is counted up each time an instruction is executed. Note that the register value BRPC is held at “0x0104”.

  When the PC value is “0x0114”, the branch instruction br next to the branch instruction br having the PC value “0x0104” is executed. At this time, the data in the address interval storage unit DMEM1 based on the register value BRPC (“0x0104”) is updated to “3” of the counter value WCT ((b) in FIG. 3). Then, the counter value WCT is reset to “0”, and the register value BRPC is updated from “0x0104” to “0x0114”. By this operation, the interval storage unit DMEM1 stores the branch instruction interval corresponding to the branch instruction.

  FIG. 4 shows an example of the operation of the branch prediction apparatus BPRE1 shown in FIG. FIG. 4 shows an example of the operation of the branch prediction device BPRE1 after the update operation shown in FIG. 3 is performed, for example. The meanings of the circles and the crosses in FIG. 4 are the same as those in FIG. In the example of FIG. 4, the history storage unit HMEM stores a direction history memory DIRM that stores a branch direction indicating whether or not a branch by a branch instruction is established, and a branch destination address when the branch by the branch instruction is established. It has a branch destination history memory DESM for storing. “-” In FIG. 4 indicates that the branch destination address is not stored in the branch destination history memory DESM. 4 indicates a period (command cycle) in which the history storage unit HMEM and the interval storage unit DMEM1 are not referred to.

  When the PC value is “0x0028”, the branch prediction device BPRE1 refers to the direction history memory DIRM and the branch destination history memory DESM to perform branch prediction. For example, the branch prediction device BPRE1 predicts that a branch by the branch instruction br of the PC value “0x0028” is established because the information in the direction history memory DIRM of the address based on the PC value “0x0028” indicates that the branch is established (taken). To do. Then, the branch prediction device BPRE1 sets the branch destination address “0x0100” stored in the branch destination history memory DESM in the program counter PC. Further, the branch prediction apparatus BPRE1 sets the branch instruction interval “1” indicating the interval from the branch instruction br of the PC value “0x0028” to the next branch instruction br from the address interval storage unit DMEM1 based on the PC value “0x0028”. read out.

  Since the branch instruction interval read from the interval storage unit DMEM1 is “1”, the branch prediction device BPRE1 does not perform branch prediction for the instruction next to the PC value “0x0028”. That is, in the period T10 in which the PC value is “0x0100”, the branch prediction device BPRE1 does not perform branch prediction. Therefore, in the period T10 in which the PC value is “0x0100”, the interval storage unit DMEM1, the direction history memory DIRM, and the branch destination history memory DESM are not referred to.

  When the PC value is “0x0104”, the branch prediction device BPRE1 refers to the direction history memory DIRM and the branch destination history memory DESM to perform branch prediction. At this time, the branch prediction device BPRE1 reads the branch instruction interval “3” from the address interval storage unit DMEM1 based on the PC value “0x0104”. Since the branch instruction interval read from the interval storage unit DMEM1 is “3”, the branch predicting device BPRE1 predicts that the subsequent three instructions having the PC value “0x0104” are not branch instructions. Therefore, in the period T20 in which the PC value is “0x0108” to “0x0110”, the branch prediction device BPRE1 does not perform branch prediction. That is, in the period T20 in which the PC value is “0x0108” to “0x0110”, the interval storage unit DMEM1, the direction history memory DIRM, and the branch destination history memory DESM are not referenced.

  When the PC value is “0x0114” (after 3 instructions from “0x0108”), the branch prediction device BPRE1 performs branch prediction with reference to the direction history memory DIRM and the branch destination history memory DESM, and from the interval storage unit DMEM1. Read the branch instruction interval. Since the branch instruction interval read from the interval storage unit DMEM1 is “7”, the interval storage unit DMEM1, the direction history memory DIRM, and the branch destination history memory DESM are in the period T30 of the subsequent seven instructions with the PC value “0x0114”. , Not referenced.

  Thus, the branch prediction device BPRE1 does not perform branch prediction in the periods T10, T20, and T30 in which the instruction is predicted not to be a branch instruction. Therefore, in this embodiment, the number of unnecessary branch predictions can be reduced, and power consumption can be reduced. For example, in the periods T10, T20, and T30 in which the instruction is predicted not to be a branch instruction, the interval storage unit DMEM1, the direction history memory DIRM, and the branch destination history memory DESM are not referenced. Therefore, in this embodiment, unnecessary access to the interval storage unit DMEM1, the direction history memory DIRM, and the branch destination history memory DESM can be reduced, and power consumption can be reduced.

  Here, when an instruction that is not a branch instruction is predicted to be a branch instruction (for example, when an instruction with a PC value of “0x0104” is not a branch instruction), the history storage unit HMEM and the like are referred to, so that power is consumed. However, it does not malfunction. Even in this case, power consumption can be reduced compared to a configuration in which branch prediction is performed for each instruction. Further, when the branch instruction br is executed during a period in which it is predicted not to be a branch instruction (for example, when the instruction with the PC value “0x0110” is a branch instruction), branch prediction is not performed and the branch is regarded as not established. . At this time, the cycle performance of the processor deteriorates but does not malfunction. Therefore, even when the branch instruction interval stored in the interval storage unit DMEM1 is different from the actual branch instruction interval, no malfunction occurs.

  FIG. 5 shows an example of the state of the interval storage unit DMEM1 having a 3-bit data width. FIG. 5 shows an example of the state of the interval storage unit DMEM1 when the branch instruction interval is “10”.

  A branch instruction interval (“10” in the example of FIG. 5) greater than the maximum value (“7” in the example of FIG. 5) that can be stored with the data width of the interval storage unit DMEM1 is divided into a plurality of times (a plurality of locations). Remembered. For example, when the interval from the branch instruction br of the PC value “0x0028” to the next branch instruction br (PC value “0x0128”) is “10”, the interval storage unit DMEM1 of the address based on the PC value “0x0028” “7” is stored. Then, “2” is stored in the address interval storage unit DMEM1 based on the PC value “0x011C” seven instructions after the PC value “0x0100” next to the PC value “0x0028”. As a result, the branch prediction apparatus BPRE1 can perform branch prediction on the branch instruction having the PC value “0x0128”.

  For example, when the PC value is “0x0028”, the branch prediction device BPRE1 reads the branch instruction interval “7” stored in the address interval storage unit DMEM1 based on the PC value “0x0028”. Since the branch instruction interval read from the interval storage unit DMEM1 is “7”, the branch predicting device BPRE1 predicts that the subsequent seven instructions “0x0028” are not branch instructions. Therefore, the branch prediction device BPRE1 does not perform the branch prediction between the seven instructions whose PC values are “0x0100” to “0x0118”.

  When the PC value is “0x011C” (7 instructions after “0x0100”), the branch instruction interval “2” stored in the address interval storage unit DMEM1 based on the PC value “0x011C” is read. Further, since the branch prediction apparatus BPRE1 predicts an instruction with the PC value “0x011C” as a branch instruction, it performs branch prediction. As described above, no malfunction occurs even when an instruction that is not a branch instruction is predicted as a branch instruction. Since the branch instruction interval read from the interval storage unit DMEM1 is “2”, the branch predicting device BPRE1 predicts that the subsequent two instructions of “0x011C” are not branch instructions.

  When the PC value is “0x0128” (after two instructions from “0x0120”), the branch instruction interval “3” stored in the address interval storage unit DMEM1 based on the PC value “0x0128” is read. Further, since the branch prediction device BPRE1 predicts an instruction with the PC value “0x0128” as a branch instruction, it performs branch prediction. Thus, in this embodiment, branch prediction can be performed for each of the two branch instructions even when the interval between the two branch instructions is equal to or greater than the maximum value that can be stored in the interval storage unit DMEM1.

  Note that the data width of the interval storage unit DMEM1 is not limited to 3 bits. Further, for example, even in a configuration using a 3-bit counter COT, it is possible to cope with a branch instruction interval equal to or larger than the maximum value of the counter COT by the same operation as in FIG. As described above, in this embodiment, the data width of the interval storage unit DMEM1 and the bit width of the counter COT can be made equal to or less than the maximum value of the branch instruction interval, so that the circuit scale of the branch prediction device BPRE1 can be reduced.

  FIG. 6 shows an example of operations of the updating unit UPP1 and the counter COT shown in FIG. The processes S100 to S140 are performed every time the decoding process is performed, for example. 6 indicates the maximum value that can be stored with the data width of the interval storage unit DMEM1. 6 indicates an address calculated from the register value BRPC (lower bits of the register value BRPC, hash value, etc.).

  In the process S100, for example, the update control unit UCNT1 of the update unit UPP1 determines whether the decoded instruction is a branch instruction based on the information received from the decoder DEC. When the instruction is not a branch instruction (No in process S100), the operation of the update unit UPP1 proceeds to process S110. In process S110, the update control unit UCNT1 determines whether or not the counter value WCT matches the maximum value DMAX.

  When the counter value WCT is not the maximum value DMAX (No in step S110), the counter value WCT of the counter COT is incremented in step S120. As a result, the counter COT counts up every time an instruction is fetched from the instruction memory IMEM. On the other hand, when the counter value WCT is the maximum value DMAX (Yes in process S110), the operation of the update unit UPP1 moves to process S130. When it is determined in process S100 that the instruction is a branch instruction (Yes in process S100), the operation of the update unit UPP1 proceeds to process S130.

  In process S130, the update control unit UCNT1 updates the interval storage unit DMEM1. For example, the update control unit UCNT1 calculates the address ADR of the interval storage unit DMEM1 to be updated from the register value BRPC. Then, the update control unit UCNT1 updates the contents of the address ADR (BRPC ') of the interval storage unit DMEM1 using the counter value WCT as the data DAT. As a result, the interval storage unit DMEM1 is updated each time a branch instruction is executed. For this reason, it is possible to improve the prediction accuracy as to whether or not the instruction to be executed is a branch instruction.

  In this embodiment, when the branch instruction interval is equal to or greater than the maximum value DMAX, the maximum value DMAX is added to the address corresponding to the branch instruction (for example, the branch instruction having the PC value “0x0028” in FIG. 5) by the processes S110 and S130. Can be stored. Then, using the PC value (for example, the PC value “0x011C” in FIG. 5) when the maximum value DMAX is updated in the interval storage unit DMEM1, the interval until the next branch instruction is calculated.

  In process S140, the update control unit UCNT1 initializes the register REG1 and the counter COT. For example, the update control unit UCNT1 sets the PC value (PC1) held in the pipeline register PRG1 to the register value BRPC of the register REG1. Further, the update control unit UCNT1 resets the counter value WCT of the counter COT to “0”. Thus, the counter COT is reset every time the content of the interval storage unit DMEM1 is updated.

  In the process S140, for example, when the process S130 is performed based on the determination result (Yes) of the process S110, the register value BRPC is the PC value when the interval storage unit DMEM1 is updated to the maximum value DMAX (for example, FIG. 5). PC value “0x011C”). Thereby, in this embodiment, the branch instruction interval equal to or larger than the maximum value DMAX of the interval storage unit DMEM1 can be divided and stored a plurality of times (a plurality of locations).

  Thus, the configuration for updating the contents of the interval storage unit DMEM1 every time a branch instruction is executed has a simple update operation. For this reason, the configuration of the branch prediction device BPRE1 can be simplified. The operation of the update unit UPP1 is not limited to this example. For example, the operation of the updating unit UPP1 may be terminated without performing the processes S130 and S140 when the counter value WCT reaches the maximum value DMAX (Yes in the process S110). Thus, the counter value WCT is maintained at the maximum value DMAX until the interval storage unit DMEM1 is updated. In this case, when the branch instruction interval is equal to or greater than the maximum value DMAX, the updating unit UPP1 stores the maximum value DMAX as the branch instruction interval in the interval storage unit DMEM1 without dividing the branch instruction interval into a plurality of times (a plurality of locations). As a result, the branch instruction interval is not stored in an address corresponding to an instruction that is not a branch instruction (for example, an address corresponding to the PC value “0x011C” in FIG. 5).

  Here, for example, the register value BRPC and the counter value WCT are meaningless at the time when the decoding process is performed on the first branch instruction after reset. For this reason, a meaningless value is written in the interval storage unit DMEM1 in the first branch instruction after reset. This meaningless value writing occurs only with the first branch instruction after resetting, and thus there is no particular problem. Note that the update unit UPP1 may have a flag indicating that writing is impossible, and may prevent writing of a meaningless value. For example, the flag indicates that writing to the interval storage unit DMEM1 is impossible until the decoding process for the branch instruction next to the first branch instruction after reset is performed.

  As described above, in this embodiment, the branch prediction device BPRE1 has the interval storage unit DMEM1 in which the branch instruction interval is stored. The branch instruction interval stored in the interval storage unit DMEM1 is used to determine the timing for referring to the history storage unit HMEM and the interval storage unit DMEM1. For example, the prediction control unit PCNT1 determines the timing for referring to the history storage unit HMEM and the interval storage unit DMEM1 based on the branch instruction interval read from the interval storage unit DMEM1. Thus, in this embodiment, even when branch prediction is performed before an instruction is decoded, unnecessary access to the history storage unit HMEM and the interval storage unit DMEM1 can be reduced, and power consumption can be reduced. Therefore, the branch prediction apparatus BPRE1 of this embodiment can reduce power consumption even when mounted on a processor that requires high-speed processing.

  FIG. 7 shows an example of the interval storage unit DMEM2 in another embodiment. The same elements as those described in the above-described embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted. In FIG. 7, the PC value and the instruction that have not been executed by the branch instruction br having the PC value “0x0028” are shown in a frame surrounded by a broken line.

  The interval storage unit DMEM2 of this embodiment stores both the branch instruction interval when the branch instruction is taken and the branch instruction interval when the branch instruction is not taken. Other configurations of the branch prediction apparatus BPRE1 are the same as those in the above-described embodiment. The processor on which the branch prediction device BPRE1 of this embodiment is mounted is the same as that of the above-described embodiment. For example, the interval storage unit DMEM2 may be configured by adding a bit for storing a branch instruction interval to the bit width of the direction history memory or the branch destination history memory of the history storage unit HMEM.

  The address interval storage unit DMEM2 based on the PC value “0x0028” includes, for example, a branch instruction interval “1” when a branch by the branch instruction br is established and a branch instruction interval “2” when a branch by the branch instruction br is not established. "Is stored. For example, since the information in the direction history memory DIRM of the address based on the PC value “0x0028” indicates that the branch has been taken (taken), the prediction control unit PCNT1 has the branch instruction interval “1” when the branch by the branch instruction is taken. Are read from the interval storage unit DMEM2. Therefore, the branch prediction device BPRE1 predicts that the instruction next to “0x0028” is not a branch instruction. In the example of FIG. 7, the branch instruction interval of the interval storage unit DMEM2 referred to based on the information in the direction history memory DIRM is surrounded by a thick line.

  The interval storage unit DMEM2 stores “2” as the branch instruction interval when the branch by the branch instruction br having the PC value “0x0028” is not established. For this reason, when the branch by the branch instruction br of the PC value “0x0028” is not established, the branch predicting device BPRE1 predicts that the subsequent two instructions of “0x0028” are not branch instructions. For example, when the information in the direction history memory DIRM of the address based on the PC value “0x0028” indicates that the branch is not taken (not taken), the prediction control unit PCNT1 predicts that the subsequent two instructions of “0x0028” are not branch instructions. To do. Therefore, when the PC value is “0x0034” (after two instructions from “0x002C”), the branch prediction device BPRE1 performs branch prediction.

  As described above, also in this embodiment, the same effect as that of the above-described embodiment can be obtained. Further, in this embodiment, the interval storage unit DMEM2 stores both the branch instruction interval when the branch instruction is taken and the branch instruction interval when the branch instruction is not taken. Therefore, it is possible to improve the prediction accuracy of whether or not the instruction to be executed is a branch instruction regardless of whether or not a branch is taken.

  Thereby, in this embodiment, for example, the frequency with which a branch instruction is predicted not to be a branch instruction can be reduced, and therefore the cycle performance of the processor can be improved. Alternatively, in this embodiment, since the frequency of predicting instructions other than branch instructions as branch instructions can be reduced, unnecessary access to the history storage unit HMEM and the interval storage unit DMEM1 can be further reduced. That is, in this embodiment, the power consumption can be reduced while preventing the cycle performance of the processor from being lowered.

  FIG. 8 shows an example of the branch prediction apparatus BPRE2 in another embodiment. The same elements as those described in the above-described embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted. A symbol DIST in FIG. 8 indicates a branch instruction interval held in the pipeline register PRG1. Reference numeral BRDIST indicates a branch instruction interval held in the register REG2.

  In the configuration of the branch prediction apparatus BPRE2 of this embodiment, a prediction control unit PCNT2 and an update unit UPP2 are provided instead of the prediction control unit PCNT1 and the update unit UPP1 shown in FIG. The other configuration of the branch prediction device BPRE2 is the same as that of the embodiment described with reference to FIGS. The processor on which the branch prediction device BPRE2 is mounted is the same as that in the embodiment described with reference to FIGS.

  For example, the prediction control unit PCNT2 outputs the branch instruction interval DIST read from the interval storage unit DMEM1 to the pipeline register PRG1. Other configurations and operations of the prediction control unit PCNT2 are the same as those of the prediction control unit PCNT1. For example, for an instruction that does not read the branch instruction interval DIST from the interval storage unit DMEM1, the prediction control unit PCNT2 sets the branch instruction interval DIST held in the pipeline register PRG1 to “0”.

  In the update unit UPP2, a register REG2 and a comparison unit COM are added to the update unit UPP1, and an update control unit UCNT2 is provided instead of the update control unit UCNT1 shown in FIG. The register REG2 holds a branch instruction interval DIST, for example. For example, the register value BRDIST (DIST) of the register REG2 is updated every time a branch instruction is executed.

  The comparison unit COM compares the branch instruction interval measured by the counter COT with the register value BRDIST of the register REG2. Note that the comparison unit COM may be provided in the update control unit UCNT2. For example, when the branch instruction interval measured by the counter COT and the branch instruction interval BRDIST stored in the interval storage unit DMEM1 are the same, the update unit UPP2 does not update the interval storage unit DMEM1. Other configurations and operations of the update unit UPP2 are the same as those in the embodiment described with reference to FIGS.

  FIG. 9 shows an example of the operations of the update unit UPP2 and the counter COT shown in FIG. Processes S100 to S142 are performed each time the decoding process is performed, for example. In the operation illustrated in FIG. 9, the process S124 is added to the operation illustrated in FIG. 6, and the process S142 is performed instead of the process S140. The other operations of the updating unit UPP2 and the counter COT are the same as the operations illustrated in FIG.

  Process S124 is performed when the instruction is a branch instruction (Yes in process S100). Alternatively, the process S124 is performed when the instruction is not a branch instruction and the counter value WCT is the maximum value DMAX (Yes in process S110). In the process S124, for example, the comparison unit COM compares the counter value WCT with the register value BRDIST. When the counter value WCT and the register value BRDIST do not match (No in process S124), the update control unit UCNT2 updates the interval storage unit DMEM1 in process S130.

  On the other hand, when the counter value WCT matches the register value BRDIST (Yes in process S124), the update control unit UCNT2 initializes the registers REG1, REG2 and the counter COT in process S142. For example, the update control unit UCNT2 sets the PC value (PC1) held in the pipeline register PRG1 to the register value BRPC of the register REG1. In addition, the update control unit UCNT2 sets the branch instruction interval DIST held in the pipeline register PRG1 to the register value BRDIST of the register REG2. Further, the update control unit UCNT2 resets the counter value WCT of the counter COT to “0”.

  In this way, the update control unit UCNT2 initializes the registers REG1 and REG2 and the counter COT without updating the interval storage unit DMEM1 when the counter value WCT and the register value BRDIST match. Thereby, in this embodiment, the frequency | count of an update of the space | interval memory | storage part DMEM1 can be reduced. As a result, power consumption can be reduced.

  The operation of the updating unit UPP2 is not limited to this example. For example, the operation of the updating unit UPP2 may be terminated without performing the processes S124, S130, and S142 when the counter value WCT reaches the maximum value DMAX (Yes in the process S110). In this case, when the branch instruction interval is equal to or greater than the maximum value DMAX, the update unit UPP2 stores the maximum value DMAX in the interval storage unit DMEM1 as the branch instruction interval without dividing the branch instruction interval into a plurality of times (a plurality of locations).

  For example, the update unit UPP2 may determine whether or not the counter value WCT is equal to or greater than the register value BRDIST in the process S124. For example, when the counter value WCT is smaller than the register value BRDIST, the update control unit UCNT2 updates the interval storage unit DMEM1 in process S130. Thus, when the counter value WCT is equal to or greater than the register value BRDIST, the interval storage unit DMEM2 is not updated.

  Alternatively, as shown in FIG. 10, the update unit UPP2 divides the branch instruction interval into a plurality of times (multiple locations) with the already stored branch instruction interval as the upper limit when updating the interval storage unit DMEM1. It may be updated.

  FIG. 10 shows another example of the operations of the update unit UPP2 and the counter COT shown in FIG. For example, in the operation of FIG. 10, a branch instruction interval (hereinafter referred to as an actually measured branch instruction interval) based on the measurement of the counter COT is stored in the interval storage unit DMEM1 (hereinafter referred to as a branch instruction interval before update). The branch instruction interval is divided into a plurality of times (multiple locations) and stored. For example, the address of the interval storage unit DMEM1 referred to based on the branch instruction interval before update (hereinafter also referred to as a relay address) is calculated based on the difference between the actually measured branch instruction interval and the branch instruction interval before update. Interval is written.

  Processes S100 to S142 are performed each time the decoding process is performed, for example. In the operation shown in FIG. 10, processes S112 and S114 are added to the operation shown in FIG. The other operations of the update unit UPP2 and the counter COT are the same as the operations illustrated in FIG.

  Process S112 is performed when the instruction is not a branch instruction and the counter value WCT is not the maximum value DMAX (No in process S110). In process S112, the update control unit UCNT2 determines whether or not the counter value WCT is “0”. Thereby, it is possible to prevent the process S114 from being performed when a meaningless value is held in the register value BRDIST.

  When the counter value WCT is “0” (Yes in process S112), the counter value WCT is counted up in process S120. On the other hand, when the counter value WCT is not “0” (No in process S112), the operation of the update unit UPP2 proceeds to process S114. In process S114, the update control unit UCNT2 determines whether or not the counter value WCT matches the register value BRDIST. When the counter value WCT and the register value BRDIST do not match (No in process S114), the counter value WCT is counted up in process S120.

  On the other hand, when the counter value WCT matches the register value BRDIST (Yes in process S114), the update control unit UCNT2 initializes the registers REG1, REG2 and the counter COT in process S142. Thus, when the branch instruction interval based on the measurement of the counter COT is larger than the branch instruction interval before the update, the PC value (hereinafter also referred to as the relay PC value) when the counter value WCT coincides with the register value BRDIST is used as a starting point. Thus, the interval (difference) until the next branch instruction is measured. The interval obtained by this measurement corresponds to the interval calculated based on the difference between the actually measured branch instruction interval and the branch instruction interval before update.

  When the branch instruction after the relay PC value is executed (Yes in process S100), for example, in process S130, the relay address (BRPC ′) of the interval storage unit DMEM1 referred to based on the branch instruction interval before the update. ), The counter value WCT measured from the relay PC value is written. In this way, the update unit UPP2 updates the contents of the interval storage unit DMEM1 using the relay PC value without updating the contents to a value that is larger than the already stored branch instruction interval.

  That is, for example, even when the branch direction of the branch instruction is different from the current time and the previous time, the update unit UPP2 keeps the information on the current branch instruction interval using the relay PC value while leaving the information on the previous branch instruction interval. Store in the storage unit DMEM1. Thereby, for example, in this embodiment, even when the branch instruction interval differs between the establishment and non-establishment of the branch, it is possible to cope with both the establishment and non-establishment of the branch by using the relay PC value.

  Note that the update operation corresponding to both establishment and failure of the branch is not limited to this example. For example, the update unit UPP2 may use a flag indicating that a meaningless value is held in the register value BRDIST. For example, the branch prediction device BPRE2 may increase the data width of the register value BRDIST by 1 bit from the branch instruction interval DIST and assign the most significant bit to the flag. For example, the flag is set to “1” by the prediction control unit PCNT2 when the instruction does not read the branch instruction interval DIST from the interval storage unit DMEM1. Since the register value BRDIST at this time becomes larger than the maximum value DMAX, the process S102 may be omitted.

  As described above, also in this embodiment, the same effect as that of the above-described embodiment can be obtained. Furthermore, in this embodiment, when the contents of the interval storage unit DMEM1 do not change, the interval storage unit DMEM1 is not updated. Thereby, in this embodiment, the frequency | count of update of the space | interval memory | storage part DMEM1 can be reduced, and power consumption can be reduced. Further, when updating using the relay PC value, it is possible to cope with both the establishment and non-establishment of the branch, so that the frequency of predicting that the branch instruction is not a branch instruction can be reduced. As a result, the cycle performance of the processor can be improved. That is, in this embodiment, the power consumption can be reduced while preventing the cycle performance of the processor from being lowered.

  FIG. 11 shows an example of the branch prediction apparatus BPRE2 that performs the update operation at the stage of the arithmetic processing. The same elements as those described in the above-described embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted. A code PC3 in FIG. 11 indicates a PC value held in the pipeline register PRG3. The configuration of the branch prediction device BPRE2 of this embodiment is connected to the processor so that the counter COT and the update unit UPP2 operate at the same stage as the stage of arithmetic processing (ALU processing). The other configuration of the branch prediction apparatus BPRE2 of this embodiment is the same as that of the branch prediction apparatus BPRE2 of the embodiment described with reference to FIGS. The operation of the branch prediction device BPRE2 of this embodiment is the same as that of the branch prediction device BPRE2 shown in FIG. 8 except that the counter COT and the update unit UPP2 operate at the same stage as the arithmetic processing stage.

  As described above, also in this embodiment, the same effect as that of the embodiment described with reference to FIGS. The branch prediction device BPRE1 of the embodiment described with reference to FIGS. 1 to 7 may also be connected to the processor so that the counter COT and the update unit UPP1 operate at the same stage as the operation processing stage. Also in this case, the same effect as the embodiment described with reference to FIGS. 1 to 7 can be obtained.

  FIG. 12 shows an example of the branch prediction apparatus BPRE3 in another embodiment. The same elements as those described in the above-described embodiment are denoted by the same reference numerals, and detailed description thereof will be omitted. A code TAGH in FIG. 12 indicates, for example, a tag comparison result held in the pipeline register PRG1. The tag comparison result TAGH is output from the prediction control unit PCNT3. A symbol BRTAGH indicates a tag comparison result held in the register REG3.

  The configuration of the branch prediction device BPRE3 of this embodiment is provided with an interval storage unit DMEM3, a prediction control unit PCNT3, and an update unit UPP3 instead of the interval storage unit DMEM1, the prediction control unit PCNT2, and the update unit UPP2 shown in FIG. ing. The other configuration of the branch prediction apparatus BPRE3 is the same as that of the embodiment described with reference to FIGS. The configuration of the processor on which the branch prediction device BPRE3 is mounted is the same as that of the embodiment described with reference to FIGS.

  As shown in FIG. 13, the interval storage unit DMEM3 stores data DAT including a tag TAG and a branch instruction interval DIST. Other configurations of the interval storage unit DMEM3 are the same as those of the interval storage unit DMEM1. For example, the interval storage unit DMEM3 may be configured by adding a bit for storing the branch instruction interval to the bit width of the direction history memory or the branch destination history memory of the history storage unit HMEM.

  For example, the prediction control unit PCNT3 compares the tag TAG with a part of the PC value, and outputs the tag comparison result TAGH to the pipeline register PRG1. The other configuration of the prediction control unit PCNT3 is the same as that of the prediction control unit PCNT2 shown in FIG.

  In the update unit UPP3, a register REG3 is added to the update unit UPP2 illustrated in FIG. 8, and an update control unit UCNT3 is provided instead of the update control unit UCNT2. The register REG3 holds, for example, a tag comparison result TAGH. For example, the register value BRTAGH (TAGH) of the register REG3 is updated every time a branch instruction is executed. The other configuration of the update unit UPP3 is the same as that of the update unit UPP2 shown in FIG.

  Note that the configuration of the branch prediction device BPRE3 is not limited to this example. For example, as shown in FIG. 11, the branch prediction device BPRE3 may be connected to the processor so that the counter COT and the update unit UPP3 operate at the same stage as the operation processing stage.

  FIG. 13 illustrates an example of the interval storage unit DMEM3 and the prediction control unit PCNT3 illustrated in FIG. FIG. 13 illustrates an example of the program counter PC, the interval storage unit DMEM3, and the prediction control unit PCNT3 for a 32-bit instruction.

  For example, the interval storage unit DMEM3 uses the upper 6 bits (PCb) of the lower 8 bits of the PC value for the address ADR. Here, in the processor of the 32-bit instruction, since the least significant 2 bits (PCa) of the PC value are fixed values, they may not be used for the address ADR of the interval storage unit DMEM3. Note that the bit width of the address ADR is not limited to 6 bits.

  The data DAT in the interval storage unit DMEM3 has a tag TAG indicating the upper 24 bits (PCc) of the PC value and a branch instruction interval DIST. For example, 4 bits are assigned to the branch instruction interval DIST. Note that the data width of the branch instruction interval DIST is not limited to 4 bits. Further, the data width of the tag TAG is not limited to 24 bits.

  The prediction control unit PCNT3 includes, for example, a counter PCOT, a tag determination unit DET, and a selection unit SEL. For example, the prediction control unit PCNT3 receives the PC value (PC0) and measures the number of instructions using the counter PCOT. Further, the prediction control unit PCNT3 reads the tag TAG and the branch instruction interval DIST (DISTi) from the interval storage unit DMEM3, and outputs the tag comparison result TAGH and the branch instruction interval DIST (DISTO). For example, the prediction control unit PCNT3, when the previously read branch instruction interval DIST matches the number of instructions measured by the counter PCOT, the address ADR indicated by the upper 6-bit portion PCb of the lower 8 bits of the PC value Data DAT (tag TAG, branch instruction interval DIST) is read.

  The counter PCOT is, for example, a down counter that counts down every time the PC value is updated. The counter PCOT may be an up counter that counts up whenever the PC value is updated. That is, the counter PCOT is a counter that measures the number of instructions.

  The tag determination unit DET compares the tag TAG read from the interval storage unit DMEM3 with the upper 24-bit portion PCc of the PC value, and outputs a tag comparison result TAGH that is a comparison result. For example, the tag determination unit DET sets the tag comparison result TAGH to “1” when the tag TAG matches the upper 24-bit portion PCc of the PC value. For example, the tag determination unit DET sets the tag comparison result TAGH to “0” when the tag TAG does not match the upper 24-bit portion PCc of the PC value.

  For example, the selection unit SEL outputs one of the branch instruction interval DISTi and “0” read from the interval storage unit DMEM3 as the branch instruction interval DISTo in accordance with the tag comparison result TAGH received from the tag determination unit DET. For example, the selection unit SEL uses the branch instruction interval DISTi read from the interval storage unit DMEM3 as the branch instruction when the tag TAG matches the upper 24-bit portion PCc of the PC value (for example, when TAGH is “1”). Output as interval DISTo. Further, the selection unit SEL sets the branch instruction interval DISTo to, for example, “0” when the tag TAG and the upper 24-bit portion PCc of the PC value do not match (for example, when TAGH is “0”).

  FIG. 14 shows an example of the operation of the prediction control unit PCNT3 shown in FIG. Processes S200-S270 are performed each time an instruction fetch process is performed, for example.

  In the process S200, it is determined whether or not the counter value of the counter PCOT is “0”. For example, the counter value of the counter PCOT is “0” until the PC value of the first branch instruction is output. When the counter value of the counter PCOT is not “0” (No in process S200), the counter value of the counter PCOT is counted down in process S210. In step S220, the prediction control unit PCNT3 sets the branch instruction interval DISTo and the tag comparison result TAGH to “0”.

  On the other hand, when the counter value of the counter PCOT is “0” (Yes in process S200), the operation of the prediction control unit PCNT3 proceeds to process S230. In the process S230, the prediction control unit PCNT3 notifies the prediction unit PRED that it is the reference timing to the history storage unit HMEM, for example. Thereby, the prediction unit PRED performs branch prediction with reference to the history storage unit HMEM. In process S230, the prediction control unit PCNT3 reads data DAT including the tag TAG and the branch instruction interval DIST (DISTi) from the address ADR (PCb) of the interval storage unit DMEM3. The address ADR (PCb) is, for example, an address indicated by the upper 6-bit portion PCb of the lower 8 bits of the PC value.

  In step S240, the tag determination unit DET compares the upper 24-bit portion PCc of the PC value with the tag TAG read in step S230. When the tag TAG does not match the value PCc (No in process S240), the operation of the prediction control unit PCNT3 proceeds to process S250. In the process S250, for example, the tag determination unit DET sets the tag comparison result TAGH to “0”, and the selection unit SEL sets the branch instruction interval DISTo to “0”. Then, in step S270, the prediction control unit PCNT3 sets the counter value of the counter PCOT to the branch instruction interval DISTo (“0”).

  On the other hand, when the tag TAG matches the value PCc (Yes in process S240), the operation of the prediction control unit PCNT3 proceeds to process S260. In the process S260, for example, the tag determination unit DET sets the tag comparison result TAGH to “1”. In addition, the selection unit SEL outputs the branch instruction interval DISTi read in step S230 as the branch instruction interval DISTO. In step S270, the prediction control unit PCNT3 sets the counter value of the counter PCOT to the branch instruction interval DISTo (the branch instruction interval DISTi read in step S230).

  In this way, the prediction control unit PCNT3 validates the branch instruction interval DIST read from the interval storage unit DMEM3 when the upper 24-bit portion PCc of the PC value matches the tag TAG read in step S230. Here, for example, when the counter value of the counter PCOT is not “0” (No in process S200), the program counter PC sets the PC value to a value indicating the next successive instruction (for example, a value increased by 4). Update. For example, when the counter value of the counter PCOT is “0” (Yes in process S200), the PC value is set to a value according to the branch prediction result.

  The operation of the prediction control unit PCNT3 is not limited to this example. For example, when the counter PCOT is an up counter, in step S200, it is determined whether or not the branch instruction interval DIST matches the counter value of the counter PCOT. In this case, as the branch instruction interval DIST compared with the counter value of the counter PCOT, for example, in step S270, the branch instruction interval DISTo is held in a register or the like. In step S270, the counter PCOT is reset to “0”, for example.

  FIG. 15 shows an example of operations of the updating unit UPP3 and the counter COT shown in FIG. In the operation illustrated in FIG. 15, the update unit UPP3 updates the interval storage unit DMEM3 so that the branch instruction interval is not written to an address corresponding to an instruction other than the branch instruction. That is, in the operation shown in FIG. 15, when the branch instruction interval is equal to or greater than the maximum value DMAX, the update unit UPP3 updates the interval storage unit DMEM1 without dividing the branch instruction interval a plurality of times (a plurality of locations).

  The codes BRPCb and BRPCc in FIG. 15 correspond to PC value portions PCb and PCc, respectively. That is, the register value BRPCb is, for example, the upper 6 bits of the lower 8 bits of the register value BRPC. The register value BRPCc is, for example, the upper 24 bits of the register value BRPC.

  Processes S100-S144 are performed each time the decoding process is performed, for example. In the operation illustrated in FIG. 15, the process S122 is added to the operation illustrated in FIG. 9, and the processes S126, S132, and S144 are performed instead of the processes S124, S130, and S142. Moreover, the process implemented after the determination result (Yes) of process S110 differs from the operation | movement shown in FIG. The other operations of the update unit UPP3 and the counter COT are the same as the operations illustrated in FIG.

  When the instruction is other than a branch instruction and the counter value WCT is the maximum value DMAX (Yes in step S110), the counter value WCT is not counted up. That is, when the counter value WCT is the maximum value DMAX, the counter value WCT is maintained at the maximum value DMAX that can be stored with the data width of the interval storage unit DMEM3 until the interval storage unit DMEM3 is updated.

  Process S122 is performed when the instruction is a branch instruction (Yes in process S100). In process S122, the update control unit UCNT3 determines whether or not the register value BRTAGH is “1”. That is, the update control unit UCNT3 determines whether or not the upper 24-bit portion PCc of the PC value to be updated matches the tag TAG.

  When the register value BRTAGH is “1” (Yes in process S122), the operation of the update unit UPP3 proceeds to process S126. In the process S126, for example, the comparison unit COM compares the counter value WCT with the register value BRDIST. For example, the update control unit UCNT3 determines whether or not the counter value WCT is greater than or equal to the register value BRDIST based on the comparison result of the comparison unit COM. That is, the update control unit UCNT3 determines whether the counter value WCT is equal to or greater than the register value BRDIST when the tag TAG and the value PCc match.

  When the counter value WCT is smaller than the register value BRDIST (No in process S126), the update control unit UCNT3 updates the interval storage unit DMEM3 in process S132. Thereby, for example, in this embodiment, it is possible to prevent branch prediction from being performed at the time of a branch instruction. Therefore, in this embodiment, the power consumption can be reduced while preventing the cycle performance of the processor from being lowered.

  When the counter value WCT is greater than or equal to the register value BRDIST (Yes in process S126), the update control unit UCNT3 initializes the registers REG1, REG2, REG3, and the counter COT in process S144. Thus, when the counter value WCT is equal to or greater than the register value BRDIST, the interval storage unit DMEM3 is not updated.

  When the register value BRTAGH is not “1” (No in process S122), the update control unit UCNT3 updates the interval storage unit DMEM3 in process S132. That is, the update control unit UCNT3 updates the interval storage unit DMEM3 when the tag TAG and the value PCc do not match.

  In process S132, the update control unit UCNT3 updates the data DAT of the address ADR (register value BRPCb) of the interval storage unit DMEM3 based on the register value BRPCc and the counter value WCT. As a result, the tag TAG and the branch instruction interval DIST of the data DAT at the address ADR (register value BRPCb) of the interval storage unit DMEM3 are updated to the register value BRPCc and the counter value WCT, respectively.

  As described above, when the tag TAG matches the value PCc and the counter value WCT is smaller than the register value BRDIST, the interval storage unit DMEM3 is updated. Alternatively, the interval storage unit DMEM3 is updated when the tag TAG and the value PCc do not match. For example, when the process S132 is performed after the determination result (Yes) of the process S110, the branch instruction interval DIST stored in the interval storage unit DMEM3 is the maximum value DMAX.

  In process S144, the update control unit UCNT3 initializes the registers REG1, REG2, REG3 and the counter COT. For example, the update control unit UCNT3 sets the PC value (PC1), branch instruction interval DIST, and tag comparison result TAGH held in the pipeline register PRG1 to the register value BRPC, the register value BRDIST, and the register value BRTAGH, respectively. Further, the update control unit UCNT3 resets the counter value WCT of the counter COT to “0”. In this way, the update unit UPP3 updates the interval storage unit DMEM3 so as not to write the branch instruction interval to an address corresponding to an instruction other than the branch instruction, for example.

  The operation of the update unit UPP3 is not limited to this example. For example, the operation of the update unit UPP3 may move to the process S122 when the counter value WCT reaches the maximum value DMAX (Yes in the process S110). That is, the update unit UPP3 may update the interval storage unit DMEM3 when the counter value WCT reaches the maximum value DMAX. At this time, the update unit UPP3 sets a flag indicating that the interval storage unit DMEM3 has been updated.

  For example, the update unit UPP3 does not update the interval storage unit DMEM3 while the flag indicating that the interval storage unit DMEM3 has been updated is set. When the branch instruction is executed after setting the flag, the flag is cleared without updating the interval storage unit DMEM3. At this time, the update control unit UCNT3 initializes the registers REG1, REG2, REG3 and the counter COT.

  Further, the update unit UPP3 may determine whether or not the counter value WCT and the register value BRDIST match in the process S126. In this case, the interval storage unit DMEM3 is updated when the counter value WCT and the register value BRDIST do not match, as in the operation shown in FIG. For example, when the counter value WCT and the register value BRDIST do not match, the update control unit UCNT3 updates the interval storage unit DMEM3 in process S132. For example, the update control unit UCNT3 does not update the interval storage unit DMEM3 when the counter value WCT matches the register value BRDIST. That is, the updating unit UPP3 may update the interval storage unit DMEM3 when the counter value WCT and the register value BRDIST do not match regardless of whether or not the counter value WCT is smaller than the register value BRDIST.

  Alternatively, the updating unit UPP3 may perform the process S122 after the determination result (Yes) of the process S110, and may determine whether or not the counter value WCT and the register value BRDIST match in the process S126. Thereby, the branch instruction interval equal to or greater than the maximum value DMAX in the interval storage unit DMEM3 is stored in a plurality of times (in a plurality of locations) as in the operation shown in FIG.

  Further, as illustrated in FIG. 10, the update unit UPP3 may perform the processes S112 and S114 after the determination result (No) of the process S110. That is, the update unit UPP3 may update the contents of the interval storage unit DMEM3 using the relay PC value without updating the contents of the interval storage unit DMEM3 to a value larger than the already stored branch instruction interval.

  In addition, in the update operation for the interval storage unit DMEM3 having a configuration in which a bit for storing the branch instruction interval is added to the bit width of the branch destination history memory, the update unit UPP3 stores the interval only when a branch by the branch instruction is established. The part DMEM3 may be updated.

  As described above, also in this embodiment, the same effect as that of the embodiment described with reference to FIGS.

The invention described in the above embodiments is organized and disclosed as an appendix.
(Appendix 1)
A prediction unit that has a history storage unit that stores a result of the branch instruction, and performs branch prediction with reference to the history storage unit;
An interval storage unit that stores an interval of the branch instruction corresponding to the branch instruction;
A control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit;
A counter for measuring the interval between the branch instructions;
An update unit that updates the contents of the interval storage unit based on the interval of the branch instruction measured by the counter.
(Appendix 2)
The branch prediction apparatus according to claim 1, wherein the update unit updates the contents of the interval storage unit each time the branch instruction is executed.
(Appendix 3)
The update unit updates the contents of the interval storage unit when the interval of the branch instruction based on the measurement of the counter is different from the interval of the branch instruction stored in the interval storage unit. The branch prediction apparatus according to appendix 1.
(Appendix 4)
The updating unit refers to the branch instruction interval stored when the interval of the branch instruction based on the measurement of the counter is larger than the interval of the branch instruction stored in the interval storage unit. The branch prediction device according to claim 1, wherein an interval calculated based on a difference between the interval of the branch instruction based on the measurement and the interval of the stored branch instruction is written in the address to be executed.
(Appendix 5)
The interval storage unit stores both the interval of the branch instruction when the branch by the branch instruction is established and the interval of the branch instruction when the branch by the branch instruction is not established. The branch prediction apparatus described.
(Appendix 6)
The update unit updates the contents of the interval storage unit when the interval of the branch instruction based on the measurement of the counter is smaller than the interval of the branch instruction stored in the interval storage unit. The branch prediction apparatus according to appendix 1.
(Appendix 7)
A decoding unit that decodes an instruction; and a branch prediction device that performs branch prediction of a branch instruction;
The branch prediction device
A prediction unit that has a history storage unit that stores a result of the branch instruction, and performs branch prediction with reference to the history storage unit;
An interval storage unit that stores an interval of the branch instruction corresponding to the branch instruction;
A control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit;
A counter for measuring the interval between the branch instructions;
An updater that updates the contents of the interval storage unit based on the interval of the branch instruction measured by the counter.
(Appendix 8)
The processor according to claim 7, wherein the update unit updates the contents of the interval storage unit each time the branch instruction is executed.
(Appendix 9)
The update unit updates the contents of the interval storage unit when the interval of the branch instruction based on the measurement of the counter is different from the interval of the branch instruction stored in the interval storage unit. The processor according to appendix 7.
(Appendix 10)
The updating unit refers to the branch instruction interval stored when the interval of the branch instruction based on the measurement of the counter is larger than the interval of the branch instruction stored in the interval storage unit. The processor according to claim 7, wherein an interval calculated based on a difference between the interval between the branch instructions based on the measurement and the interval between the stored branch instructions is written in an address to be processed.
(Appendix 11)
The interval storage unit stores both the interval of the branch instruction when the branch by the branch instruction is established and the interval of the branch instruction when the branch by the branch instruction is not established. The processor described.
(Appendix 12)
The update unit updates the contents of the interval storage unit when the interval of the branch instruction based on the measurement of the counter is smaller than the interval of the branch instruction stored in the interval storage unit. The processor according to appendix 7.

  From the above detailed description, features and advantages of the embodiments will become apparent. This is intended to cover the features and advantages of the embodiments described above without departing from the spirit and scope of the claims. Further, any person having ordinary knowledge in the technical field should be able to easily come up with any improvements and modifications, and there is no intention to limit the scope of the embodiments having the invention to those described above. It is also possible to rely on suitable improvements and equivalents within the scope disclosed in.

  ALU: Arithmetic logic unit; BPRE1, BPRE2, BPRE3: Branch prediction device; COT: Counter; DEC: Decoder; DESM: Branch destination history memory; DET: Tag decision unit; Interval memory unit; HMEM ... history memory unit; IMEM ... instruction memory; PC ... program counter; PCNT1, PCNT2, PCNT3 ... prediction control unit; PCOT ... counter; PRED ... prediction unit; REG2, REG3, register; RPD, register read section; SEL, selection section; UCNT1, UCNT2, UCNT3, update control section; UPP1, UPP2, UPP3, update section

Claims (5)

A prediction unit that has a history storage unit that stores a result of the branch instruction, and performs branch prediction with reference to the history storage unit;
An interval storage unit that stores an interval of the branch instruction corresponding to the branch instruction;
A control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit;
A counter for measuring the interval between the branch instructions;
An update unit that updates the content of the interval storage unit based on the interval of the branch instruction measured by the counter ;
The interval storage unit stores both the interval of the branch instruction when the branch by the branch instruction is established and the interval of the branch instruction when the branch by the branch instruction is not established.
The branch predicting apparatus according to claim. The branch prediction apparatus according to claim 1, wherein the update unit updates the contents of the interval storage unit each time the branch instruction is executed. The update unit updates the contents of the interval storage unit when the interval of the branch instruction based on the measurement of the counter is different from the interval of the branch instruction stored in the interval storage unit. The branch prediction apparatus according to claim 1. A prediction unit that has a history storage unit that stores a result of the branch instruction, and performs branch prediction with reference to the history storage unit;
An interval storage unit that stores an interval of the branch instruction corresponding to the branch instruction;
A control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit;
A counter for measuring the interval between the branch instructions;
An update unit that updates the content of the interval storage unit based on the interval of the branch instruction measured by the counter;
The updating unit refers to the branch instruction interval stored when the interval of the branch instruction based on the measurement of the counter is larger than the interval of the branch instruction stored in the interval storage unit. is in the address, the based on the measurement the branch instruction interval and branch prediction device you and writes the interval is calculated based on the difference between the distance of the branch instruction being the storage of. A decoding unit that decodes an instruction; and a branch prediction device that performs branch prediction of a branch instruction;
The branch prediction device
A prediction unit that has a history storage unit that stores a result of the branch instruction, and performs branch prediction with reference to the history storage unit;
An interval storage unit that stores an interval of the branch instruction corresponding to the branch instruction;
A control unit that determines the timing of referring to the history storage unit based on the interval of the branch instruction stored in the interval storage unit;
A counter for measuring the interval between the branch instructions;
An update unit that updates the content of the interval storage unit based on the interval of the branch instruction measured by the counter ;
The interval storage unit stores both the interval of the branch instruction when the branch by the branch instruction is established and the interval of the branch instruction when the branch by the branch instruction is not established.
Processor characterized by.

Images