Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-02-08
2004-12-21
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S144000, C711S119000, C711S117000
Reexamination Certificate
active
06834327
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to multilevel cache memory systems, such as may be used in modern computer systems. In particular, the invention relates to a unified cache tag system capable of storing cache tags for multiple levels of cache. The unified cache tag system is capable of supporting multiple levels of cache with nonuniform cache line sizes and associativities.
BACKGROUND OF THE INVENTION
Cache memories are high speed memory systems that store a partial copy of the contents of a larger, slower, memory system. In addition to storage, cache memory systems also have apparatus for identifying those portions of the larger, slower, memory system held in cache, this often takes the form of a cache tag memory.
Many modern computer systems implement a hierarchy of cache memory systems. Many common processors, including Intel Pentium-II and Pentium-III circuits, have two levels of cache. There exist computing systems with three levels of cache.
Cache memories typically have separate cache tag memories for each level of cache. In a three level cache memory, there are typically separate tag memories for each level of the cache.
Since off-chip references are significantly slower than on-chip references, yet off-chip cache can be much faster than main memory, three level cache systems may have the first and second levels of cache on-chip, with the third level off-chip. Alternatively, a three level cache system may have the first and second levels of cache on chip, together with the tag subsystem of the third level, while third level cache data is off-chip.
These cache systems have cache tag memory subsystems and cache data memory subsystems. Each cache data memory typically operates on units of data of a predetermined size, known as a cache line. The size of a cache line can be different for each level in a multilevel cache system; when cache line sizes differ, they are typically larger for higher levels of cache. Typically, the size of the cache data memory is also larger for higher levels of cache.
In typical cache memory systems, when a memory location at a particular main-memory address is to be read, a cache-line address is derived from part of the main-memory address. A portion of the cache-line address is typically presented to the cache tag memory and to the cache data memory; and a read operation done on both memories.
Cache tag memory typically contains one or more address tag fields. Multiple address tag fields can be, and often are, provided to support multiple “ways” of associativity in the cache. Each address tag field is compared to the remaining hits of the cache-line address to determine whether any part of data read from the cache data memory corresponds to data at the desired main-memory address. If the tag indicates that the desired data is in the cache data memory, that data is presented to the processor and next lower-level cache; if not, then the read operation is passed up to the next higher-level cache. If there is no higher-level cache, the read operation is passed to main memory. N-way, set-associative, caches perform N such comparisons of address tag fields to portions of desired data address simultaneously.
Cache memories having cache data memories not located on a processor chip are known as “off-chip” caches. Cache memories located on a processor chip are known as “on-chip” caches. Some “off-chip” caches have on-chip tag memories, although the data memory is off-chip.
Typically, a tag memory contains status information as well as data information. This status information may include “dirty” flags that indicate whether information in the cache has been written to but not yet updated in higher-level memory, and “valid” flags indicating that information in the cache is valid.
A cache “hit” occurs whenever a memory access to the cache occurs and the cache system finds, through inspecting its tag memory, that the requested data is present and valid in the cache. A cache “miss” occurs whenever a memory access to the cache occurs and the cache system finds, through inspecting its tag memory, that the requested data is not present and valid in the cache.
When a cache “miss” occurs in a low level cache of a typical multilevel cache system, the main-memory address is passed up to the next level of cache, where it is checked in the higher-level cache tag memory in order to determine if there is a “hit” or a “miss” at that higher level. In a three-level cache system of this type, an address must be tried against three successive cache tag memories before an overall cache miss can be declared, and a main memory reference started.
Typically, the number of “ways” of associativity in a set-associative cache tag subsystem is the number of sets of address tags at each index, or line, of tag memory, and corresponding sets of comparators. The number of ways of storage is the number of cache lines that can be stored and independently referenced through a single line of cache tag memory. In most caches, the number of ways of associativity is the same as the number of ways of storage. Cache superlines are combinations of multiple cache lines that can be referenced though a single address tag in a line of tag memory.
Writethrough caches are those in which a write operation to data stored in the cache results in an immediate update of data in a higher level of cache or in main memory. Writeback caches are those in which a write operation to data stored in the cache writes data in the cache, but update of data in higher levels of cache or in main memory is delayed. Operation of cache in writeback and writethrough modes is known in the art.
It is desirable to quickly determine a cache “miss”, so as to more quickly start main memory references for data not found in cache. It is desirable to minimize the physical area on a CPU chip required as overhead for multiple, separate, tag memories. It is also desirable to have flexibility to adjust cache sizes, or ways of associativity, in later stages of processor development to adjust for power or growth of other units on the circuit. It is also desirable to have a simple way to adjust cache sizes to provide lower cost product offerings.
Whenever a cache “miss” occurs at any level of the cache, data fetched from a higher level of cache or main memory is typically stored in the cache's data memory and the tag memory is updated to reflect that data is now present. Typically also, other data may have to be evicted to make room for the newly fetched data. Cache line eviction and replacement is well known in the art.
Many computer systems embody multiple processors, each having its own cache system. Typically, processors of such systems may access shared memory. Coherency is required in cache memory of such computer systems. Cache coherency means that each cache in the system “sees” the same memory values. Therefore, if a cache wants to change the value of memory, all other caches in the system having copies of that memory location in its cache must either update its value or invalidate its contents.
There are several solutions to cache coherency in multiple processor cache-equipped systems that are commonly used with conventional cache systems. Typically this is done by providing cache coherency maintenance logic.
Cache coherency maintenance logic may take the form of “snoop” logic for snooping accesses to the shared memory. Snooping can involve having each processor cache of the system monitor a bus for memory accesses, including writes, by other processors and caches of the system. This monitoring is typically performed by performing a cache tag lookup, through a snoop port on the cache tag memory subsystem, whenever an address from another processor or cache is present on the bus. When a cache tag memory subsystem sees snoop references to an address corresponding to data held in the cache, that cache invalidates or updates its copy of the data as appropriate to maintain coherency.
Other forms of cache coherency maintenance logic are known, including directory based coherency maintenance systems where a system contro
LandOfFree
Multilevel cache system having unified cache tag memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multilevel cache system having unified cache tag memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multilevel cache system having unified cache tag memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293084