PREDICTING CACHE MISSES USING DATA ACCESS BEHAVIOR AND INSTRUCTION ADDRESS

• US 20120284463A1
• Filed: 05/02/2011
• Published: 11/08/2012
• Est. Priority Date: 05/02/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Srinivasan, Vijayalakshmi, Prasky, Brian R.
• Granted Patent: US 10,007,523 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

In a decode stage of hardware processor pipeline, one particular instruction of a plurality of instructions is decoded. It is determined that the particular instruction requires a memory access. Responsive to such determination, it is predicted whether the memory access will result in a cache miss. The predicting in turn includes accessing one of a plurality of entries in a pattern history table stored as a hardware table in the decode stage. The accessing is based, at least in part, upon at least a most recent entry in a global history buffer. The pattern history table stores a plurality of predictions. The global history buffer stores actual results of previous memory accesses as one of cache hits and cache misses. Additional steps include scheduling at least one additional one of the plurality of instructions in accordance with the predicting; and updating the pattern history table and the global history buffer subsequent to actual execution of the particular instruction in an execution stage of the hardware processor pipeline, to reflect whether the predicting was accurate.

Claims

1. A method comprising:

decoding, in a decode stage of hardware processor pipeline, one particular instruction of a plurality of instructions;

determining that said particular instruction requires a memory access;

responsive to determining that said particular instruction requires a memory access, predicting whether said memory access will result in a cache miss, said predicting in turn comprising accessing one of a plurality of entries in a pattern history table stored as a hardware table in said decode stage, said accessing being based, at least in part, upon at least a most recent entry in a global history buffer, said pattern history table storing a plurality of predictions, said global history buffer storing actual results of previous memory accesses as one of cache hits and cache misses;

scheduling at least one additional one of said plurality of instructions in accordance with said predicting; and

updating said pattern history table and said global history buffer subsequent to actual execution of said particular instruction in an execution stage of said hardware processor pipeline, to reflect whether said predicting was accurate.

2. The method of claim 1, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table comprises a miss pattern history table and a hit pattern history table; and

said predicting comprises;

accessing said most recent entry in said global history buffer to determine whether said most recent entry in said global history buffer comprises a hit or a miss;

accessing said miss pattern history table if said most recent entry in said global history buffer comprises said miss, said accessing of said miss pattern history table comprising accessing an entry therein corresponding to a number of contiguous misses in said global history buffer, including said most recent entry in said global history buffer; and

accessing said hit pattern history table if said most recent entry in said global history buffer comprises said hit, said accessing of said hit pattern history table comprising accessing an entry therein corresponding to a number of contiguous hits in said global history buffer. including said most recent entry in said global history buffer.

3. The method of claim 1, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table has M entries arranged in rows and N columns. and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said predicting comprises;

hashing said program counter to obtain a hash having log M bits;

extracting a tag from said program counter;

accessing said one of said plurality of entries in said pattern history table based on said hash;

determining whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history table resides matches said extracted tag;

if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does not match said extracted tag, making a default prediction; and

if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does indeed match said extracted tag, accessing an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer. until a first bit that is different from said most significant bit, said global history buffer being an N-bit global history buffer.

4. The method of claim 1, wherein:

said pattern history table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said predicting comprises;

hashing said program counter to obtain a hash having log M bits;

extracting a tag from said program counter;

accessing said one of said plurality of entries in said pattern history table based on said hash;

determining whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history table resides matches said extracted tag;

if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does not match said extracted tag, making a default prediction; and

if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does indeed match said extracted tag, accessing an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first hit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.

5. The method of claim 1, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table has M entries arranged in rows and N columns, and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said predicting comprises;

extracting a tag from said program counter;

accessing a corresponding one of said rows for said one of said plurality of entries in said pattern history table based on said extracted tag; and

accessing an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer, until a first bit that is different from said most significant bit.

6. The method of claim 1, wherein:

said pattern history table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said predicting comprises;

extracting a tag from said program counter;

accessing a corresponding one of said rows for said one of said plurality of entries in said pattern history table based on said extracted tag; and

accessing an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first bit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.

7. A hardware processor comprising:

