PROCESSOR, MULTIPROCESSOR SYSTEM AND METHOD FOR SPECULATIVELY EXECUTING MEMORY OPERATIONS USING MEMORY TARGET ADDRESSES OF THE MEMORY OPERATIONS TO INDEX INTO A SPECULATIVE EXECUTION RESULT HISTORY STORAGE MEANS TO PREDICT THE OUTCOME OF THE MEMORY OPERATION

• US 6,970,997 B2
• Filed: 05/22/2002
• Issued: 11/29/2005
• Est. Priority Date: 05/23/2001
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Torii, Sunao, Shibayama, Atsufumi, Nishi, Naoki, Matsushita, Satoshi
• Primary Examiner(s): Chan, Eddie
• Assistant Examiner(s): Buehl, Brett
• Application Number:
  US10/151,819
• Publication Number:
  US 20020178349A1
• Time in Patent Office: 1,287 Days
• Field of Search: 712/239, 712/240, 712/235, 712/216, 712/217, 712/218, 712/219, 712/225, 712/238
• US Class Current: 712/225
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3842 Speculative instruction execution

Abstract

When a processor executes a memory operation instruction by means of data dependence speculative execution, a speculative execution result history table which stores history information concerning success/failure results of the speculative execution of memory operation instructions of the past is referred to and thereby whether the speculative execution will succeed or fail is predicted. In the prediction, the target address of the memory operation instruction is converted by a hash function circuit into an entry number of the speculative execution result history table (allowing the existence of aliases), and an entry of the table designated by the entry number is referred to. If the prediction is “success”, the memory operation instruction is executed in out-of-order execution speculatively (with regard to data dependence relationship between the instructions). If the prediction is “failure”, the speculative execution is canceled and the memory operation instruction is executed later in the program order non-speculatively. Whether the speculative execution of the memory operation instructions has succeeded or failed is judged by detecting the data dependence relationship between the memory operation instructions, and the speculative execution result history table is updated taking the judgment into account.

Claims

1. A processor having a function for executing memory operation instructions in out-of-order execution by means of speculative execution with regard to dependence relationships between the memory operation instructions, comprising:

address conversion means for converting a target address of a memory operation instruction into a corresponding entry number allowing the existence of aliases;

speculative execution result history storage means for storing history information concerning success/failure results of speculative execution of memory operation instructions of the past, with regard to each of a plurality of entry numbers;

speculative execution success/failure prediction means for predicting whether speculative execution of a particular memory operation instruction that is going to be carried out will succeed or fail by referring to an entry of the speculative execution result history storage means corresponding to an entry number that is obtained by the address conversion means for a target address of the particular memory operation instruction;

instruction execution means for executing the memory operation instructions;

speculation control means for letting the instruction execution means execute the particular memory operation instruction in out-of-order execution by means of speculative execution if the prediction by the speculative execution success/failure prediction means is success while letting the instruction execution means execute the particular memory operation instruction in in-order execution by means of non-speculative execution if the prediction by the speculative execution success/failure prediction means is failure;

speculative execution success/failure judgment means for judging whether speculative execution of the memory operation instructions has succeeded or failed by detecting the dependence relationships between the memory operation instructions; and

speculative execution result history update means for updating the history information stored in the speculative execution result history storage means taking the judgment by the speculative execution success/failure judgment means into account.

2. A processor as claimed in claim 1, wherein:

the speculative execution success/failure judgment means judges the success/failure of speculative execution when a store instruction is executed, by detecting a presence/absence of a true dependence relationship of the store instruction on load instructions that are posterior to the store instruction in program order and that have been executed by means of speculative execution, and

the speculative execution result history update means increases an index concerning success probability of speculative execution as history information stored in an entry corresponding to a target address of the store instruction if the speculative execution success/failure judgment means judged that speculative execution has succeeded, while the speculative execution result history update means decreases the index as the history information if the speculative execution success/failure judgment means judged that speculative execution has failed.

3. A processor as claimed in claim 2, wherein the speculative execution success/failure judgment means detects the presence/absence of the true dependence relationship of the store instruction on the load instructions by comparing the target address of the store instruction with target addresses of the load instructions that have been stored in address buffers.

4. A processor as claimed in claim 1, wherein the address conversion means converts the target address into the entry number by extracting predetermined bits from the target address.

