给定主存与缓存参数，求三种映射方式下的缓存地址及解法

Alright, let's walk through this cache mapping problem step by step—first, we'll nail down all the key parameters, then break down each mapping method clearly.

Key Parameters to Start With #

Let's list out the specs we need to calculate everything correctly:

• Main Memory: 1MB = 2²⁰ bytes (so we have a 20-bit address, which matches the 20-bit address given in the problem)
• Addressing: Byte-addressable (since word length is 8 bits, each address points to 1 byte)
• Cache Block Size: 32 bits = 4 bytes → we need 2 bits for the block offset (2²=4, to target each byte in the block)
• Total Cache Blocks: 16 = 2⁴ → this will drive the index size for direct and set-associative mappings

i) Direct Cache Mapping #

Direct mapping is the simplest: each main memory block maps to exactly one cache block, determined by main memory block number % total cache blocks.

Address Structure #

The 20-bit main memory address splits into three parts:

• Tag: 20 - 4 - 2 = 14 bits → unique identifier for the main memory block, used to verify cache hits
• Block Index: 4 bits → directly points to the specific cache block the main memory block maps to
• Block Offset: 2 bits → locates the exact byte within the cache block

Calculation for the Given Address #

Given main memory address (binary): 1000 1111 1010 0101 1101 (hex: 0x8FA5D, decimal: 588381)

1. Block Offset: Take the last 2 bits → 01 (decimal 1, meaning the 2nd byte in the block, 0-indexed)
2. Main Memory Block Number: Divide the address by block size (4 bytes) → 588381 // 4 = 147095 (or right-shift the binary address by 2 bits: 100011111010010111)
3. Cache Block Index: 147095 % 16 = 7 (binary 0111) → this is the only cache block this main memory block can map to
4. Cache Address: Combine the block index and offset → binary 0111 01, decimal 29
5. Tag: The first 14 bits of the address → 1000 1111 1010 01 (binary)

For a cache hit, the tag stored in cache block 7 must match this 14-bit tag. If not, we load the main memory block into cache block 7.

ii) Fully Associative Cache Mapping #

Fully associative mapping is the most flexible: any main memory block can map to any cache block. There's no block index—we use the entire address (minus the offset) as the tag to match against all cache blocks.

Address Structure #

The 20-bit address splits into two parts:

• Tag: 20 - 2 = 18 bits → uniquely identifies the main memory block (we check this against every cache block's tag for hits)
• Block Offset: 2 bits → same as before, locates the byte within the block

Calculation for the Given Address #

1. Block Offset: Last 2 bits → 01 (decimal 1)
2. Tag: First 18 bits of the address → 1000 1111 1010 0101 11 (binary)
3. Cache Address: There's no fixed cache block here. When we load the main memory block into cache, we can choose any empty block (or evict an existing one using a replacement policy like LRU). For example, if we load it into cache block 5, the cache address would be (5 * 4) + 1 = 21; if we use block 12, it's (12 *4)+1=49.

The key here is that we have to check all 16 cache blocks' tags to see if any match the 18-bit tag—if yes, we have a hit.

iii) 2-Way Set Associative Cache Mapping #

Two-way set associative splits the cache into groups (sets) of 2 blocks each. A main memory block maps to exactly one set (determined by main memory block number % number of sets), and can be stored in either block within that set.

First, calculate the number of sets: Total cache blocks / 2 = 16 /2 =8 sets → so we need 3 bits for the set index (2³=8).

Address Structure #

The 20-bit address splits into three parts:

• Tag: 20 -3 -2=15 bits → identifies the main memory block, checked against the two blocks in the target set
• Set Index:3 bits → points to the specific set the main memory block maps to
• Block Offset:2 bits → locates the byte within the block

Calculation for the Given Address #

1. Block Offset: Last 2 bits → 01 (decimal 1)
2. Main Memory Block Number: 147095 (same as direct mapping)
3. Set Index: 147095 %8=7 (binary 111) → this main memory block can only map to set 7
4. Tag: First 15 bits of the address → 1000 1111 1010 010 (binary)
5. Cache Address: We can store the block in either of the two blocks in set 7:
   • If stored in block 0 of set7: cache address = (7 * 2 *4) + (0*4) +1= 56+0+1=57 (binary 111 0 01)
   • If stored in block1 of set7: cache address = (7*2*4)+(1*4)+1=56+4+1=61 (binary 111 1 01)

For a hit, we only need to check the tags of the two blocks in set7—if either matches the 15-bit tag, we have a hit.

内容的提问来源于stack exchange，提问作者user3187800