퀴즈 하나.

멀티 프로세서 시대가 개막하면서 "공짜 점심은 끝났다"는 표현을 많이들 한다. 똑같은 프로그램을 사용해도 프로세서가 빨라지면 수행 속도 역시 알아서 빨라지던 시기는 지나고 이제 멀티 프로세서를 효율적으로 이용하는 프로그램을 짜야 빠른 수행이 가능한 시기가 왔기 때문이다. 이러한 병렬적 확장성은 대개 프로그램이 얼마나 병렬성을 잘 확보했느냐에 달려 있는데, 이를 객관적으로 평가하기 위한 수치 역시 존재한다.

 

멀티 프로세서를 활용하여 병렬적으로 돌아가는 알고리즘을 평가할 때, 프로세서 숫자가 증가함에 따라 이루어지는 속도 향상 비율을 일반적으로 속도 향상율(Speedup)이라 한다. 이를테면 단일 CPU에서 5초 걸리는 특정 알고리즘을 병렬화하여 10개의 프로세서에서 돌리니 1초가 걸렸다, 이러면 속도 향상치는 5인 셈이다. 또한 이를 프로세서 갯수로 나눈 값은 효율(Efficiency)라 한다. 위의 예시에서 효율은 0.5이다.

 

N개의 프로세서를 이용하면 최대 N의 속도 향상율과 1의 효율을 가지는 것이 가장 이상적인 경우일 것이다. 이를 Linear speedup이라 하며, 이는 병렬 프로그램의 궁극점이라 할 수 있다. 하지만 동기화에 따른 오버헤드가 명백하게 존재하는 상황에 이렇게 이상적인 속도 향상율을 얻는 것은 불가능에 가깝다.

 

여기서 문제. 그렇다면 가능한 최고의 속도 향상 효율은 몇일까?

 

답안

정답 : 놀랍게도 1을 넘는다!

직관적으로 보면 말도 안 되는 결과이나, 실제로 이런 경우가 존재하며, 이를 Super linear speedup이라 한다. 즉, 4개의 프로세서를 썼는데 4.1배의 속도 향상이 나오는 것도 불가능이 아니라는 것.

이 것이 가능한 까닭은 현대 프로세서의 다층 캐쉬 구조에 있다. 요즘 프로세서들은 L1, L2 두 개의 캐쉬를 가지는 것이 일반적이다. 이 때 각각의 코어들은 고유한 L1 캐쉬를 가지고, L2 캐쉬를 공유하는 것이 일반적인 구조이다. 이 때 프로세서 숫자에 따라 프로세서에 근접한, 다시 말해 빠른 메모리인 L1 캐쉬의 크기 합이 커지는 것이 일반적이고, 이러면서 캐쉬에 상주하는 데이터의 비율이 커짐에 따라 속도 향상이 이루어진다는 것이다. 만약 병렬 처리되는 부분에서 동기화가 전혀 필요 없고, 부수 효과도 없어서 정확히 프로세서 수만큼의 속도 향상이 이루어질 때 이러한 속도 향상이 이루어진다면 1 이상의 효율을 보일 수도 있는 것이다.

사실 대부분 0.85~0.9 수준의 효율이 나와주기만 해도 대단히 잘 된 병렬화로 보기 때문에 Super linear speedup 같은 개념은 그냥 재미 삼아 알아두는 수준으로도 충분하다. 나 역시도 졸업 발표 때 발표를 듣던 교수님이 질문하시는 것을 보고 처음 안 개념으로, 대부분 이런 걸 가지고 뭘 하려고 하는 경우는 그리 많지 않을 것이다.