Load-store dependency predictor PC hashing

Patent metadata

Field	Value
Publication number	US-9600289-B2
Application number	US-201213483268-A
Country	US
Kind code	B2
Filing date	May 30, 2012
Priority date	May 30, 2012
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

Methods and processors for managing load-store dependencies in an out-of-order instruction pipeline. A load store dependency predictor includes a table for storing entries for load-store pairs that have been found to be dependent and execute out of order. Each entry in the table includes hashed values to identify load and store operations. When a load or store operation is detected, the PC and an architectural register number are used to create a hashed value that can be used to uniquely identify the operation. Then, the load store dependency predictor table is searched for any matching entries with the same hashed value.

First claim

What is claimed is:

1. An apparatus comprising:
a plurality of entries, each of said entries being configured to store an identifier; and
circuitry comprising a first hashing stage and a second hashing stage, wherein the circuitry is configured to:
hash in the first hashing stage a portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the circuitry is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result; and
hash in the second hashing stage at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce a first identifier;
store the first identifier in an entry of the plurality of entries; and
predict a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

2. The load-store dependency predictor as recited in claim 1 , wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

3. The load-store dependency predictor as recited in claim 1 , wherein the first operation is a load operation and the second operation is a store operation.

4. The load-store dependency predictor as recited in claim 1 , wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

5. The load-store dependency predictor as recited in claim 1 , wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.

6. A processor comprising:
circuitry comprising a first hashing stage and a second hashing stage, wherein the circuitry is configured to:
hash in the first hashing stage a portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the circuitry is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result; and
hash in the second hashing stage at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce a first identifier; and
store the first identifier in an entry of a plurality of entries;

a load-store dependency predictor comprising said plurality of entries, each of said entries being configured to store an identifier generated by the circuitry; and
circuitry configured to:
predict a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

7. The processor as recited in claim 6 , wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

8. The processor as recited in claim 6 , wherein the first operation is a load operation and the second operation is a store operation.

9. The processor as recited in claim 6 , wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

10. The processor as recited in claim 6 , wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.

11. A method comprising:
generating a first identifier, wherein the first identifier is generated by circuitry comprising a plurality of hashing stages, wherein
a first hashing stage of the plurality of hashing stages is configured to hash a first portion of a program counter (PC) value of a given operation with at least a portion of a corresponding architectural register number or a micro-op number to produce an intermediate result, wherein the first hashing stage is configurable to switch between using the corresponding architectural register number or the micro-op number to produce the intermediate result, and wherein
a second hashing stage of the plurality of hashing stages is configured to hash at least a portion of the intermediate result with a portion of the PC value of the given operation, the corresponding architectural register number, and the micro-op number to produce the first identifier;

storing the first identifier by the circuitry in an entry of a plurality of entries of a load-store dependency predictor; and
predicting by circuitry a first operation is dependent on a second operation based at least in part on the first operation having a second identifier that matches the first identifier stored in said entry of the plurality of entries.

12. The method as recited in claim 11 , wherein the given operation is a load operation and the architectural register number is a destination architectural register number of the load operation.

13. The method as recited in claim 11 , wherein the first operation is a load operation and the second operation is a store operation.

14. The method as recited in claim 11 , wherein each of said entries is configured to store both a load identifier and a store identifier, wherein the first identifier in said entry is a load identifier and an identifier of the second operation is stored in said entry as a store identifier.

15. The method as recited in claim 11 , wherein each of said entries is configured to store a valid indicator that indicates whether a corresponding entry is valid.

Assignees

• Meier Stephan G
• Mylius John H
• Williams Iii Gerard R
• Vats Suparn
• Apple Inc

Inventors

• Meier Stephan G
• Mylius John H
• Williams Iii Gerard R
• Vats Suparn

Classifications

• G06F12/0864

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/1018

  involving hashing techniques, e.g. inverted page tables · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F9/3834 Primary

  Maintaining memory consistency · CPC title

• G06F9/3838

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