CSC264 Computer Org & Arch II - Problem Set Answers: Cache

Problem Set Answers: Cache

Suppose we have a main memory of 16MB and a direct mapped cache of 16KB, and suppose the size of a memory block is 32 bytes.
1. 1K = 1024₁₀ = 2¹⁰ which is 400₁₆
2. 1M = 1,048,576₁₀ = 2²⁰ which is 100000₁₆
3. lines of cache m = 512 = 2⁹
4. blocks in memory M = 524,288 = 2¹⁹
5. memory is 16M = 2²⁴ so addresses are 24 bits
6. each block contains 32 bytes; 32 = 2⁵ so 5 bits are needed
7. 9 bits are used for the block field
8. the high order 10 bits are the tag field
Suppose a computer using direct mapped cache has 2³² words of word-addressable main memory, and a cache of 1024 lines, where each cache line contains 64 words.
1. 2³²/2⁶ = 2²⁶
2. 32 bit addresses with 16 bits in the tag field, 10 in the block field, and 6 in the offset field
3. 0x63FA16 = 0000 0000 0110 0011 1111 1010 0001 0110 (add leading zeros to get a 32 bit address. This is separated as 0000 0000 0110 0011 | 1111 1010 00 | 01 0110. Thus the offset is 01 0110, the block is 1111 1010 00, and the tag is 0000 0000 0110 0011 This maps to cache line 0x3E8.
Suppose a computer using direct mapped cache has 2³² bytes of byte-addressable main memory and a cache size of 512 bytes, and each cache block contains 64 bytes.
1. 2³²/2⁶ = 2²⁶
2. The cache is 512 bytes, and each cache block/line is 64 bytes, so the cache contains 512/64 = 8 lines. Therefore there are 3 bits in the block field, so we have 32 bit addresses with 23 bits in the tag field, 3 in the block field, and 6 in the offset field.
3. 0x13A4498A = 0001 0011 1010 0100 0100 1001 1000 1010 (add leading zeros to get a 32 bit address. This is separated as 0001 0011 1010 0100 0100 100 | 1 10 | 00 1010. Thus the offset is 00 1010, the block is 110, and the tag is 0001 001 1101 0010 0010 0100. This address maps to cache block/line 6.
Suppose a computer using fully associative cache has 224 bytes of byte-addressable main memory and a cache of 128 blocks, where each cache block contains 64 bytes.
1. 2²⁴/2⁶ = 2¹⁸
2. 24 bit addresses with 18 bits in the tag field and 6 in the offset field
3. Since it's associative cache, it can map anywhere
A 2-way set-associative cache consists of four sets. Main memory contains 2K blocks of eight words each and word addressing is used.
1. There are 4 sets and each set contains 2 lines, so there are 8 lines.
2. 2K blocks * 2³ words per block = 2¹⁴ words in memory, so we have 14-bit addresses with 9 bits in the tag field, 2 bits in the set field (since we have four sets), and 3 in the offset field:
```
	-------------------------------------------------------
	| tag (9 bits) | block/set (2 bits) | offset (3 bits) |
	-------------------------------------------------------
	
```
3. First iteration of the loop: Address 8 is a miss, then entire block brought into Set 1. 9- F are then hits. 10 is a miss, entire block brought into Set 2, 11-17 are hits. 18 is a miss, entire block brought into Set 3, 19-1F are hits. 20 is a miss, entire block brought into Set 0, 21-27 are then hits. 28 is a miss, entire block brought into Set 1 (note we do NOT have to throw out the block with address 8 as this is 2-way set associative), 29-2F are hits. 30 is a miss, entire block brought into Set 2, 31-33 are hits. For the first iteration of the loop, we have 6 misses, and 5*7 + 3 hits, or 38 hits. On the remaining iterations, we have 5*8+4 hits, or 44 hits each, for 88 more hits. Therefore, we have 6 misses and 126 hits, for a hit ratio of 126/132, or 95.45%.
A 2-way set-associative cache consists of four sets. Main memory contains 64K blocks of 64 bytes each.
1. The cache contains 8 lines.
2. Main memory contains 2¹⁶ blocks and each block is 2⁶ bytes, so the total number of bytes is 2²². This means an address is 22 bits.
3. 6 bits are needed to specify the location within the line, 2 bits are needed to specify the set, and the remaining 14 bits are used for the tag. The address format is:
```
	--------------------------------------------------------
	| tag (14 bits) | block/set (2 bits) | offset (6 bits) |
	--------------------------------------------------------
	
```
4. Address 0x4AE7 is 100 1010 1110 0111 which has offset 10 0111, block/set 11, and tag 100 1010. This address is in a block which maps to set 3. Looking at the tags in set 3 we see this block is in line 1.
5. Address 0x10592B is 1 0000 0101 1001 0010 1011 which has offset 10 1011, block/set 00, and tag 1 0000 0101 1001. This address is in a block which maps to set 0. Looking at the tags in set 0 we see this block is in line 0.
6. Address 0xCA86 is 1100 1010 1000 0110 which has offset 00 1001, block/set 10, and tag 1100 1010. This address is in a block which maps to set 2. Looking at the tags in set 2 we do not see block CA, so this block is not in cache.