Processor Apparatus for Executing Instructions with Local Slack Prediction of Instructions and Processing Method Therefor

• US 20100095151A1
• Filed: 12/09/2009
• Published: 04/15/2010
• Est. Priority Date: 03/28/2006
• Status: Abandoned Application

• Current Assignee: Hisahiro Hayashi, Ryotaro Kobayashi
• Original Assignee: Hisahiro Hayashi, Ryotaro Kobayashi
• Inventors: HAYASHI, Hisahiro, KOBAYASHI, Ryotaro
• Application Number:
  US12/634,069
• Publication Number:
  US 20100095151A1
• Time in Patent Office: Days
• US Class Current: 714/16
• 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-21. -21. (canceled)

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.