퀴즈: 다음 코드의 문제점은?

아래와 같은 간단한 멀티스레드 프로그램이 있다. 각 스레드가 각각의 변수에다 계산을 하는 코드이다. 코드 자체는 제대로 작동은 하지만 최적 성능의 관점에서 보면 문제점이 있는 코드다. 그래서 이런 코드가 멀티코어 CPU에서 빡세게 돌 때는 심각한 성능 저하가 일어날 수 있다.

테스트해보니 아래 코드는 내 컴퓨터 (Core 2 Duo E6400) 에서 약 1.37초가 걸린다. 그러나 문제점을 수정할 경우에는 대략 (릴리즈모드로 컴파일) 1.13초가 걸린다. 약 20%가 넘는 차이다. 만약 그냥 디버그 모드로 컴파일 할 경우에는 그 차이가 3배에 달한다. 한번 문제가 무엇인지 잘 생각해보고 최적의 성능을 얻기 위해 코드를 수정 해보세요.

코드는 윈도우 용이고 리눅스에서도 간단히 pthread로 만들 수 있음. volatile을 쓴 이유는 이 코드를 그대로 최적화 컴파일하면 for 루프가 그냥 사라지게 된다. 왜냐면 data1, data2를 아무도 참조하지 않기 때문에 그냥 날려버린다. 그래서 이걸 막기 위해 최적화를 하지마라는 의미에서 volatile이 필요하다.

이 코드는 듀얼 코어 이상에서만 코드 수정으로 성능 차이를 목격 할 수 있다. 그리고 for 루프에서 계산하는 data1, data2 전역 변수는 다른 스레드가 그 중간 값을 관찰할 수 있어야 한다는 조건이 더 있다. 즉, for 루프 계산을 로컬 변수로 대체하는 것 말고, for 계산 부분에서 전역 변수 업데이트는 그대로 둬야만 한다.

#include <windows.H>
#include <stdio.H>
#include <tchar.H>

volatile int data1;
volatile int data2;

DWORD CALLBACK TestThread1(void* /*arg*/)
{
for (int i = 0; i < 500000000; ++i)
data1 = data1 + 1;
return data1;
}

DWORD CALLBACK TestThread2(void* /*arg*/)
{
for (int i = 0; i < 500000000; ++i)
data2 = data2 + 1;
return data2;
}

int _tmain(int argc, _TCHAR* argv[])
{
HANDLE thread[2];
SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);

DWORD startTime = GetTickCount();
thread[0] = CreateThread(NULL, 0, TestThread1, (LPVOID)0, 0, NULL);
thread[1] = CreateThread(NULL, 0, TestThread2, (LPVOID)0, 0, NULL);
WaitForMultipleObjects(2, thread, TRUE, INFINITE);
_tprintf(_T("%d\n"), GetTickCount() - startTime);
return 0;
}
by object | 2008/04/15 12:42 | 컴퓨터 | 트랙백(2) | 덧글(15)
트랙백 주소 : http://minjang.egloos.com/tb/1845004
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from eslife's me2.. at 2008/04/15 19:04

제목 : 사진찍는프로그래머의 생각
퀴즈: 다음 코드의 문제점은? 세상에는 고수들이 너무 많타. 차마 댓글이 끼어 물을 흐릴 수도 없고 그냥 멍하니 글만 보고 나왔다....more

Tracked from rein's world at 2008/05/24 21:34

제목 : Locality 그리고 false-sharing
object님의 art.oriented 블로그에서 얼마 전에 false-sharing이 일어날 경우에 성능이 떨어지는 것에 관해 퀴즈를 내고 / 정답과 설명을 한 적이 있다. 퀴즈에서는 false-sharing이 아주 극단적으로 일어......more

Commented by 까막 at 2008/04/15 13:06
DWORD CALLBACK TestThread1(void* /*arg*/)
{
int local_data = data1;
for (int i = 0; i < 500000000; ++i)
local_data = local_data + 1;
data1 = local_data;
return data1;
}

아닌가요?
Commented by 이홍석 at 2008/04/15 13:08
암만 봐도 잘 모르겠네요.. -_-;;;
코드만 봐서는 ++data1 로 바꾸면 cpu 연산은 쫌 줄어들 것 같은데
이건 쓰레드랑은 별 상관없는 것 같아서 답이 아닌 것 같구;
자 밑에 분 정답 풀어주세요
Commented by object at 2008/04/15 13:11
까막: 아하! 그렇게 해도 되는군요! local_data에도 volatile을 붙여서 돌리면 최적의 시간과 같은 시간이 나옵니다.

그러면 제한 조건을 하나 더 추가하죠. for 루프에서 계산하는 data1, data2를 다른 스레드도 볼 수 있다는 조건을 달아보죠. 즉, 까막님처럼 로컬 변수로 대체할 수 없다는 조건을 달아보겠습니다.
Commented by kc at 2008/04/15 13:23
지난 번에 한번 글 올리셨던 내용인 거 같네요.
두 프로세서의 케시(?)에 의한 효과 아닌가요?
data1과 data2를 약간(64바이트 정도 였던가?) 떨어뜨려 놓아야 하는 거 아닌가요?
Commented by 자연풍선생 at 2008/04/15 13:34
듀얼코어 이상에서만 성능차이를 볼 수 있다고 하신 힌트로 봐서는 혹시 코어 하나당 스레드를 하나씩 계산하게 해서 스위칭으로 인한 시간손실을 없에는 것이 아닐까 하는 생각이 들긴하는데요. 확실하진 않네요.