5. A processor as claimed in claim 1, wherein the address conversion means converts the target address into the entry number by applying logical operations to predetermined bits of the target address.

6. A processor as claimed in claim 5, wherein the address conversion means converts the target address into the entry number by applying XOR operations to predetermined bits of the target address.

7. A multiprocessor system including two or more processors for executing parallel processing in units of threads, comprising:

thread assignment means for assigning the threads to the processors so that the threads will be executed by the processors in parallel;

address conversion means for converting a target address of a memory operation instruction included in the threads into a corresponding entry number allowing the existence of aliases;

speculative execution result history storage means for storing history information concerning success/failure results of speculative execution of memory operation instructions of the past, with regard to each of a plurality of entry numbers;

speculative execution success/failure prediction means for predicting whether speculative execution of a particular memory operation instruction that is going to be carried out by a processor will succeed or fail by referring to an entry of the speculative execution result history storage means corresponding to an entry number that is obtained by the address conversion means for a target address of the particular memory operation instruction;

speculation control means for letting the processor execute the particular memory operation instruction in out-of-order execution by means of speculative execution if the prediction by the speculative execution success/failure prediction means is success while letting the processor execute the particular memory operation instruction in in-order execution by means of non-speculative execution if the prediction by the speculative execution success/failure prediction means is failure;

speculative execution success/failure judgment means for judging whether speculative execution of memory operation instructions has succeeded or failed by detecting dependence relationships between the memory operation instructions; and

speculative execution result history update means for updating the history information stored in the speculative execution result history storage means taking the judgment by the speculative execution success/failure judgment means into account.

8. A multiprocessor system as claimed in claim 7, wherein:

each of the processors includes a speculative execution success/failure judgment means and a speculative execution success/failure judgment means of the processor judges the success/failure of speculative execution of load instructions that have been carried out by the processor when a store instruction is executed by another processor that is executing a thread that is prior in program order to a thread executed by the processor, by detecting a presence/absence of a true dependence relationship of the store instruction on the load instructions, and

the speculative execution result history update means increases an index concerning success probability of speculative execution as history information stored in an entry corresponding to a target address of the store instruction if the speculative execution success/failure judgment means of the processor judge that speculative execution has succeeded, while the speculative execution result history update means decreases the index as the history information if the speculative execution success/failure judgment means of the processor judged that speculative execution has failed.

9. A multiprocessor system as claimed in claim 8, wherein the speculative execution success/failure judgment means of each processor detects the presence/absence of the true dependence relationship of the store instruction on the load instructions by comparing the target address of the store instruction with target addresses of the load instructions that have been stored in address buffers of the processor.

10. A multiprocessor system as claimed in claim 7, wherein the address conversion means converts the target address into the entry number by extracting predetermined bits from the target address.

11. A multiprocessor system as claimed in claim 7, wherein the address conversion means converts the target address into the entry number by applying logical operations to predetermined bits of the target address.

12. A multiprocessor system as claimed in claim 11, wherein the address conversion means converts the target address into the entry number by applying XOR operations to predetermined bits of the target address.

13. A data dependence speculative execution method for executing memory operation instructions in out-of-order execution by means of speculative execution with regard to dependence relationships between the memory operation instructions, comprising the steps of:

an address conversion step for converting a target address of a memory operation instruction into a corresponding entry number allowing the existence of aliases;

a speculative execution result history storage step for storing history information concerning success/failure results of speculative execution of memory operation instructions of the past in history storage means, with regard to each of a plurality of entry numbers;

a speculative execution success/failure prediction step for predicting whether speculative execution of a particular memory operation instruction that is going to be carried out will succeed or fail by referring to an entry of the history storage means corresponding to an entry number that is obtained by the address conversion step for a target address of the particular memory operation instruction;

a speculative execution step for executing the particular memory operation instruction in out-of-order execution by means of speculative execution if the prediction by the speculative execution success/failure prediction step is success;

a non-speculative execution step for executing the particular memory operation instruction in in-order execution by means of non-speculative execution if the prediction by the speculative execution success/failure prediction step is failure;

a speculative execution success/failure judgment step for judging whether speculative execution of the memory operation instructions has succeeded or failed by detecting the dependence relationships between the memory operation instructions; and

a speculative execution result history update step for updating the history information stored in the history storage means taking the judgment by the speculative execution success/failure judgment step into account.

