US 6,970,997 B2 · 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

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.

Claims24

Dependent claims

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.

5 more elements

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.

5 more elements

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.

5 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims24