프로그램의 성능을 미리 예측하는 것은 매우 중요한 문제이다. 이 예측을 기반으로 다른 여러 유용한 일을 할 수 있기 때문이다. 최근 몇 달 간, 직렬 프로그램(serial program, 단일 스레드)을 병렬화했을 때 성능 향상이 얼마나 있는지를 미리 예측하는 방법에 대해 이런 저런 삽질을 해보았다. 별 대단한 내용은 아니고 익히 알려진 내용이지만, 병렬 프로그래밍에 대한 기초적인 내용과 몇 가지 흥미로운 사실을 이 글에서 좀 써본다.

요즘 블로그에 글을 한 달에 하나 겨우 쓰는데, 그래서 쓸 때 작정하고 그냥 길게 씁니다. 트위터/페이스북 시대에 매우 역행하는 처사인데 양해 부탁 드립니다.

1. 전통적인 단일 스레드 프로그램의 성능 예측

프로그램 성능 예측의 태초는 병렬 프로그램이 아닌 일반 단일 스레드 프로그램의 예측이다. 프로그래머가 직접 볼 일이 드물기는 한데, 이 일은 매번 일어난다. 바로 컴파일러 최적화가 가장 좋은 예이다. 컴파일러가 최적화를 할 수 있다는 소리는 “이렇게 코드를 바꾸면 성능이 좋아질 것이다”라는 예측, 좀 더 엄밀히 말하면, 정적인 예측(실제 프로그램을 돌리지 않고)에 기반했기에 가능한 얘기다. 이 예측은 너무나 단순한 다음 공식을 따른다:

N은 수행할 명령어 개수, T_inst는 명령어 하나를 수행하는데 걸리는 평균 시간. 이 정보를 알면 프로그램의 수행 시간 T를 자명하게 예측할 수 있다. 보다 풀어 쓰면 CPI, 명령어 당 평균 소요 사이클과 T_cycle, 사이클의 주기로 쓸 수 있다. 컴파일러 최적화는 대부분 수행 시간 T를 줄이는 것이 목표이다. 컴파일러가 클럭 속도를 조절할 수는 없으니 결국 수행될 명령어 개수를 최대한 줄이고, 실행 비용이 저렴한 명령어를 많이 써야 한다. 그래서 기초적인 컴파일러 최적화가 중복된 것을 없애고 연산 강도가 낮은 것으로 바꾼다. 물론 루프 풀기 같은 최적화는 다른 변수가 워낙 많아서 컴파일러의 최적화가 늘 좋은 것은 아니다. 이를 극복할 수 있는 방법으로 .NET/JVM 같은 곳에서 할 수 있는 동적 컴파일이나 PGO(Profile Guided Optimization)이 있다.

2. 병렬 프로그래밍에서의 성능 예측하기

“병렬 프로그램에서 성능 예측”은 사실 너무 광범위한 주제이므로 서두에서 말했듯이 다음의 문제로 국한한다:

어떤 직렬 프로그램을 병렬화 하기 이전에 미리 성능 향상(speedup)을 어떻게 알 수 있을까?

대부분의 병렬화 작업은 어떤 직렬 프로그램을 병렬 버전으로 바꾸는 것이다. 예전에 작성된 직렬 코드가 있다면 자명한 사실이고, 처음부터 병렬화가 고려된 코드를 작성한다 하더라도 보통 검증 용 직렬 프로그램을 두므로 “직렬 프로그램을 병렬화 하는 문제”을 일반적인 병렬화 문제로 생각해도 큰 문제는 없다. 컴파일러가 자동으로 병렬화할 수 있는 매우 제한적인 상황을 제외하면, 간단한 코드라도 병렬화를 직접 해서 성능을 측정하는 것은 너무 노고가 뒤따르니까 이를 미리 알 수 있으면 참 좋을 것이다. 자 그러면 어떻게?

아마도 이 문제에 대한 가장 간단한 답안은 그 유명한 암달의 법칙이다:

P는 프로그램 수행 시간 중 병렬로 처리될 수 있는 부분, N는 스레드/프로세서/코어 개수이다. 그러면 이 공식은 직렬 프로그램에 비해 병렬 프로그램이 몇 배나 빨라질 수 있는가(스피드업)를 구해준다. 암달의 법칙은 단순하지만 매우 중요한 가르침, 예를 들어, 80%가 병렬화 되더라도 프로그램의 스피드업은 최대 5 밖에 되지 않는다 처럼, 병렬화에 있어 직렬로 처리되어야 하는 부분이 결국 스피드업을 결정한다는 사실을 알려준다.

그런데, 암달의 법칙만 가지고 일반적인 직렬 프로그램의 스피드업을 예측하라는 소리는 F=ma만 가지고 새로 디자인하는 페라리 자동차가 시속 250Km로 달릴 때의 공기 마찰 저항을 구하라는 것과 같은 소리다. 기본적인 물리 법칙이 있더라도 이는 매우 이상적인 상황을 가정한 것이므로 실제 공학 문제에 적용할 수 없다. 풀고자 하는 특정 문제를 다시 엄밀히 정의하고 추상화해 유도된 또 하나의 모델을 만든다. 이걸로도 또 무리가 있으므로 각종 경험식과 커브 피팅을 동원해 실제 공학 문제를 푼다.

지금 이 문제도 딱 그러하다. 스피드업은 직렬 처리 부분의 비율이 근본적으로 결정하지만 다른 요소가 무척 많다. 따라서 이 스피드업 예측 문제를 아름다운 공식으로 모델링해서 변수 몇 개만 주면 풀 수 있기란 쉽지 않다. 자동차/항공기 풍동 실험과 같은 노가다를 해야그럴듯한 예측을 할 수 있다.

3. 동적 분석으로 병렬화 후의 성능을 미리 예측하기

암달의 법칙 이외에 지난 30년간 수많은 연구자들이 각종 모델로(예를 들어, 확률 기반) 병렬 환경에서의 성능 예측을 하려 노력을 했다. 그런데 이게 쉽지 않은 문제라 그 대안으로 동적 분석, 즉 프로파일링 기법으로 예측하고자 한다. 대표적인 방법으로 인텔 Parallel Advisor의 적합성 검사(Suitability)가 있다 (참고 PDF).

적합성 검사는 먼저, 직렬 프로그램에다 “어디를 병렬화할 것이다”와 “어디를 뮤텍스로 보호할 것이다”를 표기한다. 이 과정을 annotation (주석이라 번역이 되지만)이라 보통 부른다. Annotation은 그냥 일반적으로 코드에 부가 내용을 덧 기입하는 것이다. Parallel Advisor의 헤더파일을 #include하고 ANNOTATE_SITE_BEGIN(), ANNOTATE_LOCK_ACQUIRE() 과 같은 매크로를 원하는 부분에 넣으면 된다.

(여기서 “도대체 프로그래머가 무슨 수로 병렬화할 부분/보호할 부분을 알 것인가?”라는 매우 중요한 질문이 나온다. 이 병렬성을 발견은 또 다른 진짜 어려운 문제인데, Parallel Advisor는 정확성 분석이라는 것으로 어느 정도 방법론을 제시한다. 일단, 프로그래머가 대충 어디를 병렬화할 것인지 알 수 있다는 무책임한 가정을 하자.)

이렇게 annotation 노가다를 좀 뛰고, 우아하게 Visual Studio에서 Parallel Advisor의 적합성 검사 아이콘을 클릭한다. 그러면 프로그램을 실제로 돌리면서 분석하고 아래와 같은 예측 화면을 보여준다. 수행 소요 시간은 원래 프로그램의 1.2~3배 정도면 대부분 끝난다.

이 프로그램을 8 코어에서 돌리면 스피드업이 약 3.2 정도가 나온다는 예측이다.

이 적합성 검사에 대한 연구를 최근 좀 했다. 어떻게 하면 예측성을 더 높일 수 있을까라는 문제인데, 실제 인텔의 소스 코드를 가지고 작업할 수 없으니, 인텔의 적합성 검사와 기본 원리가 같은, 그렇지만 거의 나 혼자만 쓸 수 있는 발로 프로그램을 하나 만들었다. 코드의 양은 다 합쳐서 5천 줄 정도 밖에 안 된다.

아주 간단하게 원리를 설명하자면 annotation이 적힌 부분, 즉 프로그래머가 의도한 병렬화가 될 부분과 뮤텍스로 보호될 부분의 소요 시간을 측정한다. 수집된 소요 시간을 트리 구조로 만들고, 이 트리를 순회하면서 병렬화가 되었을 때의 수행 시간을 에뮬레이션하는 것이다. 말은 간단한데 쌍코피 좀 흘리면서 만들어야 한다. 패러럴 어드바이저에 있는 이 상용 코드는 한 명의 아키텍트와 두 명의 프로그래머가 최소 6개월 동안 만든 코드인데, 이걸 대충이나마 나 혼자 만드는 건 생각만큼 간단하지는 않다. (참고로 저 두 분의 프로그래머는 초짜가 아니고 20년 정도 컴파일러와 런타임을 만들던 분이다.)

4. 스피드업을 결정하는 여러 요소

그렇다면 왜 암달의 법칙 같은 간단한 수식 모델링으로 스피드업 예측이 어려운가? 스피드업을 결정하는 요소에 어떤 것이 있는지 나열해보자.

