Predicting and avoiding operand-store-compare hazards in out-of-order microprocessors

Patent metadata

Field	Value
Publication number	US-9430235-B2
Application number	US-201313953303-A
Country	US
Kind code	B2
Filing date	Jul 29, 2013
Priority date	Dec 22, 2009
Publication date	Aug 30, 2016
Grant date	Aug 30, 2016

Abstract

A method and information processing system manage load and store operations that can be executed out-of-order. At least one of a load instruction and a store instruction is executed. A determination is made that an operand store compare hazard has been encountered. An entry within an operand store compare hazard prediction table is created based on the determination. The entry includes at least an instruction address of the instruction that has been executed and a hazard indicating flag associated with the instruction. The hazard indicating flag indicates that the instruction has encountered the operand store compare hazard. When a load instruction is associated with the hazard indicating flag, the load instruction becomes dependent upon all store instructions associated with a substantially similar hazard indicating flag.

First claim

What is claimed is:

1. An information processing system capable of managing execution order of computer instructions in program order execution or in out-of-order execution in a computer system, a first instruction comprising a store instruction and a second instruction comprising a load instruction, the information processing system comprising:
a memory; and
a processor communicatively coupled to the memory, wherein the processor is configured to perform a method comprising:
storing an instruction address of the first instruction in a first entry in a prediction table, each entry of the prediction table comprising no more than one instruction address;
storing an instruction address of the second instruction in a second entry, different from the first entry, in the prediction table;
storing a first flag in the first entry, associated with the first instruction, indicating a type of data dependency relationship between the first instruction and the second instruction with the first instruction in a sequence of instructions being in program order prior to the second instruction, and wherein the first flag stored in the first entry does not reference any other entry in the prediction table;
storing a second flag in the second entry, associated with the second instruction, indicating the type of data dependency relationship between the first instruction and the second instruction, and wherein the second flag stored in the second entry does not reference any other entry in the prediction table; and
predicting the execution order of the second instruction relative to the first instruction based at least on the type of data dependency relationship indicated by the first flag and second flag that are stored in the first entry and the second entry, respectively, in the prediction table.

2. The system of claim 1 , wherein responsive to predicting that the first instruction and second instruction are to be executed in program order, causing the second instruction to be executed after execution of the first instruction.

3. The system of claim 1 , wherein responsive to predicting that the first instruction and second instruction are not required to be executed in program order, permitting out-of-order execution of the second instruction relative to the execution of the first instruction.

4. The system of claim 1 , wherein the first instruction and the second instruction are included in one complex instruction.

5. The system of claim 1 , wherein the method further comprising:
determining that the execution of the load instruction of the second instruction is data dependent on the execution of the store instruction of the first instruction in a sequence of instructions for execution by the computer system, with the store instruction in the sequence of instructions being in program order prior to the load instruction;
determining a type of data dependency relationship between the store instruction and the load instruction;
storing an instruction address of the store instruction of the first instruction in a first entry in the prediction table, each entry of the prediction table comprising no more than one instruction address;
storing an instruction address of the load instruction of the second instruction in a second entry in the prediction table;
storing in the prediction table a first flag in the first entry, associated with the instruction address of the store instruction of the first instruction, indicating the type of data dependency relationship between the store instruction and the load instruction, and wherein the first flag stored in the first entry for the store instruction of the first instruction does not reference any other entry in the prediction table;
storing in the prediction table a second flag in the second entry, associated with the instruction address of the load instruction of the second instruction, indicating the type of data dependency relationship between the store instruction and the load instruction, and wherein the second flag stored in the second entry for the load instruction of the second instruction does not reference any other entry in the prediction table;
predicting the execution order of the load instruction relative to the store instruction based at least on the type of data dependency relationship indicated by the first flag and second flag that are stored in the first entry and the second entry, respectively, in the prediction table; and
responsive to predicting that the store instruction and load instruction are to be executed in program order, causing the load instruction to be executed after execution of the store instruction.

6. The system of claim 1 , wherein the method further comprising:
determining that the execution of the load instruction of the second instruction is data dependent on the execution of the store instruction of the first instruction in a sequence of instructions for execution by the computer system, with the store instruction in the sequence of instructions being in program order prior to the load instruction;
determining a type of data dependency relationship between the store instruction and the load instruction;
storing an instruction address of the store instruction of the first instruction in a first entry in the prediction table, each entry of the prediction table comprising no more than one instruction address;
storing an instruction address of the load instruction of the second instruction in a second entry in the prediction table;
storing in the prediction table a first flag in the first entry, associated with the instruction address of the store instruction of the first instruction, indicating the type of data dependency relationship between the store instruction and the load instruction, and wherein the first flag stored in the first entry for the store instruction of the first instruction does not reference any other entry in the prediction table;
storing in the prediction table a second flag in the second entry, associated with the instruction address of the load instruction of the second instruction, indicating the type of data dependency relationship between the store instruction and the load instruction, and wherein the second flag stored in the second entry for the load instruction of the second instruction does not reference any other entry in the prediction table;
predicting the execution order of the load instruction relative to the store instruction based at least on the type of data dependency relationship indicated by the first flag and second flag that are stored in the first entry and the second entry, respectively, in the prediction table; and
responsive to predicting that the store instruction and load instruction are not required to be executed in program order, permitting out-of-order execution of the load instruction relative to the execution of the store instruction.

7. The system of claim 1 , wherein the method further comprising:
determining that the execution of the load instruction is data dependent on the execution of each of a plurality of instances of the store instruction in the sequence of instructions for execution by the computer system, with the plurality of instances of the store instruction in the sequence of instructions being in program order prior to the load instruction;
determining a type of data dependency relationship between each of the plurality of instances of the store instruction and the load instruction;
storing in a plurality of entries of the prediction table a respective plurality of instruction addresses of the plurality of instances of the store instruction in the sequence of instructions for execution by the computer system, each entry of the prediction table comprising no more than one instruction address;
storing in the prediction table a plu

Assignees

• IBM

Inventors

• Alexander Gregory W
• Alexander Khary J
• Curran Brian
• Hsieh Jonathan T
• Jacobi Christian
• Mitchell James R
• Prasky Brian R
• Thompto Brian W

Classifications

• G06F9/3826

  Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage · CPC title

• G06F9/3838

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F9/3834

  Maintaining memory consistency · CPC title

• G06F9/383 Primary

  Operand prefetching (cache prefetching G06F12/0862) · CPC title

• G06F9/3836 Primary

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title