Making precise operand-store-compare predictions to avoid false dependencies

Patent metadata

Field	Value
Publication number	US-10929142-B2
Application number	US-201916358791-A
Country	US
Kind code	B2
Filing date	Mar 20, 2019
Priority date	Mar 20, 2019
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

Abstract

Provided are embodiments including a computer-implemented method, system and computer program product for determining precise operand-store-compare (OSC) predictions to avoid false dependencies. Some embodiments include detecting an instruction causing an OSC event, wherein the OSC event is at least one of a store-hit-load event or a load-hit-store event, marking an entry in a queue for the instruction based on the detected OSC event, wherein marking the entry comprises setting a bit and saving a tag in the entry in the queue. Some embodiments also include installing an address for the instruction and the tag in the history table responsive to completing the instruction.

First claim

What is claimed is:

1. A computer-implemented method for determining precise operand-store-compare (OSC) predictions to avoid false dependencies, the computer-implemented method comprising:
detecting an instruction causing an OSC event, wherein the OSC event is at least one of a store-hit-load event or a load-hit-store event;
marking an entry in a queue for the instruction based on the detected OSC event, wherein marking the entry comprises setting a bit and saving a tag in the entry in the queue;
installing an address for the instruction and the tag in a history table responsive to completing the instruction; and
responsive to dispatching a potential OSC-victim load instruction, performing a lookup in a marked store table (MST), wherein the potential OSC-victim load instruction is a load instruction that was previously predicted as an OSC-victim load instruction, wherein performing the MST lookup is based on a load-bit that is set in the history table indicating the subsequent instruction is a victim load instruction of a previous OSC event.

2. The computer-implemented method of claim 1 , further comprising:
performing a prediction for a subsequent instruction;
identifying at least one of a potential OSC-victim load and store-tag or potential OSC-perp store and load-tag based on the subsequent instruction; and
performing a lookup in the history table for the subsequent instruction.

3. The computer-implemented method of claim 1 , further comprising:
responsive to dispatching a potential OSC-perp store instruction, installing the store instruction and load tag into a marked store table (MST), wherein the potential OSC-perp instruction is a store instruction that was previously predicted as an OSC-perp store instruction in the history table.

4. The computer-implemented method of claim 3 , further comprising:
when installing the store instruction and load-tag, determining if an entry is available in the MST; and
overwriting an oldest entry in the MST based on the determination.

5. The computer-implemented method of claim 1 , wherein performing the MST lookup comprises:
comparing the store-tag of the load instruction with store instruction addresses in the MST;
determining a dependency between the load instruction and the store instruction based on the comparison; and
providing the dependency to an instruction queue.

6. The computer-implemented method of claim 5 , further comprising:
based on the comparison, further comparing a load instruction address of the load instruction with load-tags in the MST;
determining the dependency on the load-tag and stores; and
providing the dependency to an instruction queue.

7. A system for determining precise operand-store-compare (OSC) predictions to avoid false dependencies, the system comprising:
a history table (OHT); and
a storage medium, the storage medium being coupled to a processor;
the processor configured to:
detect an instruction causing an OSC event, wherein the OSC event is at least one of a store-hit-load event or a load-hit-store event;
mark an entry in a queue for the instruction based on the detected OSC event, wherein marking the entry comprises setting a bit and saving a tag in the entry in the queue;
install an address for the instruction and the tag in the history table responsive to completing the instruction; and
perform a lookup in a marked store table (MST), responsive to dispatching a potential OSC-victim load instruction, wherein the potential OSC-victim load instruction is a load instruction that was previously predicted as an OSC-victim load instruction, wherein performing the MST lookup is based on a load-bit that is set in the history table indicating the subsequent instruction is a victim load instruction of a previous OSC event.

8. The system of claim 7 , wherein the processor is configured to:
perform a prediction for a subsequent instruction;
identify at least one of a potential OSC-victim load and store-tag or a potential OSC-perp store and load-tag based on the subsequent instruction; and
perform a lookup in the history table for the subsequent instruction.

9. The system of claim 7 , wherein the processor is configured to:
install the store instruction and load tag into a marked store table (MST), responsive to dispatching a potential OSC-perp store instruction, wherein the potential OSC-perp instruction is a store instruction that was previously predicted as an OSC-perp store instruction in the history table.

10. The system of claim 9 , wherein the processor is further configured to:
install the store instruction and load-tag, determining if an entry is available in the MST; and
overwrite an oldest entry in the MST based on the determination.

11. The system of claim 7 , wherein, when performing the MST lookup, the processor is configured to:
compare the store-tag of the load instruction with store instruction addresses in the MST;
determine a dependency between the load instruction and the store instruction based on the comparison; and
provide the dependency to an instruction queue.

12. The system of claim 11 , wherein based on the comparison, the processor is configured to:
compare the load instruction address of the load instruction with load-tags in the MST;
determine the dependency on the load-tag and stores; and
provide the dependency to an instruction queue.

13. A computer program product for determining precise operand-store-compare (OSC) predictions to avoid false dependencies, the computer program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
detect an instruction causing an OSC event, wherein the OSC event is at least one of a store-hit-load event or a load-hit-store event;
mark an entry in a queue for the instruction based on the detected OSC event, wherein marking the entry comprises setting a bit and saving a tag in the entry in the queue;
install an address for the instruction and the tag in a history table responsive to completing the instruction; and
responsive to dispatching a potential OSC-victim load instruction, perform a lookup in a marked store table (MST), wherein the potential OSC-victim load instruction is a load instruction that was previously predicted as an OSC-victim load instruction, wherein performing the MST lookup is based on a load-bit that is set in the history table indicating the subsequent instruction is a victim load instruction of a previous OSC event.

14. The computer program product of claim 13 , wherein the instructions are further executable by the processor to cause the processor to:
perform a prediction for a subsequent instruction;
identify at least one of a potential OSC-victim load and store-tag or a potential OSC-perp store and load-tag based on the subsequent instruction; and
perform a lookup in the history table for the subsequent instruction.

15. The computer program product of claim 13 , wherein the instructions are further executable by the processor to cause the processor to:
install the store instruction and load tag into a marked store table (MST), responsive to dispatching a potential OSC-perp store instruction, wherein the potential OSC-perp instruction is a store instruction that was previously predicted as an OSC-perp store instruction in the history table.

16. The computer program product of claim 15 , wherein the instructions are further executable by the processor to cause the processor to:
install the store instruction and load-tag, determining if an entry is a

Assignees

• IBM

Inventors

• Alexander Gregory William
• Bonanno James
• Collura Adam
• Cuffney James Raymond
• Fried Yair
• Hsieh Jonathan
• Lee Jang-Soo
• Malley Edward
• Saporito Anthony
• Naor Eyal

Classifications

• G06F9/383

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

• G06F9/3836

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

• G06F9/30043

  LOAD or STORE instructions; Clear instruction · CPC title

• G06F9/3834 Primary

  Maintaining memory consistency · CPC title

• G06F9/3838 Primary

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