메모리 일관성, CPU 메모리 접근방식

메모리 일관성

지금까지의 프로그램은 공유메모리에 대한 접근(쓰기/읽기)는 Atomic 하다고 가정하고 있습니다. 하지만 PC에서의 메모리 접근은 Atomic이 아닙니다. 메모리에 쓴 순서대로 메모리가 수정되지 않습니다. 매우 낮은 확률로 atomic하지 않게 나옵니다.

-> 정확히는 메모리에 쓴 순서대로 메모리의 내용이 관측되지 않음.

 

※ Atomic : 메모리의 접근이 순간적으로 행해지며, 서로 겹쳐지지 않고(메모리상에 읽거나 쓸때 서로 겹쳐지지 않음) 정해진 순서로 발생하며 모든 쓰레드에서 같은 순를 보인다.

 

피터슨 알고리즘 / 빵집 알고리즘의 문제점

• 컴파일러는 문제가 없다. (volatile과 디스어셈블리코드를 살펴봤을때 문제없음)
• 쓰고 읽는데, 옆에 쓰레드가 쓰기전에 값을 읽음

 

정말 Atomic하지 않게 돌아가는가?

atomic fence를 사용하여 실행순서의 역전을 막아보자

• 메모리 접근 순서를 강제하는 명령어 (_asm mfence)
• 앞의 명령어들의 메모리 접근이 끝나기 전까지 뒹의 명령어들의 메모리 접근을 시작하지 못하게 한다.

void p_lock(int my_id)
{
	int other = 1 - my_id;
	flag[my_id] = true;
	// fence로 이 기준에서 메모리 일관성을 가진다.
	// flag[my_id] = true; / victim = my_id; 는 순서대로 메모리접근이 일어난다.
	atomic_thread_fence(memory_order_seq_cst);
	victim = my_id;
	while (true == flag[other] && victim == my_id);
}

 

실행결과

제대로된 결과가 나온다.

 

메모리 접근이 Atomic하지 않은 이유는?

CPU가 기계어의 실행순서를 바꿔서 실행하는 경우가 발생함.

 

Out of Order(CPU) : CPU가 수행 할 수 있는것은 미리미리 수행해버림.

a = fsin(b);
f = 3;

a = b; // a,b는 cache miss
c = d; // c,d는 cache hit

 

CPU의 발전

<Classic (8bit CPU)>

한국산업기술대학교 게임공학부 정내훈교수님 멀티코어 프로그래밍 ppt 참고

예전에는 CPU가 한번에 하나씩 기능을 수행하였습니다.

 

<PipeLining (RISC CPU)>

한국산업기술대학교 게임공학부 정내훈교수님 멀티코어 프로그래밍 ppt 참고

이후 파이프라인이 추가되면서 할수 있는 작업은 미리미리 수행합니다.

 

<Super scalar (Pentium)>

한국산업기술대학교 게임공학부 정내훈교수님 멀티코어 프로그래밍 ppt 참고

.

.

.

Out of Order

ax = 1
bx = ax + 3

위와같이 만약 데이터 의존성이 있는경우 순서를 계속 미루어 처리한다고 가정한다면 계속해서 미뤄지게됨

 

성능향상을 위한 하드웨어 (x86 CPU)

한국산업기술대학교 게임공학부 정내훈교수님 멀티코어 프로그래밍 ppt 참고

Write Buffer: 캐시미스나면 WriteBuffer에다 써놓고 다음 일을 수행함

( Cache는 동기화가 되고 있지만 Write Buffer까지는 동기화되고 있지 않습니다. )

 

문제는 메모리

프로그램을 순서대로 읽고 쓰지 않는다. = atomic하지 않음

• voilatile로도 해결되지 않는다. (volatile은 compiler의 최적화 방지, CPU와는 연관이 없음)
• 읽고 쓰기 시간이 많이 걸림
• 옆의 코어에서 보면 어긋난 순서가 보인다, 또는 읽는 순서가 어긋난다.

 

