CPU의 비순차적 명령어 처리(Out Of Order Execution)
결론부터 말하자면, CPU는 코드 즉, 기계어로 번역된 명령어를 처리할때에
순차적으로 처리하지 않을 수 있다는 것이다.
다음의 아주 간단한 코드를 보자.
int A = 0;
int B = 0;
int WatchingA[100000000] = { 0 ,};
int WatchingB[100000000] = { 0 ,};
int main()
{
A = 4;
for (int i = 0; i < 100000000; ++i)
{
//A의 카운터가 증가하며 값을 기록하기로 한다.
A = i;
WatchingB[A] = B;
}
}
실행결과는? 당연히 모든 B의 값을 기록한 WatchingB에 0이 가득 차있다.
원하는 결과가 맞다.
그럼 별 문제가 아직 없다.
무엇이 비순차적이라는 말인가?
그래 그럼 이제 멀티스레드로 가본다.
int A = 0;
int B = 0;
int WatchingA[100000000] = { 0 ,};
int WatchingB[100000000] = { 0 ,};
void EntryA()
{
for (int i = 0; i < 100000000; ++i)
{
//A는 0 ~ 100000000 카운팅하며, 매순간의 B값을 순차적으로 기입한다.
A = i;
WatchingB[A] = B;
}
}
void EntryB()
{
for (int i = 0; i < 100000000; ++i)
{
//B는 0 ~ 100000000 카운팅하며, 매순간의 A값을 순차적으로 기입한다.
B = i;
WatchingA[B] = A;
}
}실행결과 이상한 값이 들어있음을 포착할 수 있었다.
실행을 거슬러 올라가보자. 양쪽 스레드가 출발했다.
잠깐만 시계를 멈춰보자.
A가 4일때, B의 값을 포착해 보았다. B는 9였다.
지금 두개의 스레드가 돌고있다.
포착되었던 9는 어떤 9일까?
1. B는 방금 막 갱신된 따끈따끈한 9일 수도 있고,
2. 아니면 A의 값을 기입하고 있던 9일 수 도 있다.
한가지 매우 확실한것은 A에서는 카운터가 4가되었고 그 다음에 B의 값을 포착했고, 9였다는 것이다.
이제 B가 A의 값을 관측하면 어떻게 나와야 하는지 유추해보자.
1.
상황을 가정해 A가 가져갔던 9의 값이 방금 막 갱신된 따끈따끈한 9라고 하자.
B도 이제 A값을 기록하러 가보자. WatchingA[9] = 4라고 하는 것이 타당하다.(뭐 5가 되었을 수도 있겠지.)
명백한 사실은 분명히 A가 B의 9라는 값을 가져가 감시배열에 기입하기 전에,
4로 자신의 카운터 값을 올렸다는 것이다.
방금나온 9를 A가 가져갔으므로, B가 값을 기입하러 가려하는 이 시점은, A가 4가 된 시점 이후다.
왜? A가 자신이 4가 된다음, 그 다음에 기입한 B가 9라고 했으니까.
그러니 방금 9가된 B는, 4라는 값을 얻을 수 있어야한다.
2. 헷갈릴수 있으니 다른 상황의 예시를 하나만 더 들어보자.
아까 그 B의 9가, 이제 딱 10이 되었다고 해보자.
그러니까 아까의 그 9는 10이 될랑 말랑 하는 상태의 9 였던 것이다.
A의 값을 가져와볼까? 그럼 당연히 4이상의 값이 나와야한다.
왜? A가 자신을 4로 올린다음, 그 다음에 B값 9를 가져왔고,
B가 10인된건 당연히 그 다음이다
이제 10이 된 B는 당연히 값을 A값을 가져오면 4 이상의 값이 나와야한다.
B가 9 일때도 이미 4가 되었다. 이미 10이되었으니 4이상인건 당연하지 않은가?
B의 값이 10일때는 당연히 A의 값은 4이상의 값이 되어야 한다.
A가 4로 바뀌고,
WatchingB[4] = 9,
B의 값이 10으로 바뀌었을 것이고,
WatchingA[10]의 값은 4이상의 값이 되어야 한다.
이런 상황이 항상 맞아 떨어지는지 보도록 하자.
void CheckOutOfOrder()
{
for (int i = 0; i < 100000000; ++i)
{
//A 기준에서 보도록하자.
//해당 시점의 B값?
int BValueInThatTime = WatchingB[i];
//인덱스 초과 방지.
if (BValueInThatTime == 99999999) continue;
//A 가 i일때 B값이 X라고 하자..
//A가 i로 값을 올린게 먼저, 그리고 B값인 X를 기록한게 그 다음이다.
//따라서, B의 다음턴 즉 B가 X+1 이 되었다면,
//A의 값을 보았을때 아직도 i의 값이 안되었으면 그건 Out Of Order이다.
if (i > WatchingA[BValueInThatTime + 1])
{
OutOfOrderCount += 1;
}
}
}돌렸을 때의 결과는 ?
다 틀렸다...
왜 이럴까? 컴파일러 최적화가 범인이구나 !!
그래서 각 변수에 volatile을 추가해보자.
#include <iostream>
#include <thread>
#include <atomic>
int OutOfOrderCount = 0;
volatile int A = 0;
volatile int B = 0;
volatile int WatchingA[100000000] = { 0 , };
volatile int WatchingB[100000000] = { 0 , };
void EntryA()
{
for (int i = 0; i < 100000000; ++i)
{
//A는 0 ~ 100000000 카운팅하며, 매순간의 B값을 순차적으로 기입한다.
A = i;
WatchingB[A] = B;
}
}
void EntryB()
{
for (int i = 0; i < 100000000; ++i)
{
//B는 0 ~ 100000000 카운팅하며, 매순간의 A값을 순차적으로 기입한다.
B = i;
WatchingA[B] = A;
}
}
void CheckOutOfOrder()
{
for (int i = 0; i < 100000000; ++i)
{
//A 기준에서 보도록하자.
//해당 시점의 B값?
int BValueInThatTime = WatchingB[i];
//인덱스 초과 방지.
if (BValueInThatTime == 99999999) continue;
//A 가 i일때 B값이 X라고 하자..
//A가 i로 값을 올린게 먼저, 그리고 B값인 X를 기록한게 그 다음이다.
//따라서, B의 다음턴 즉 B가 X+1 이 되었다면,
//A의 값을 보았을때 아직도 i의 값이 안되었으면 그건 Out Of Order이다.
if (i > WatchingA[BValueInThatTime + 1])
{
OutOfOrderCount += 1;
}
}
}
int main()
{
std::thread threadA = std::thread(EntryA);
std::thread threadB = std::thread(EntryB);
threadA.join();
threadB.join();
CheckOutOfOrder();
std::cout << "Out Of Order Count : " << OutOfOrderCount << std::endl;
}과연 결과는 ??
많이 줄기는 했다..
volatile을 추가해도 오작동이 저리 많은걸 보니 이건 컴파일러의 문제에 다른게 더 있다.
CPU가 명령어를 순차적으로 수행을 안한다.
CPU가 마음대로 메모리 읽기/쓰기 순서를 바꿔서 문제인거다.
#include <iostream>
#include <thread>
#include <atomic>
int OutOfOrderCount = 0;
volatile int A = 0;
volatile int B = 0;
volatile int WatchingA[100000000] = { 0 , };
volatile int WatchingB[100000000] = { 0 , };
void EntryA()
{
for (int i = 0; i < 100000000; ++i)
{
//A는 0 ~ 100000000 카운팅하며, 매순간의 B값을 순차적으로 기입한다.
A = i;
std::atomic_thread_fence(std::memory_order::memory_order_seq_cst);
WatchingB[A] = B;
}
}
void EntryB()
{
for (int i = 0; i < 100000000; ++i)
{
//B는 0 ~ 100000000 카운팅하며, 매순간의 A값을 순차적으로 기입한다.
B = i;
std::atomic_thread_fence(std::memory_order::memory_order_seq_cst);
WatchingA[B] = A;
}
}
void CheckOutOfOrder()
{
for (int i = 0; i < 100000000; ++i)
{
//A 기준에서 보도록하자.
//해당 시점의 B값?
int BValueInThatTime = WatchingB[i];
//인덱스 초과 방지.
if (BValueInThatTime == 99999999) continue;
//A 가 i일때 B값이 X라고 하자..
//A가 i로 값을 올린게 먼저, 그리고 B값인 X를 기록한게 그 다음이다.
//따라서, B의 다음턴 즉 B가 X+1 이 되었다면,
//A의 값을 보았을때 아직도 i의 값이 안되었으면 그건 Out Of Order이다.
if (i > WatchingA[BValueInThatTime + 1])
{
OutOfOrderCount += 1;
}
}
}
int main()
{
std::thread threadA = std::thread(EntryA);
std::thread threadB = std::thread(EntryB);
threadA.join();
threadB.join();
CheckOutOfOrder();
std::cout << "Out Of Order Count : " << OutOfOrderCount << std::endl;
}CPU가 메모리에 읽고 쓰는 순서를 맞추기 위해
std::atomic_thread_fence(std::memory_order::memory_order_seq_cst) 를 추가했다.
결과는 ?
깔끔하다.
우리가 원하는 대로 순차적으로 실행된다.
자 그럼 이런일이 왜 일어나는가??
아래의 그림을 보도록하자.
CPU가 파이프라인 스톨을 피하기위해 명령어 순서를 바꿔버리기 때문이다.
파이프라인에 대해서 약간은 이해하고 있어야 한다.
파이프라인을 간단하게 설명하고 넘어가면, CPU에서 이해하고 처리해야 하는 명령어는 몇개의
작은 작업으로 나누어지는데, 이 작업은 몇단계의 협업을 거쳐야하는 작업이다.
이 쪼개진 작업을 맡아서 전담하는 각 부서가 있다고 이해하자.
그러면 동시에 처리하면 안될까? 안된다. 순서가 있는 작업이다.
작은 작업이 하나 끝나면, 다음 부서로 넘기고, 또 넘어가고 해야 제대로 작업이 이루어진다.
예를 들어 어떤 프로세서에서 하나의 명령어가 작은 작업 6종으로 이루어진다고 하자.
그럼 총 6개의 부서에서 처리를 다해야 한개의 명령어가 비로소 다 처리가 되는거다.
대신 한 부서에서는 그 임무만 전담한다 Fetch 부서는 Fetch만. Decode 부서에서는 Decode만.
위의 그림이 약간 헷갈릴 수 있는데, 색깔 블럭에 대해 CPU의 각 부서들이 배치된 것이라고 생각하자.
각 부서가 노는 시간없이 이전 부서로 계속 일을 넘겨받아 계속 일하는것이 업무효율이 높은거다.
그런데 그렇지 못한경우가 생긴다. 바로 메모리 접근이다. 메모리 접근이 시간이 꽤 걸리는 일이다.
몇개의 부서가 놀고있다.
이게 파이프라인 스톨이다.
그래서 어떻게 하느냐. 최대한 노는 시간 없이 일을 처리하게 하기위해 명령어 순서를 바꿔버린다.
이래서 Out of order가 발생한다.
노는 시간이 없게 하려고 하다 보니 발생하는 일이다.
위에서 사용했던 memory fence 가 바로 이런 명령어의 실행순서를 바꾸지 못하게 한다.
메모리 접근때문에 늦어질 수 있는 거 아는데,
의도한 바가 있으니 순서대로 해라.
싱글스레드에서는 왜 문제가 보이지 않을까? C++ 컴파일러도 바보가 아니기 때문이다.
CPU가 파이프라인 스톨을 막기위해 명령어 순서를 바꿀 수 있다는 것을 알고있고,
명령어 순서가 바뀌어도 관계 없다고 판단하고 어셈블리어로 바꾼다.
허나 컴파일러는 다른 스레드의 존재까지는 알지 못한다.
이 메모리는 어짜피 안 바뀌겠지 누가 바꾸겠어? 스레드 하나에서 실행될 거 아닌가? 라고 생각한다.
그리고 이제 멀티스레드를 사용하면 의도하지 않은 결과가 나오게 되는 것이다.
'컴퓨터시스템' 카테고리의 다른 글
| 캐시메모리와 Cache Friendly Code (0) | 2022.04.03 |
|---|