Deterministic setting of replacement policy in a cache

• US 6,961,824 B2
• Filed: 06/04/2004
• Issued: 11/01/2005
• Est. Priority Date: 08/07/2000
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Rowlands, Joseph B., Dickman, Michael P.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/861,638
• Publication Number:
  US 20040221110A1
• Time in Patent Office: 515 Days
• Field of Search: 711/128, 711/159, 711133-137, 711/160
• US Class Current: 711/137
• 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. An apparatus comprising:

a cache memory arranged to having a plurality of ways to store data;

a replacement circuit having a linear feedback shift register to hold a value to select a way for replacement when a cache miss is to occur, the replacement circuit to receive a predetermined value by a cache direct access transaction which loads the predetermined value into the linear feedback shift register to select a particular way of the cache memory to be evicted with a next cache miss, and the replacement circuit also including a next state circuit coupled to the linear feedback shift register to receive a first of one or more bits from the linear feedback shift register and to use the first of one or more bits to generate an output bit from the next state circuit to shift into the linear feedback shift register to set a new value in the linear feedback shift register to select a way for eviction with the next cache miss; and

a control circuit coupled to the replacement circuit to select between replacement by direct access transaction or by shifting in of the output bit.

2. The apparatus of claim 1 wherein the next state circuit is to generate a new value for the linear feedback shift register with a memory transaction that results in a cache miss.

3. The apparatus of claim 1 wherein the replacement circuit further includes an output circuit coupled to the linear feedback shift register to receive a second of one or more bits from the linear feedback shift register and to use the second of one or more bits to generate a way value to determine which way of the plurality of ways is to be evicted.

4. The apparatus of claim 1 wherein the cache memory is set associative.

5. The apparatus of claim 1 wherein the cache memory is fully associative.

6. The apparatus of claim 1 wherein the cache memory is a level 2 cache.

7. A method comprising:

establishing a value in a linear feedback shift register for a cache memory in which the value is used to select a way from a plurality of ways of the cache memory for replacement when a cache miss occurs by;

(i) using one or more bits from the linear feedback shift register to generate a bit to shift into the linear feedback shift register to update the linear feedback shift register with a new value to randomly select a way for a next eviction;

or

(ii) receiving a cache direct access transaction to load the linear feedback shift register with a predetermined value to select a particular way to be evicted with a next eviction, instead of randomly selecting a way; and

evicting on a cache miss by either selecting a random way or by using the predetermined value.

8. The method of claim 7 wherein update of the linear feedback shift register with the new value occurs with a memory transaction that results in a cache miss.