The different placement policies (the mapping functions) are illustrated below by an example with these parameters:
The 4096 memory blocks can be mapped to the 128 cache blocks in three different ways:
For a 16-bit address , the top 12 bits (101001011011) are matched with the 12-bit tag of each of the 128 CM blocks. If a match is found, the last 4 bits (0010) select word 2 (the 3rd word) of the block with a matching tag.
To avoid the search through all CM blocks needed by associative mapping, this method only allows MM blocks to be mapped to each CM block. A tag of 5 bits need to be attached to each CM block to identify which of the MM blocks is currently in there. There are two ways to map the MM blocks to the CM blocks:
The first 32 consecutive MM blocks (0 through 31) are mapped to the first CM block, the second 32 MM blocks (32 through 63) are mapped to the second CM block, etc.
Addressing process: The 16-bit address is divided into 3 fields, the 7 MSBs to identify the CM block, the middle 5 bits to match with the 5-bit tag of the block, and the 4 LSBs to select the word in the block in case of a match.
Example: For the 16-bit address , the top 7 bits (1010010) indicate CM block 82, the next 5 bits (11011) is to match with the tag of the block.
The first 128 consecutive MM blocks are mapped, respectively, to the 128 CM blocks, so that the first CM block takes one of these 32 MM blocks: 0, 128, 256, ..., 4064, the second CM block takes one of these MM blocks: 1, 129, 257, ..., 4065, etc.
Addressing process: The 16-bit address is divided into 3 fields, the 5 MSBs to match with the 5-bit tag of the CM block identified by the middle 7 bits, and the 4 LSBs to select the word in the block in case of a match.
Example: For the 16-bit address , the top 5 bits (10100) are to be matched with the tag of CM block 91, identified by the next 7 bits (1011011).
Which of the two methods is better in light of the spatial locality nature of memory usage?
This is a trade-off between associative and direct mappings. The 128 CM blocks are divided into sets each containing blocks. By direct mapping, every MM blocks are mapped to each CM set. A 7-bit tag is attached to each CM block to identify the current MM block. By associative mapping, an incoming MM block can use any of the 4 blocks in the set, so long as it is available.
Again, either continuous or interleaving direct mapping can be used to map MM blocks to the CM sets. But the latter is better (why?).
Addressing process (interleaving): The 16-bit address is divided into 3 fields of 7, 5 and 4 bits, respectively (from MSB to LSB). (a) The middle 5 bits select one of the sets, (b) the top 7 bits are compared with the 7-bit tag of each of the 4 blocks in the set, if there is a match, (c) the last 4 bits find the needed word in the block.
In the 16-bit address , the middle 5 bits (11011) identifies set 27, the top 7 bits (1010010) are compared with the tag of each of the 4 blocks in the set. If a match is found, the last 4 bits (0010) select word 2 in the block.
All three mappings can be considered as set-associative mapping with
direct mapping and associative mapping as two special cases (each
set contains 1 or all 128 CM blocks, respectively). The usage of the
16-bit address for each of the mappings is shown below:
Example 1: Interleaved Direct Mapping
Each block has four 4-byte words or bytes. The CM has KB or blocks, and the MM has bytes (4GB) or blocks. There are MM blocks mapped to each CM block, i.e., each CM block needs a 16-bit tag to identify the current MM block. The top 16 bits of a 32-bit address is compared with the tag of the CM block identified by the next 12 bits of the address, and the next 2 bits in the address select the word by a 4x1 MUX, while the last 2 bits select the byte in the word if needed.
Example 2: Set-associative Mapping
Each block contains only four bytes (one word). The CM has sets each containing four words. As there are MM words mapped to each CM set, a 22-bit tag is needed to identify the current word in CM. The top 22 bits of the 32-bit address is to be compared with the tag of each of the four words of one of the 256 CM set identified by the next 8 bits in the address. The last 2 bits in the address select the byte in the word.
The process of addressing a word in a CM/MM memory system is shown in the following diagram (note here a line is the same as a block):