Page 179 -

4.7 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 149

4.15 Consider the following code:
for (i = 0; i 6 20; i )
for (j = 0; j 6 10; j )
a[i] = a[i]* j
a. Give one example of the spatial locality in the code.
b. Give one example of the temporal locality in the code.
4.16 Generalize Equations (4.2) and (4.3), in Appendix 4A, to N-level memory hierarchies.
4.17 A computer system contains a main memory of 32K 16-bit words. It also has a 4K-
word cache divided into four-line sets with 64 words per line.Assume that the cache is
initially empty. The processor fetches words from locations 0, 1, 2, . . ., 4351 in that
order. It then repeats this fetch sequence nine more times.The cache is 10 times faster
than main memory. Estimate the improvement resulting from the use of the cache.
Assume an LRU policy for block replacement.
4.18 Consider a cache of 4 lines of 16 bytes each. Main memory is divided into blocks of
16 bytes each. That is, block 0 has bytes with addresses 0 through 15, and so on. Now
consider a program that accesses memory in the following sequence of addresses:
Once: 63 through 70
Loop ten times: 15 through 32; 80 through 95
a. Suppose the cache is organized as direct mapped. Memory blocks 0, 4, and so on are
assigned to line 1; blocks 1, 5, and so on to line 2; and so on. Compute the hit ratio.
b. Suppose the cache is organized as two-way set associative, with two sets of two
lines each. Even-numbered blocks are assigned to set 0 and odd-numbered blocks
are assigned to set 1. Compute the hit ratio for the two-way set-associative cache
using the least recently used replacement scheme.
4.19. Consider a memory system with the following parameters:
-4
T c = 100 ns C c = 10 $/bit
-5
T m = 1200 ns C m = 10 $/bit
a. What is the cost of 1 Mbyte of main memory?
b. What is the cost of 1 Mbyte of main memory using cache memory technology?
c. If the effective access time is 10% greater than the cache access time, what is the
hit ratio H?
4.20 a. Consider an L1 cache with an access time of 1 ns and a hit ratio of H = 0.95. Sup-
pose that we can change the cache design (size of cache, cache organization) such
that we increase H to 0.97, but increase access time to 1.5 ns. What conditions
must be met for this change to result in improved performance?
b. Explain why this result makes intuitive sense.
4.21 Consider a single-level cache with an access time of 2.5 ns, a line size of 64 bytes, and a
hit ratio of H = 0.95. Main memory uses a block transfer capability that has a first-
word (4 bytes) access time of 50 ns and an access time of 5 ns for each word thereafter.
a. What is the access time when there is a cache miss? Assume that the cache waits
until the line has been fetched from main memory and then re-executes for a hit.
b. Suppose that increasing the line size to 128 bytes increases the H to 0.97. Does this
reduce the average memory access time?
4.22 A computer has a cache, main memory, and a disk used for virtual memory. If a refer-
enced word is in the cache, 20 ns are required to access it. If it is in main memory but
not in the cache, 60 ns are needed to load it into the cache, and then the reference is
started again. If the word is not in main memory, 12 ms are required to fetch the word
from disk, followed by 60 ns to copy it to the cache, and then the reference is started
again.The cache hit ratio is 0.9 and the main memory hit ratio is 0.6.What is the aver-
age time in nanoseconds required to access a referenced word on this system?