Logical processor cache organization
The other day I decided to systematize knowledge regarding the principles of memory mapping to processor cache memory. As a result, this article was born.
Processor cache memory is used to reduce processor idle time when accessing RAM.
The basic idea of caching is based on the locality property of data and instructions: if it is addressed to a certain address, then it is likely that memory will be accessed to the same address or neighboring addresses in the near future.
')
Logically, cache memory is a collection of cache lines. Each cache line stores a block of data of a certain size and additional information. Under the size of the cache line usually understand the size of the data block that is stored in it. For x86 architecture, the line cache size is 64 bytes.
So the essence of caching is to split the RAM into cache lines and map them to the cache cache lines. Perhaps several options for such a display.
The basic idea of direct mapping (RAM) to cache memory is as follows: RAM is divided into segments, the size of each segment is equal to the cache size, and each segment is divided into blocks, the size of each block is equal to the size of the cache line.
RAM blocks from different segments, but with the same numbers in these segments, will always be mapped to the same cache cache line:
The address of each byte is the sum of the sequence number of the segment, the sequence number of the cache line within the segment, and the sequence number of the byte within the cache line. From this it follows that the addresses of bytes differ only in the upper parts, which are the sequence numbers of the segments, and the sequence numbers of the cache lines inside the segments and the sequence numbers of the bytes inside the cache lines are repeated.
Thus, there is no need to store the full address of the cache line, it is enough to save only the older part of the address. Tag (tag) of each cache line just stores the most significant part of the address of the first byte in this cache line.
b - the size of the cache line.
m is the number of cache lines in the cache.
To address b bytes within each cache line, you need: log2b bits.
To address m cache lines within each segment, you need: log2m bit.
m = Cache size / cache line size.
To address N segments of RAM: log2N bit.
N = Volume RAM / Segment Size.
For addressing bytes, you need: log2N + log2m + log2b bits.
Cache lookup steps:
1. The middle part of the address (log2m) is extracted, which determines the number of the cache line in the cache.
2. Tag cache line with this number is compared with the highest part of the address (log2N).
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
The main idea of a fully associative mapping of RAM to cache memory is as follows: RAM is divided into blocks whose size is equal to the size of the cache lines, and each RAM block can be stored in any cache line:
The address of each byte is the sum of the ordinal number of the cache line and the ordinal number of the byte within the cache line. It follows that the byte addresses differ only in the higher parts, which are the sequence numbers of the cache lines. The sequence numbers of the bytes within the cache lines are repeated.
Tag (tag) of each cache line stores the most significant part of the address of the first byte in this cache line.
b - the size of the cache line.
m is the number of cache lines that fit in the RAM.
To address b bytes within each cache line, you need: log2b bits.
To address m cache lines: log2m bit.
m = RAM size / cache line size.
For addressing bytes, you need: log2m + log2b bits.
Cache lookup steps:
1. Tags of all cash lines are compared with the highest part of the address at the same time.
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
The basic idea of a set associative mapping (set associative mapping) of RAM on cache memory is as follows: RAM is divided as in direct mapping, and the cache consists of k caches (k channels) using direct mapping.
Cache lines that have the same number in all channels form a set (set, set). Each set is a cache that uses a fully associative mapping.
RAM blocks from different segments, but with identical numbers in these segments, will always be mapped to the same set cache. If there are free cache lines in this set, then the block read from the RAM will be saved to the free cache line, if all the cache lines in the set are occupied, then the cache line is selected according to the replacement algorithm used.
The structure of the byte address is exactly the same as in the direct mapping: log2N + log2m + log2b bits, but since Since the set is k different cache lines, then the search in the cache is slightly different.
Cache lookup steps:
1. The middle part of the address (log2m) is extracted, which determines the number of the set in the cache.
2. Tags of all cache lines of this set are compared with the highest part of the address (log2N) at the same time.
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
Thus, the number of cache channels determines the number of simultaneously compared tags.
Processor cache memory is used to reduce processor idle time when accessing RAM.
The basic idea of caching is based on the locality property of data and instructions: if it is addressed to a certain address, then it is likely that memory will be accessed to the same address or neighboring addresses in the near future.
')
Logically, cache memory is a collection of cache lines. Each cache line stores a block of data of a certain size and additional information. Under the size of the cache line usually understand the size of the data block that is stored in it. For x86 architecture, the line cache size is 64 bytes.
So the essence of caching is to split the RAM into cache lines and map them to the cache cache lines. Perhaps several options for such a display.
DIRECT MAPPING
The basic idea of direct mapping (RAM) to cache memory is as follows: RAM is divided into segments, the size of each segment is equal to the cache size, and each segment is divided into blocks, the size of each block is equal to the size of the cache line.
RAM blocks from different segments, but with the same numbers in these segments, will always be mapped to the same cache cache line:
The address of each byte is the sum of the sequence number of the segment, the sequence number of the cache line within the segment, and the sequence number of the byte within the cache line. From this it follows that the addresses of bytes differ only in the upper parts, which are the sequence numbers of the segments, and the sequence numbers of the cache lines inside the segments and the sequence numbers of the bytes inside the cache lines are repeated.
Thus, there is no need to store the full address of the cache line, it is enough to save only the older part of the address. Tag (tag) of each cache line just stores the most significant part of the address of the first byte in this cache line.
b - the size of the cache line.
m is the number of cache lines in the cache.
To address b bytes within each cache line, you need: log2b bits.
To address m cache lines within each segment, you need: log2m bit.
m = Cache size / cache line size.
To address N segments of RAM: log2N bit.
N = Volume RAM / Segment Size.
For addressing bytes, you need: log2N + log2m + log2b bits.
Cache lookup steps:
1. The middle part of the address (log2m) is extracted, which determines the number of the cache line in the cache.
2. Tag cache line with this number is compared with the highest part of the address (log2N).
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
FULLY ASSOCIATIVE MAPPING
The main idea of a fully associative mapping of RAM to cache memory is as follows: RAM is divided into blocks whose size is equal to the size of the cache lines, and each RAM block can be stored in any cache line:
The address of each byte is the sum of the ordinal number of the cache line and the ordinal number of the byte within the cache line. It follows that the byte addresses differ only in the higher parts, which are the sequence numbers of the cache lines. The sequence numbers of the bytes within the cache lines are repeated.
Tag (tag) of each cache line stores the most significant part of the address of the first byte in this cache line.
b - the size of the cache line.
m is the number of cache lines that fit in the RAM.
To address b bytes within each cache line, you need: log2b bits.
To address m cache lines: log2m bit.
m = RAM size / cache line size.
For addressing bytes, you need: log2m + log2b bits.
Cache lookup steps:
1. Tags of all cash lines are compared with the highest part of the address at the same time.
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
SET ASSOCIATIVE MAPPING
The basic idea of a set associative mapping (set associative mapping) of RAM on cache memory is as follows: RAM is divided as in direct mapping, and the cache consists of k caches (k channels) using direct mapping.
Cache lines that have the same number in all channels form a set (set, set). Each set is a cache that uses a fully associative mapping.
RAM blocks from different segments, but with identical numbers in these segments, will always be mapped to the same set cache. If there are free cache lines in this set, then the block read from the RAM will be saved to the free cache line, if all the cache lines in the set are occupied, then the cache line is selected according to the replacement algorithm used.
The structure of the byte address is exactly the same as in the direct mapping: log2N + log2m + log2b bits, but since Since the set is k different cache lines, then the search in the cache is slightly different.
Cache lookup steps:
1. The middle part of the address (log2m) is extracted, which determines the number of the set in the cache.
2. Tags of all cache lines of this set are compared with the highest part of the address (log2N) at the same time.
If there was a match on one of the tags, then a cache hit occurred.
If there was no match on any of the tags, then a cash slip occurred.
Thus, the number of cache channels determines the number of simultaneously compared tags.
Source: https://habr.com/ru/post/179647/
All Articles