Introduction to Cache Mapping Methods and Calculations

Cache is a high-speed memory in computer to solve the speed mismatch between CPU and main memory. Usually it does not use DRAM technology like system main memory, but uses the SRAM technology. The setting of the cache is one of the important factors for the high performance of all modern computer systems. Then, how to distinguish the corresponding relationship between the cache and the data blocks of the main memory?

Cache Memory Mapping

Cache Block & Line

The data exchange between the cache and the main memory is carried out in units of "blocks". A "block" contains several "words", and the word length is determined by the actual situation. Customarily, the main memory"block" in the cache is called a "line". The "lines" of cache have the same storage capacity as the "blocks" of main memory. The tag in the cache corresponds to the "line" of the cache one by one. If a block data is copied to a cache line, a corresponding tag will be formed by cache.

Assume that the main memory of the computer is 256MB, addressed by byte, the data cache has 8 lines, and the data block size is 64B. How should main memory data be stored in the cache? What kind of correspondence should be established between the two?

[Analysis] Main memory and cache exchange data in units of blocks, so the main memory block size ≡ \equiv ≡ cache line size

The data block size is 64B (26B), addressing in bytes, occupying 6 bits.

The main memory size is 256MB (228B), addressing in bytes, occupying 28 bits in total.

Using different mapping methods, there will be different division methods for the main memory address (28 bits):

Three Mapping Methods

2.1 Associative mapping

All lines of the cache can be used to store any piece of data in the main memory.

Disadvantage: The search speed is the the slowest. And when the cache block is full, you may need to search all the cache lines.

Main memory address structure division:

Main Memory Block Number	Block Address
22 bits	6 bits

Mapping process:

If the access address is: 1...1101 001110

Use the first 22 bits to compare with the cache block tag in turn.

If the tag matches and the valid bit is 1, the cache hits and the unit with address 001110 in the block is accessed.

If the cache misses or the valid bit is 0, access the memory normally.

Advantages: The probability of block collision is low and the cache utilization rate is high.

Disadvantages: The hardware control is complex, especially the comparator circuit used to compare the main memory block number and tag is difficult to design and implement.

Applicable: It is suitable for small capacity cache.

2.2 Direct mapping

Each main memory block can only be placed in a fixed cache line, and the cache line to which each main memory block belongs is the main memory block number % of the total number of cache lines.

Disadvantage: Multiple blocks will be mapped to the same line, which will cause unnecessary swap in and swap out, even if there are empty lines in the cache, they cannot be utilized.

For the above example, "No. 0, No. 8, No. 16..." main memory block is mapped to No. 0 cache line, "No. 1, No. 9, No. 17..." main memory block is mapped to No. 1 cache line...

Since the cache has a total of 8 lines (23), it occupies 3 bits. And it happens that the last three digits of the 22-bit main memory block number are consistent with the cache line number, so the main memory block number is split again.

Main memory address structure division:

Main Memory Block Number	Block Address
memory tag (19 bits) +cache line (3 bits) = 22bits	6 bits

Mapping process:

If the access address is: 0...01000 001110

Determine the cache line number according to the last 3 digits of the main memory block number. If the first 19 bits of the main memory block number match the cache tag and the valid bit is 1, the cache hits and the unit with the address 001110 in the block is accessed.

If the cache misses or the valid bit is 0, access the memory normally.

Advantages: Simple hardware, easy to implement, and low cost.

Disadvantages: The probability of block conflicts is high, resulting in a decrease in cache hit rate and efficiency.

Applicable: It is suitable for large-capacity cache, more lines can reduce the chance of conflicts.

2.3 Set-associative mapping

First of all, all cache lines must be grouped. Each main memory block can only be placed in a fixed cache group. The cache group to which each main memory block belongs is the main memory block number % cache total group number.

This method is a combination of the above two methods. The main memory data first finds its corresponding group, and the vacancies in the group are randomly placed, which not only improves the search efficiency, but also reduces the number of swaps in and out due to conflicts.

Still for the above example, taking 2-way set associative as an example, the cache line can be divided into 8/2=4 groups (22), and the group number occupies 2 bits.

"No. 0, No. 4, No. 8..." main memory block is mapped to No. 0 cache set, while "No. 1, No. 5, No. 9..." main memory block is mapped to No. 1 cache line, and so on. And it happens that the last 2 digits of the 22-bit main memory block number are consistent with the cache set number, so there is another way to divide the main memory block number.

