Processor apparatus for executing instructions with local slack prediction of instructions and processing method therefor

• US 20070234014A1
• Filed: 03/13/2007
• Published: 10/04/2007
• Est. Priority Date: 03/28/2006
• Status: Abandoned Application

• Current Assignee: Semiconductor Technology Academic Research Center
• Original Assignee: Semiconductor Technology Academic Research Center
• Inventors: Kobayashi, Ryotaro, Hayashi, Hisahiro
• Application Number:
  US11/717,063
• Publication Number:
  US 20070234014A1
• Time in Patent Office: Days
• US Class Current: 712/220
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A processor predicts predicted slack which is a predicted value of local slack of an instruction to be executed and executes the instruction using the predicted slack. A slack table is referred to upon execution of an instruction to obtain predicted slack of the instruction and execution latency is increased by an amount equivalent to the obtained predicted slack. Then, it is estimated, based on behavior exhibited upon execution of the instruction, whether or not the predicted slack has reached target slack which is an appropriate value of current local slack of the instruction. The predicted slack is gradually increased each time the instruction is executed, until it is estimated that the predicted slack has reached the target slack.

Claims

1. A processor apparatus for predicting predicted slack which is a predicted value of local slack of an instruction to be executed by the processor apparatus and executing the instruction using the predicted slack, the processor apparatus comprising:

a storage unit for storing a slack table including the predicted slack;

a setting unit for referring to the slack table upon execution of an instruction to obtain predicted slack of the instruction and increasing execution latency by an amount equivalent to the obtained predicted slack;

an estimation unit for estimating, based on behavior exhibited upon execution of the instruction, whether or not the predicted slack has reached target slack which is an appropriate value of current local slack of the instruction; and

an update unit for gradually increasing the predicted slack each time the instruction is executed until it is estimated by the estimation unit that the predicted slack has reached the target slack.

2. The processor apparatus as claimed in claim 1,

wherein the update unit changes a parameter to be used to update the slack, according to a value of the predicted slack such that a degradation in performance of the processor apparatus is suppressed while a number of slack instructions is maintained.

3. The processor apparatus as claimed in claim 2,

wherein the update unit changes the parameter to be used to update the slack, according to whether the predicted slack is larger than or equal to a predetermined threshold value.

4. The processor apparatus as claimed in claim 1,

wherein the estimation unit estimates that the predicted slack has reached the target slack, using, as an establishment condition for the estimation, at least one of the following facts:

(A) a branch prediction miss occurs upon execution of the instruction;

(B) a cache miss occurs upon execution of the instruction;

(C) operand forwarding to a subsequent instruction occurs;

(D) store data forwarding to a subsequent instruction occurs;

(E) the instruction is the oldest one of instructions present in an instruction window;

(F) the instruction is the oldest one of instructions present in a reorder buffer;

(G) the instruction is an instruction that passes an execution result to the oldest one of the instructions present in the instruction window;

(H) the instruction is an instruction that passes an execution result to a largest number of subsequent instructions among instructions executed in a same cycle; and

(I) a number of subsequent instructions that are brought into an executable state by passing an execution result of the instruction is larger than or equal to a predetermined determination value.

5. The processor apparatus as claimed in claim 1, further comprising a reliability counter in which when an establishment condition for an estimation that the predicted slack has reached the target slack is established, a counter value of the reliability counter is increased or decreased, and when the establishment condition for the estimation is not established, the counter value is decreased or increased,

wherein the update unit increases the predicted slack on a condition that the counter value of the reliability counter is an increase determination value and decreases the predicted slack on a condition that the counter value of the reliability counter is a decrease determination value.

6. The processor apparatus as claimed in claim 5,

wherein an amount of increase or decrease in the counter value upon establishment of the establishment condition for the estimation in the reliability counter is set to a value larger than that of an amount of decrease or increase in the counter value upon non-establishment of the establishment condition for the estimation.

7. The processor apparatus as claimed in claim 5,

