멀티프로그래밍 위키로 바로가기 → http://www.devnote.net/wiki
브라운 대학의 Maurice Herlihy 교수가 쓰던 책이 드디어 출간 되었습니다. 제목은 The Art of Multiprocessor Programming 입니다. 제가 자주 다니는 Barns & Noble 서점에 벌써 전시되어 있더군요. 가격이 $69.99 여서 좀 망설였지만, 그만한 가치는 있다고 생각해 구입하고 말았습니다.

책 값이 비싼 것은 멀티프로세서 프로그래밍에 관한 좋은 서적이 그리 많지 않기 때문이지 않을까 생각합니다. 사실 이 책의 draft 버전이 작년에 많은 부분 이미 공개된 적이 있어, pdf파일을 통해 읽었기 때문에 이것이 또 책 구입을 망설인 이유 중의 하나입니다.

이 책은 대학 교재 스타일로 되어 있어, 멀티프로세서 혹은 멀티코어 프로그래밍을 처음 공부하기에 좋을 것 같습니다. 다만, 그동안 발표된 논문들을 요약 정리한듯하여 실제 응용에 있어서는 좀 부족한 점이 있고, 가격에 비해 제본 상태나 폰트가 별로 정성을 들이지 않은 것 같습니다. 아마 빨리 출간하려고 신경을 쓰지 못한 것이 아닌가 생각됩니다.


크리에이티브 커먼즈 라이센스
Creative Commons License

어제 얼마전 발표된 Microsoft Parallel Extensions to .NET Framework 3.5 2007 CTP 설치하여 살펴보았습니다. MS Research와 공동 개발하고 있다는 이 Parallel FX 라이브러리는 .NET에서 비교적 쉽게 병렬처리를 가능하게 해주고 있습니다. 자세한 내용은 아래 MSDN 기사에서 링크에서 찾아볼 수 있습니다.


그런데, 이 Parallel FX Library가 어떻게 구현되었을까하는 궁금증을 가지고 있던 차에, .NET 바이너리를 디컴파일하여 소스를 보여주는 .NET Reflector 덕분에 내부를 들여다 볼 수 있었습니다.

간단히 말해 기본 구조는 MIT 대학에서 개발되었던 Cilk 에서 많은 부분을 빌어 왔다는 것을 알 수 있었습니다. Cilk는 1990년대 중반부터 개발되어 온 것이며 Work Stealing이라는 작업 스케줄링 개념을 만들어 내었습니다. .NET PFX도 Work Stealing을 그대로 적용시키고 있습니다.

PFX에서 핵심적으로 사용되는 자료구조 중에 "ConcurrentStack", "ConcurrentDeque (TakeQueue)", "ConcurrentListBag" 가 사용되고 있는데 이들은 대부분의 경우 Lock-free로 동작하도록 되어있습니다. .NET Reflector를 이용하면 소스를 살펴 볼 수 있습니다. 이들도 MS가 새로운 알고리즘을 개발한 것은 아니고, 모두 기존에 발표되었던 논문에 바탕하여 .NET에 적용한 것입니다.

하지만, NET의 Garbage Collector의 도움으로 이러한 Lock-Free 자료구조 제작이 C/C++에 비해 손쉽게 되었습니다. 다시 말해 Lock-Free의 난제들 중의 ABA문제와 메모리 액세스 문제(다른 스레드가 해제한 메모리를 참조하려고할 때 메모리 액세스 오류의 가능성이 있음)가 Garbage Collector로 인해 자동으로 제거되었다는 것입니다.

좀 극단적으로 말하면 PFX는 Cilk의 .NET 버전이라고 할 수 있습니다. 그만큼 Cilk에서 많은 부분을 빌어왔지만, 그다지 혁신적인 내용이 추가되지는 않았다는 것 입니다.

Java를 이용한 JCilk가 이미 발표된 지금, 늦은 감이 있으나 MS는 PFX 라이브러리로 .NET에서 병렬프로그래밍을 손쉽게 제공하려고 노력하고 있음을 알 수 있습니다. 하지만, 이것이 성공할지는 조금 더 지켜봐야 할 것 같습니다.

