The following memory addresses are used consecutively by a running program (from
ID: 3695747 • Letter: T
Question
The following memory addresses are used consecutively by a running program (from left to right, shown in decimal). Note that the followings are memory address not block number: 500, 40, 360, 116, 836, 224, 1348, 18, 440, 100, 1024, 44, 168, 40, 104 In each of the following cache structures, compute the number of hits, misses and the final values stored in each cache location (show finally which block of memory is in each cache block). Each word is 4-bytes and the memory size is 8Kbyte
(a) Direct-mapped cache with 16-word blocks and a total size of cache is 128 words of data
(b) 2-way set associative cache with 16-word blocks and a total size of cache is 128 words of data. (LRU replacement)
Explanation / Answer
Block size = 64 bytes = 26 bytes = 26 words (since 1 word = 1 byte) Therefore, Number of bits in the Word field = 6 Cache size = 2K-byte = 211 bytes Number of cache blocks = Cache size / Block size = 211/26 = 25 Therefore, Number of bits in the Block field = 5 Total number of address bits = 16 Therefore, Number of bits in the Tag field = 16 - 6 - 5 = 5 For a given 16-bit address, the 5 most significant bits, represent the Tag, the next 5 bits represent the Block, and the 6 least significant bits represent the Word. (b) The cache is initially empty. Therefore, all the cache blocks are invalid. Access # 1: Address = (128)10 = (0000000010000000)2 (Note: Address is shown as a 16-bit number, because the computer uses 16-bit addresses) For this address, Tag = 00000, Block = 00010, Word = 000000 Since the cache is empty before this access, this will be a cache miss After this access, Tag field for cache block 00010 is set to 00000 Access # 2: Address = (144)10 = (0000000010010000)2 For this address, Tag = 00000, Block = 00010, Word = 010000 Since tag field for cache block 00010 is 00000 before this access, this will be a cache hit (because address tag = block tag) Access # 3: Address = (2176)10 = (0000100010000000)2 For this address, Tag = 00001, Block = 00010, Word = 000000 Since tag field for cache block 00010 is 00000 before this access, this will be a cache miss (address tag block tag) After this access, Tag field for cache block 00010 is set to 00001 Access # 4: Address = (2180)10 = (0000100010000100)2 For this address, Tag = 00001, Block = 00010, Word = 000100 Since tag field for cache block 00010 is 00001 before this access, this will be a cache hit (address tag = block tag) Access # 5: Address = (128)10 = (0000000010000000)2 For this address, Tag = 00000, Block = 00010, Word = 000000 Since tag field for cache block 00010 is 00001 before this access, this will be a cache miss (address tag block tag) After this access, Tag field for cache block 00010 is set to 00000 Access # 6: Address = (2176)10 = (0000100010000000)2 For this address, Tag = 00001, Block = 00010, Word = 000000 Since tag field for cache block 00010 is 00001 before this access, this will be a cache miss (address tag block tag) After this access, Tag field for cache block 00010 is set to 00001 Cache hit rate = Number of hits / Number of accesses = 2/6 = 0.333Block size = 64 bytes = 26
bytes = 26
words (since 1 word = 1 byte)
Therefore, Number of bits in the Word field = 6
Cache size = 2K-byte = 211 bytes
Number of cache blocks = Cache size / Block size = 211/26
= 25
Therefore, Number of bits in the Block field = 5
Total number of address bits = 16
Therefore, Number of bits in the Tag field = 16 - 6 - 5 = 5
For a given 16-bit address, the 5 most significant bits, represent the Tag, the next 5 bits represent
the Block, and the 6 least significant bits represent the Word.
(b) The cache is initially empty. Therefore, all the cache blocks are invalid.
Access # 1:
Address = (128)10 = (0000000010000000)2
(Note: Address is shown as a 16-bit number, because the computer uses 16-bit addresses)
For this address, Tag = 00000, Block = 00010, Word = 000000
Since the cache is empty before this access, this will be a cache miss
After this access, Tag field for cache block 00010 is set to 00000
Access # 2:
Address = (144)10 = (0000000010010000)2
For this address, Tag = 00000, Block = 00010, Word = 010000
Since tag field for cache block 00010 is 00000 before this access, this will be a cache hit (because
address tag = block tag)
Access # 3:
Address = (2176)10 = (0000100010000000)2
For this address, Tag = 00001, Block = 00010, Word = 000000
Since tag field for cache block 00010 is 00000 before this access, this will be a cache miss
(address tag block tag)
After this access, Tag field for cache block 00010 is set to 00001
Access # 4:
Address = (2180)10 = (0000100010000100)2
For this address, Tag = 00001, Block = 00010, Word = 000100
Since tag field for cache block 00010 is 00001 before this access, this will be a cache hit (address
tag = block tag)
Access # 5:
Address = (128)10 = (0000000010000000)2
For this address, Tag = 00000, Block = 00010, Word = 000000
Since tag field for cache block 00010 is 00001 before this access, this will be a cache miss
(address tag block tag)
After this access, Tag field for cache block 00010 is set to 00000
Access # 6:
Address = (2176)10 = (0000100010000000)2
For this address, Tag = 00001, Block = 00010, Word = 000000
Since tag field for cache block 00010 is 00001 before this access, this will be a cache miss
(address tag block tag)
After this access, Tag field for cache block 00010 is set to 00001
Cache hit rate = Number of hits / Number of accesses = 2/6 = 0.333
Repeat Problem # 1, if the cache is organized as a 2-way set-associative cache that uses the LRU
replacement algorithm.
Solution
(a) Block size = 64 bytes = 26 bytes = 26 words
Therefore, Number of bits in the Word field = 6
Cache size = 2K-byte = 211 bytes Number of cache blocks per set = 2Number of sets = Cache size / (Block size * Number of blocks per set) = 211/(26
* 2) = 24
Therefore, Number of bits in the Set field = 4
Total number of address bits = 16
Therefore, Number of bits in the Tag field = 16 - 6 - 4 = 6
(b) The cache is initially empty. Therefore, all the cache blocks are invalid.
Access # 1:
Address = (128)10 = (0000000010000000)2
For this address, Tag = 000000, Set = 0010, Word = 000000
Since the cache is empty before this access, this will be a cache miss
After this access, Tag field for the first block in set 0010 is set to 000000
Access # 2:
Address = (144)10 = (0000000010010000)2
For this address, Tag = 000000, Set = 0010, Word = 010000
The tag field for this address matches the tag field for the first block in set 0010. Therefore, this
access will be a cache hit.
Access # 3:
Address = (2176)10 = (0000100010000000)2
For this address, Tag = 000010, Set= 0010, Word = 000000
The tag field for this address does not match the tag field for the first block in set 0010. The
second block in set 0010 is empty. Therefore, this access will be a cache miss.
After this access, Tag field for the second block in set 0010 is set to 000010
Access # 4:
Address = (2180)10 = (0000100010000100)2
For this address, Tag = 000010, Set = 0010, Word = 000100
The tag field for this address matches the tag field for the second block in set 0010. Therefore,
this access will be a cache hit.
Access # 5:
Address = (128)10 = (0000000010000000)2
For this address, Tag = 000000, Set = 0010, Word = 000000
The tag field for this address matches the tag field for the first block in set 0010. Therefore, this
access will be a cache hit.
Access # 6:
Address = (2176)10 = (0000100010000000)2
For this address, Tag = 000010, Set = 0010, Word = 000000
The tag field for this address matches the tag field for the second block in set 0010. Therefore,
this access will be a cache hit.
Cache hit rate = Number of hits / Number of accesses = 4/6 = 0.666
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.