• (1) 반드시 직렬로 처리되어야 하는 부분: 암달의 법칙이 아주 잘 설명한다.
• (2) 임계 영역(critical section) 혹은 동기화: 병렬화 되더라도 동기화가 필요하다면 스피드업은 감소.
• (3) 작업 불균형: 병렬 처리가 되더라도 작업 간에 불균형이 있다면 스피드업은 심각하게 떨어질 수 있다.
• (4) 스케줄링 정책: 어떻게 여러 스레드에게 작업을 분배할 것인가도 매우 중요하다. OpenMP를 예를 들면, 정적/ 동적 스케줄링의 차이가 있고(참고 글), TBB나 Cilk에 있는 work-stealing 동적 스케줄링도 있다. 이 스케줄링은 직렬 부분에 해당하므로 오버헤드를 줄이는 것이 관건이다. 작업 불균형이 있다면 동적 스케줄링이 일반적으로 우수한 성능을 보인다.
• (5) 병렬화 오버헤드: 병렬화 자체에도 오버헤드가 따른다. 루프를 병렬화 했다면 스레드를 만들고(보통은 스레드 풀을 미리 만듦), 스레드로 일감을 보내고, 일을 마쳤을 때 기다리는(barrier 혹은 join) 작업이 필요하다. 특히 병렬화된 루프가 for 문 내에 있고 반복 횟수가 많다면 이 비용은 많을 수 있다. Lock을 잡는데 경쟁이 심하다면 또 문제가 될 수 있다. 중첩된 병렬화도(병렬화된 루프 내에서 또 병렬화) 오버헤드가 커질 수 있다.
• (6) 캐시 문제: 이제부터 어려운 문제가 나온다. 현대 컴퓨터에서 캐시가 성능에 미치는 영향은 상당하다. 직렬 프로그램이 병렬화되었을 때, 캐시에 대한 행동이 어떻게 변하는가에 따라 스피드업이 영향을 받을 수 있다. 병렬화가 되더라도 캐시 행동에 변화가 별로 없을 수도 있고, 좋은 쪽으로 변할 수도 있고, 또 나빠질 수도 있다. 뒤에서 실제 예로 자세히 설명.
• (7) 메모리 대역폭: 병렬화가 되면 동시에 여러 스레드가 작업하기에 메모리 대역폭이 모자랄 수 있다. GPU는 CPU보다 훨씬 많은 스레드가 동시에 돌아서 메모리 대역폭이 CPU보다 훨씬 크다. 보통 100GB/s를 훌쩍 넘는다. CPU에서는 최고 20~30GB/s가 보통이다.

암달의 법칙은 (1)만 고려 가능하고 몇몇 방법이 좀 더 (2)-(4)를 예측하려 노력하는데 실제 직렬 프로그램의 성능 향상을 현실적으로 예측하려면 결국 동적 분석이 답이다. Parallel Advisor나 내가 만든 프로그램은 (1)-(5)를 잘 고려해서 예측한다. 문제는 이제 캐시/메모리의 영향을 고려하는 것이다.

5. 실험 결과 1: 캐시로 인한 스피드업 정체

실제 어떤 벤치마크 프로그램에 대한 스피드업 예측 결과로 캐시와 메모리 영향을 살펴보자. 이런 영향을 받는 실제 프로그램을 찾는 것도 그리 간단하지는 않다.

위 두 그래프는 동일한 한 프로그램의 병렬화 후 성능을 내가 만든 프로그램으로 예측하고(Pred), 실제 미리 병렬화된 버전의 결과(Real)와 비교한 것이다. 실험 결과는 같은 프로그램을 대상으로 했고 입력 값의 크기만 다르다. 왼쪽은 입력 값이 작아 프로그램이 최대로 쓰는 메모리 양이 10MB 밖에 안 되는데, 우측은 입력 값이 커서 850MB의 메모리 사용률을 보인다. 이 프로그램은 OpenMP로 병렬화가 되었으며 크리티컬 섹션(뮤텍스)는 없다. 병렬화된 프로그램에서 스레드 사이에 데이터 공유는 전혀 없는 embarrassingly parallel한 형태이다.

실험은 Xeon (Westmere 구조) 6코어 프로세서가 두 개 있는 시스템에서 돌렸다. 각 프로세서는 12MB의 L3 공유 캐시가 있다. 전체적으로는 L3 24MB 캐시가 있는 셈.

보다시피 왼쪽의 경우, 즉 입력 값이 작을 때는 예측값이 상당히 적중했다. 예측은 위의 6가지 이유 중 (1)~(5)는 거의 완벽하게 고려한다. 이 예측력은 다른 실험으로도 충분히 검증했다. 현재 Parallel Advisor도 비슷하게 고려가 되었고 예측 결과도 거의 같다. 다만, 나는 실험 결과치를 잘 뽑고자 특별히 더 엄밀히 모델링 했을 뿐이다.

