프로그래머가 몰랐던 멀티코어 CPU 이야기, Story04 암달의 법칙과 프로세서의 성능 지표 챕터를 읽으면서 재정리 및 복습하는 글입니다.
프로세서가 하는 일은 프로그램에 있는 명령어들의 흐름을 처리하는 것(Datapath) → 어떤 장치가 명령어를 메모리에서 읽어와 해독하고 이것을 ALU에 넣어 결과 값을 얻게 할까? (Control Unit)
암달의 법칙
가정: 어떤 한 프로그램의 함수 foo( )는 전체 프로그램 수행 시간 중 80%를 차지한다는 것을 프로파일링 도구를 통해 알아냈다. 그럼 foo( )의 수행 시간이 전체 프로그램의 수행 시간에는 어떤 영향을 끼칠 것 인가?
개선 전의 프로그램 수행 시간을 1로 놓았을 때, foo의 실행 시간을 0.8 이다. 최적화 후의 수행 시간이 반으로 줄었을 때 실질적인 속도 향상은 1.67배이다. 프로그램에서 큰 비중을 차지하는 함수의 수행 시간을 2배 줄여도 실질적으로 프로그램은 두 배만큼 빨라지지 않는다. 물론 최적화된 함수가 밖에 영향을 끼치지 않는다는 가정 하이다.
0.8/2 + 0.2 = 0.6, 1/0.6 = 1.67
그렇다면 foo의 수행 시간을 1/10로 줄인다면 그때는 어떻게 될까?
foo의 수행 시간이 이전 최적화 보다 5배나 빨라졌다. 하지만 전체 성능은 1.67 → 3.56, 약 2배밖에 향상되지 않았다.
0.8/10 + 0.2 = 0.28, 1/0.28 = 3.56
아무리 최적화를 하더라도 이 최적화로 부터 영향받지 않는 다른 부분으로 그 효과는 제한적일 수 있다.
아래 공식은 암달의 법칙을 수식화한 것이다. 전체 중 P부분이 S만큼 개선될 때 기대되는 전체 속도 향상을 말한다.
\[\frac{1}{(1-P) + \frac{P}{S}}\]- P: 최적화된 부분의 비율
- S: 최적화된 부분의 성능 향상(스피드업)
$1 / ((1 - 0.8) + 0.8/2) = 1.6$
$1/((1 - 0.8) + 0.8/10) = 3.57$
병렬화
암달의 법칙은 병렬 처리에도 적용 가능하다. 위 공식의 N을 함수의 최적화가 아닌 프로세서의 개수로 바꾸면 똑같이 적용가능하다. 병렬화시 오버 헤드는 없다는 가정 하이다
그래서 병렬화 가능한 부분을 효율적으로 병렬화하여 최적의 성능을 얻는 것도 중요하지만, 병렬화 가능한 부분을 극대화, 직렬로 구성되어 있는 부분을 최소화하는 것이 핵심이다. 당연히 프로그램의 구조나 목적에 따라 적절히 반영해야 한다.
프로그램의 속도
컴퓨터의 속도는 한 컴퓨터가 프로그램을 (1)얼마나 빨리, (2)단위 시간당 얼마나 많이 처리할 수 있는 지로 정의할 수 있다. (1)에 해당하는 것을 레이턴시(latency), (2)에 해당하는 것을 처리율(throughtput)이라고 한다.
레이턴시는 응답 시간 혹은 실행 시간으로도 불린다.
프로그램의 실행 시간 정리
$T = N \times T_{inst}$
- T: 프로그램의 전체 실행 시간
- N: 프로그램이 실행한 명령어의 개수
- T_inst: 명령어 하나를 처리하는 데 드는 평균 시간
현대 OS에서는 여러 프로그램과 백그라운드 서비스 등등이 있어 위의 공식이 이상적으로 들어맞지 않는다. 하지만 N이 매우 크다면 이런 잡음은 무시할 수 있다.
T_inst는 어떻게 구할 수 있는가?
명령어의 종류에 따라 수행 시간은 제각각이다. e.g) 불 연산 < 비트 연산 < 정수 사칙 연산 < 부동소수점 연산. 프로그램에 따라 위 명령어의 분포가 다를 수 있다. 그러므로 알아야 할 정보는 다음과 같다.
- 프로그램에 어떤 종류의 명령어가 얼마나 많이 있는가
- 각각의 명령어가 프로세서에서 수행될 때 얼마나 걸리는가
위 내용에 따라 수식을 재정의 한다.
$T = (\sum{N_i \times CPI_i}) \times T_{cycle}$
CPI(Cycle Per Insturction) 명령어당 평균 소요 사이클이다.
앞의 항은 각 명령어마다 각기 다른 CPI를 곱하여 더하고, 거기에 명령어의 개수와 T_cycle(사이클 하나의 처리 시간)을 곱하면 처리시간을 구할 수 있다.
결론
프로그램의 속도를 높일려면, 명령어의 개수를 줄이거나(불필요한 코드제거), CPI가 높은 명령어 보다 적게드는 명령어(상황에 따라 unsigned를 붙인다거나, float대신 int자료형을 사용한다거나)를 사용한다.