A computer typically has a main memory that stores data that is accessed by a processor. In the typical configuration, main memory consists of dynamic random access memory (DRAM). To improve the speed at which data is retrieved from the main memory, a cache memory (a higher-speed data storage medium than the main memory) is often placed between the main memory and the processor. Memory caching is effective because many computer programs that run in the processor repeatedly access the same data. By keeping as much of this data as possible in the cache memory, the computer avoids accessing the slower main memory and instead accesses the higher speed cache memory.
When the processor needs to access data from memory, it first checks the cache memory to see if the data is there. If the data is in the cache memory, it is retrieved without accessing the main memory. Memory caching may dramatically improve the performance of applications because accessing a byte of data in cache memory can be many times faster than accessing a byte in main memory. This speed difference is possible because cache memory is usually made of high-speed static random access memory (SRAM) instead of the slower and cheaper DRAM.
Alternatively, cache memories may be built into the architecture of microprocessors. For example, the 80486 and the Pentium microprocessors from Intel Corporation contain cache memory.
Another form of caching, similar to memory caching, is disk caching. Disk caching works under the same principle as memory caching, but instead of using high-speed SRAM, a disk cache may use conventional main memory. The most recently accessed data from the disk (and possibly adjacent sectors) is stored in the disk cache. When the processor needs to access data from the disk, it first checks the disk cache to see if the data is there. If the data is there, it is retrieved without accessing the disk drive. Disk caching can dramatically improve the performance of programs in the processor because accessing a byte of data from RAM can be thousands of times faster than accessing a byte on a hard disk.
Memory caching and disk caching are considered “hierarchical” memory systems. For instance, in memory caching, the slower main memory is lower in the hierarchy than the faster cache memory. It is also possible that there are several layers of cache memory, where a second cache memory is placed between a first cache and the processor. In this case, the second cache memory is higher in the hierarchy than the first cache memory. Similarly, with disk caching, the slower disk drive is lower in the hierarchy than the faster main memory.
With memory caching, the processor may write to a memory address whose data is stored in the cache memory. In this case, the processor may write the data to the cache memory but may not to the main memory. Thus, for periods of time it is possible that the cache memory is current, i.e., up-to-date, but the main memory is not current. It is the function of a “coherence protocol” to eventually copy the data in the cache memory to the main memory to keep the main memory current.
Cache memory is typically much smaller than main memory. Eventually, the cache memory may become full, and the coherence protocol will copy some data in the cache memory to the main memory to make room for new, more-ofen accessed data from the main memory. Copying data from the cache memory to the main memory, however, is time consuming for the computer system. Often, the data the coherence protocol copies to the main memory is trash or “scratch” data that may be discarded. As a result, the coherence protocol wastes computer resources by copying useless data from the cache memory to the main memory.
The Intel Pentium chip provides for a way to prevent data in the cache memory from being copied to the main memory. Using an “INVD” instruction, the entire cache memory may be marked “invalid,” so that the data in the cache memory is not copied to the main memory. This command is used for initialization processes, however, and is impractical for use during normal processing. Because this instruction invalidates the entire cache memory, if the instruction were used during normal processing it is likely that useful, necessary data would be invalidated. Thus, the Intel Pentium chip “INVD” instruction does not address the problem of wasting computer resources by copying scratch data from the cache memory to the main memory during normal processing.
Disk caching has the same problem as memory caching. For instance, coherence protocols in a disk caching system may unnecessarily copy scratch data from main memory to the disk drive, wasting computer resources. Other hierarchical storage systems such as virtual memory and non-uniform memory access (NUMA) also encounter this problem.
NUMA is a type of parallel processing architecture in which each processor has a designated local memory but can also access remote memory owned by remote processors. It is “non-uniform” because the memory access times are faster when a processor accesses its own local memory than when it accesses memory of a remote processor. To increase memory access times in a NUMA system, the local memory may also act as a cache memory between the local processor and the memory of a remote processor. A coherence protocol functions to keep the remote memory current by coping data from the local memory to the remote memory when necessary. Thus, the processor's own local memory is higher in the hierarchy than the remote processor's memory. In this situation, the coherence protocol may unnecessarily copy scratch data from the local memory to the remote processor's memory.
Virtual memory is a type of memory management where some data that would otherwise be stored in main memory is stored on a disk drive instead, possibly because there is not enough main memory to store all the data. The access times of disk drives, as discussed above, is typically slower than the access times of main memory. To increase memory access times in a virtual memory system, the frequently accessed data is stored in main memory. A coherence protocol functions to keep the data stored on the disk drive current by copying data from the main memory to the disk drive when necessary. Thus, the main memory has a higher hierarchy than the disk drive. In this situation, similar to disk caching, the coherence protocol may unnecessarily copy scratch data from the main memory to the disk drive.
More generally, therefore, it is desirable to provide a way to save computer system resources in a hierarchical data storage system by preventing scratch data from being copied from a higher hierarchy data storage space to a lower hierarchy data storage space.