코어를 열 배 늘렸는데 왜 다섯 배만 빨라질까: 암달의 법칙
여러 사람이 해도 한 줄로 서야 하는 일
이삿짐을 나르는 사람이 늘면 운반은 빨라진다. 하지만 모두가 출입증 하나를 돌려 쓰거나, 마지막 확인을 한 사람만 할 수 있다면 기다리는 시간이 남는다. 칩의 코어를 늘리는 일도 비슷하다. 계산기를 여러 개 준비해도 실제 작업을 동시에 나눌 수 있는지가 먼저다.
프로그램에는 서로 독립적으로 진행할 부분과 앞선 결과를 기다려야 하는 부분이 섞여 있다. 후자의 실행시간은 코어를 추가했다고 저절로 줄어들지 않는다. 병렬화의 한계를 설명하는 암달의 법칙은 이 단순한 사실을 시간의 비율로 표현한다. 핵심은 같은 크기의 문제를 더 빨리 푼다는 조건이다. 작업량을 함께 늘리는 실험과는 다른 질문이다.
10%가 남으면 속도에는 천장이 생긴다
한 코어에서 걸린 시간을 기준으로 직렬 부분의 비중을 s, 같은 처리 능력을 가진 코어 수를 n이라고 하자. 나머지 작업이 완벽히 고르게 나뉘고 추가 비용이 없으면 속도 향상 S는 다음과 같다.
S(n) = 1 / [s + (1 − s) / n]
S는 기존 실행시간을 새 실행시간으로 나눈 값이다. s는 소스코드 줄 수나 함수 개수의 비율이 아니다. 같은 입력을 한 코어에서 실행했을 때 실제로 소비한 시간의 비율이다. 코드 몇 줄의 반복문이 전체 시간 대부분을 차지할 수도 있다. NVIDIA, 고정 문제 크기와 암달의 법칙
설명용으로 100초짜리 작업 중 10초는 직렬이고 90초는 완전히 나눌 수 있다고 하자. 코어 열 개에서는 10초에 9초를 더해 19초, 속도 향상은 약 5.26배다. 코어 백 개라면 10.9초로 약 9.17배다. 아무리 늘려도 처음의 10초가 남으므로 이 모형의 상한은 10배다.
흥미로운 점은 병목의 비중이 달라진다는 것이다. 처음에는 전체의 10%였던 직렬 작업이 열 코어 실행에서는 절반을 넘게 차지한다. 빨라진 프로그램을 다시 측정하면, 전에는 작아 보였던 구간이 최적화의 중심이 된다.
나누고 다시 모으는 비용도 계산해야 한다
현실의 병렬 작업은 공짜로 시작되지 않는다. 일을 배분하고 데이터를 옮기며, 서로 맞춰야 하는 지점에서 기다린다. 작업량을 똑같이 나누어도 입력에 따라 어떤 코어가 더 오래 걸리면 다른 코어는 마지막 주자를 기다린다. 이를 부하 불균형이라고 한다.
추가 지연을 원래 한 코어 실행시간으로 나눈 값을 o(n)이라고 놓으면, 단순한 확장 모형은 다음처럼 쓸 수 있다.
S(n) ≈ 1 / [s + (1 − s) / n + o(n)]
o(n)은 코어 수에 따라 달라질 수 있는 무차원 추가 비용이다. 앞의 100초 예에서 열 코어 실행에 통신·대기 등으로 2초가 더 들면 총 21초, 약 4.76배가 된다. 이 식은 겹쳐 처리하지 못하고 실행시간에 남은 비용을 더하는 근사다. 통신과 계산이 겹칠 수 있는 실제 시스템에서는 모든 통신 시간을 무조건 합하면 과대평가한다.
더 많은 코어가 같은 메모리 경로를 다투면 코어당 데이터 공급도 줄 수 있다. 일을 너무 잘게 쪼개면 계산보다 배분과 동기화가 더 큰 문제가 되기도 한다. 짧은 작업에서 병렬 실행이 오히려 느려질 수 있는 이유다. LLNL, 병렬 실행의 오버헤드와 확장성
법칙이 알려주는 것은 포기보다 측정 순서
먼저 같은 입력과 같은 결과 기준으로 한 코어 실행을 측정한다. 그다음 코어를 늘리며 총시간, 직렬 구간, 통신, 대기를 구분해 본다. 프로세스 수를 올리는 일보다 공유 자원을 덜 다투게 만들거나, 직렬 처리 자체를 줄이는 알고리즘 변경이 더 효과적일 수 있다.
반대로 코어가 늘어난 만큼 더 큰 문제를 같은 시간에 풀고 싶다면 목표가 달라진다. 코어당 작업량을 유지하며 전체 문제를 키우는 약한 확장성에서는 직렬과 병렬 부분의 비중도 다시 따져야 한다. 고정된 작업에서 계산한 상한을 그대로 가져오면 안 된다. NVIDIA, 약한 확장성의 조건
암달의 법칙은 어떤 컴퓨터에도 영원히 고정된 천장을 매기는 규칙이 아니다. 특정 작업과 실행 조건에서 무엇이 남아 있는지 드러내는 모형이다. 캐시 동작이나 코어 속도, 알고리즘까지 바뀌었다면 처음의 s와 처리 능력 가정부터 다시 확인해야 한다. 코어 개수보다 먼저 알아야 할 숫자는, 늘어난 코어가 실제로 줄일 수 있는 시간이다.