Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-08-07
2004-06-08
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S137000, C711S133000
Reexamination Certificate
active
06748492
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to digital systems and, more particularly, to caches within digital systems.
2. Description of the Related Art
Processors and/or the computer systems including the processors typically provide caches to alleviate the high memory latency frequently experienced in computer systems. Generally, a cache is a relatively small, high speed memory which may store copies of data corresponding to various recently-accessed memory locations. Generally, cache storage is allocated and deallocated in units of cache lines (a group of bytes from contiguous memory locations). In other words, the cache may include multiple entries, and each entry may include storage for a cache line of bytes. If requested data for an access is not in the cache (a “miss”), an entry is allocated for the cache line including the requested data and the cache line is filled into the allocated entry. Subsequently, the data may be found in the cache upon request (a “hit”). In some cases, a portion of the cache line (often called a “sector”) may be valid while other portions are invalid. However, the entire cache entry is allocated for the cache line if one or more of the sectors are valid.
Since a cache is generally smaller than the system memory for which the cache is used, cache lines currently stored in the cache may need to be deleted from the cache (referred to as “evicting” the cache line) to make room for newly accessed data which is not stored in the cache. The newly accessed data may be statistically more likely to be accessed again in the near future than is data that has been in the cache for some time, particularly for code which exhibits locality of reference (in which access to a particular datum makes access to nearby data within the memory more likely). Typically, the cache selects one or more cache entries which are eligible to store data corresponding to a given transaction, and searches these entries to detect a hit or miss. In a direct-mapped cache, one entry is eligible to store the data based on the address of the data. If a miss is detected in a direct mapped cache, that cache line in that entry is evicted. In a set associative cache, on the other hand, two or more entries are eligible to store the data based on the address of the data. The cache line of any one of the two or more entries could be evicted on a miss. Set associative caches employ a replacement policy to select one of the two or more eligible entries for eviction. A variety of replacement policies exist.
Unfortunately, it is frequently difficult to predict, from a viewpoint external to the cache, which cache entry will be allocated to a given cache line. Complex monitoring of the transactions presented to the cache, along with detailed knowledge of the implemented replacement policy, would be required to determine the state of the replacement policy at any given point in time. During the typical access of various data from memory, this lack of ability to determine which cache entry will be selected is generally not a problem. However, in some cases, it may be desirable or even critical to know which cache entry will be allocated according to the replacement policy. For example, in certain testing situations, it may be desirable to ensure that a particular entry is used for a particular transaction. Additionally, knowing which entry will be allocated to a cache miss could be used to intentionally evict the cache line in the entry (e.g. to flush the particular entry from the cache). Thus, a method for easily determining which entry will be selected by a replacement policy is desired.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a cache as described herein. The 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 other embodiments, the replacement circuit may receive a deterministic setting in response to other transactions (e.g. a memory-mapped transaction directed to the replacement circuit or a dedicated bus command).
The deterministic setting of the replacement policy may have a number of uses. For example, the transaction used to set the replacement policy may provide a synchronization point for the cache. Thus, the same tests may be run in multiple test environments (which may have varying initialization procedures) and the portion after the synchronization may operate in the same manner in the different environments, at least with respect to the cache 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).
The combination of the direct access transactions and the deterministic setting of the replacement policy may be used in a variety of ways as well. For example, a cache entry flush may be accomplished by performing a direct access transaction to the desired way, followed by a memory transaction which misses. The direct access transaction causes the replacement policy to select the entry in the desired way for eviction for the following memory transaction.
Additionally, the combination of direct access transactions and the deterministic setting may be used to provide cache testing by using a direct access transaction to select a test way, then using a memory transaction which misses the cache to cause test data to be loaded into the test way. A subsequent direct access transaction may then read the data from the test way to check the test data for correct storage in the selected entry. Additionally, the tag information may be captured in a register within the cache. The tag information may be read from the register and checked for accuracy.
Broadly speaking, a cache is contemplated comprising an associative memory and a replacement circuit. The memory has a plurality of entries, and each of the plurality of entries is configured to store a cache line of data. The plurality of entries are arranged in a plurality of ways. The replacement circuit is configured to select an entry of the associative memory for eviction responsive to a cache miss by a memory transaction. The replacement circuit is configured, responsive to a first transaction specifying an explicit update of said replacement circuit to select a first way of the plurality of ways, to establish a first state corresponding to a selection of the first way.
Additionally, a system is contemplated comprising an associative cache and a first circuit coupled to the cache. The cache has a plurality of entries. Each of the plurality of entries configured to store a cache line of data. The plurality of entries are arranged in a plurality of ways. The first circuit is configured to initiate a first transaction specifying an explicit update of a replacement policy of said cache to select a first way of the plurality of ways. The cache is configured to select an entry of the cache for eviction in response to a cache miss by a memory transaction. Additionally, the cache is configured to establish a first state corresponding to a selection of the first way of the cache responsive to the first transaction.
Moreover, a method for flushing a cache is contemplated. A first tran
Dickman Michael P.
Rowlands Joseph B.
Bataille Pierre-Michel
Broadcom Corporation
Merkel Lawrence J.
LandOfFree
Deterministic setting of replacement policy in a cache... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deterministic setting of replacement policy in a cache..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic setting of replacement policy in a cache... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301252