Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1996-12-06
2001-01-16
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S144000, C711S156000, C711S202000, C711S203000, C711S205000
Reexamination Certificate
active
06175906
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to caches in microprocessor systems and, more particularly, to the revalidation of virtual tags after memory mapping changes.
2. Description of the Relevant Art
Microprocessors utilize caches to provide faster access to data stored in memory. Caches are typically smaller and faster memory devices that store the most recently accessed blocks of data. Because memory accesses are typically made to memory locations in close proximity to previously accessed memory locations, storing the most recently accessed blocks of data significantly reduces the number of accesses to the system memory.
Virtual addresses in a microprocessor must be translated to physical addresses prior to memory accesses. Likewise, caches that reference data blocks using physical addresses must convert virtual addresses to physical addresses before detecting a cache hit. Rather than translating a virtual address each time it is accessed, a translation lookaside buffer (TLB) stores the most recently accessed virtual-to-physical address translations.
The use of virtual address tags in a cache provides faster and simpler access to data blocks stored in cache. Virtual tags eliminate the need to perform a TLB look-up prior to detecting a cache hit. Although a TLB look-up can be done in parallel with cache access, increasing the number of TLB look-ups requires a larger TLB to minimize TLB misses. It is advantageous to keep the TLB small enough to avoid impacting the memory access time. Large TLB's in aggressive clock rate processors typically force a hierarchical TLB structure that adds further complications. The use of virtual tags in a cache greatly reduces the demand on the TLB because the TLB only needs to be referenced on cache misses. In virtual tag caches, the demand for the TLB may be sufficiently low to allow one TLB to services two caches, e.g., an instruction cache and a data cache.
The main drawback of using virtual tags in a cache is that the tags must be invalidated whenever a virtual-to-physical memory mapping change occurs. Although mapping changes typically involve little if any of the data stored in the cache, the tags must be invalidated. The chance exists that one or more virtual tags are remapped to a different physical location. An access to a virtual tag that has been remapped would yield the wrong data.
Invalidating the virtual tags of a cache effectively empties the cache. All data blocks must be re-fetched from memory according to the new mapping, even though many cache entries still have valid virtual tags. Therefore, many of the existing blocks in cache are re-fetched and re-loaded into the cache.
Processors which support write-back caching and maintain coherency with physical memory must typically store physical tags for each cache entry. The physical tags are required for snooping and provide the proper memory address on a write-back. Each physical tag is associated with a cache entry and a virtual tag.
The presence of the physical tags can be used to avoid the unnecessary re-loading of the cache when a memory mapping change occurs. When a cache miss occurs due to an invalidated virtual tag, the TLB is referenced to translate the virtual address of the requested data to a physical address. The physical address from the TLB is checked against the physical tag associated with the invalidated virtual tag. If the physical tag matches the physical address from the TLB, the virtual tag is still valid and the requested data block resides in cache. Because the data block is already in cache, there is no need to refetch the data from memory. The data is read from cache and the virtual tag is revalidated by asserting a valid bit of the virtual tag. This recovery mechanism reduces cache misses and system memory accesses.
The above described recovery mechanism causes a flurry of TLB accesses when a virtual-to-physical memory mapping change occurs (i.e. a remapping occurs). A remapping invalidates all the virtual tags, which effectively empties the cache. Because the TLB is accessed on each cache miss, a remapping causes a short term high demand on the TLB accesses. During these periods of high demand on the TLB, the TLB can create a bottleneck that slows down the recovery from the remapping. What is desired is a way to reduce the number of TLB accesses during a virtual-to-physical memory mapping recovery.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a mechanism that revalidates virtual tags of data blocks on the same page as recovered data blocks. Once a virtual-to-physical mapping of one data block in a given page has been revalidated, other blocks in the same page can be recovered without referring to the TLB. Typically, most of the cache contents are not affected by the remapping that caused the invalidation of the virtual tags. Therefore, most of the virtual tags are still valid. Once one virtual tag is revalidated by converting the virtual address to a physical address and comparing the physical address to the physical tag, it is concluded that the corresponding page has not been remapped. Therefore, all other virtual tags that are associated with data blocks on the same page have also not been remapped. After the virtual tag of one block of data within a page of data has been revalidated, other blocks of data on that page can be revalidated without accessing the TLB.
A register records the page numbers of data blocks that have been successfully recovered, i.e. the associated virtual tag has been revalidated. The register is referenced in parallel with the cache look-up. If the page number of the requested address matches an entry in this register, and a previously valid virtual tag matches the requested virtual address, then the virtual tag is still valid and can be revalidated immediately.
Broadly speaking, the present invention contemplates a cache control circuit including a virtual tag register for storing virtual tags, a physical tag register for storing physical tags, a valid register, a recovery register, and a valid circuit. Each virtual tag is associated with a data block in a cache. Each physical tag is associated with a data block in a cache. The valid register includes a plurality of registers for storing current valid bits and previous valid bits, wherein the current valid bits indicate that an associated virtual tag is currently valid, and the previous valid bits indicate that an associated virtual tag was valid during a previous cycle. The recovery register stores a page number of a recovered data block. The valid circuit asserts a current valid bit associated with a virtual tag if a page number of a data block associated with the virtual tag matches the page number stored in the recovery register, and a previous valid bit associated with the virtual tag indicates the virtual tag was valid during a previous cycle.
The present invention still further contemplates a method for validating a virtual tag including the steps of: storing a page number of a recovered data block, storing a previous valid bit indicative of the validity of a virtual tag in a previous validation cycle, and validating the virtual tag if the previous bit indicates the virtual tag was valid in a previous cycle, and a page number of a data block associated with the virtual tag matches the stored page number.
REFERENCES:
patent: 4044338 (1977-08-01), Wolf
patent: 4453212 (1984-06-01), Gaither et al.
patent: 4680700 (1987-07-01), Hestler et al.
patent: 4807115 (1989-02-01), Torng
patent: 4858105 (1989-08-01), Kuriyama et al.
patent: 4928223 (1990-05-01), Dao et al.
patent: 5053631 (1991-10-01), Perlman et al.
patent: 5058048 (1991-10-01), Gupta et al.
patent: 5129067 (1992-07-01), Johnson
patent: 5136697 (1992-08-01), Johnson
patent: 5226126 (1993-07-01), McFarland et al.
patent: 5226130 (1993-07-01), Favor et al.
patent: 5239635 (1993-08-01), Stewart et al.
patent: 5349651 (1994-09-01), Hetherington et al.
patent: 5428757 (1995-06-01), Sutton
patent: 5481689 (1996-01-01), Stamm et al.
patent:
Advanced Micro Devices , Inc.
Cabeca John W.
Chace Christian P.
Conley Rose & Tayon PC
Merkel Lawrence J.
LandOfFree
Mechanism for fast revalidation of virtual tags does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for fast revalidation of virtual tags, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for fast revalidation of virtual tags will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2538812