Page 36 - DCAP104_EXPOSURE_TO_COMPUTER_DISCPLINES

Unit 2: Data Processing

When the cache client (a CPU, web browser, operating system) needs to access a datum presumed Notes
to exist in the backing store, it first checks the cache. If an entry can be found with a tag matching
that of the desired datum, the datum in the entry is used instead. This situation is known as a
cache hit. So, for example, a web browser program might check its local cache on disk to see if
it has a local copy of the contents of a web page at a particular URL. In this example, the URL is
the tag, and the contents of the web page is the datum. The percentage of accesses that result in
cache hits is known as the hit rate or hit ratio of the cache.
The alternative situation, when the cache is consulted and found not to contain a datum with
the desired tag, has become known as a cache miss. The previously uncached datum fetched
from the backing store during miss handling is usually copied into the cache, ready for the
next access.

During a cache miss, the CPU usually ejects some other entry in order to make room for the
previously uncached datum. The heuristic used to select the entry to eject is known as the
replacement policy. One popular replacement policy, “least recently used” (LRU), replaces the
least recently used entry. More efficient caches compute use frequency against the size of the
stored contents, as well as the latencies and throughputs for both the cache and the backing
store. While this works well for larger amounts of data, long latencies and slow throughputs,
such as experienced with a hard drive and the Internet, it is not efficient for use with a CPU
cache. When a system writes a datum to the cache, it must at some point write that datum
to the backing store as well. The timing of this write is controlled by what is known as the
write policy.
In a write-through cache, every write to the cache causes a synchronous write to the backing
store.
Alternatively, in a write-back (or write-behind) cache, writes are not immediately mirrored to
the store. Instead, the cache tracks which of its locations have been written over and marks these
locations as dirty. The data in these locations are written back to the backing store when those
data are evicted from the cache, an effect referred to as a lazy write. For this reason, a read miss
in a write-back cache (which requires a block to be replaced by another) will often require two
memory accesses to service: one to retrieve the needed datum, and one to write replaced data
from the cache to the store.
Other policies may also trigger data write-back. The client may make many changes to a datum
in the cache, and then explicitly notify the cache to write back the datum.

No-write allocation (a.k.a. write-no-allocate) is a cache policy which caches only processor reads,
i.e. on a write-miss:
• Datum is written directly to memory,
• Datum at the missed-write location is not added to cache.
This avoids the need for write-back or write-through when the old value of the datum was absent
from the cache prior to the write.
Entities other than the cache may change the data in the backing store, in which case the
copy in the cache may become out-of-date or stale. Alternatively, when the client updates
the data in the cache, copies of those data in other caches will become stale. Communication
protocols between the cache managers which keep the data consistent are known as coherency
protocols.
2.6.2 Applications

2.6.2.1 CPU Cache
Small memories on or close to the CPU can operate faster than the much larger main memory.
Most CPUs since the 1980s have used one or more caches, and modern high-end embedded,

LOVELY PROFESSIONAL UNIVERSITY 29