어떠한 일이 벌어지는가?

[Case 1]

thread a			thread b
write(x,1)			write(x,2)
read(x,2)			read(x,2)

or

thread a			thread b
write(x,1)			write(x,2)
read(x,1)			read(x,1)

→ 이전 피터슨 알고리즘에서 발생했던 문제

[Case 2]

thread a			thread b
write(x,1)			write(x,2)
read(x,2)			read(x,1)

or

thread a			thread b
write(x,1)			write(x,1)
read(x,1)			read(x,0)

[Case 3]

thread a			thread b
write(x,1)			write(x,1)
read(x,0)			read(x,0)

or

thread a			thread b		thread c			thread d
write(x,1)			write(x,2)		read(x,1)			read(x,2)
							read(x,2)			read(x,1)

위와 같은 현상 모두 가능하다.

 

부정확해 보이는 결과가 나오는 이유?

• 현재의 CPU는 Out of Order실행을 한다.
• 메모리의 접근은 순간적이 아니다.
• 멀티코어에서는 옆코어의 Out of Order 실행이 관측된다.

 

[실습]

• Atomic하지 않은 메모리접근을 직접 확인해보자.
• 메모리 수정이 서로 다른 코어에서도 같은 순서로 관찰되는지 비교해보자.
• 메모리를 수정하면서도 다른쓰레드에서 수정한 내용을 기록한다.
• 두 개의 쓰레드에서의 기록을 비교한다.

Case 1

#include <iostream>
#include <thread>
#include <atomic>
using namespace std;

const auto SIZE = 5000'0000;
volatile int x, y;
int trace_x[SIZE], trace_y[SIZE];

void ThreadFunc0()
{
	for (int i = 0; i < SIZE; ++i)
	{
		x = i;
		//atomic_thread_fence( std::memory_order_seq_cst );
		// 다른 쓰레드의 메모리 read & write
		trace_y[i] = y;
	}
}

void ThreadFunc1()
{
	for (int i = 0; i < SIZE; ++i)
	{
		y = i;
		//atomic_thread_fence( std::memory_order_seq_cst );
		// 다른 쓰레드의 메모리 read & write
		trace_x[i] = x;
	}
}

int main()
{
	std::thread t_x{ ThreadFunc0 };
	std::thread t_y{ ThreadFunc1 };
	t_x.join();
	t_y.join();

	int count = 0;

	for (int i = 0; i < SIZE; ++i)
	{
		if (trace_x[i] == trace_x[i + 1])
		{
			if (trace_y[trace_x[i]] == trace_y[trace_x[i] + 1])
			{
				if (trace_y[trace_x[i]] == i)
				{
					std::cout << "X = " << trace_x[i] << " , Y = " << i << std::endl;
					count++;
				}
			}
		}
	}
	std::cout << "Total Memory Inconsistency : " << count << std::endl;
}

결과창

서로 다른순서로 메모리가 업데이트 되는 상황이 발생

 

Case 2

메모리 변경 순서가 뒤바뀔 확률은? - mfence로 오류를 없애보자.

void ThreadFunc0()
{
	for (int i = 0; i < SIZE; ++i)
	{
		x = i;
		atomic_thread_fence( std::memory_order_seq_cst );
		// 다른 쓰레드의 메모리 read
		trace_y[i] = y;
	}
}

void ThreadFunc1()
{
	for (int i = 0; i < SIZE; ++i)
	{
		y = i;
		atomic_thread_fence( std::memory_order_seq_cst );
		// 다른 쓰레드의 메모리 read
		trace_x[i] = x;
	}
}

결과창

Atomic하게 진행된다. 혹은 atomic<int>를 사용해도 0개의 결과가 나온다. 하지만 atomic 사용시 속도가 매우 저하된다.

