This problem considers a simple model for a computer cache memory system. This model is as illustrated in Fig. 10. The computer uses two types of memory: large, slow mass storage and small, fast cache memory. When the CPU executes an instruction, it checks to see if the required data is in the cache. If so, it pulls it out of the cache; if not it pulls the data from mass storage. After the instruction is executed, the data used is written into the cache. The cache holds N of these data items - i.e., the N most recently used by the CPU. mass storage (hard drive) Cache CPU 1 2 3 ... Figure 10: Simple model for a memory cache system. The cache is a FIFO (first-in, first out) memory. That is, the oldest item is removed to make room for the newest item. Thus, a specific data item leaves the cache in one of two ways: it is pulled by the cache for use or it is pushed out of the cache after N instruction cycles i.e., in this latter case, we say that the data item "aged-out". (a) Let X (u) model the time, in instruction cycles from it being used, until a given data item is removed from the cache for the first time. Specifically, X (u) = 1 corresponds to the data being used in the next cycle after it was first used, X(u) = N corresponds to the data being pulled by the CPU when it is the oldest item in the cache, and X (u) = N +1 corresponds to the data item aging out. The probability that the CPU needs the given data item is p for each cycle and is modeled as independent over cycles. Determine the probability mass function for X (u). Sketch this pmf for the case of p= 0.25 and N = 4. (b) The cache hit probability Phit is the probability that the given data item is in the cache when the CPU needs it - i.e., the probability that the given data item has not aged after being written to the cache before the CPU needs it. For a minimum desired hit probability Phit.min and a given p, find the minimum cache size Nmin so that Phit > Phit, min. For the specific case of p= 10-4 and Phit,min = 0.8, what is Nmin (numerical)? (c) What is the mean of X (u) from part (a)? (d) If the cache is designed to satisfy the Phit > Phit, min condition in (c) - i.e., N = Nmin, what is the mean as a function of p, and Phit,min? Specifically, provide a simple approx- imation of the mean in terms of Phit.min and p. For the specific case of p = 10-4 and Phit, min = 0.8, and N = Nmin what is the mean (numerical)? This problem considers a simple model for a computer cache memory system. This model is as illustrated in Fig. 10. The computer uses two types of memory: large, slow mass storage and small, fast cache memory. When the CPU executes an instruction, it checks to see if the required data is in the cache. If so, it pulls it out of the cache; if not it pulls the data from mass storage. After the instruction is executed, the data used is written into the cache. The cache holds N of these data items - i.e., the N most recently used by the CPU. mass storage (hard drive) Cache CPU 1 2 3 ... Figure 10: Simple model for a memory cache system. The cache is a FIFO (first-in, first out) memory. That is, the oldest item is removed to make room for the newest item. Thus, a specific data item leaves the cache in one of two ways: it is pulled by the cache for use or it is pushed out of the cache after N instruction cycles i.e., in this latter case, we say that the data item "aged-out". (a) Let X (u) model the time, in instruction cycles from it being used, until a given data item is removed from the cache for the first time. Specifically, X (u) = 1 corresponds to the data being used in the next cycle after it was first used, X(u) = N corresponds to the data being pulled by the CPU when it is the oldest item in the cache, and X (u) = N +1 corresponds to the data item aging out. The probability that the CPU needs the given data item is p for each cycle and is modeled as independent over cycles. Determine the probability mass function for X (u). Sketch this pmf for the case of p= 0.25 and N = 4. (b) The cache hit probability Phit is the probability that the given data item is in the cache when the CPU needs it - i.e., the probability that the given data item has not aged after being written to the cache before the CPU needs it. For a minimum desired hit probability Phit.min and a given p, find the minimum cache size Nmin so that Phit > Phit, min. For the specific case of p= 10-4 and Phit,min = 0.8, what is Nmin (numerical)? (c) What is the mean of X (u) from part (a)? (d) If the cache is designed to satisfy the Phit > Phit, min condition in (c) - i.e., N = Nmin, what is the mean as a function of p, and Phit,min? Specifically, provide a simple approx- imation of the mean in terms of Phit.min and p. For the specific case of p = 10-4 and Phit, min = 0.8, and N = Nmin what is the mean (numerical)
