캐시 메모리는 프로세서가 데이터를 얻기 위해 메인 메모리를 참조하지 않도록 할 수 있어, 속도 향상에 많은 도움을 준다.
하지만 캐시 메모리를 사용하면 같은 데이터가 여러 곳의 메모리에 존재하는 경우가 생기는데, 이 여러 곳에 존재하는 데이터들이 같은 값 또는 유효한 값을 가지도록 하는 것이 중요하다. 이것을 캐시 일관성(cache coherence) 문제라고 한다.
통일(coherence)과 일관성(consistency)
‘통일(coherence)’은 한 위치에 있는 데이터를 읽어올 때, 이 데이터가 유효 또는 가장 최신인 데이터 임을 보장하는 의미이고,
‘일관성(consistency)’은 여러 위치에 존재하는 데이터들을 가져오거나 실행할 때, 정해진 순서로 가져오거나 실행되는 것을 보장하는 의미이다.
쓰기 정책(Wirte Policy)
프로세서가 한 개인 싱글프로세서 환경에선 캐시가 여러개 존재할 때(여러 level) 한 캐시에 일어난 변경을 다른 계층의 메모리로 바로 전달할 것인지 미룰지 정하면 된다.
변경점을 바로 다른 계층의 메모리로 전달하여 일관성 문제를 해결하는 방법을 ‘write through’,
변경점을 바로 다른 계층의 메모리로 전달하는 것이 아닌, 변경이 일어난 캐시에만 저장해두고 이후 변경이 일어난 ‘라인’이 캐시에서 방출(evicted)될 때 메인 메모리에 반영하는 방법을 ‘write back’이라고 한다.
하지만 프로세서가 여러개인 멀티프로세서 환경에선 각 프로세서마다 전용 캐시가 존재하고, 여러 프로세서가 공유하는 캐시도 존재하는 등, 좀 더 복잡한 구조를 가지므로 캐시 일관성 문제는 더 복잡해진다. 여기서 멀티 프로세서의 범위는 하나의 CPU 단위를 넘어서 개별적 처리능력을 갖춘 하나의 개체를 의미한다.
MESI 프로토콜
MESI 프로토콜은 캐시 일관성(cache coherence)을 유지하기 위한 프로토콜로, 캐시 라인의 상태를 나타내는 네 가지 독립적인 상태를 표현하는 데 사용된다. 이 네 가지 상태는 다음과 같다
- M = Modified
해당 캐시 line의 data는 이 캐시에서만 변경이 이루어진 상태(가장 최근에 변경이 일어난 곳)
메인 메모리와 값 다름(dirty)
- E = Exclusive
오직 이 캐시에 존재하는 data를 의미한다.
메인 메모리와 값 같음(clean)
- S = Shared
해당 캐시 line의 data는 다른 위치의 캐시에도 같은 값으로 존재하는 상태
메인 메모리와 값 동일(clean)
- I = Invalidate
해당 캐시 line의 data는 유효하지 않은 상태
-
상세과정
Local Processor Action
캐시가 속해 있는 프로세서에서 read, write 동작이 일어나는 경우
캐시의 변경이 발생하면 발생 했다고 bus를 통해 broadcast한다.
초기 캐시의 모든 line은 I상태로 초기화된다.
I 상태에서 local processor가 read 동작
- → read miss가 발생하고 메인 메모리에서 data를 읽어 캐시에 저장한다. 다른 캐시가 해당 data에 대해 M 상태인 line을 가진 경우, M 상태인 캐시에서 data를 읽어온다. (M 상태인 캐시는 S 로 변경됨)
(line의 상태: I ⇒ S)
I 상태에서 local processor가 write 동작
- → write miss가 발생하고 메인 메모리에서 data를 읽어오고 그 값을 변경한다. 값이 변경되었으므로 다른 캐시에 해당 data가 존재하면 invalidate하라는 신호를 bus로 전달
(line의 상태: I ⇒ M)
S 상태에서 local processor가 write 동작
- → write hit이 발생하고 캐시의 값을 변경한다. 값이 변경되었으므로 다른 캐시에 해당 data가 존재하면 invalidate하라는 신호를 bus로 전달
(line의 상태: S⇒M)
문제 상황 예시
#include <iostream>
#include <thread>
#include <windows.h>
#include <vector>
#define MAX (10000000)
int total = 0;
void workerFunction(int id) {
for (int i = 0; i < MAX; i++)
total += i;
}
int main()
{
int numThreads = 100;
std::vector<std::thread> threads;
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < MAX * numThreads; i++)
total += i;
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "single core_ms: " << totalDuration.count() << std::endl;
}
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < numThreads; ++i) {
threads.emplace_back(workerFunction, i);
}
for (auto& th : threads) {
th.join();
}
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "multi core_ms: " << totalDuration.count() << std::endl;
}
}
해당 코드를 실행했을 경우, 멀티 스레드를 사용함으로써 성능이 현저히 감소함을 확인할 수 있다. 해당 코드에서 각각의 코어는 같은 데이터를 캐싱하게된다. 이때 하나의 코어에서 Modifi가 발생한다면, 다른 코어의 캐시는 Invalid 상태를 가지게된다. 따라서 MESI 프로토콜에 따라서 메인 메모리에 접근하여 Shared 상태를 가지고자 한다. 따라서 Main memory로 접근하는 지연시간에 의해서 각각의 코어의 스레드는 높은 레이턴시를 가진다.
해결 방안 1
#include <iostream>
#include <thread>
#include <windows.h>
#include <vector>
#define MAX (10000000)
struct alignas(64) AlignedInt {
int value;
};
AlignedInt totals[24];
void workerFunction(int id) {
const int ID = id % 4 + 1;
SetThreadAffinityMask(GetCurrentThread(), ID);
for (int i = 0; i < MAX; i++)
totals[ID].value += i;
}
int main()
{
int numThreads = 100;
std::vector<std::thread> threads;
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < MAX * numThreads; i++)
totals[0].value += i;
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "single core_ms: " << totalDuration.count() << std::endl;
}
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < numThreads; ++i) {
threads.emplace_back(workerFunction, i);
}
for (auto& th : threads) {
th.join();
}
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "multi core_ms: " << totalDuration.count() << std::endl;
}
}해당 코드는 2가지 방법을 사용하여 언급한 문제를 피하는 방식으로 구현했다. 먼저 window API인 SetThreadAffinityMask를 이용해서 특정한 코어에 해당 스레드의 작업을 고정하도록 했다. 그리고 alignas(64)를 사용해서 각각의 코어에서 사용하는 변수에 대해서 서로 캐싱되지 않도록 했다. 단점으로는 64바이트의 패딩을 넣는 것과 비슷한 효과를 가지기 때문에 필연적으로 공간이 낭비된다는 특성을 가진다는 점이 있다. 다만 이렇게 사용할 경우, 코어에 강제로 작업을 붙잡아두기 때문에, 스케줄링에서 굉장히 불리한 점을 가지게 되므로, 결국 성능이 느려진다. 테스트 에서는 스레드를 나누지 않은 것과 비슷한 성능을 보였다.
해결방안 2
#include <iostream>
#include <thread>
#include <windows.h>
#include <vector>
#define MAX (10000000)
int total;
void workerFunction(int id) {
const int ID = id % 4 + 1;
int tmp = total;
for (int i = 0; i < MAX; i++)
tmp += i;
total = tmp;
}
int main()
{
int numThreads = 100;
std::vector<std::thread> threads;
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < MAX * numThreads; i++)
total += i;
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "single core_ms: " << totalDuration.count() << std::endl;
}
{
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < numThreads; ++i) {
threads.emplace_back(workerFunction, i);
}
for (auto& th : threads) {
th.join();
}
auto end = std::chrono::high_resolution_clock::now();
auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "multi core_ms: " << totalDuration.count() << std::endl;
}
}방안 1번을 잊어도 될 정도로 엄청난 성능을 가지게 된다. MESI 프로토콜로 인한 문제를 완전히 피할 수는 없지만, 스케줄링을 강제하지 않음으로써 온전한 성능을 발휘할 수 있게되어 성능에서 굉장히 큰 이점을 가지게 되었다. 서버에서 온전히 특정 스레드 만을 스케줄링 한다고 가정한다면 1번 방안이 더 효과적일 수도 있겠지만, 대다수 2번의 방식이 효율적일 것이라 생각된다.