wherein amounts of increase and decrease in the counter value are set to be different for different types of instructions.

8. The processor apparatus as claimed in claim 1,

wherein an amount of update of the predicted slack of each instruction at a time by the update unit is set to be different for different types of each instruction.

9. The processor apparatus as claimed in claim 1,

wherein an upper limit value is set to the predicted slack of each instruction to be updated by the update unit and the upper limit value is set to be different for different types of instructions.

10. The processor apparatus as claimed in claim 1, further comprising a branch history register in which a branch history of a program is kept,

wherein the slack table individually stores the predicted slack of the instruction for different branch patterns obtained by referring to the branch history register.

11. A processing method for use in a processor apparatus that predicts predicted slack which is a predicted value of local slack of an instruction to be executed by the processor apparatus and executes the instruction using the predicted slack, the processing method including:

a control step of executing an instruction to be executed by the processor apparatus such that execution latency of the instruction is increased by an amount equivalent to a value of the predicted slack, estimating, based on behavior exhibited upon execution of the instruction, whether or not the predicted slack has reached target slack which is an appropriate value of current local slack, and updating the predicted slack each time the instruction is executed so as to gradually increase the predicted slack, until it is estimated that the predicted slack has reached the target slack.

12. The processing method for use in the processor apparatus as claimed in claim 11,

wherein in the control step, a parameter to be used to update the slack is changed according to the value of the predicted slack such that a degradation in performance of the processor apparatus is suppressed while a number of slack instructions is maintained.

13. The processing method for use in the processor apparatus as claimed in claim 12,

wherein in the control step, the parameter to be used to update the slack is changed according to whether the predicted slack is larger than or equal to a predetermined threshold value.

14. The processing method for use in the processor apparatus as claimed in claim 11,

wherein an establishment condition for an estimation that the predicted slack has reached the target slack includes at least one of the following facts:

(A) a branch prediction miss occurs upon execution of the instruction;

(B) a cache miss occurs upon execution of the instruction;

(C) operand forwarding to a subsequent instruction occurs;

(D) store data forwarding to a subsequent instruction occurs;

(E) the instruction is the oldest one of instructions present in an instruction window;

(F) the instruction is the oldest one of instructions present in a reorder buffer;

(G) the instruction is an instruction that passes an execution result to the oldest one of the instructions present in the instruction window;

(H) the instruction is an instruction that passes an execution result to a largest number of subsequent instructions among instructions executed in a same cycle; and

(I) a number of subsequent instructions that are brought into an executable state by passing an execution result of the instruction is larger than or equal to a predetermined determination value.

15. The processing method for use in the processor apparatus as claimed in claim 11,

wherein the predicted slack is decreased when it is estimated that the predicted slack has reached the target slack.

16. The processing method for use in the processor apparatus as claimed in claim 15,

wherein an increase of the predicted slack is performed on a condition that a number of non-establishments for an establishment condition for an estimation that the predicted slack has reached the target slack reaches a specified number of times, and a decrease of the predicted slack is performed on a condition that a number of establishments for the establishment condition reaches a specified number of times.

17. The processing method for use in the processor apparatus as claimed in claim 16,

wherein the number of non-establishments for the establishment condition required to increase the predicted slack is set to a value larger than that of the number of establishments for the establishment condition required to decrease the predicted slack.

18. The processing method for use in the processor apparatus as claimed in claim 15,

wherein an increase of the predicted slack is performed on a condition that a number of non-establishments for an establishment condition for an estimation that the predicted slack has reached the target slack reaches a specified number of times, and a decrease of the predicted slack is performed on a condition that the establishment condition is established.

19. The processing method for use in the processor apparatus as claimed in claim 16,

wherein the specified number of times is set to be different for different types of the instructions.

20. The processing method for use in the processor apparatus as claimed in claim 11,

wherein an amount of update of predicted slack at a time is set to be different for different types of the instructions.

