Cache: 1. Consider the following sequence of address references given as decimal
ID: 3711544 • Letter: C
Question
Cache:
1. Consider the following sequence of address references given as decimal word references:
0, 1, 8, 1, 0, 1, 2, 8, 2, 1, 0, 1, 2, 3, 8, 9, 10, 11, 12, 0
Assume that each of the following caches uses an LRU replacement scheme, and that each cache is initially empty. Each cache holds a total of eight words, and the binary address of each reference consists of five bits (e.g., 01100).
a) Assuming a direct-mapped cache with 8 one-word blocks, label each reference in the list as a hit (H) or miss (m) and show the final contents of the cache (including the valid bit, tag, and data at each cache index).
b) Show the hits, misses, and final cache contents for a direct-mapped cache with 2 four-word blocks.
c) Show the hits, misses, and final cache contents for a 2-way set-associative cache with 4 sets of two one-word blocks. Assume that the cache is initially empty.
d) Based entirely upon the results you reported in parts (a), (b), and (c) of this question, which of these three cache utilization schemes is best? Explain your answer.
Explanation / Answer
a) Number of blocks = 23
As each block contains 1 word therefore offset field contains 0 bit.
As there are 23 blocks so index field contains 3 bits.
As address size is 5 bits so, rest 2 bits are tag bits.
References:
00 | 000 = m
00 | 001 = m
01 | 000 = m [ 000 line replaced]
00 | 001 = H
00 | 000 = m[ 000 line replaced]
00 | 001 = H
00 | 010 = m
01 | 000 = m[ 000 line replaced]
00 | 010 = H
00 | 001 = H
00 | 000 = m [000 line replaced]
00 | 001 = H
00 | 010 = H
00 | 011 = m
01 | 000 = m [ 000 line replaced]
01 | 001 = m[ 001 line replaced]
01 | 010 = m[ 010 line replaced]
01 | 011 = m[ 011 line replaced]
01 | 100 = m
00 | 000 = m[ 000 line replaced]
b) size of block = 22 words
therefore offset field contains 2 bits.
Number of blocks = 2
therefore index field contains 1 bit
rest 2 bits are TAG.
00 | 0 | 00 = m
00 | 0 | 01 = H
01 | 0 | 00 = m [ 0 line replaced]
00 | 0 | 01 = m [ 0 line replaced]
00 | 0 | 00 = H
00 | 0 | 01 = H
00 | 0 | 10 = H
01 | 0 | 00 = m[ 0 line replaced]
00 | 0 | 10 = m[ 0 line replaced]
00 | 0 | 01 = H
00 | 0 | 00 = H
00 | 0 | 01 = H
00 | 0 | 10 = H
00 | 0 | 11 = H
01 | 0 | 00 = m [ 0 line replaced]
01 | 0 | 01 = H
01 | 0 | 10 = H
01 | 0 | 11 = H
01 | 1 | 00 = m
00 | 0 | 00 = m[ 0 line replaced]
c) As one word block so offset field will contain 0 bits.
As 4 sets are there so index bit will be 2 bits
rest 3 bits will be tag.
000 | 00 = m
000 | 01 = m
010 | 00 = m
000 | 01 = H
000 | 00 = H
000 | 01 = H
000 | 10 = m
010 | 00 = H
000 | 10 = H
000 | 01 = H
000 | 00 = H
000 | 01 = H
000 | 10 = H
000 | 11 = m
010 | 00 = H
010 | 01 = m
010 | 10 = m
010 | 11 = m
011 | 00 = m[replaced ]
000 | 00 = H
D) Lat scheme of set associativity is best because it has more number of hits.