a decode pipeline stage which decodes one particular instruction of a plurality of instructions;

hard-wired logic circuitry which determines that said particular instruction requires a memory access;

a pattern history hardware table within said decode pipeline stage;

a global history buffer within said decode pipeline stage;

hard-wired logic circuitry which, responsive to determining that said particular instruction requires a memory access, predicts whether said memory access will result in a cache miss, said predicting in turn comprising accessing one of a plurality of entries in said pattern history hardware table, said accessing being based, at least in part, upon at least a most recent entry in said global history buffer, said pattern history hardware table storing a plurality of predictions, said global history buffer storing actual results of previous memory accesses as one of cache hits and cache misses;

an issue pipeline stage which schedules at least one additional one of said plurality of instructions in accordance with said predicting;

an execution pipeline stage which actually executes said particular instruction; and

hard-wired logic circuitry which updates said pattern history hardware table and said global history buffer subsequent to said actual execution of said particular instruction, to reflect whether said predicting was accurate.

8. The hardware processor of claim 7, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history hardware table comprises a miss pattern history hardware table and a hit pattern history hardware table; and

said hard-wired logic circuitry which predicts comprises;

hard-wired logic circuitry which accesses said most recent entry in said global history buffer to determine whether said most recent entry in said global history buffer comprises a hit or a miss;

hard-wired logic circuitry which accesses said miss pattern history hardware table if said most recent entry in said global history buffer comprises said miss, said accessing of said miss pattern history hardware table comprising accessing an entry therein corresponding to a number of contiguous misses in said global history buffer. including said most recent entry in said global history buffer; and

hard-wired logic circuitry which accesses said hit pattern history hardware table if said most recent entry in said global history buffer comprises said hit, said accessing of said hit pattern history hardware table comprising accessing an entry therein corresponding to a number of contiguous hits in said global history buffer, including said most recent entry in said global history buffer.

9. The hardware processor of claim 7, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history hardware table has M entries arranged in rows and N columns. and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said hard-wired logic circuitry which predicts comprises;

hard-wired logic circuitry which hashes said program counter to obtain a hash having log M bits;

hard-wired logic circuitry which extracts a tag from said program counter;

hard-wired logic circuitry which accesses said one of said plurality of entries in said pattern history hardware table based on said hash;

hard-wired logic circuitry which determines whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides matches said extracted tag;

hard-wired logic circuitry which, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides does not match said extracted tag, makes a default prediction; and

hard-wired logic circuitry which, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides does indeed match said extracted tag, accesses an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer, until a first bit that is different from said most significant bit, said global history buffer being an N-bit global history buffer.

10. The hardware processor of claim 7, wherein:

said pattern history hardware table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said hard-wired logic circuitry which predicts comprises;

hard-wired logic circuitry which hashes said program counter to obtain a hash having log M bits;

hard-wired logic circuitry which extracts a tag from said program counter;

hard-wired logic circuitry which accesses said one of said plurality of entries in said pattern history hardware table based on said hash;

hard-wired logic circuitry which determines whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides matches said extracted tag;

hard-wired logic circuitry which, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides does not match said extracted tag, makes a default prediction; and

hard-wired logic circuitry which, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history hardware table resides does indeed match said extracted tag, accessing an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first bit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.

11. The hardware processor of claim 7, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history hardware table has M entries arranged in rows and N columns, and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said hard-wired logic circuitry which predicts comprises;

hard-wired logic circuitry which extracts a tag from said program counter;

hard-wired logic circuitry which accesses a corresponding one of said rows for said one of said plurality of entries in said pattern history hardware table based on said extracted tag; and

hard-wired logic circuitry which accesses an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer, until a first bit that is different from said most significant bit, said global history buffer being an N-bit global history buffer.

12. The hardware processor of claim 7, wherein:

said pattern history hardware table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said hard-wired logic circuitry which predicts comprises;

hard-wired logic circuitry which extracts a tag from said program counter;

hard-wired logic circuitry which accesses a corresponding one of said rows for said one of said plurality of entries in said pattern history hardware table based on said extracted tag; and

hard-wired logic circuitry which accesses an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first bit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.