Main memory address structure division:

Main Memory Block Number	Block Address
memory tag (20 bits) +cache line (2 bits) =22bits	6 bits

Mapping process:

If the access address is: 1...0101 001110

Determine the cache set number according to the last 2 digits of the main memory block number.

If the first 20 bits of the main memory block number match a line tag in the cache set and the valid bit is 1, the cache hits and the unit with the address 001110 in the block is accessed.

If the cache misses or the valid bit is 0, access the memory normally.

This method is easier to implement, the block collision probability is lower than the direct mapping method, and the hit rate is between the above mentioned mapping methods.

Cache Capacity Calculation

Since the Cache lines number is much less than the number of main memory blocks, the Cache can only store a part of the info in the main memory, and it needs to add a tag for each piece of data to indicate which block of the main memory it is. Therefore when calculating the cache capacity, it is necessary to analyze the number of tags and the cache data blocks at the same time.

Each cache line will correspond to a tag, which is used to mark the data status saved in the current cache line, including:

Valid Bit	Tag Bit	Dirty Bit	Replace Control Bit
1bit	Main memory block tag	1bit	Related to replacement algorithm

* Valid bit: (must have) fixedly occupies 1 bit, since the main memory block tag is 0 by default when the cache is not loaded with data blocks, the valid bit is to distinguish whether the current cache block is not loaded with data or a main memory is installed the 0th data.

* Tag bit: (must have) the number of tag bits in the main memory block, which is used to identify which data block in the main memory is stored in the current cache line.

* Dirty bit: (only available under certain conditions) is also called the consistency maintenance bit. This bit takes effect and occupies 1 bit only when the cache adopts the write-back method.

* Replacement control bit: (only under certain conditions) or replacement algorithm bit, which is used to mark which line of the replacement cache will be swapped out. In the cache replacement strategy, when the LRU and LFU replacement algorithms are used, this control bit will be used as the basis for swapping out.

* Related to dirty bits and replacement control bits: Cache replacement algorithm and Cache write strategy.

Note: Since Cache is an associative memory, it is addressed according to content and does not divide the address structure. The order of subitems in the Cache line tag does not need to be deliberately pursued.

The topic is generally given in various ways more intuitively. The size of the cache line is consistent with the size of the main memory block, and it is very convenient to calculate the number of bits occupied by a block.

Data bit: Since the data exchange of the main memory and the cache is based on the block, a data bit is the number of a data block.

The number of lines = the number of line tags + the number of blocks.

Calculate the number of cache lines according to the total cache capacity and the cache block size, and finally

Total capacity = number of rows × number of bits in rows

That is, the total capacity = the number of lines × (the number of line tags + the number of blocks) 

Calculation example:

Assume that the main memory capacity is 512K*16 bits, the Cache capacity is 4096*16 bits, the block length is four 16-bit words, and the access address is words.

(1) Under direct mapping, design the address format of the main memory.

(2) Under associative mapping, design the address format of the main memory.

(3) Under set-associative mapping, design the address format of the main memory.

(4) If the main memory capacity is 512K*32 bits and the block length remains unchanged, the address format of the main memory is designed under the four-way set associative mapping.

Do exercise:

(1) Under direct mapping, find t, c, b. Note that the access address is a word, and each is 16 bits, so the block length is 4, then b=2.

The length of the main memory address is 19 (512K=2^{19}), and the length of the Cache address is 12 (4096=2^{12}), then t=19-12=7.

Cache can be divided into 1024 blocks, that is, 2^{10} blocks (4096/4=1024 blocks), then c=10.

(2) According to the first question, where b=2, m=19 - 2 = 17

(3) Because it is set-associative, where r=1, s = t + r = 8, q = c - r = 9, b = 2.

(4) Note that the block length has not changed, the main memory capacity has been changed to 512K*32 bits, and the memory access address is a word address, so the main memory capacity can be rewritten to 1024K*16 bits, and the length of the main memory address is 20. The Cache has not changed, so its length is still 12 bits, then t=20-12=8. c has not changed also and is still 10, four-way set associative, so r=2, s = t + r = 10, q = c - r = 8. The block length has not changed, so b has not changed, it is still 2.

Another method can also be used: Cache can be divided into 1024 blocks, each set is 2^{r}=4 blocks, then it can be divided into 1024/4=256 groups, 256=2^{8}, then q= 8.