문제는 오른쪽의 그래프. 같은 프로그램이고 같은 부분이 병렬로 작동하는데 차이점이라면, 입력 값의 크기이다. 실제 프로그램은 10개의 스레드부터 성능에 병목이 생기기 시작했다. 그러나 나의 예측은 이를 고려 하지 못하고 계속 나아지는 것으로 보여준다.

추가 프로파일링 결과로 봐서는 메모리 대역폭은 문제가 되지 않았다. 사실 12 스레드 정도에서 메모리 대역폭이 후달리는 상황을 목격하기가 쉽지 않다. 완벽히 아무런 의미 없는 메모리 입출력만 해야 가능할 정도이다.

결국, 이 문제는 캐시가 원인이다. 각 스레드가 겪는 캐시 미스가 늘어나서이다. 이 프로그램은 각 스레드가 각자의 데이터만 쓰므로 데이터 공유가 없으니 캐시 코히런스 미스에 의한 것은 아니다. 따라서 스레드가 늘어남에 따라 유효(effective) L3 공유 캐시 크기가 줄어드는 것을 원인일 것이다. L3 캐시는 하나인데 여러 스레드가 자신의 데이터를 쓰고 지우고자 경쟁하니까 유효 크기가 줄어든다. 그러면, 각 스레드가 겪는 L3 캐시 미스 비율이 높아지고, 싱글 스레드 버전에 비해 더 많은 데이터를 메모리에서 가져와야 하므로 스피드업이 정체된다. 자 그렇다면 이걸 예측할 수 있을까? 이걸 하려면 별도의 프로파일링 데이터와 메모리/캐시 행동을 근사한 모델과 그에 따른 예측이 필요하다. 이하 자세한 설명은 생략.

6. 실험 결과 2: 캐시로 인한 스피드업 향상

이번에는 실험 결과 1과 반대의 상황을 볼 수도 있었다. 다른 프로그램을 가지고 또 실험을 해봤다.

이 프로그램은 비교적 매우 짧은 코드인데, 실제 프로그램이 보여주는 스피드업은 이상적이다. 12코어에서 스피드업이 거의 12라는 완벽히 병렬화가 된다는 이야기이다. 그런데 이번에는 예측값이 오히려 낮았다. 위에는 예측값이 더 오버하는 모습이었는데 이번에는 그 반대였다.

이걸 초선형(super linear) 현상이라 보기에는 다소 망설여진다. 초선형 현상은 늘어난 CPU 코어 개수보다 더 높은 스피드업을 얻는 경우이다. 4코어로 병렬화를 했는데 스피드업이 6이 되는 것 같은 현상이다. 이건 대부분 캐시의 영향이 긍정적으로 나타나서 그런 것으로 대표적으로 행렬 곱셈 예가 있다. 행렬 곱셈의 매우 단순한 버전을 그대로 병렬화하면 오히려 병렬화 버전에서 캐시 히트가 더 많이 나서 초선형 현상을 아주 쉽게 볼 수 있다.

이 경우는 12코어에서 12의 스피드업을 기록했으므로 초선형은 아니지만, 예측값보다 더 높은 실제 스피드업이 얻어졌으므로 초선형 상황과 유사한 일이 벌어졌다고 볼 수 있다.

일단, 이 경우는 당연히 L3 캐시 미스가 늘어나지 않았다. 더 이상의 분석은 못 해보았는데, 추측하기에는 L1/L2 캐시의 양이 늘어나서라고 본다. 예를 들어, 8코어의 경우와 12코어의 경우를 비교해보자. 지금 이 실험은 두 개의 6코어 프로세서에서 하고 있다. 8코어를 쓰는 경우라면, 현대 운영 체제는 각 소켓에 4개의 스레드를 할당한다. 그러면 이미 4개의 스레드는 총 24MB의 L3 캐시를 사용한다. 여기서 12코어로 늘어도 L3 캐시의 양이 느는 것은 아니다. 그런데 4코어에 더 있는 L1/L2 캐시의 양이 늘어나게 된다. L1 데이터 캐시(32KB), L2 캐시(256KB)는 코어마다 있다. 공유되는 것이 아니다. 따라서, L3 캐시 미스에 변함이 없다면 코어를 많이 쓰면 전체 L1/L2 캐시가 늘어나는 긍정적인 효과가 발생한다. 자, 과연 이러한 것도 예측이 가능한가라는 문제가 남는다...

결론:

• 병렬화 후의 성능 예측은 유용합니다.
• 동적인 방식으로 분석해서 기본적인 예측은 가능합니다.
• 그런데, 캐시와 메모리 영향을 이해하기란 쉽지 않습니다.

병렬화 성능에 대한 기본적인 이해를 이 글로 이해할 수 있었으면 좋겠습니다.