14. A data dependence speculative execution method as claimed in claim 13, wherein:

in the speculative execution success/failure judgment step, the success/failure of speculative execution is judged when a store instruction is executed, by detecting a presence/absence of a true dependence relationship of the store instruction on load instructions that are posterior to the store instruction in program order and that have been executed by means of speculative execution, and

in the speculative execution result history update step, an index concerning success probability of speculative execution as history information stored in an entry corresponding to a target address of the store instruction is increased if speculative execution is judged to have succeeded in the speculative execution success/failure judgment step, while the index as the history information is decreased if the speculative execution is judged to have failed in the speculative execution success/failure judgment step.

15. A data dependence speculative execution method as claimed in claim 14, wherein in the speculative execution success/failure judgment step, the presence/absence of the true dependence relationship of the store instruction on the load instructions is detected by comparing the target address of the store instruction with target addresses of the load instructions that have been stored in address buffers.

16. A data dependence speculative execution method as claimed in claim 13, wherein in the address conversion step, the target address is converted into the entry number by extracting predetermined bits from the target address.

17. A data dependence speculative execution method as claimed in claim 13, wherein in the address conversion step, the target address is converted into the entry number by applying logical operations to predetermined bits of the target address.

18. A data dependence speculative execution method as claimed in claim 17, wherein in the address conversion step, the target address is converted into the entry number by applying XOR operations to predetermined bits of the target address.

19. A data dependence speculative execution method for executing parallel processing in units of threads by executing memory operation instructions in out-of-order execution by means of speculative execution with regard to dependence relationships between the memory operation instructions, comprising the steps of:

a thread assignment step for assigning the threads to two or more processors so that the threads will be executed by the processors in parallel;

an address conversion step for converting a target address of a memory operation instruction included in the threads into a corresponding entry number allowing the existence of aliases;

a speculative execution result history storage step for storing history information concerning success/failure results of speculative execution of memory operation instructions of the past in history storage means, with regard to each of a plurality of entry numbers;

a speculative execution success/failure prediction step for predicting whether speculative execution of particular memory operation instruction that is going to be carried out by a processor will succeed or fail by referring to an entry of the history storage means corresponding to an entry number that is obtained by the address conversion step for a target address of the particular memory operation instruction;

a speculative execution step for letting the processor execute the particular memory operation instruction in out-of-order execution by means of speculative execution if the prediction by the speculative execution success/failure prediction step is success;

a non-speculative execution step for letting the processor execute the particular memory operation instruction in in-order execution by means of non-speculative execution if the prediction by the speculative execution success/failure prediction step is failure;

a speculative execution success/failure judgment step for judging whether speculative execution of the memory operation instructions has succeeded or failed by detecting the dependence relationships between the memory operation instructions; and

a speculative execution result history update step for updating the history information stored in the history storage means taking the judgment by the speculative execution success/failure judgment step into account.

20. A data dependence speculative execution method as claimed in claim 19, wherein:

the speculative execution success/failure judgment step is executed for each processor, in which the success/failure of speculative execution of load instructions that have been carried out by the processor is judged when a store instruction is executed by another processor that is executing a thread that is prior in program order to a thread executed by the processor, by detecting a presence/absence of a true dependence relationship of the store instruction on the load instructions, and

in the speculative execution result history update step, an index concerning success probability of speculative execution as history information stored in an entry corresponding to a target address of the store instruction is increased if speculative execution is judged to have succeeded in the speculative execution success/failure judgment step, while the index as the history information is decreased if the speculative execution is judged to have failed in the speculative execution success/failure judgment step.

21. A data dependence speculative execution method as claimed in claim 20, wherein in the speculative execution success/failure judgment step for each processor, the presence/absence of the true dependence relationship of the store instruction on the load instructions is detected by comparing the target address of the store instruction with target addresses of the load instructions that have been stored in address buffers of the processor.

22. A data dependence speculative execution method as claimed in claim 19, wherein in the address conversion step, the target address is converted into the entry number by extracting predetermined bits from the target address.

23. A data dependence speculative execution method as claimed in claim 19, wherein in the address conversion step, the target address is converted into the entry number by applying logical operations to predetermined bits of the target address.

24. A data dependence speculative execution method as claimed in claim 23, wherein in the address conversion step, the target address is converted into the entry number by applying XOR operations to predetermined bits of the target address.