성능 계산과 종합 추적

"클록이 2 GHz에서 3 GHz로 올랐으니 프로그램이 1.5배 빨라졌다"는 말은 맞을 수도 있고 틀릴 수도 있습니다. 프로그램이 끝나기까지의 시간은 클록의 빠르기뿐 아니라 명령어를 몇 개 실행하는지, 명령어 하나에 클록을 몇 번 쓰는지에 함께 달려 있기 때문입니다. 성능을 비교하려면 이 요소들을 나누어 계산하고, 어떤 가정 아래의 계산인지 함께 적어야 합니다. 이 글에서는 성능을 계산하는 기본 식을 다루고, 지금까지 배운 내용을 종합 문제로 묶습니다.

CPU 시간의 세 요소

가장 단순한 모델에서 CPU 시간은 명령어 수 × 명령어당 평균 사이클 수 × 클록 주기입니다. 명령어당 평균 사이클 수를 CPI(cycles per instruction)라 하고, 클록 주기는 클록 주파수의 역수라서 2 GHz이면 0.5 ns입니다. 명령어 100만 개를 CPI 2로 2 GHz CPU에서 실행하면 200만 사이클이 필요하고, 1초에 20억 사이클을 실행하므로 0.001초가 걸립니다.

세 요소는 서로 맞물려 있습니다. 새 컴파일러가 명령어 수를 80만 개로 줄였더라도, 그 대신 더 복잡한 명령어를 써서 CPI가 3이 되었다면 240만 사이클이 필요해 오히려 느려집니다. 마찬가지로 클록을 높이려고 파이프라인을 잘게 나누면 위험에 따른 정지가 늘어 CPI가 커질 수 있습니다. 그래서 어느 한 요소만 보고 성능을 판단하면 안 됩니다.

평균 CPI는 명령어 종류마다 그 비율을 곱해 더한 가중 평균입니다. 실행한 명령어의 60%가 CPI 1, 30%가 CPI 2, 10%가 CPI 5라면 평균 CPI는 0.6 × 1 + 0.3 × 2 + 0.1 × 5 = 1.7입니다. 세 CPI를 단순히 평균한 (1 + 2 + 5) / 3 ≈ 2.67과는 다르며, 드물게 실행되는 느린 명령어의 무게가 비율만큼만 반영됩니다.

일부만 빠르게 했을 때의 한계

프로그램의 일부만 빠르게 만들면, 나머지 부분이 전체 속도의 한계가 됩니다. Amdahl의 법칙(Amdahl's law)은 원래 실행 시간 가운데 비율 p인 부분을 s배 빠르게 했을 때 전체가 얼마나 빨라지는지를 다음과 같이 계산합니다.

원래 시간의 80%를 차지하는 부분을 4배 빠르게 하면 1 / (0.2 + 0.8 / 4) = 2.5배가 됩니다. 그 부분을 아무리 빠르게 해도 p / s가 0에 가까워질 뿐이라 전체는 1 / 0.2 = 5배를 넘지 못합니다. 그래서 개선할 곳을 고를 때는 그 부분이 원래 시간에서 얼마나 큰 비율을 차지하는지부터 측정해야 합니다.

def cpu_time(instructions, cpi, hz):
    return instructions * cpi / hz


def weighted_cpi(mix):
    return sum(share * cpi for share, cpi in mix)


def speedup(fraction, factor):
    return 1 / ((1 - fraction) + fraction / factor)


print(cpu_time(1_000_000, 2, 2e9), cpu_time(800_000, 3, 2e9))
print(round(weighted_cpi([(0.6, 1), (0.3, 2), (0.1, 5)]), 2))
print(round(speedup(0.8, 4), 2), round(speedup(0.8, 1e9), 2))
print([round(speedup(0.9, n), 2) for n in (1, 2, 4, 8, 16, 1000)])

0.001 0.0012
1.7
2.5 5.0
[1.0, 1.82, 3.08, 4.71, 6.4, 9.91]

첫 줄은 앞의 두 컴파일러 결과로, 명령어가 적은 쪽이 0.0012초로 더 느립니다. 둘째 줄은 가중 평균 CPI이고, 셋째 줄은 80%를 4배 빠르게 한 결과와 사실상 무한히 빠르게 한 결과입니다. 마지막 줄은 프로그램의 90%를 n개의 코어로 완벽하게 나눌 수 있다고 할 때의 속도로, 코어가 16개이면 6.4배, 1000개여도 10배를 넘지 못합니다. 실제 병렬 처리에서는 작업을 나누고, 결과를 주고받고, 서로를 기다리는 비용까지 더해지므로, 코어 수를 그대로 s에 넣으면 지나치게 좋은 값이 나옵니다. 모델의 예측과 실제 측정이 다르다면, 모델이 빠뜨린 비용이 무엇인지 찾는 단서로 쓰면 됩니다.

종합 문제로 다시 보기

지금까지의 내용을 하나의 예로 묶어 보겠습니다. 바이트 주소를 쓰는 메모리의 주소 0, 4, 8, 12에 4바이트 정수 2, 3, 5, 7이 들어 있습니다. 캐시는 데이터 용량 8바이트, 블록 8바이트인 직접 매핑 캐시이고 처음에는 비어 있습니다. 합계 레지스터를 0에서 시작해 네 값을 차례로 읽어 더합니다. 아래 연습 문제의 세 질문은 이 예에 대한 것으로, 각각 캐시 주소·매핑·교체, 이 글의 Amdahl의 법칙, 병렬처리와 Flynn 분류의 부분 합을 씁니다.

정리

• CPU 시간은 명령어 수 × CPI × 클록 주기이고, 세 요소가 서로 맞물려 있어 하나만 보고 성능을 판단하면 안 됩니다.
• 평균 CPI는 명령어 종류별 CPI에 실행 비율을 곱해 더한 가중 평균입니다.
• Amdahl의 법칙에 따라 원래 시간의 비율 p인 부분을 s배 빠르게 하면 전체는 1 / ((1 − p) + p / s)배 빨라지며, 나머지 부분 1 − p가 한계를 정합니다.
• 병렬 처리의 속도는 나눌 수 있는 비율과 함께 나누고 합치는 비용에 따라 정해지므로, 코어 수만큼 빨라진다고 가정하면 안 됩니다.

연습 문제

1. 배열을 읽는 동안의 캐시

종합 문제의 네 주소에 대해 블록 번호, 오프셋, 적중 결과를 구하고, 최종 합을 구하세요.

2. 배열 처리만 빠르게 하면

전체 실행 시간의 60%가 배열 처리이고, 이 부분만 3배 빠르게 했습니다. 전체는 몇 배 빨라지나요?

3. 두 코어로 나누어 더하기

두 코어가 앞의 두 값과 뒤의 두 값을 나누어 더한 뒤 합치려고 합니다. 각 코어가 따로 저장해야 할 중간 결과는 무엇이고, 하나의 공유 합계 변수에 각자 바로 더하는 방법과 비교하면 무엇이 다른가요?

종합 문제에서 막힌 곳이 있다면, 블록과 오프셋은 캐시 주소·매핑·교체에서, 값이 레지스터와 메모리 사이를 오가는 과정은 CPU 데이터 경로에서, 부분 합으로 나누는 이유는 병렬처리와 Flynn 분류에서 다시 확인해 보세요. 이것으로 컴퓨터구조 교재의 본문을 마칩니다. 운영체제가 이 하드웨어 위에서 프로세스와 메모리를 어떻게 관리하는지는 운영체제 교재에서 이어지며, 처음부터 다시 훑어보려면 교재 목차로 돌아가세요.