Off-line caching Modern computers use a cache to store a

Chapter 16, Problem 16-5

(choose chapter or problem)

Off-line caching Modern computers use a cache to store a small amount of data in a fast memory. Even though a program may access large amounts of data, by storing a small subset of the main memory in the cachea small but faster memoryoverall access time can greatly decrease. When a computer program executes, it makes a sequence hr1; r2;:::;rni of n memory requests, where each request is for a particular data element. For example, a program that accesses 4 distinct elements fa; b; c; dg might make the sequence of requests hd; b; d; b; d; a; c; d; b; a; c; bi. Let k be the size of the cache. When the cache contains k elements and the program requests the .k C 1/st element, the system must decide, for this and each subsequent request, which k elements to keep in the cache. More precisely, for each request ri , the cache-management algorithm checks whether element ri is already in the cache. If it is, then we have a cache hit; otherwise, we have a cache miss. Upon a cache miss, the system retrieves ri from the main memory, and the cache-management algorithm must decide whether to keep ri in the cache. If it decides to keep ri and the cache already holds k elements, then it must evict one element to make room for ri. The cache-management algorithm evicts data with the goal of minimizing the number of cache misses over the entire sequence of requests. Typically, caching is an on-line problem. That is, we have to make decisions about which data to keep in the cache without knowing the future requests. Here, however, we consider the off-line version of this problem, in which we are given in advance the entire sequence of n requests and the cache size k, and we wish to minimize the total number of cache misses. We can solve this off-line problem by a greedy strategy called furthest-in-future, which chooses to evict the item in the cache whose next access in the request sequence comes furthest in the future. a. Write pseudocode for a cache manager that uses the furthest-in-future strategy. The input should be a sequence hr1; r2;:::;rni of requests and a cache size k, and the output should be a sequence of decisions about which data element (if any) to evict upon each request. What is the running time of your algorithm? b. Show that the off-line caching problem exhibits optimal substructure. c. Prove that furthest-in-future produces the minimum possible number of cache misses.