13. A hardware processor comprising:

means for decoding, in a decode stage of a hardware processor pipeline of said hardware processor, one particular instruction of a plurality of instructions;

means for determining that said particular instruction requires a memory access;

means for, responsive to determining that said particular instruction requires a memory access, predicting whether said memory access will result in a cache miss, said predicting in turn comprising accessing one of a plurality of entries in a pattern history table stored as a hardware table in said decode stage, said accessing being based, at least in part, upon at least a most recent entry in a global history buffer, said pattern history table storing a plurality of predictions, said global history buffer storing actual results of previous memory accesses as one of cache hits and cache misses;

means for scheduling at least one additional one of said plurality of instructions in accordance with said predicting; and

means for updating said pattern history table and said global history buffer subsequent to actual execution of said particular instruction in an execution stage of said hardware processor pipeline, to reflect whether said predicting was accurate.

14. The hardware processor of claim 13, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table comprises a miss pattern history table and a hit pattern history table; and

said means for predicting comprise;

means for accessing said most recent entry in said global history buffer to determine whether said most recent entry in said global history buffer comprises a hit or a miss;

means for accessing said miss pattern history table if said most recent entry in said global history buffer comprises said miss, said accessing of said miss pattern history table comprising accessing an entry therein corresponding to a number of contiguous misses in said global history buffer, including said most recent entry in said global history buffer; and

means for accessing said hit pattern history table if said most recent entry in said global history buffer comprises said hit, said accessing of said hit pattern history table comprising accessing an entry therein corresponding to a number of contiguous hits in said global history buffer, including said most recent entry in said global history buffer.

15. The hardware processor of claim 13, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table has M entries arranged in rows and N columns, and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said means for predicting comprise;

means for hashing said program counter to obtain a hash having log M bits;

means for extracting a tag from said program counter;

means for accessing said one of said plurality of entries in said pattern history table based on said hash;

means for determining whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history table resides matches said extracted tag;

means for, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does not match said extracted tag, making a default prediction; and

means for, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does indeed match said extracted tag, accessing an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer, until a first bit that is different from said most significant bit, said global history buffer being an N-bit global history buffer.

16. The hardware processor of claim 13, wherein:

said pattern history table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said means for predicting comprise;

means for hashing said program counter to obtain a hash having log M bits;

means for extracting a tag from said program counter;

means for accessing said one of said plurality of entries in said pattern history table based on said hash;

means for determining whether that one of said stored tag values corresponding to a given one of said rows in which said one of said plurality of entries in said pattern history table resides matches said extracted tag;

means for, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does not match said extracted tag, making a default prediction; and

means for, if said one of said stored tag values corresponding to said given one of said rows in which said one of said plurality of entries in said pattern history table resides does indeed match said extracted tag, accessing an entry in said given one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first bit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.

17. The hardware processor of claim 13, wherein:

said global history buffer stores combined results for all given ones of said plurality of instructions requiring said memory access;

said pattern history table has M entries arranged in rows and N columns, and each of said rows has a stored tag value associated therewith;

said particular instruction has a program counter associated therewith; and

said means for predicting comprise;

means for extracting a tag from said program counter;

means for accessing a corresponding one of said rows for said one of said plurality of entries in said pattern history table based on said extracted tag; and

means for accessing an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of said global history buffer, until a first bit that is different from said most significant bit, said global history buffer being an N-bit global history buffer.

18. The hardware processor of claim 13. wherein:

said pattern history table has M entries arranged in rows and N columns, each of said rows has a stored tag value associated therewith, and each of said rows has an instruction-specific portion of said global history buffer associated therewith;

said particular instruction has a program counter associated therewith; and

said means for predicting comprise;

means for extracting a tag from said program counter;

means for accessing a corresponding one of said rows for said one of said plurality of entries in said pattern history table based on said extracted tag; and

means for accessing an entry in said corresponding one of said rows based on traversing a number of contiguous bits starting with a most significant bit of a corresponding one of said instruction-specific portions of said global history buffer, until a first bit that is different from said most significant bit, said instruction-specific portions of said global history buffer having N-bits.