21. The processing method for use in the processor apparatus as claimed in claim 11,

wherein an upper limit value of the predicted slack is set to be different for different types of the instructions.

22. A processor apparatus for predicting predicted slack which is a predicted value of local slack of an instruction to be stored at a memory address of a main storage apparatus and executed by the processor apparatus, and executing the instruction using the predicted slack, the processor apparatus comprising:

a control unit for predicting and determining that a store instruction having predicted slack larger than or equal to a predetermined threshold value has no data dependency relationship with a subsequent load instruction to the store instruction and speculatively executing the subsequent load instruction even if a memory address of the store instruction is not known.

23. The processor apparatus as claimed in claim 22,

wherein, when a memory address of a load instruction is known and a preceding store instruction to the load instruction is such one case of the following:

(1) a memory address is known; and

(2) though the memory address is not known, predicted slack of the store instruction is larger than or equal to the threshold value,

the control unit makes an address comparison between the load instruction and a store instruction which is preceding to the load instruction and whose memory address is known, and executes memory access when it is determined that there is no dependency relationship between the load instruction and a store instruction whose memory address is not known and which has predicted slack larger than or equal to the threshold value;

otherwise, the control unit obtains data from a dependent store instruction by forwarding, thereby predicting a memory dependency relationship and speculatively executes the load instruction.

24. The processor apparatus as claimed in claim 23,

wherein the control unit compares, after a memory address of a store instruction having predicted slack larger than or equal to the threshold value is found out, the memory address of the store instruction with a memory address of a subsequent load instruction whose execution has been completed and determines, if the memory addresses are not matched, that memory dependence prediction is successful and thus executes memory access;

on the other hand, if the memory addresses are matched, the control unit determines that the memory dependence prediction is failed and thus flushes the load instruction having a matched memory address and an instruction subsequent thereto from the processor apparatus and redoes execution of the instructions.

25. A processing method for use in a processor apparatus for predicting predicted slack which is a predicted value of local slack of an instruction to be stored at a memory address of a main storage apparatus and executed by the processor apparatus, and executing the instruction using the predicted slack, the processing method comprising:

a control step of predicting and determining that a store instruction having predicted slack larger than or equal to a predetermined threshold value has no data dependency relationship with a subsequent load instruction to the store instruction and speculatively executing the subsequent load instruction even if a memory address of the store instruction is not known.

26. The processing method for use in the processor apparatus as claimed in claim 25,

wherein when a memory address of a load instruction is known and a preceding store instruction to the load instruction is such one case of the following:

(1) a memory address is known; and

(2) though the memory address is not known, predicted slack of the store instruction is larger than or equal to the threshold value,

in the control step, an address comparison between the load instruction and a store instruction which is preceding to the load instruction and whose memory address is known is made and memory access is executed when it is determined that there is no dependency relationship between the load instruction and a store instruction whose memory address is not known and which has predicted slack larger than or equal to the threshold value;

otherwise, by obtaining data from a dependent store instruction by forwarding, a memory dependency relationship is predicted and the load instruction is speculatively executed.

27. The processing method for use in the processor apparatus as claimed in claim 26,

wherein in the control step, after a memory address of a store instruction having predicted slack larger than or equal to the threshold value is found out, the memory address of the store instruction is compared with a memory address of a subsequent load instruction whose execution has been completed and it is determined, if the memory addresses are not matched, that memory dependence prediction is successful and thus memory access is executed;

on the other hand, if the memory addresses are matched, it is determined that the memory dependence prediction is failed and thus the load instruction having a matched memory address and an instruction subsequent thereto are flushed from the processor apparatus and execution of the instructions is redone.

28. A processor apparatus for predicting, using a predetermined first prediction method, predicted slack which is a predicted value of local slack of an instruction to be stored at a memory address of a main storage apparatus and executed by the processor apparatus, and executing the instruction using the predicted slack, the processor apparatus comprising:

