Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-09-15
2003-02-04
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S128000
Reexamination Certificate
active
06516388
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains to the storage of data in a cache, and more particularly, to the reduction of cache pollution. Cache pollution is defined herein as 1) the overwrite of data that is more likely to be fetched from a cache with data that is less likely to be fetched from a cache, and 2) the preservation of data in a cache, which data is unlikely to be reused in the near future.
Note that the word “data” is used herein in two senses. In one sense, it is used to refer to specific data values which are to be added, shifted, or otherwise consumed by a functional unit of a computer. In another sense, “data” is used to generically refer to both specific data values which are consumed, and/or instructions which are executed, by a functional unit of a computer. In the preceding paragraph, the word “data” is used in its generic sense.
BACKGROUND OF THE INVENTION
Most modern computer systems comprise a number of functional units
104
and a memory hierarchy
102
. The functional units, in combination with a portion of the memory hierarchy
106
,
108
, and control logic for transferring instructions and data between the functional units and memory hierarchy, form a central processing unit (or “processor”
100
). See FIG.
1
. Functional units may comprise integer processing units, floating-point processing units, branch target adders, instruction fetch units, data fetch units, and so on.
The speed at which the processor can consume instructions and data is largely dependent upon the rate at which instructions and data can be transferred between the functional units and the memory hierarchy. In an attempt to increase these transfer rates, many computer systems employ a hierarchy of memory caches
106
,
108
.
A cache is simply a small, high-speed buffer memory which is used to temporarily hold those portions of the contents of main memory
110
which it is believed will be consumed in the near future by a processor's functional units. The main purpose of a cache is to shorten the time necessary to perform memory accesses, either for instruction or data fetch. Information stored in cache memory may be accessed in much less time than information located in main memory. Thus, a processor with a cache memory needs to spend far less time waiting for instructions and data to be fetched and/or stored. In a cache hierarchy, lower level caches typically store increasingly smaller subsets of the instructions and data which are stored in main memory and/or higher level caches. However, lower level caches also tend to provide fetched instructions and data to functional units at an increasingly faster rate.
Since instructions and data are retrieved from a cache much more quickly than they are retrieved from main memory, it is desirable to keep caches filled with the instructions and data which functional units are likely to consume next. To achieve this goal, some processors fetch instructions and data speculatively. That is, they will predict the outcomes of conditional instructions (e.g., branch instructions) and fetch instructions and data from target code sections. If the execution of a conditional instruction is predicted to result in a first outcome, a target code section might be synonymous with a sequential code section. If the execution of a conditional instruction is predicted to result in a second outcome, branching to a target code section might require a redirection of program flow so that instructions and data are fetched from a non-sequential code section.
Instructions and data which are retrieved from memory as a result of the predicted program flow described in the preceding paragraph are known as “fetch” data. However, additional instructions and data are sometimes retrieved from memory. These additional instructions and data are known as “prefetch” data. Prefetch data may comprise 1) instructions and data retrieved from an alternate program flow path, 2) instructions and data which an instruction explicitly asks hardware to load into a cache, and 3) instructions and data whose retrieval are triggered by a hint which is encoded in an instruction.
While some caches only store fetch data, other caches store both fetch and prefetch data. When a cache stores prefetch data, it is possible that some of the prefetch data will never be consumed by a functional unit. The storage of unneeded prefetch data in a cache is referred to as “cache pollution” (and is sometimes referred to herein as “prefetch pollution”). Cache pollution also results from the continued storage of fetch data in a cache, long after a current need for the data has passed. This second form of cache pollution is sometimes referred to herein as “fetch pollution”.
A number of methods have been devised to reduce cache pollution. One method involves writing new cache data over least recently used cache data. A least recently used (LRU) replacement algorithm therefore requires the tracking of data usage. Although numerous LRU-based algorithms exist, a true LRU algorithm simply ranks the temporal use order of data values stored in a cache. In an n-way, set-associative cache, for example, the data values in each indexed set of data values can be ranked from most to least recently used. When a new data value is written into such a cache, it will typically 1) overwrite the least recently used data value in a set of data values, and 2) be ranked as the most recently used data value in the set. The use rankings of other data values in the set are then downgraded accordingly.
If a cache stores both fetch and prefetch data, the use of an LRU-based based algorithm to store data in the cache can be problematic. Although the use of an LRU-based algorithm tends to alleviate pollution due to the storage of stale fetch data, the use of such an algorithm can sometimes overpopulate a cache's data entries with prefetch data, and thus increase prefetch cache pollution.
Another method for reducing cache pollution, and a method which alleviates both fetch and prefetch cache pollution, is to implement an LRU-based algorithm for data storage, but to only store fetch data in a cache
202
. Such a solution can be implemented by storing fetch and prefetch data retrieved from a higher level memory
208
in a buffer
204
, and then performing writes of data from the buffer to the cache. See FIG.
2
. Fetch data can be written from the buffer to the cache at any time (e.g., when cache fill port bandwidth so permits). If data is allowed to be fetched from the buffer, thus bypassing the cache, then provisions can be made for upgrading the status of this data to “fetched”, and also writing this data into the cache.
To assist in determining which data values should be written from the buffer to the cache, data can be stored in the buffer with a reference status (e.g., a single reference bit). A reference bit can be set to a first value to indicate that a data value stored in the buffer has been fetched—either prior to storage in the buffer, or subsequently. Likewise, a reference bit can be set to a second value to indicate that a data value stored in the buffer has only been prefetched. Since a reference bit is used to determine which data values are written into the cache, fetch data values which are written from the buffer to the cache will be referred to herein as “referenced” data values, and all other data values which are written from the buffer to the cache will be referred to as “non-referenced” data values.
Typically, the buffer which is used in the above method is small (perhaps on the order of eight entries). If the buffer is too large, it becomes similar to the cache, and some of its usefulness and efficiencies are lost. However, the small size of the buffer can also be problematic. If non-polluting prefetches are issued far in advance of fetches, or if many polluting prefetches are issued, the capacity of the buffer can quickly be exceeded, and useful prefetch data can be lost. Thus, the buffer reduces pollution in the cache, but at the risk of losing a greater percentage of prefetch data due to data overwrit
McCormick, Jr. James E.
Undy Stephen R.
Hewlett--Packard Company
Nguyen Hiep T.
LandOfFree
Method and apparatus for reducing cache pollution does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing cache pollution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing cache pollution will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3147195