Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-01-10
2004-05-11
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C709S247000, C710S068000
Reexamination Certificate
active
06735673
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to processing systems and, more particularly, to compression of lines of data in processing system cache memories.
BACKGROUND OF THE INVENTION
Cache memories typically are utilized in processing systems for speeding up processor access to data stored in a main memory. A cache memory is smaller, faster and typically more expensive than main memory. When a processor requests data that resides in main memory, the processing system transmits the requested data to the processor and also may store the data in a cache memory, of which there may be a plurality of levels. When the processor issues a subsequent request for the same data, the processing system first checks cache memory. If requested data resides in the cache, the system gets a cache “hit” and delivers the data to the processor from the cache. If the data is not resident in the cache, a cache “miss” occurs, and the system retrieves the data from main memory. Frequently utilized data thus is retrieved more rapidly than less frequently requested data, and overall data access latency, i.e. time between a request for data and delivery of the data, is reduced.
Intermediate levels of cache may be utilized between a primary cache and main memory and are typically slower, and less expensive, than the primary cache. Upper-level caches in such a cache hierarchy generally are arranged in order of decreasing speed and typically are used to hold data accessed less frequently than data kept in the primary cache. When a cache miss occurs at the primary cache level, the processing system checks the upper cache level(s) for the requested data before accessing the data from main memory. Thus, although utilizing upper levels of cache can tend to improve overall system performance, it nevertheless remains desirable to make the lowest level of cache as large as affordable, to improve the chances of a cache hit in the lowest level of cache.
When a data address is presented to a cache, a lookup in a cache tag array is performed to determine if the requested data is currently in a data array of the cache. If so, then the data array is read. Data is stored in a cache data array as “lines”, all lines in the array containing equal numbers of bytes. The cache line size is generally the same for all levels of cache in a system. Current line sizes frequently are set at 64 or 128 bytes. A one-megabyte cache (having 2**20 bytes), for example, would store 8,192 128-byte lines, and a corresponding tag structure would contain 8192 entries. Increasing a cache size in a processing system not only can be expensive, but also can increase latency, as the processing system could be required to search a larger tag array, and then search a larger data array, to locate data in the cache.
Techniques are known which are aimed at reducing latency in cache searches. For example, data and tag lookup can be performed in parallel to reduce the number of clock cycles needed to search a cache. It also would be desirable, however, to increase the storage capacity of a cache without having to increase its physical size. Thus it would be desirable to provide for data compression in a cache. Such compression would be particularly appropriate for lower levels of a cache hierarchy, where capacity, more than latency, can affect system performance.
SUMMARY OF THE INVENTION
In one preferred form, the present invention is directed to a method for storing lines of data in a data array of a cache memory mapped to a main memory of a processing system. The data array includes a plurality of data storage lines having equal lengths. The method includes steps of compressing at least one of the lines of data, fitting the compressed line of data within a subsection of one of the data storage lines, and pointing to the subsection using a tag array.
When lines of data are compressed on writes to cache and decompressed on reads from cache, more lines can fit into the cache. Thus a probability of a cache hit is increased, and processing system performance is enhanced.
Further areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention.
REFERENCES:
patent: 6032148 (2000-02-01), Wilkes
patent: 6115787 (2000-09-01), Obara
patent: 6128094 (2000-10-01), Smith
patent: 6324621 (2001-11-01), Singh et al.
patent: 6484228 (2002-11-01), Breternitz et al.
patent: 6580427 (2003-06-01), Orenstein et al.
patent: 6581131 (2003-06-01), Vondran, Jr.
Hewlett--Packard Development Company, L.P.
Moazzami Nasser
LandOfFree
Apparatus and methods for cache line compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and methods for cache line compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and methods for cache line compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266476