크리에이티브 커먼즈 라이센스
Creative Commons License

아래 위키 페이지에 윈도우즈의 LFH와 Hoard의 비교를 위해 만들었던 멀티스레드 메모리 테스트 프로그램의 소스를 공개하였습니다. 결과가 LFH가 상당히 좋게 나와 테스트에 문제가 있나 보고 있었지만, 별다른 문제는 없어 보입니다. 테스트 환경은 Intel Quad Core + 윈도우즈 비스타 입니다.

http://devnote.net/wiki/index.php/Windows_Heap_Memory
크리에이티브 커먼즈 라이센스
Creative Commons License

Visual C 2005에는 많은 Intrinsic 함수가 추가 되어 있습니다. 그 중 Lock-Free를 위해 많이 사용되는 Atomic Operation이 대부분 Intrinsic 함수로 지원되는데, 이것은 inline assembly를 사용하는 것과 동일한 효과를 발휘합니다.

아래 32비트 디스어셈블리 코드를 보면 Intrinsic 함수인 _InterlockedExchangeAdd 사용함으로써 함수 호출 없이 바로 에셈블리 코드가 삽입되는 것을 볼 수 있습니다.

   InterlockedExchangeAdd(&inc2, 0xffff);
00401001  push   0FFFFh
00401006  lea    eax,[esp+4]
0040100A  push   eax 
0040100B  mov    dword ptr [esp+8],1234h
00401013  call   dword ptr [__imp__InterlockedExchangeAdd@8 (402000h)]
   _InterlockedExchangeAdd(&inc2, 0xffff);
00401019  mov         ecx,0FFFFh 0040101E  lea         edx,[esp]
00401021  lock xadd   dword ptr [edx],ecx


Intrinsic 함수는 특히 inline assembly가 지원되지 않는 64비트 프로그램 제작에 매우 유용한데 아래 x64 디스어셈블리 코드를 보면, Intrinsic 함수가 아닌 윈도우즈 API함수도 Intrinsic과 동일하게 최적화 되고 있는 것을 알 수 있습니다.

   InterlockedExchangeAdd(&inc2, 0xffff);
0000000140001008  mov         eax,0FFFFh
000000014000100D  lock xadd   dword ptr [inc2],eax
   _InterlockedExchangeAdd(&inc2, 0xeeee);
0000000140001013  mov         ecx,0EEEEh
0000000140001018  lock xadd   dword ptr [inc2],ecx

크리에이티브 커먼즈 라이센스
Creative Commons License

Lock-Free에 관해 2004년 말에 CUJ에 연재되었던 기사를 소개합니다. Andrei Alexandrescu와 Maged Michael이 쓴 기사로 Lock-Free 자료구조를 처음 접하는 사람들에게 매우 유익한 내용입니다.

http://erdani.org/publications/cuj-2004-10.pdf
http://erdani.org/publications/cuj-2004-12.pdf

아래 10월 기사 중 일부를 발췌하여 번역하였습니다. 2004년말 Lock-free 프로그래밍 전문가가 대여섯명 정도일 거라고 말했으니, 지금은 몇 명이나 될까요?

In fact, there must be around half a dozen of lock-free programming experts around the world, and yours truly is not among them. With luck, however, this article will provide you with the basic tools, references, and enthusiasm to help you become one.

사실, 전세계에 lock-free 프로그래밍 전문가는 분명 대여섯명 정도 있으며, 당신은 그 중 한사람은 아닐 것입니다. 그러나, 운이 좋다면, 이 글이
당신이 lock-free 전문가가 되는데 도움을 줄 기본적인 도구와 참고자료 그리고 열정을 제공해 줄 것입니다.
크리에이티브 커먼즈 라이센스
Creative Commons License

전에 윈도우즈 비스타 힙(Heap) 메모리 관리자의 성능향상에 관해 언급한 적이 있습니다. 이 성능향상은 대부분 멀티코어나 멀티프로세서 컴퓨터에만 해당됩니다. CPU가 하나인 컴퓨터에서는 오히려 성능을 저하시킬 수도 있습니다.

