The following memory addresses are used consecutively by a running program (from
ID: 3572492 • 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:
520, 400, 380, 540, 816, 204, 1348, 200, 440, 140, 1064, 44, 196, 404, 180
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 32-word blocks and a total size of cache is 128 words of data
(b) 2-way set associative cache with 32-word blocks and a total size of cache is 128 words of data. (LRU replacement)
(c) For (a) and (b) find the size of the cache required to hold the data (as mentioned in 2.a and 2.b above the cache should hold 128 words of data).
Explanation / Answer
(a)
The size of each block is 32 size of the word and cache has 128 words.
Therefore, there are 4 blocks of cache.
Each memory corresponds to one word.
Since, each block consists of 32 memories of word which are brought to the 32-size block.
The last 5 bits are represented the bits of offset.
The indices of the memory are represented by the 6th and the 7th bit.
For address 520, the block index would be 00.
Hence, belongs to the block 0. The cache tags are 100, -, -, -.
Therefore, miss = 1 and hit = 0
For address 400, the block index would be 00.
The tag is not 11. The cache tags are 11, -, -, -.
Therefore, miss = 2 and hit = 0
For address 380, the block index would be 11.
The cache tags are 11, -, -, 10.
Therefore, miss = 3 and hit = 0
For address 540, the block index would be 00.
The tag is not 11. Therefore, replacement.
The cache tags are 11, -, -, 10.
Therefore, miss = 4 and hit = 0
For address 816, the block index would be 01.
The block is an empty block. The cache tags are 100, 110, -, 10.
Therefore, miss = 5 and hit = 0
For address 204, the block index would be 10.
The block is an empty block. The cache tags are 100, 110, 1, 10.
Therefore, miss = 6 and hit = 0
For address 1348, the block index would be 10.
The tag is not equal to 1. The replacement of block occurs.
The cache tags are 100, 110, 1010, 10.
Therefore, miss = 7 and hit = 0
For address 200, the block index would be 10.
The tag is not equal to 1010. The replacement of block occurs.
The cache tags are 100, 110, 1, 10.
Therefore, miss = 8 and hit = 0
For address 440, the block index would be 01.
The tag is not equal to 110. The replacement of block occurs.
The cache tags are 100, 11, 1, 10.
Therefore, miss = 9 and hit = 0
For address 140, the block index would be 00.
The tag is not equal to 100. The replacement of block occurs.
The cache tags are 1, 11, 1, 10.
Therefore, miss = 10 and hit = 0
For address 1064, the block index would be 01.
The tag is not equal to 11. The replacement of block occurs.
The cache tags are 1, 1000, 1, 10.
Therefore, miss = 11 and hit = 0
For address 44, the block index would be 01.
The tag is not equal to 1000. The replacement of block occurs.
The cache tags are 1, 0, 1, 10.
Therefore, miss = 12 and hit = 0
For address 196, the block index would be 10.
The tag is equal-equal to 1. Hit occurs.
The cache tags are 1, 0, 1, 10.
Therefore, miss = 12 and hit = 1
For address 404, the block index would be 00.
The tag is not equal to 1. The replacement of block occurs.
The cache tags are 11, 0, 1, 10.
Therefore, miss = 13 and hit = 1
For address 180, the block index would be 01.
The tag is not equal to 0. The replacement of block occurs.
The cache tags are 11, 1, 1, 10.
Therefore, miss = 14 and hit = 1
Finally, the total count of miss = 14 and hit = 1.
(b)
Each block of cache consists of 32-word size. There are two cache blocks since this is 2-way set associative.
For address 520, the index of the block is 0.
So, this belongs to block 0. The cache tag is ([1000, -] lru 1, [-, -])
Therefore, miss = 1 and hit = 0
For address 400, the index of the block is 0.
So, this belongs to block 0.
The tag is not equal to 100. The cache tag is ([1000, 110] lru 0, [-, -])
Therefore, miss = 2 and hit = 0
For address 380, the index of the block is 1.
The first block is empty so, it will be brought to the block 1.
The content of tag of cache ([1000, 110] lru 0, [101, -] lru 1)
Therefore, miss = 3 and hit = 0
For address 540, the index of the block is 0.
The tag is 1000 and the tag is 1000. Therefore, it is a hit.
The content of tag of cache are ([1000, 110] lru 1, [101, -]lru 1)
Therefore, miss = 3 and hit = 1
For address 816, the index of the block is 1 and is empty.
The content of tag of cache is ([1000, 110] lru 0, [101, 1100] lru 0)
Therefore, miss = 4 and hit = 1
For address 204, the index of the block is 0.
The tag is 11 and isn’t a set. LRU replacement. The content of cache is ([1000, 11] lru 0, [101, 1100] lru 0)
Therefore, miss = 5 and hit = 1
For address 1348, the index of the block is 0.
The tag is 10101 and isn’t a set. Replacement of block occurs. The content of cache is ([1000, 11] lru 0, [101, 1100] lru 0)
Therefore, miss = 6 and hit = 1
For address 200, the index of the block is 0.
The tag is 11 and is present. This is a hit. The content of cache is ([10101, 11] lru 0, [101, 1100] lru 0)
Therefore, miss = 6 and hit = 2
For address 440, the index of the block is 1.
The tag is not equal 110 and is not present in the set. Replacement occurs. The content of cache is ([10101, 11] lru 0, [110, 1100] lru 1)
Therefore, miss = 7 and hit = 2
For address 140, the index of the block is 0.
The tag is 10 and is not present. LRU Replacement occurs. The content of cache is ([10, 11] lru 1, [110, 1100] lru 1)
Therefore, miss = 8 and hit = 2
For address 1064, the index of the block is 1.
The tag is 10000 and is not in the set. Replacement occurs. The content of cache is ([10, 11] lru 1, [110, 10000] lru 0)
Therefore, miss = 9 and hit = 2
For address 44, the index of the block is 1.
The tag is 00 and is not present. Replacement occurs. The content of cache is ([10, 11] lru 1, [0, 10000] lru 1)
Therefore, miss = 10 and hit = 2
For address 196, the index of the block is 0.
The tag is equal-equal to 11. There is a hit. The content of cache is ([10, 11] lru 0, [0, 10000] lru 1)
Therefore, miss = 10 and hit = 3
For address 404, the index of the block is 0.
The tag is not there. Replacement occurs. The content of cache is ([110, 11] lru 1, [0, 10000] lru 1)
Therefore, miss = 11 and hit = 3
For address 180, the index of the block is 01.
The tag 10 is not there. Replacement occurs. The content of cache is ([110, 11] lru 1, [0, 10] lru 0)
Therefore, miss = 12 and hit = 3
Finally, the total count of miss = 12 and hit = 3.
(c)
For part (a):
The count of total number of tags (distinct) are 8.
They are as follows:
100, 11, 10, 110, 1, 11010, 1000, 0
Therefore, the number of blocks of cache required are greater than 8 to hold all of them completely.
Hence, the count of cache blocks is 32 in which each block consists of 4 words.
For part (b):
The count of tags is 9.
To hold the data completely, the index of 4 bits is enough.
And each block has 4 words.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.