The following memory addresses are used consecutively by a running program (from
ID: 3573261 • 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).
PLEASE DO NOT JUST COPY SOLUTION. IF YOU DO NOT KNOW, DO NOT ANSWER. I KEEP GETTING THE SAME COPIED-PASTED SOLUTION AND ONLY FOR PART A
IF YOU ANSWERED THIS PREVIOUSLY ON CHEGG PLEASE DO NOT ANSWER UNLESS POSITIVELY SURE IS CORRECT. BECAUSE ANSWERS FOR THIS PROBLEM ON CHEGG EXIST BUT ARE WRONG 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).
PLEASE DO NOT JUST COPY SOLUTION. IF YOU DO NOT KNOW, DO NOT ANSWER. I KEEP GETTING THE SAME COPIED-PASTED SOLUTION AND ONLY FOR PART A
IF YOU ANSWERED THIS PREVIOUSLY ON CHEGG PLEASE DO NOT ANSWER UNLESS POSITIVELY SURE IS CORRECT. BECAUSE ANSWERS FOR THIS PROBLEM ON CHEGG EXIST BUT ARE WRONG 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).
PLEASE DO NOT JUST COPY SOLUTION. IF YOU DO NOT KNOW, DO NOT ANSWER. I KEEP GETTING THE SAME COPIED-PASTED SOLUTION AND ONLY FOR PART A
IF YOU ANSWERED THIS PREVIOUSLY ON CHEGG PLEASE DO NOT ANSWER UNLESS POSITIVELY SURE IS CORRECT. BECAUSE ANSWERS FOR THIS PROBLEM ON CHEGG EXIST BUT ARE WRONG
Explanation / Answer
Convert Every Address to Binary: separated with tag index(2bits) offset(5 bits)
520 - 100 00 01000
400 - 11 00 10000
380 - 10 11 11100
540 - 100 00 11100
816 - 110 01 10000
204 - 1 10 01100
1348 - 1010 10 00100
200 - 1 10 01000
440 - 11 01 11000
140 - 1 00 01100
1064 - 1000 01 01000
44 - 0 01 01100
196 - 1 10 00100
404 - 11 00 10100
180 - 1 01 10100
a)cache is 128 words and each cache block is 32 words size i.e, there are 4 cache blocks . each memory address corresponds to a word and since each block has 32 word memories are brought in blocks of 32 which means last 5 bits are block offset and there are 4 blocks i.e, 6th and 7th bits are block indices of memory.
1 st request 520 block index is 00 so belongs to block 0 .. contents of cache tags (100 , - , - , -) miss:1 hit:0
2nd request 400 block index is 00 and tag is not 100 .. contents of cache tags(11,-,-,-) miss:2 hit:0
3rd request 380 block index is 11 and block 11 is empty so it's brought into block 11 .contents of cache (11,-,-,10) miss:3 hit:0
4th request 540 block index is 00 and tag is not 11. Hence replacement. contents (100,-,-,10) miss:4 hit:0
5th request 816 block index : 01 and is empty . contents (100,110,-,10) miss:5 hit:0
6th request 204 block index:10 and is empty. Contents ( 100,110,1,10) miss:6 hit:0
7th request 1348 block index:10 tag != 1 block replacement occurs . contents (100,110,1010,10) miss:7 hit:0
8th request 200 block index:10 tag!=1010 .block replacement occurs . contents (100,110,1,10) miss:8 hit:0
9th reuest 440 . block index:01 tag != 110 . block replacement occurs.Contents (100,11,1,10) miss:9 hit:0
10th request 140. block index:00 and tag!= 100 block replacement occurs.Contents (1,11,1,10) miss:10 hit:0
11th request 1064. block index : 01 and tag!=11 .block replacement occurs .Contents (1,1000,1,10) miss:11 , hit:0
12th request 44. block index 01 tag!=1000 .block replacement occurs .Contents are (1,0,1,10) miss:12 hit:0
13th request 196, block index is 10 and tag == 1 . hit occured .contents are (1,0,1,10) miss:12 hit:1
14th request 404 block index : 00 but tag!= 1 .block replacement occurs . Contents are (11,0,1,10) miss:13 hit:1
15th request 180 block index : 01 but tag!=0 .Block replacement occurs.Contents are (11,1,1,10) miss:14 hit:1
Total 14 misses and a hit
B)
Convert Every Address to Binary: separated with tag index(2bits) offset(5 bits)
520 - 1000 0 01000
400 - 110 0 10000
380 - 101 1 11100
540 - 1000 0 11100
816 - 1100 1 10000
204 - 11 0 01100
1348 - 10101 0 00100
200 - 11 0 01000
440 - 110 1 11000
140 - 10 0 01100
1064 - 10000 1 01000
44 - 00 1 01100
196 - 11 0 00100
404 - 110 0 10100
180 - 10 1 10100
cache is 128 words and each cache block is 32 words size i.e, there are 2 cache blocks since each cache is 2 way set assosciative . each memory address corresponds to a word and since each block has 32 word memories are brought in blocks of 32 which means last 5 bits are block offset and there are 2 blocks i.e, 6th bit is block indices of memory.
1 st request 520 block index is 0 so belongs to block 0 .. contents of cache tags ([1000 ,-] lru 1,[-, -]) miss:1 hit:0
2nd request 400 block index is 0 and tag is not 100 .. contents of cache tags ([1000 ,110] lru 0,[-, -] ) miss:2 hit:0
3rd request 380 block index is 1 and block 1 is empty so it's brought into block 1 .contents of cache ([1000 ,110] lru 0,[101, -] lru 1 )miss:3 hit:0
4th request 540 block index is 0 and tag is 1000.Hence a Hit.contents ([1000 ,110] lru 1,[101, -] lru 1 ) miss:3 hit:1
5th request 816 block index : 1 and is empty . contents ([1000 ,110] lru 0,[101, 1100] lru 0 ) miss:4 hit:1
6th request 204 block index:0 and tag 11 is not in set. lru replacement. Contents ([1000 ,11] lru 0,[101, 1100] lru 0 ) miss:5 hit:1
7th request 1348 block index:0 tag 10101 is not in set. block replacement occurs . Contents ([10101 ,11] lru 1,[101, 1100] lru 0 ) miss:6 hit:1
8th request 200 block index:0 .tag 11 is present hence a Hit.Contents ([10101 ,11] lru 0,[101, 1100] lru 0 ) miss:6 hit:2
9th reuest 440 . block index:1 tag 110 is not present in set. block replacement occurs.Contents ([10101 ,11] lru 0,[110, 1100] lru 1 ) miss:7 hit:2
10th request 140. block index:0 , tag 10 is not present lru replacement occurs.Contents ([10 ,11] lru 1,[110, 1100] lru 1 ) miss:8 hit:2
11th request 1064. block index : 1 and tag 10000 is not in set .block replacement occurs .Contents ([10 ,11] lru 1,[110, 10000] lru 0 ) miss:9 hit:2
12th request 44. block index 1 tag00 is not present.block replacement occurs .Contents ([10 ,11] lru 1,[0,10000] lru 1 ) miss:10 hit:2
13th request 196, block index is 0 and tag == 11 . hit occured ..Contents ([10 ,11] lru 0,[0,10000] lru 1 ) miss:10 hit:3
14th request 404 block index : 0 but tag 110 is not present .block replacement occurs . Contents ([110 ,11] lru 1,[0,10000] lru 1 ) miss:11 hit:3
15th request 180 block index :1 tag 10 is not present .Block replacement occurs.Contents ([110 ,11] lru 1,[0,10] lru 0 ) miss:12 hit:3
Total 12 misses and 3 hits
C)Number of distinct tags for given total cache size are (100,11,10,110,1,1010,1000,0 ) 8.
Hence number of cache blocks required are >= 8 to completely hold all and therefore number of cache blocks are (from observing addresses )32 and each cache block is 4 words size for Part A.
Similarly number of distinct tags are 9 for part B.
4 bits for index is sufficient to hold complete data.And each cache block contains 4 words
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.