Cache in multiprocessor systems. Cache coherence MESI protocol
Hi, Habr!
At one time, this topic seemed very interesting to me, so I decided to share my modest knowledge with you. This article does not claim to be a complete, detailed description; rather, this is a brief overview.
It is not a secret for anyone that in modern computers memory access can simultaneously have several independent processors (cores, trades). Each of them has its own private caches, in which copies of the necessary lines are stored, and some of them are locally modified. The question arises, what if one and the same line is simultaneously needed by several processors. It is not difficult to conclude that for the correct operation of the system it is necessary to provide a single memory space for all processors.
')
To ensure this, special coherence protocols were invented. Cache coherence - cache properties, meaning the integrity of data stored in local caches of a shared system. Each cache cell has flags describing how its state relates to the state of the cell with the same address in other processors of the system.
When the state of the current cell changes, you need to somehow inform the rest of the caches. For example, generating broadcast messages delivered via the internal network of a multiprocessor system.
Many coherence protocols were invented, differing in algorithms, number of states and, as a consequence, speed of operation and scalability. Most modern coherence protocols represent variations of the MESI protocol [1]. For this reason we will consider it.
In this scheme, each cache line can be in one of four states:
MESI protocol transition diagram. Access is local, if it was initiated by the processors of the cache, remote - if it was called by any other.
I also want to consider one of the optimizations of the MESI protocol
For this protocol, the status flags have been extended with another value, “Owner” (O) English. owner. This state is a combination of the “Modified” and “Shared” states. This condition avoids the need to write a modified line into memory, thereby reducing traffic sent to memory. The cache line in this state contains the most recent data. The described state is similar to Shared in that other processors can also have the most up-to-date data in their cache memory relative to RAM. However, in contrast, such a state means that the data in memory is outdated. Only one line with a specific address can have such a state, while it is she who will respond to all requests for reading at that address, and not memory.
This is all that I wanted to talk about today, I hope that my article will be interesting to someone.
Additional information on this topic can be found in the sources indicated below.
[1] Review of existing protocols, with transition diagrams
[2] G.S. Rechistov, E.A. Yulyugin, A.A. Ivanov, P.L. Shishpor, N.N. Clicks "Fundamentals of computer software simulation" URL
[3] Ulrich Drepper "What Every Programmer Should Know About Memory" URL
At one time, this topic seemed very interesting to me, so I decided to share my modest knowledge with you. This article does not claim to be a complete, detailed description; rather, this is a brief overview.
Introduction
It is not a secret for anyone that in modern computers memory access can simultaneously have several independent processors (cores, trades). Each of them has its own private caches, in which copies of the necessary lines are stored, and some of them are locally modified. The question arises, what if one and the same line is simultaneously needed by several processors. It is not difficult to conclude that for the correct operation of the system it is necessary to provide a single memory space for all processors.
')
To ensure this, special coherence protocols were invented. Cache coherence - cache properties, meaning the integrity of data stored in local caches of a shared system. Each cache cell has flags describing how its state relates to the state of the cell with the same address in other processors of the system.
When the state of the current cell changes, you need to somehow inform the rest of the caches. For example, generating broadcast messages delivered via the internal network of a multiprocessor system.
Many coherence protocols were invented, differing in algorithms, number of states and, as a consequence, speed of operation and scalability. Most modern coherence protocols represent variations of the MESI protocol [1]. For this reason we will consider it.
MESI
In this scheme, each cache line can be in one of four states:
- Modified (M) English modified. Only a line in one cache can be marked with this flag. This state means that this line has been changed, but these changes have not yet reached memory. The owner of such a line can safely read and write to it without interviewing the others.
- Exclusive (E) English exclusive. The line designated by such flag, the same as the M-line can be only in one cache. The data contained in it is completely identical to the data in RAM. You can write and read from it without external requests, since it is stored only in one cache. After recording such a line should be marked as modified.
- Shared (S) English shared. A line can simultaneously be contained in the caches of several devices and be shared. Requests to write to such a line always go to a common bus, which leads to the fact that all lines with such addresses in other caches are marked as invalid. The content of the main memory is also updated. Reading from this line does not require any external queries.
- Invalid (i) English invalid. Such a line is considered invalid, and an attempt to read will result in a cash slip. A line is marked invalid if it is empty or contains outdated information.
MESI protocol transition diagram. Access is local, if it was initiated by the processors of the cache, remote - if it was called by any other.
I also want to consider one of the optimizations of the MESI protocol
MOESI
For this protocol, the status flags have been extended with another value, “Owner” (O) English. owner. This state is a combination of the “Modified” and “Shared” states. This condition avoids the need to write a modified line into memory, thereby reducing traffic sent to memory. The cache line in this state contains the most recent data. The described state is similar to Shared in that other processors can also have the most up-to-date data in their cache memory relative to RAM. However, in contrast, such a state means that the data in memory is outdated. Only one line with a specific address can have such a state, while it is she who will respond to all requests for reading at that address, and not memory.
This is all that I wanted to talk about today, I hope that my article will be interesting to someone.
Additional information on this topic can be found in the sources indicated below.
Literature
[1] Review of existing protocols, with transition diagrams
[2] G.S. Rechistov, E.A. Yulyugin, A.A. Ivanov, P.L. Shishpor, N.N. Clicks "Fundamentals of computer software simulation" URL
[3] Ulrich Drepper "What Every Programmer Should Know About Memory" URL
Source: https://habr.com/ru/post/183834/
All Articles