저는 요즘 Maged Michael의 알고리즘에 기반한 Lock-Free 메모리 관리자를 만들고 있습니다. 조만간 멀티프로그래밍 위키에 소스 코드와 함께 공개하려고 합니다. Maged Micheal은 Lock-Free 분야에 몇 안되는 전문가로, 특히 그가 쓴 논문들은 매우 복잡하고 어려운 알고리즘을 최대한 심플하게 최적화시켜 놓았으며 바로 실제 프로그래밍에 응용할 수 있는 내용이 주를 이루고 있어, 제가 가장 좋아하는 스타일입니다.

제가 개발한 Lock-Free 메모리 관리자와 윈도우즈의 LFH(Low Fragmentation Heap)와의 성능 비교를 해본 결과 10%이상 더 빠른 것으로 나타나고 있습니다만 여러 가지 테스트 설정 변수들을 변경할 때마다 조금씩 다른 결과가 나오고 있습니다. 때로는 윈도우즈 LFH가 더 좋은 성능을 보이고 있습니다. Lock-Free 메모리 관리자를 만들다 보니 Lock-Free 프로그래밍이 얼마나 어렵고 디버깅하기 힘든 것인지 다시 깨닫고 있습니다.

윈도우즈의 LFH는 거의 Lock-Free로 이루어져 있고 이미 운영체제에서 지원되고 있어 상당히 많은 테스트를 거쳐 검증된 것으로 보입니다. 따라서, 만약 멀티스레드로 이루어진 상용 프로그램을 개발하고 있는데, 메모리 alloc/free가 병목현상을 일으킨다면, 저는 별도로 메모리 관리자를 개발하지 말고 LFH를 사용하도록 적극 권장합니다. (윈도우즈 비스타에서는 LFH를 실행시간 중에 자동으로 사용하도록 하고 있기도 합니다.) 단, LFH는 윈도우즈 XP이상에서만 지원됩니다. 그리고 Lock-Free 메모리 관리자들은 기본적으로 super block이라는 비교적 큰 메모리 블럭을 단위로 사용하고 있어 기존 memory allocator에 비해 보다 많은 메모리를 사용한다는 것을 기억하시기 바랍니다.


크리에이티브 커먼즈 라이센스
Creative Commons License

XP이후 5년만에 새로운 운영체제인 윈도우즈 비스타가 드디어 출시되었습니다. 마이크로소프트사 회장인 빌게이츠는 이번 릴리즈 이벤트에 맞춰 NBC "Today" 쇼를 비롯한 ComedyCentral쇼에 출연하며 비스타와 오피스 2007을 선전하기 위한 세일즈맨 모드로 뛰고 있습니다.

빌게이츠란 인물 자체가 상당한 영향력을 갖기 때문이기도 하지만, 한 대기업의 회장이 새로운 제품 선전을 위해 뛰는 모습은 우리나라에선 보기 힘든 일이지요. 얼마전 애플사의 스티브 잡스 또한 CES에서 iPhone을 소개하였는데, 그의 열정적인 모습만으로도 보는 사람들을 즐겁게 해주었다고 합니다.

그런데, 에어로(Aero)를 비롯한 세련된 UI 외에 비스타는 어떤 점이 좋아 졌을까요? 우연히 메모리 관리에 관한 자료를 찾다가 발견한 몇가지 힙 메모리에 관련된 내용을 적어 보기로 하겠습니다.

MS 힙메모리 개발자인 Adrian의 작년 DefCon에서의 발표자료에 따르면, 비스타에서는 보안 기능 강화와 멀티코어나 멀티프로세서 환경에서 엄청난 성능 향상이 있다고 합니다. 이 자료는 비스타가 메모리 Fragmentation 시나리오에서 6,000에서 7,000배 더 많은 초당 메모리 연산을 보인다고 합니다. 물론 믿기지 않습니다만.

