Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-06-24
2002-10-01
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S122000, C365S049130
Reexamination Certificate
active
06460117
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to cache memories in general, and in particular to set-associative cache memories. Still more particularly, the present invention relates to a set-associative cache memory having a mechanism for migrating a most recently used set.
2. Description of the Prior Art
In order to increase the speed of access to data stored within a main memory, modern data processing systems generally maintain the most recently used data in a high-speed memory known as a cache memory. This cache memory has multiple cache lines, with several bytes per cache line for storing information in contiguous addresses within the main memory. In addition, each cache line has an associated tag that typically identifies a partial address of a corresponding page of the main memory. Because the information within each cache line may come from different pages of the main memory, the tag provides a convenient way identify to which page of the main memory the information within a cache line belongs.
In a typical cache memory implementation, information is stored in one or several memory arrays. In addition, the corresponding tags for each cache line are stored in a structure known as a directory or tag array. Usually, an additional structure, called a translation lookaside buffer (TLB), is utilized to facilitate the translation of an effective address to a real address during a cache memory access.
In order to access a byte in a cache memory with an effective address, the mid-order bits, for example, of the effective address are utilized to select a cache line from the memory array along with a corresponding tag from the directory. The low-order bits, for example, of the effective address are then utilized to choose the indicated byte from the selected cache line. At the same time, the high-order bits, for example, of the effective address are translated via the translation lookaside buffer to determine a real page number. If the real page number obtained by this translation matches the real address tag stored within the directory, then the data read from the selected cache line is the data actually sought by a processing unit. This is commonly referred to as a cache “hit,” meaning the requested data was found in the cache memory. If the real address tag and translated real page number do not agree, a cache “miss” occurs, meaning that the requested data was not stored in the cache memory. Accordingly, the requested data have to be subsequently retrieved from the main memory or elsewhere within the memory hierarchy.
With a direct-mapped cache, only one of the group of corresponding lines from all pages in a real memory page can be stored in the cache memory at a time; but in order to achieve a better “hit” ratio, sometimes a set-associative cache is utilized instead. For example, with an N-way set associative cache, corresponding lines from N different pages may be stored. Since all entries can be distinguished by their associated tags, it is always possible to resolve which of the N lines having the same line number contains the requested information. The resolution requires comparison of the translated real page number to the N tags associated with a given line number. Each comparison generates an input to an N-to-1 multiplexor to select an appropriate cache line from among the N possibilities. In order to achieve high parallelism and uniformity within the cache design, according to the prior art cache architecture, each set within the N-way set-associative cache is identical in size. Furthermore, the layout and wiring of the N-way set-associative cache are fashioned in such a manner that the access time to each set within the cache is identical.
SUMMARY OF THE INVENTION
A cache memory has multiple congruence classes of cache lines. Each congruence class includes a number of sets organized in a set-associative manner. In accordance with a preferred embodiment of the present invention, the cache memory further includes a migration means for directing information from a cache “hit” to a predetermined set of the cache memory.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4823259 (1989-04-01), Aichelmann, Jr. et al.
patent: 5276848 (1994-01-01), Gallagher et al.
patent: 5883904 (1999-03-01), Arimilli et al.
patent: 5900012 (1999-05-01), Tran
patent: 5920888 (1999-07-01), Shirotori et al.
Arimilli Lakshminarayana Baba
Fields, Jr. James Stephen
Guthrie Guy Lynn
Anderson Matthew D.
Kim Matthew
LandOfFree
Set-associative cache memory having a mechanism for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Set-associative cache memory having a mechanism for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set-associative cache memory having a mechanism for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2963253