|
|
|
|
|
|
|
Examples of Snoopy Protocols |
|
|
|
|
|
|
|
|
The following paragraphs describe some representative examples of the different classes of bus-based protocols. All caches are basically assumed to be CBWA, but requests to a shared line may force a line write. (See Table 8.4.) State tables of the protocol are provided in Appendix F, along with some descriptions. |
|
|
|
|
|
|
|
|
Write-invalidate (or simply Invalidate) This is one of the simplest protocols, and has only three states: Invalid, Valid, and Dirty. For a read hit, clearly there are no coherency problems. When there is a read miss, the CPU changes the state of the cache line to Valid. On a write hit, the bus notifies all users that the line is Invalid. This is similar to the action on a write miss. In either case, the write line is marked Dirty and all other users mark their lines Invalid (Figure 8.20). |
|
|
|
|
|
|
|
|
When another processor tries to access a dirty line, a bus read for the line occurs. The processor holding the line supplies the data, updates memory, and marks the line valid if the remote process tries to write (i.e., a bus write occurs). The processor holding the line would respond similarly, but would mark the line invalid on completion. |
|
|
|
|
|
|
|
|
The state diagram (Figure 8.20) is interpreted as follows. A line is initially invalid and not in any cache. A read miss causes the line to be transferred to the requesting cache and marked valid. Subsequent read misses to the same cache entry by conflicting memory line addresses also receive valid line copies. When a processor writes to a line in its cache, that line is marked dirty and the bus broadcasts an invalid signal for the line. This is repeated in any subsequent write to the dirty line. If a read miss to a dirty line (from another processor) is detected by the bus (bus read miss), the bus and cache update the line in memory. Then the requesting processor accesses the updated line now marked valid. The originating processor also marks the line valid. |
|
|
|
|
|
|
|
|
Berkeley The Berkeley (also called Berkeley-SPUR) cache coherency protocol [157] uses the idea of cache line ownership (see Figure 8.21). At any time, a cache line can only be owned by either one of the caches or, if no caches own the line, by memory. There are four states: Invalid, Read Only, Shared Dirty, and Private Dirty. When a line is shared, only the owner has the cache line in the Shared Dirty state; all others have the line in the Read Only state. Therefore, a cache line can be Shared Dirty or Private Dirty in only one cache (the owner). |
|
|
|
|
|
|
|
|
When a read miss occurs, the requesting cache gets the data from the owner of the cache line, which can be memory (if the line is in the Invalid or Read Only states in other caches) or the other caches (where it is in the Shared Dirty or Private Dirty), and sets the state to Read Only. If the line requested is in the Read Only state in any other caches, it is main memory, the owner, which supplies the data. The state of the cache line then remains as Read Only. If the line requested is owned by another cache (i.e., in the Shared Dirty or Private Dirty state), then the cache (owner) that supplies the data sets the state of the cache line to Shared Dirty. |
|
|
|
|
|