Review of Memory Hierarchy - Computer Architecture: A Quantitative Approach - page 613

a. [20] <B.3> What is the asymptotic instruction miss rate for a 64-byte loop with a large
number of iterations?
b. [20] <B.3> Repeat part (a) for loop sizes 192 bytes and 320 bytes.
c. [15] <B.3> If the cache replacement policy is changed to most recently used (MRU) (re-
place the most recently accessed cache line), which of the three above cases (64-, 192-,
or 320-byte loops) would benefit from this policy?
d. [25] <B.3> Suggest additional replacement policies that might outperform LRU.
B.9 [20] <B.3> Increasing a cache's associativity (with all other parameters kept constant), stat-
istically reduces the miss rate. However, there can be pathological cases where increasing
a cache's associativity would increase the miss rate for a particular workload. Consider the
case of direct mapped compared to a two-way set associative cache of equal size. Assume
that the set associative cache uses the LRU replacement policy. To simplify, assume that the
block size is one word. Now construct a trace of word accesses that would produce more
misses in the two-way associative cache. (Hint: Focus on constructing a trace of accesses
that are exclusively directed to a single set of the two-way set associative cache, such that
the same trace would exclusively access two blocks in the direct-mapped cache.)
B.10 [10/10/15] <B.3> Consider a two-level memory hierarchy made of L1 and L2 data caches.
Assume that both caches use write-back policy on write hit and both have the same block
size. List the actions taken in response to the following events:
a. [10] <B.3> An L1 cache miss when the caches are organized in an inclusive hierarchy.
b. [10] <B.3> An L1 cache miss when the caches are organized in an exclusive hierarchy.
c. [15] <B.3> In both parts (a) and (b), consider the possibility that the evicted line might
be clean or dirty.
B.11 [15/20] <B.2, B.3> Excluding some instructions from entering the cache can reduce con-
lict misses.
a. [15] <B.3> Sketch a program hierarchy where parts of the program would be beter
excluded from entering the instruction cache. (Hint: Consider a program with code
blocks that are placed in deeper loop nests than other blocks.)
b. [20] <B.2, B.3> Suggest software or hardware techniques to enforce exclusion of certain
blocks from the instruction cache.
B.12 [15] <B.4> A program is running on a computer with a four-entry fully associative (mi-
cro) translation lookaside buffer (TLB):

VP# PP# Entry valid

5 30 1

7 1 0

10 10 1

15 25 1

The following is a trace of virtual page numbers accessed by a program. For each access indic-
ate whether it produces a TLB hit/miss and, if it accesses the page table, whether it produces a
page hit or fault. Put an X under the page table column if it is not accessed.