This invention relates to caching data.
Caches improve the performance of microprocessors by storing copies of data that would otherwise be subject to frequent accesses from main memory. Because changes to the data in the cache are not immediately copied back to main memory, the version of data kept in main memory may not be correct. Because a cache typically uses memory chips that have faster access times than those used in main memory, a microprocessor can read and write data in its cache faster than in its main memory. Fast access cache memory chips cost more than slower access main memory chips and so a cache is typically smaller than main memory. Only a portion of the main memory data can reside in the cache at one time. Caches have circuitry to transfer data back and forth from main memory depending on which data the microprocessor is accessing. When data which the microprocessor needs to read or write is not in its cache, the cache decides whether to copy the data from main memory to the cache. Whole groups of contiguous words, known as "lines", are copied at one time into the cache. When the cache is full, lines being copied overwrite old lines.
Cache management is more complicated in multiprocessor systems in which, for example, one microprocessor runs a word processing system while another runs a data base, or two microprocessors run different tasks of a single data base program. Both processors may seek to access the same location in main memory, creating a conflict between the processors' caches.
In the known system illustrated in FIG. 1, the two processors CPU A 10 and CPU B 12 share a common level 2 cache 22. CPU A 10 and CPU B 12 are connected to a common host bus 14 by which they communicate with a cache/memory controller 16. The cache/memory controller manages access to main memory 18 by CPU A and CPU B and by other devices via a PCI bus 20. Each CPU has its own level 1 cache (not shown) which is typically on the same chip as the CPU and is not shared with the other CPU. CPU A and CPU B resolve ownership of the host bus via bus arbitration signals 24. Those same signals are used to resolve conflicts involving the level 1 caches in the two CPUs.
A typical known cache, shown in FIG. 2, has a cache memory 30 holding lines of data 32a-k, each including two or more words 34a-e. The number of lines in the cache and the number of words per line varies from cache to cache.
The typical known cache also includes a tag ram 36, which contains an address 38a-k and a status 40a-k for each line in the cache. Each address is an address in main memory corresponding to the data in the corresponding line in the cache. For example, address 38a may be the main memory address corresponding to the data in line 32a.
The status indicates the validity of the data in the corresponding line. For example, status 40a may contain the status for line 32a. Each status can have one of four values: (1) "modify", which means that a CPU has modified one or more words in the corresponding line, leaving the data in main memory corresponding to that line "stale"; (2) "exclusive", which means that the data is available in only one cache and it is not modified; (3) "shared", which means that the data in the corresponding line is potentially shared with other caches in the system; and (4) "invalid", which means that the data in the corresponding line of the cache is invalid.
Because each CPU has its own cache, the possibility exists for conflict between the caches such as, for example, if CPU B changes data in its cache without changing main memory and CPU A attempts to read the same data from main memory into its cache. Unless the CPUs resolve this conflict, i.e. as shown in FIG. 3 for a known system, CPU A will process stale data. Assume CPU A has control of the host bus, i.e. is the "host master", so CPU A attempts to read from its level 1 cache. CPU A experiences a "read miss", meaning that its level 1 cache does not contain a line corresponding to the address sought to be accessed 52. CPU A tries to read the corresponding line of data from the level 2 cache or from main memory 56 and notifies CPU B of the impending read via the bus arbitration signals. CPU B detects that its level 1 cache contains the line CPU A is about to read and that the status of the line is "modify" which means that the data CPU A is attempting to read from the level 2 cache or main memory is stale. This is called a "hit on modify." CPU B notifies CPU A that the read is to a data line with stale data 58. CPU A completes the read from the level 2 cache or main memory through the cache/memory controller and discards the stale data 60. CPU A transfers control of the host bus to CPU B 62. CPU B writes the modified line to main memory through the cache/memory controller and changes the status of the modified line to "shared" 64. CPU A transfers control of the host memory back to CPU A 66. CPU A reads a line of data into its L1 cache from main memory through the cache/memory controller 68. CPU A then completes the read from its level 1 cache 70. CPU A and B change the status of the line in their L1 caches to "shared."
A similar sequence occurs if CPU A experiences a write miss to its L1 cache 72. The operation follows the same logic described above for steps 56, 58, 60, 62, 64, 66 and 68, except that in step 64 CPU B changes the status of the requested line in its L1 cache to "invalid" because it knows CPU A is about to write to that line. After CPU A reads the line of data into its L1 cache from main memory, it performs the write to its L1 cache and changes the status of the line in its L1 cache to "modified" 74.