Please complete the following problems, preparing your submission in .pdf format and uploading to Carmen by 11:59pm on the stated due date. Be sure (especially if scanning handwritten work) that your submitted files are clear and legible.
1. [20 pts.] Given a cache with parameters little b = 8, little s = 8 and E = 4. Let:
@x[256] = AAAA0000 using the code segment: for i = 0 to 255
@y[256] = AABB0000 res1 = x[ i ] * y[ i ]
@a[512] = AAAA8000 for j = 0 to 1
@b[512] = AABB8000 res2 = a[i*2+j] + b[i*2+j]
|element| = 8
res1 and res2 are in registers.
a.) Fully describe the cache in terms of the cache parameters discussed in class.
b.) What is the hit rate for each of x, y, a and b?
c.) What is the overall hit rate?
d.) What are the cache contents after 1 iteration of the "i" loop?
e.) What are the cache contents after the completion of the "i" loop?
[5 pts.] Many caches implement an LRU or LFU eviction policy by adding eviction bits to the individual cache lines. Let us say that, instead, we were to associate the eviction bits with each set. Consider such a cache which is 8-way set associative and has 3 eviction bits per set. Write a potential eviction policy that would work on such a configuration. Describe circumstances, in terms of address access patterns, where your policy would perform well and also circumstances where it would perform poorly.
[5 pts.] Consider an LRU set-associative cache. Beginning with an initial scan to determine that a cache miss has occurred, how many times would the cache lines in the affected set be scanned in order to successfully replace a cache line requiring eviction? What information is determined by each scan? What specific cache line content is inspected during each scan?
[5 pts.] In general terms, describe an address access pattern that would work well with an LRU cache. Describe an address access pattern that would work better in a similar cache which implements LFU.
[10 pts.] Given an LRU cache with parameters little b = 8, little s = 0 and E = 256.
@x[8192] = AAAA0000 using the code segment: for i = 0 to 8191
Let: @y[8192] = AAAB0000 res1 = x[ i ] + y[ i ]
|element| = 8
res1 is in a register.
a.) Fully describe the cache in terms of the cache parameters discussed in class.
b.) What is the hit rate for each of x, and y?
c.) What is the overall hit rate?
d.) What are the cache contents after the completion of the "i" loop?
6. [5 pts.] Which of the following cache hierarchies will provide better AMAT?
hierarchy
hit time
hit
hierarchy
hit time
hit
A
(cycles)
rate
B
(cycles)
rate
L1$
2
25%
L1$
2
50%
L2$
10
80%
L2$
5
65%
L3$
80
95%
L3$
20
80%
main memory
500
main memory
500
The Ohio State University
