ABSTRACT
Caching is an important technique in the computing world. Most of us are familiar with cache used for a single processor computer, as illustrated in Figure 15.1. In a typical single processor system, a cache is a small fast memory for holding frequently used data. In fact, all the different types of memories in a computer system, such as disk, main memory, and cache, can be viewed as a part of a memory hierarchy in which the closer a memory unit is to the processor the smaller is its capacity and access time. The main problem in such a single processor computing environment with a memory hierarchy is to determine how to reduce memory read/write latency in the presence of memory hierarchy? To achieve this, the focus is to decide what data to cache (to copy from a farther memory unit to a closer memory unit) so that the cache (memory unit closer to the processor) can satisfy as many memory requests as possible, effectively achieving average access time close to that of the fast memory unit at the effective price of the large memory unit. Therefore, the problem for cache management is to predict what data items will most probably be used in the future and either copy them to a memory unit closer to the processor when they are accessed for the first time (i.e., on a cache miss) or to prefetch them well in advance so that they are available in the cache memory when they are needed. Many cache replacement algorithms such Least Recently Used (LRU) and prefetching algorithms have been developed to solve this problem [Silberschatz].
