Deterministic setting of replacement policy in a cache

• US 20040221110A1
• Filed: 06/04/2004
• Published: 11/04/2004
• Est. Priority Date: 08/07/2000
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Rowlands, Joseph B., Dickman, Michael P.
• Granted Patent: US 6,961,824 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning

Abstract

A cache is configured to receive direct access transactions. Each direct access transaction explicitly specifies a way of the cache. The cache may alter the state of its replacement policy in response to a direct access transaction explicitly specifying a particular way of the cache. The state may be altered such that a succeeding cache miss causes an eviction of the particular way. Thus, a direct access transaction may be used to provide a deterministic setting to the replacement policy, providing predictability to the entry selected to store a subsequent cache miss. In one embodiment, the replacement policy may be a pseudo-random replacement policy. In one embodiment, a direct access transaction also explicitly specifies a cache storage entry to be accessed in response to the transaction. The cache may access the cache storage entry (bypassing the normal tag comparisons and hit determination used for memory transactions) and either read the data from the cache storage entry (for read transactions) or write data from the transaction to the cache storage entry (for write transactions). Other embodiments may set the replacement policy based on other types of transactions.

Claims

1. A cache comprising:

an associative memory having a plurality of entries, each of said plurality of entries configured to store a cache line of data, said plurality of entries arranged in a plurality of ways; and

a replacement circuit configured to select an entry of said associative memory for eviction responsive to a cache miss by a memory transaction, and wherein said replacement circuit is configured, responsive to a first transaction specifying an explicit update of said replacement circuit to select a first way of said plurality of ways, to establish a first state corresponding to a selection of said first way.

2. The cache as recited in claim 1 wherein said replacement circuit employs a pseudo-random replacement policy.

3. The cache as recited in claim 2 wherein said replacement circuit comprises:

a control circuit coupled to receive a signal indicative of said first transaction; and

a register coupled to said control circuit and configured to store a state of said replacement circuit;

wherein said control circuit is configured to cause said register to store a predetermined value representing said first state responsive to said signal.

4. The cache as recited in claim 3 wherein said register comprises a linear feedback shift register.

5. The cache as recited in claim 4 wherein said control circuit is coupled to receive a second signal indicative of a memory transaction, and wherein said control circuit is configured to cause said register to shift and establish a new state responsive to said second signal.

6. The cache as recited in claim 3 wherein said control circuit is coupled to receive an indication of said first way, and wherein said control circuit is configured to select said predetermined value from a plurality of predetermined values responsive to said indication.

7. The cache as recited in claim 3 wherein said control circuit is coupled to receive a second signal indicative of a memory transaction, and wherein said control circuit is configured to change said state in said register responsive to said second signal.

8-26. -26. (Canceled)