정확한 테스트 방법을 공개하지 않아 자세한 사항은 모르겠으나, 일반적인 경우가 아니라 최악의 상황을 멀티 프로세서나 멀티 코어 컴푸터에서 64비트 운영체제를 사용하여 테스트 한 것으로 짐작됩니다.
이것을 그냥 비스타가 정말 좋아졌다라고 받아들이기 전에, 바꾸어 생각하면 비스타 이전의 XP나 윈도우즈 2003의 힙메모리 관리자는 멀티프로세서에서 문제가 많다라는 말로도 생각할 수 있습니다. 이 자료는 윈도우즈 2003 SP1에서 초당 12~400 연산 밖에 수행하지 못하는 것으로 나와 있습니다.

아래 그래프는 Adrian이 Channel 9 인터뷰에서 언급한 것을 제가 다시 그린 것입니다. 보시다시피 비스타는 스레드 개수가 늘어날수록 선형으로 속도향상을 보이고 있고 기존의 윈도우 힙은 성능이 떨어지는 것을 볼 수 있습니다. (여기서 물론 "스레드 개수 = 프로세서 개수"일 때 까지만 성능향상이 일어납니다)  X축은 1부터 시작하며 비스타 힙은 스레드가 한개일 경우는 일반 힙에 비해 약 5~10% 저조한 성능을 보인다고 합니다. (이것은 CPU가 하나인 시스템에서는 오히려 성능 저하가 나타날 수 있다는 말이기도 합니다.)



이러한 비스타 힙메모리 성능향상은 어디서 왔을까요? 주요 원인 중의 하나는 Low Fragmentation Heap의 사용입니다. LFH는 이미 Windows XP와 2003 에 적용되었으나 디폴트로 사용되지는 않았으며 프로그램상에서 HeapSetInformation API를 호출하여야 하는데, 이 기능을 사용하는 응용프로그램은 거의 없었습니다. 비스타에서는 LFH를 실행시간 중에 자동으로 사용하는 오토 튜닝 기능이 추가되었습니다.

LFH는 내부적으로 Lock-Free 데이터 구조로 이루어져 멀티프로세서나 멀티코어 시스템에서 좋은 성능을 보입니다.

아래표는 제가 제작한 힙 메모리 테스트 툴을 이용하여, 윈도우즈 2003 에서 일반힙과 LFH의 초당 메모리 연산성능을 비교한 것입니다. Xeon 3.00 GHZ 4 CPU 시스템에서 테스트하였습니다. LFH가 약 6배에서 7배까지 높은 성능을 보이고 있습니다.



LFH의 단점은 전체 메모리 사용량(Memory footprint)이 일반 힙에 비해 크다는 것입니다.

또다른 성능향상 요인은 병렬성을 높이기 위한 힙 내부 알고리즘과 데이터 구조의 최적화 입니다.  Adrian의 슬라이드 자료만으로는 이러한 알고리즘과 데이터 구조가 얼마나 많은 성능향상을 가져왔는지 짐작하기 힘듭니다. 제가 비스타를 구할 수 있게되면 테스트 툴을 사용하여 다시 확인해보도록 하겠습니다. 이밖에도 보안 강화를 위한 포인터 랜덤마이징이 사용되었다고 하는데, 이로써 힙 메모리 할당 과정에서 같은 주소를 되돌리는 확률을 낮췄다고 합니다.

어쨋거나 결론적으로 현재 윈도우 XP나 2003의 힙 메모리 관리자는 멀티코어나 멀티프로세서 시스템에 적합하지 않다는 것입니다.

그러나, 이것이 비스타가 XP보다 성능이 좋다는 말은 절대로 아닙니다. 실제로 여러 벤치마크테스트에서 이미 XP가 비스타 보다 좋게 나와 있습니다. 비스타에 추가된 새로운 여러 기능과 서비스들로 인해 많은 메모리 사용과 성능 저하를 보이고 있으며 힙 메모리 관리자 때문은 아닙니다. Windows 7에서 이러한 문제들이 해결된 것으로 보입니다. 비스타의 문제점들을 해결한 것이 결국 Windows 7이라는 말이 나오고 있습니다.


크리에이티브 커먼즈 라이센스
Creative Commons License