(수업시간에는 atomic하지 않게 진행됬었던것 같다,,, atomic하지 않다고 가정하고 테스트를 더해보겠다.)

 

[실습2] 변수값을 변경하였을 경우 변경자체는 Atomic한가? 모든 비트가 한순간에 변하는가?

Case 1

#include <iostream>
#include <thread>

volatile bool done = false;
volatile int* bound;
int error{ 0 };

void ThreadFunc1()
{
	for (int i = 0; i < 2500'0000; ++i)
		*bound = -(1 + *bound);
	done = true;
}

void ThreadFunc2()
{
	while (!done)
	{
		int v = *bound;
		if ((v != 0) && (v != -1))
		{
			std::cout << std::hex << v << " _ " << std::endl;
			error++;
		}
	}
}

int main()
{
	bound = new int { 0 };

	std::thread t_1{ ThreadFunc1 };
	std::thread t_2{ ThreadFunc2 };
	t_1.join();
	t_2.join();

	std::cout << "Num of memory Error = " << error << std::endl;

	delete bound;
}

 

결과창

문제없다.

 

Case 2

int main()
{
	//bound = new int { 0 };
	int* big_array = new int[64];
	int addr = reinterpret_cast<int>(&big_array[31]);
	addr = addr / 64;
	addr = addr * 64;
	// addr = addr - addr % 64 이거랑 같다
	addr = addr - 1;
	bound = reinterpret_cast<int*>(addr);
	*bound = 0;

	std::thread t_1{ ThreadFunc1 };
	std::thread t_2{ ThreadFunc2 };
	t_1.join();
	t_2.join();

	std::cout << "Num of memory Error = " << error << std::endl;

	//delete bound;
}

 

결과창

bound에는 값이 잘들어가 있는데 v에는 이상한 값이 들어가 있다. bound가 가리키는 데이터가 두개의 캐시메모리에 걸쳐져서 그렇다. 캐시라인을 전송하는것은 atomic하게 전송된다. 하지만 캐시라인 2개는 두번의 걸쳐서 계산되었다.(ffff / ffff0000)

 

Case2 - Cache Line size Boundary

한국산업기술대학교 게임공학부 정내훈교수님 멀티코어 프로그래밍 ppt 참고

Cache Line size Boundary: write시 최종값과 초기값이 아닌 다른값이 도중에 메모리에 써지는 현상

• 포인터를 절대 믿지 마라
• Byte밖에 믿을 수 없다. (char도 가능)
• 포인터 사용시 정말 우려해서 사용해라

실습으로 알수있었던 메모리 일관성 특징 정리

• Consistency(무모순성)라고 불린다. 메모리가 순서대로 진행되지 않는다.
• Memory Consistency 또는 Memory Ordering이라고 불린다. (하드웨어에서 Out of Order을 없앨 순 없다.)
• 강한모델과 약한 모델이있고 각각 허용되는 결과들을 제한하는 정도가 다르다.
• 실제 컴퓨터가 제공하는 모델과 프로그래밍에 사용되는 모델을 동기화 명령을 사용해서 일치시켜야한다.

 

최종정리

• 멀티쓰레드에서의 공유 메모리
  • 다른코어에서 보았을때 업데이트 순서가 틀릴 수 있다. (read / write 둘다 문제)
  • 메모리의 내용이 한 순간에 업데이트 되지 않을때도 있다. 

※ 일반적인 프로그래밍 방식으로는 멀티쓰레드에서 안정적으로 돌아가는 프로그램을 만들 수 없다.

• 피터슨 알고리즘 / 빵집 알고리즘 같은 경우, 모든 메모리 순서를 프로그래밍 해주어야한다.(상당히 어려움)
  • 적절한 곳에 atomic thread fence를 사용해줘야함
  • 공유변수를 알맞게 atomic한 메모리 사용을 해야한다.

---

출처

한국산업기술대학교 게임공학부 정내훈 교수님 강의 - 멀티코어 프로그래밍