Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-07-07
2002-04-23
Robertson, David L. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
Reexamination Certificate
active
06378047
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to electronic circuits within a computer system. More specifically, this invention relates to systems and methods for invalidating cache memory within a computer system.
2. Description of the Related Art
Modern computer systems use a memory hierarchy to maximize their performance. This type of hierarchy exists so that the computer system can simultaneously store large amounts of data and provide rapid access to that data for the consumer. In current computer systems, the memory hierarchy resides within three stages. The first memory stage is designed to permanently store large amounts of data, and is normally provided by a magnetic disk or CD-ROM. The second memory stage is usually called “main memory” and is normally provided by 16, 32, 64 or more megabytes of dynamic random access memory (DRAM). The second stage of memory holds data and program information while the computer system is turned on. However, the main memory area is normally erased once power is removed from the computer.
The third stage of memory is a cache memory system. The cache memory system normally resides between a host processor and the main memory. In some cases, such as with an Intel® Pentium® Pro processor, portions of the cache memory system are incorporated into the host processor. Most cache memory systems are made up of static RAM which has a very fast access time. Static RAMs with 15, 20 or 25 nanosecond access times or faster are currently available. In use, blocks of the main memory are copied into the static RAM of the cache memory. When the host processor requires data or program instructions from main memory, it normally first checks the cache memory for that data. If the requested data is found within the cache memory, then the processor retrieves the data without having to access the slower main memory. Because most processors access data segments that reside near each other sequentially, one block of cache memory may hold the required data for several processor requests.
One challenge in designing a cache memory system is the maintenance of cache coherency between the main memory and the cache memory. For example, when a block of data is updated in the cache memory, the same address in the main memory must also be eventually updated. One mechanism for providing cache coherency involves storing “valid” and “modified” flags with every address in the cache memory. These flags are usually single bits that help the computer system identify addresses in the cache memory which have been updated, but not written back to the main memory.
As one example, the processor may write a new piece of data into an address in the cache memory and then mark that address as both valid and modified by setting the valid and modified bits to a one. A memory controller within the computer system can then determine that this particular address in cache memory holds valid data from the processor that has been modified, but not written back to the main memory. Once the memory controller writes the data from the cache memory to the main memory, the modified bit is set to a zero to indicate that the data block at this location in cache has been written back to the main memory.
Cache memory systems are normally organized into blocks, called cache lines, with each line typically containing 16, 32, 64 or 128 bytes of consecutive memory locations. A cache controller manages the cache memory and intercepts the read and write signals going to the main memory from the processor. For example, if the processor attempts a memory read operation, the cache controller first checks the desired memory address against a list of current addresses within the cache memory system to determine if the desired address has already been stored in the cache. If the memory address is found within the cache, the requested data is immediately sent from the fast cache memory to the processor, normally with zero wait states. If the cache memory does not contain data at the desired address, the cache controller reads the requested memory block from the main memory into a cache line in the cache memory system and passes the requested data to the CPU.
Although the CPU must wait for the cache controller to fill a cache line from the main memory, addresses located next to the requested address will be loaded into the cache system and thereby be available to the processor should it desire any of these addresses. As discussed above, many processors gather data from segments that are very near the previously read segment.
Various cache schemes have been designed to efficiently transfer data from the main memory to the processor. One cache memory scheme is a set-associative cache, and is known to efficiently manage memory requests from the processor. In this system, the cache controller stores a given memory block in any one of several cache lines. Each of these cache lines is known as a set. Thus, these types of cache systems, wherein the memory block is stored in either of two cache lines is called a two-way set-associative cache.
As discussed above, the host processor marks specific addresses as valid or modified within the cache memory system in order to maintain cache coherency. In addition, it is sometimes necessary for the host processor to “flush” the cache by invalidating every address within the cache system. Some host processors, such as the Intel® Pentium® Pro processor, provide a FLUSH signal interface to the cache controller for just this purpose. However, prior to invalidating each address within the cache, the processor must first determine if any data needs to be written back to the main memory.
Modified, but not written back data, is first copied to the main memory during a FLUSH cycle. As discussed above, the Intel® Pentium® and Intel® Pentium® Pro processors include a FLUSH signal on their host interface. If the FLUSH signal is asserted, the Pentium® or Pentium® Pro processor writes back all of the internal cache lines that have modified data to the main memory. In addition, each address in the cache memory system is invalidated. This operation puts all internal cache lines into the invalid state. This process is used, for example, when the system is shutting down to ensure that all data within the cache system has been written to the main memory. However, current systems do not perform these flush cycles efficiently, thus leading to a slower overall computer performance.
Various systems have been designed in the prior art for invalidating the cache memory during a flush cycle. For example, some systems perform a flush cycle by reading the first address in the cache, determining whether that data has been modified, writing any modified data back to main memory, and then invalidating that address. The process then moves sequentially to the next address within the cache memory and repeats. When this type of flush process begins in computers with a set-associative cache memory system, each address in every set is analyzed individually to determine whether the data in that particular address has been modified, but not written back to the main memory. Because each set in the cache system is analyzed sequentially, these systems perform the FLUSH cycle very inefficiently.
Due to the aforementioned limitations in prior systems, the technology needs a method and system for efficiently invalidating multiple addresses within a memory cache. What is also needed in the technology is a mechanism responsive to a signal from a computer processor for efficiently invalidating every address within the computer system's cache memory.
SUMMARY OF THE INVENTION
One embodiment of the invention is a set-associative cache memory system in communication with a computer processor and main memory. The cache memory system includes cache tag memory and cache data memory. The cache memory system includes: a counter for outputting an address to be invalidated in the cache memory; an update circuit in communication with the cache tag memory for simultaneously determining whether any set in
Knobbe Martens Olson & Bear LLP
Robertson David L.
LandOfFree
System and method for invalidating set-associative cache... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for invalidating set-associative cache..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for invalidating set-associative cache... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2852725