Method and apparatus for store dependence prediction

Patent metadata

Field	Value
Publication number	US-9619750-B2
Application number	US-201313931872-A
Country	US
Kind code	B2
Filing date	Jun 29, 2013
Priority date	Jun 29, 2013
Publication date	Apr 11, 2017
Grant date	Apr 11, 2017

Abstract

An apparatus and method for store dependence prediction is described. For example, one embodiment of the invention includes a processor comprising a store buffer for buffering store operations prior to completion, the store operations to store data to a memory hierarchy; and a store dependence predictor to predict whether load operations should be permitted to speculatively skip over each store operation and responsively setting an indication within an entry associated with each store operation in the store buffer; wherein a load operation checks the indication in the store buffer to determine whether to speculatively execute ahead of each store operation.

First claim

What is claimed is:

1. A processor comprising:
a store buffer for buffering store operations prior to completion, the store operations to store data to a memory hierarchy; and
a store dependence predictor to predict whether load operations should be permitted to speculatively skip over each store operation based on a lookup of an array and responsively setting an indication within an entry associated with each store operation in the store buffer, the entry including bits of an instruction address of the store operation, wherein the store dependence predictor comprises the array containing a counter value associated with each store operation, wherein the store dependence predictor decrements a counter for a store operation each time a load operation hits an address of the store operation and increments the counter each time a load operation does not hit the address of the store operation;
wherein a load operation checks the indication in the store buffer to determine whether to speculatively execute ahead of each store operation.

2. The processor as in claim 1 wherein the indication comprises a bit for each entry which the store dependence predictor sets for store operations which may be skipped by load operations.

3. The processor as in claim 1 wherein the array comprises an array indexed by a current instruction address or a portion of the current instruction address of each of the store operations.

4. The processor as in claim 1 further comprising threshold comparison logic to determine whether a counter threshold has been reached for a new store operation, the threshold comparison logic responsively setting the indication within the entry associated with the store operation in the store buffer.

5. The processor as in claim 1 further comprising:
a load-based dependence predictor to predict whether specified load operations may skip over store operations using one or more load-based dependence prediction techniques.

6. A method comprising:
buffering store operations prior to completion, the store operations to store data to a memory hierarchy;
performing a lookup in an array containing a counter value associated with each store operation, wherein the counter is decremented for a store operation each time a load operation hits an address of the store operation and incremented each time a load operation does not hit the address of the store operation; and
predicting whether load operations should be permitted to speculatively skip over each store operation based on the lookup and responsively setting an indication within an entry associated with each store operation in the store buffer, the entry including bits of an instruction address of the store operation;
wherein a load operation checks the indication in the store buffer to determine whether to speculatively execute ahead of each store operation.

7. The method as in claim 6 wherein the indication comprises a bit for each entry which the store dependence predictor sets for store operations which may be skipped by load operations.

8. The method as in claim 6 wherein the array comprises an array indexed by a current instruction address or a portion of a current instruction address of each of the store operations.

9. The method as in claim 6 further comprising determining whether a counter threshold has been reached for a new store operation and responsively setting the indication within the entry associated with the store operation in the store buffer.

10. The method as in claim 6 further comprising:
predicting whether specified load operations may skip over store operations using one or more load-based dependence prediction techniques.

Assignees

• Intel Corp

Inventors

• Kim Ho-Seop
• Chappell Robert S
• Soo Choon Yip

Classifications

• G06F9/3842

  Speculative instruction execution · CPC title

• G06F9/3834 Primary

  Maintaining memory consistency · CPC title

• G06N5/04 Primary

  Inference or reasoning models · CPC title

• G06F9/3855

  Physics · mapped topic

• G06F9/3856

  Reordering of instructions, e.g. using queues or age tags · CPC title