|
|
|
|
|
|
|
Figure 8.31
SCI distributed directory structure. Nc = number of caches. |
|
|
|
|
|
|
|
|
[12,148], respectively. In the singly-linked list (SDD), each processor-cache points only to its predecessor. Memory points to the head of the list (Figure 8.30). |
|
|
|
|
|
|
|
|
The scalable coherence interface (the SCI) maintains this list as a doubly linked list, so that each cache entry points not only to its successor in the list, but also to its predecessor (Figure 8.31). In either scheme, a pointer occupies bits. |
|
|
|
|
|
|
|
|
For a singly linked list, the overall number of bits required for the protocol is (approximately) determined by the number of bits required in memory to point to the possible "head of the list." The number of bits required for the memory directory is: |
|
|
|
|
|
|
|
|
This does not include additional bits required in the local caches. For the doubly linked list (the SCI), the number of memory directory bits needed to maintain the protocol is, to a first approximation, the same as the singly linked case, but the local cache pointer bits are doubled. |
|
|
|
|
|
|
|
|
8.11.2 Invalidate Protocols |
|
|
|
|
|
|
|
|
The invalidate-based protocols maintain consistency by invalidating the entry for a shared line in all processors that are using the line except, of course, for the processor that is writing. The invalidate protocols use the directory to establish which processors have a copy of the line so that these invalidate requests can be forwarded to the appropriate processors. After the invalidate transaction, only the writing processor will have a cache with a copy of the line. |
|
|
|
|
|
|
|
|
In the centralized directory invalidate protocol (CD-INV), the directory specifies each processor that has a copy of the line. Invalidate signals and a pointer to the requesting processor can be forwarded (in parallel, if the implementation allows) to all of the processors that have a copy of the line (processors 3 and 1 in Figure 8.32). Each invalidated cache acknowledges invalidation so that a completion of the write can be established. After the write and the subsequent invalidations, the directory indicates that the writing cache has an exclusive read-write copy of the line. Because of the |
|
|
|
|
|
