1. Assume that 8-bit byte address is used and there is a cache with two-word blo
ID: 3602410 • Letter: 1
Question
1. Assume that 8-bit byte address is used and there is a cache with two-word blocks
and a total size of 16 words. (Hint: 1 word = 4 bytes)
(a) If the cache is direct-mapped cache,
i. Show the number of bits in each field of the address subdivision:
ii. How many total bits are required for each of the caches, including data,
tag, and valid fields?
iii. Give a series of address references as word addresses: 13, 26, 15, 30, 17,
34, 15 and 30. For each of the caches, show the hit/miss of each
reference and the cache contents after the reference. Initially, the
contents of the cache are shown as follows:
(b) Repeat (a) if the cache is 4-way set-associative. Assume that LRU
(Least-Recently Used) replacement is applied. Initially, the contents of the
cache are shown as follows and the block in the smaller way is referenced
earlier:
Tag Index Block offse Byte offsetExplanation / Answer
Answer for (a)
Since the address is byte-addressable, we need to count in terms of bytes, not words.
(i)
No of bytes in a block = 2 X 4 = 8 = 23
So no. of bits for byte offset = log2(No of bytes in a block) = log2(23) = 3
Since it is a direct-mapped cache, there is only one block at a given index. So no. of bits for block offset = log2(No of blocks at a given index) = log2(20) = 0.
Number of blocks = 8 = 23
So no. of bits for index = log2(Number of blocks) = log2(23) = 3.
Length of address = 8 bits.
No of bits for tag = Total address length - (Bits for index + bits for block offset + bits for byte offset) = 8 - (3 + 0 + 3) = 2 bits
(ii)
In a direct mapped cache, for each block the following information needs to be stored: Tag, valid bit, data.
So total bits per block = 2 bits + 1 bit + 8 bytes = 3 bits + 64 bits = 67 bits
Total bits for the cache = 67 bits X 8 = 536 bits.
(iii)
The references are for word addresses. Since each word contains 4 (=22) bytes, the word address denotes the first 6 bits of the byte address (2 tag + 3 index + 1 word offset within block).
So 3rd to 5th bits denote the index
The binary values are:
Address Index Cache hit/miss New cache content in case of miss, and valid bit if changed
13 001101 6 miss Block 6 = M[12,13], Tag = 00, V= Y
26 011010 5 miss Block 5 = M[26,27], Tag = 01, V =Y
15 001111 7 hit
30 011110 7 miss Block 7 = M[30,31], Tag = 01
17 010001 0 miss Block 0 = M[16,17], Tag = 01
34 100010 1 miss Block 1 = M[34,35], Tag = 10
15 001111 7 miss Block 7 = M[14,15], Tag = 00
30 011110 7 miss Block 7 = M[30,31], Tag = 01
Answer (b)
(i) The byte offset will remain as in case a since the block size is the same. No. of bits for byte offset = 3.
Since it is 4-way associative, there is no block offset associated with a block.
No. of bits for block offset = 0
No. of sets = 2 = 21
No. of bits for index = log2(No of sets) = 1
No. of bits for tag = Total bits for address - (Bits for byte offset, block offset, index) = 8 - (3 + 0 + 1) = 4 bits.
(ii)
For each block, apart from the data, the tag and valid bits have to be stored.
No. of bits for one block = 4 bits + 1 bit + 8 bytes = 5 bits + 64 bits = 69 bits.
Total number of bits in the cache = 69 bits X 8 = 552 bits.
(iii)
In this case, the first four bits give the tag, while the fifth gives the index.
Address Index Cache hit/miss New cache content in case of miss, and way changed
13 001101 0 miss Block 0, Way 3 = M[12,13], Tag = 0011, V= Y
26 011010 1 miss Block 1, Way 2 = M[26,27], Tag = 0110, V =Y
15 001111 1 hit
30 011110 1 miss Block 1, Way 3 = M[30,31], Tag = 0111
17 010001 0 miss Block 0, Way 0 = M[16,17], Tag = 0100
34 100010 1 miss Block 1, Way 0 = M[34,35], Tag = 1000
15 001111 1 miss Block 1, Way 2 = M[14,15], Tag = 0011
30 011110 1 miss Block 1, Way 1 = M[30,31], Tag = 0111
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.