a control unit for propagating, using a second prediction method which is a slack prediction method based on shared information and based on an instruction having local slack, shared information indicating that there is sharable slack, from a dependent destination to a dependent source between instructions that do not have local slack, and determining an amount of local slack used by each instruction based on the shared information and using a predetermined heuristic technique, thereby performing control to enable the instructions that do not have local slack to use local slack.

29. The processor apparatus as claimed in claim 28,

wherein the control unit propagates the shared information when predicted slack of an instruction is larger than or equal to a predetermined threshold value.

30. The processor apparatus as claimed in claim 29,

wherein the control unit calculates and updates, based on behavior exhibited upon execution of an instruction and the shared information, predicted slack of the instruction and reliability indicating a degree of whether or not the predicted slack can be used.

31. The processor apparatus as claimed in claim 30,

wherein the control unit performs an update such that when the control unit receives shared information upon execution of an instruction, the control unit determines that the predicted slack has not yet reached usable slack and thus increases the reliability;

otherwise, the control unit determines that the predicted slack has reached the usable slack and thus decreases the reliability and when the reliability is decreased to a predetermined value, the control unit decreases the predicted slack and when the reliability is larger than or equal to a predetermined threshold value, the control unit increases the predicted slack.

32. The processor apparatus as claimed in claim 30,

wherein the control unit includes:

a first storage unit for storing a slack table;

a second storage unit for storing a slack propagation table; and

an update unit for updating the slack table and the slack propagation table,

wherein the slack table includes for each of all instructions;

(a) a propagation flag (Pflag) indicating whether a local slack prediction is made using the first prediction method or the second prediction method;

(b) the predicted slack; and

(c) reliability indicating a degree of whether or not the predicted slack can be used,

wherein the slack propagation table includes for each of instructions that do not have local slack;

(a) memory addresses of the instructions that do not have the local slack;

(b) a predicted slack of the instructions that do not have the local slack; and

(c) reliability indicating a degree of whether or not the predicted slack of the instructions that do not have the local slack can be used, and

wherein, when a propagation flag of a received instruction indicates that a local slack prediction is made using the second prediction method, the update unit updates the slack table and the slack propagation table based on predicted slack and reliability of the received instruction and using the second prediction method;

on the other hand, when the propagation flag of the received instruction indicates that a local slack prediction is made using the first prediction method, the update unit updates the slack table based on the predicted slack and the reliability of the received instruction and using the first prediction method.

33. A processing method for use in a processor apparatus for predicting, using a predetermined first prediction method, predicted slack which is a predicted value of local slack of an instruction to be stored at a memory address of a main storage apparatus and executed by the processor apparatus, and executing the instruction using the predicted slack, the processing method comprising:

a control step of propagating, using a second prediction method which is a slack prediction method based on shared information and based on an instruction having local slack, shared information indicating that there is sharable slack, from a dependent destination to a dependent source between instructions that do not have local slack, and determining an amount of local slack used by each instruction based on the shared information and using a predetermined heuristic technique, thereby performing control to enable the instructions that do not have local slack to use local slack.

34. The processing method for use in the processor apparatus as claimed in claim 33,

wherein in the control step, when predicted slack of an instruction is larger than or equal to a predetermined threshold value, the shared information is propagated.

35. The processing method for use in the processor apparatus as claimed in claim 34,

wherein in the control step, based on behavior exhibited upon execution of an instruction and the shared information, predicted slack of the instruction and reliability indicating a degree of whether or not the predicted slack can be used are calculated and updated.

36. The processing method for use in the processor apparatus as claimed in claim 35,

wherein in the control step, an update is performed such that it is determined, when shared information is received upon execution of an instruction, that the predicted slack has not yet reached usable slack and thus the reliability is increased;

otherwise, it is determined that the predicted slack has reached the usable slack and thus the reliability is decreased and when the reliability is decreased to a predetermined value, the predicted slack is decreased and when the reliability is larger than or equal to a predetermined threshold value, the predicted slack is increased.