About the cache thing
This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging
Introduction: In the last section, we looked at the definition of caching, why we use caching, and the principle of locality. In this section, we will continue to learn more about caching.
How does the CPU access data in the cache
CPU Catch is similar to Redis cache access in that it accesses the cache first and then accesses the memory or database if the cache does not exist.
Cache memory
- Map the cache directly
- Fully associated cache
- Group associated cache
Definition of address mapping:
The main memory address is mapped to the cache according to some rule (function), when the CPU access, its memory will automatically translate to the cache address.Copy the codeMap the cache directly
When the CPU accesses memory data, it reads and writes data according to the cache line size, which is usually 64 bytes. Each memory address must fall on a memory block. The offset of data in this memory block is also determined, and then determined by the index number mapping relationship.
Index number: THE CPU direct mapping is realized by the mod operation. The number of cache rows must be 2^n, so that the index row can be directly represented by the low order. Offset: The offset is determined based on the block size.Copy the codeIn this mapping mode, each main memory block corresponds to a cache block, and the mapping relationship is: I =j mod C or I =j mod 2^ C, where I is the cache block number, and j is the main memory block number. In this mode of modulo, it is easy to know how many main memory blocks correspond to each cache block.
The storage is similar to the following figure:
It is easy to see from the figure above that there must be collisions in the storage, i.e., conflicts. To address this problem, we need to add tags to the cache, providing the tag bits through the high bits of memory, and using the middle bits as group indexes, so that we can distinguish between different storage locations mapped to the same cache block. By combining the cache block tag with the block index, we can know exactly which addresses of main memory are stored in the cache.
Cache is indexed in the middle bit: The reason is that if the high bit is indexed, several contiguous memory blocks may be mapped to the same cache block, which does not provide good spatial locality and results in performance degradation. The diagram below:
Advantages of direct mapping: Simple hardware, low cost, and fast address shuffling Disadvantages of direct mapping: The Cache storage space is not fully used, which may cause conflicts.Copy the codeFully associated cache
An address in main memory can be mapped to any cache line, but to determine whether the address is in the cache, you need to traverse each cache line. The fully associated cache consists of a group containing all the cache lines. Here is the basic structure:
Fully associated mapping is more flexible
Group associated cache
The problem with a collision miss in the direct mapping cache is that a group has only one row. The group-linked cache loosens this restriction, meaning that a group has multiple cache rows. The specific structure is as follows:
Line matching and word selection in the fully associated cache
Because line matching in the cache in group concatenation checks the mark bits and significant bits of multiple rows, it is more complex than direct mapping. Associative memory is an array of (key, value) pairs, so we can think of each group in a group associative as a small associative memory, where key is the tag bit and the significant bit, and value is the contents of the block.
