Page 166 -

4.3 / ELEMENTS OF CACHE DESIGN 137

of this technique is that it generates substantial memory traffic and may create a
bottleneck. An alternative technique, known as write back, minimizes memory
writes.With write back, updates are made only in the cache.When an update occurs,
a dirty bit, or use bit, associated with the line is set.Then, when a block is replaced, it
is written back to main memory if and only if the dirty bit is set. The problem with
write back is that portions of main memory are invalid, and hence accesses by I/O
modules can be allowed only through the cache. This makes for complex circuitry
and a potential bottleneck. Experience has shown that the percentage of memory
references that are writes is on the order of 15% [SMIT82]. However, for HPC ap-
plications, this number may approach 33% (vector-vector multiplication) and can go
as high as 50% (matrix transposition).

Example 4.3 Consider a cache with a line size of 32 bytes and a main memory that re-
quires 30 ns to transfer a 4-byte word. For any line that is written at least once before
being swapped out of the cache, what is the average number of times that the line must be
written before being swapped out for a write-back cache to be more efficient that a write-
through cache?
For the write-back case, each dirty line is written back once, at swap-out time, taking
8 * 30 = 240 ns. For the write-through case, each update of the line requires that one
word be written out to main memory, taking 30 ns.Therefore, if the average line that gets
written at least once gets written more than 8 times before swap out, then write back is
more efficient.

In a bus organization in which more than one device (typically a processor)
has a cache and main memory is shared, a new problem is introduced. If data in one
cache are altered, this invalidates not only the corresponding word in main memory,
but also that same word in other caches (if any other cache happens to have that
same word). Even if a write-through policy is used, the other caches may contain in-
valid data.A system that prevents this problem is said to maintain cache coherency.
Possible approaches to cache coherency include the following:
• Bus watching with write through: Each cache controller monitors the address
lines to detect write operations to memory by other bus masters. If another
master writes to a location in shared memory that also resides in the cache
memory, the cache controller invalidates that cache entry. This strategy de-
pends on the use of a write-through policy by all cache controllers.
• Hardware transparency: Additional hardware is used to ensure that all up-
dates to main memory via cache are reflected in all caches.Thus, if one proces-
sor modifies a word in its cache, this update is written to main memory. In
addition, any matching words in other caches are similarly updated.
• Noncacheable memory: Only a portion of main memory is shared by more
than one processor, and this is designated as noncacheable. In such a system,
all accesses to shared memory are cache misses, because the shared memory is
never copied into the cache.The noncacheable memory can be identified using
chip-select logic or high-address bits.