기존의 코드가 코어2개가 1개의 스레드를 나눠서 연산하고 리턴후에 다른 스레드를 연산한다면, 코드를 수정해서 각각의 코어가 스레드를 1개씩 가지고 연산을 하는 방식으로 코드를 고치는 것이 가능하다면 시간이 단축되지 않을까요? 근데 어떻게 코드를 수정해야 하는지는 모르겠네요.;;;
Commented by uriel at 2008/04/15 13:36
지금 Visual Studio가 안깔려서 테스트는 못하겠는데, data 증가시키는 부분을 InterlockedIncrement로 바꾸는 것 아닌가요?
Commented by rein at 2008/04/15 14:00
data1, data2가 cache alaign 되어 있지 않아서 속도가 느린 문제가 아닐까 하는데요 :)
둘 사이에 cache 커밋?되는 크기 만큼의 패딩을 두면 빨라질듯합니다. intel TBB malloc()도 저렇게 cache-align안되면 느려지는 것 때문인지, 캐쉬 크기 단위로 얼라인 맞춰서 할당해주는 애가 있더군요
Commented by 까막 at 2008/04/15 14:32
object: 오랜만의 코드대화이군요.
그런데 제 기억으로는 듀얼코어가 아니더라도 성능향상이 어느정도 있었던 걸로 기억합니다. 스택에 생성된 변수와 전역에 생성된 변수는 접근하는 코스트가 다르더군요.
Commented by 까막 at 2008/04/15 15:04
언뜻 생각하기에는 저런 형태로 data1과 data2를 선언하게 되면 같은 페이지 안에 두 변수가 존재를 하게 되고, Thread1(혹은 Thread2)이 값을 writing하게 되면 Cache invalidation이 일어나면서 성능 저하가 발생한다. 라는 소설을 써보고 있습니다. :)

이게 문제라면 두 변수의 간격을 충분히 벌려주면 될듯 한데.. 지금 머릿속에는 힙에다 메모리를 잡는 방법외에는 딱히 떠오르는게 없군요.. 쿨럭;
Commented by 청어 at 2008/04/15 18:20
그것 외에도 VS2005 이상에서는 volatile 을 이용하게되면 메모리 가드가 발생해서 메모리 억세스 할 때 시간이 많이걸립니다. 원인은 캐시 업데이트 때문에 생기는 것이 맞고요.
Commented by Lyn at 2008/04/16 01:12
이홍석 // ++data1 과 data = data + 1 은 생성되는 바이너리가 완전히 동일하다는..
Commented by object at 2008/04/16 05:31
kc님이 정답입니다. 까막님도 약간의 용어는 틀렸지만 cache invalidation 때문에 그렇습니다. 시간 날 때 정리해서 자세하게 올려보겠습니다. malloc으로 얻어진 메모리 공간도 똑같이 이런 문제를 겪을 수 있습니다. 그래서 rein님이 언급한 것 처럼 TBB같은 라이브러리에서는 malloc도 보다 특수하게 처리합니다.
Commented by ogre at 2008/04/17 14:11
움,~ 제 컴 cpu가 펜티엄 D 900 에서 테스트 해보니,
volatile int data1;
volatile int data0[31]; //펜티엄 D 의 cache line size 128byte? //Core 2 DUO 면 64Byte 를~
volatile int data2;
근데요, 싱글코어에서도 동일한 문제가 있는것이 아닌가여? core 2 duo 는 shard L2때문에 문제가 더 된다는 말씀인건가여?...
Commented by 이홍석 at 2008/04/18 06:14
흑.. for 문도 날려먹을까봐 volatile 붙여드려야 하는 컴파일러님을 제가 너무 무시했습니다 -_-;;
깊이 있는 지식 배우고 갑니다 꾸벅
Commented by kkamagui at 2008/04/18 08:08
와우~ 멋진 글 잘 보고 갑니다. ;) 덕분에 많은 생각을 하게 되었습니다.
Dual Core에서 Cache 문제가 있을 것이라고 막연히 생각을 했는데, 이 정도까지 성능에 차이가 있을 줄은... ㅠ_ㅠ
앞으로도 좋은 글 많이 부탁드립니다. ^^

:         :

:

비공개 덧글

<< 이전 페이지 다음 페이지 >>





by object 2008 이글루스 TOP 100
최근 등록된 덧글
최근 등록된 트랙백
민영의 생각
by kkung's me2DAY
IT분야에서, 일이 더딘 사..
by Effortless - 上善若水 - ..
메뉴릿

한RSS 구독자수 website counter

한RSS에 추가

Add to Google

rss

skin by 이글루스