“mapping” refers to the process of associating data in a larger memory space (such as main memory) with a smaller, faster memory space (such as a cache). In the context of cache memory, mapping refers to the way in which the cache is organized to store and retrieve data from main memory.
There are three main types of cache mapping:
- Fully associative
1. Direct-mapped cache mapping
In a direct-mapped cache, each block of data in main memory is mapped to exactly one block in the cache. The mapping is based on the address of the data in main memory, which is divided into two parts: a tag and an index. The tag is used to identify the block of data in main memory, while the index is used to identify the block of data in the cache. For example, if the cache has 8 blocks and the memory address is 32 bits, the lower 3 bits could be used as the index, allowing for 8 blocks in the cache.
2. Fully associative cache mapping
In a fully associative cache, each block of data in main memory can be mapped to any block in the cache. There is no fixed mapping based on the memory address, so the cache can be searched for a matching block of data without first determining the index. This allows for more flexible use of the cache space, but requires a more complex search mechanism to find the desired data.
3. Set-associative cache mapping
A set-associative cache is a compromise between direct-mapped and fully associative mapping. It is divided into a number of sets, each of which contains multiple blocks of data. Each block of data in main memory is mapped to one of the sets, and within each set, the blocks are arranged in a specific order (such as LRU). The mapping process uses both the tag and a portion of the address to determine which set the data should be mapped to. For example, if the cache has 8 blocks and is divided into 2 sets of 4 blocks each, the lower 2 bits of the address could be used to determine the set, while the remaining bits would be used as the tag.
As an example, consider a set-associative cache with 4 sets and 4 blocks per set, for a total of 16 blocks. Suppose we want to map a block of data with address 0x12345678 into the cache. The address is divided into a tag and an index: the tag is the upper 20 bits (0x12345), and the index is the lower 4 bits (0x8). The index is used to determine which set the data should be mapped to, so in this case, it would be set 0. Within set 0, the blocks are arranged in a specific order (such as LRU), and the cache controller would search for a matching block of data based on the tag. If a matching block is found, it is used to satisfy the memory request. If not, the block is fetched from main memory and stored in the cache, displacing the least recently used block if necessary.