컴퓨터공학 300 주제 시리즈의 100번째 글이다. 전체 지도는 여기.

한 줄 요약

프로그램의 CPU 시간은 “명령어 수 × 명령어당 평균 사이클(CPI) × 클록 주기” 로 분해된다. 그리고 어떤 부분을 아무리 빠르게 해도 전체 속도 향상은 그 부분이 차지하던 비율에 묶인다는 것이 암달의 법칙이다. 둘을 알면 “어디를 고쳐야 얼마나 빨라질지” 를 고치기 전에 계산할 수 있다.

왜 필요한가

5부의 주제문은 “코드가 실제로 도는 기계를 알면 성능 문제의 절반이 보인다” 였다. 나머지 절반은 제대로 재는 것이다. 현업에서 자주 보는 실수는 다음과 같다.

  • 클록이 높은 CPU 가 무조건 빠르다고 생각한다.
  • 전체 시간의 5% 를 차지하는 함수를 10배 빠르게 만들고 큰 개선을 기대한다.
  • 한 번 돌려 본 숫자로 “20% 빨라졌다” 고 보고한다.

이 글은 5부를 마무리하며 지금까지 본 파이프라인, 캐시, 분기 예측, 멀티코어가 성능 공식의 어느 항을 건드리는지 정리한다.

핵심 개념

CPU 성능 공식

CPU 시간 = 명령어 수(IC) × CPI × 클록 주기
         = IC × CPI / 클록 주파수
항 무엇이 결정하나 5부의 관련 글
명령어 수(IC) 알고리즘, 언어, 컴파일러, ISA #087 ISA, #088 어셈블리, #098 SIMD(명령어 하나로 여러 연산)
CPI 마이크로아키텍처, 캐시 미스, 분기 예측 실패, 의존성 #090 파이프라인, #091 해저드, #092~#095 메모리
클록 주기 회로 임계 경로, 공정, 전력 #085 순차 회로

세 항은 서로 얽혀 있다. RISC 는 IC 를 늘리는 대신 CPI 와 주기를 줄이려 했다. 파이프라인을 깊게 하면 주기는 줄지만 해저드로 CPI 가 오를 수 있다. 어느 한 항만 보고 성능을 말할 수 없다. 같은 이유로 클록 주파수나 MIPS(초당 백만 명령어) 같은 단일 지표는 서로 다른 ISA·프로그램 사이 비교에 쓰면 오해를 부른다.

CPI 의 역수인 IPC(사이클당 명령어 수)도 자주 쓴다. 슈퍼스칼라 CPU 는 IPC 가 1 을 넘을 수 있다. 리눅스 perf stat 은 instructions 와 cycles 를 함께 보여 주며 IPC 를 계산해 준다. IPC 가 낮게 나오면 메모리나 분기에서 멈춰 있을 가능성이 높다.

평균 CPI

명령어 종류마다 CPI 가 다르면 비율로 가중 평균한다.

평균 CPI = Σ (종류 i 의 비율 × 종류 i 의 CPI)

적재 명령의 CPI 가 높은 것은 대개 캐시 미스 때문이다. 캐시를 개선하면 적재의 CPI 가 내려가고 전체 CPI 가 내려간다. 아래 실험에서 계산한다.

암달의 법칙

전체 실행 시간 중 비율 p 인 부분을 s 배 빠르게 했을 때 전체 속도 향상은 다음과 같다.

              1
속도 향상 = ─────────────────
           (1 − p) + p / s

s 가 무한대로 가도 속도 향상은 1 / (1 − p) 를 넘을 수 없다. 90% 를 무한히 빠르게 해도 10배가 끝이다. 진 암달이 1967년 AFIPS 학회에서 발표한 논문에서 나온 논증이다.

병렬화에 적용하면 p 는 병렬화할 수 있는 비율, s 는 코어 수다. 순차 부분이 5% 만 남아도 코어를 1,024개 써서 20배를 넘지 못한다. 실제로는 통신·동기화 비용까지 붙어서 코어를 늘리면 오히려 느려지는 지점도 생긴다.

구스타프슨의 법칙: 문제를 키우면

암달의 법칙은 문제 크기를 고정했다. 존 구스타프슨은 1988년, 코어가 늘면 사람들은 같은 시간에 더 큰 문제를 푼다고 지적했다. 병렬 부분이 문제 크기와 함께 커지고 순차 부분은 거의 그대로라면, 확장된 속도 향상은 대략 N − (1 − p’)(N − 1) 로 코어 수에 가깝게 늘 수 있다(p’ 는 병렬 시스템에서 측정한 병렬 부분 비율). 두 법칙은 모순이 아니라 서로 다른 질문(같은 일을 더 빨리 vs 같은 시간에 더 큰 일)에 대한 답이다.

측정의 원칙

  1. 무엇을 재는지 정한다: 지연(한 요청) vs 처리량(초당 요청), 벽시계 시간 vs CPU 시간, 평균 vs 꼬리 지연(p99).
  2. 여러 번 잰다: 캐시 상태, CPU 주파수 변동, 다른 프로세스, 가비지 컬렉션 때문에 매번 다르다. 분포를 보고 최솟값·중앙값·편차를 함께 보고한다.
  3. 예열한다: 첫 실행은 캐시가 비어 있고 JIT 이 아직 컴파일하지 않았을 수 있다.
  4. 최적화가 측정 대상을 지우지 않게 한다: 결과를 쓰지 않으면 컴파일러가 계산 자체를 지울 수 있다(5부 실험들이 결과를 출력한 이유).
  5. 프로파일링으로 p 를 먼저 찾는다: 암달의 법칙에서 가장 중요한 숫자는 p 다. 추측하지 말고 프로파일러로 시간이 실제로 어디서 쓰이는지 확인한 뒤 고친다.
  6. 표준 벤치마크는 조건과 함께: SPEC CPU 같은 표준 벤치마크는 실행 규칙과 보고 형식을 엄격히 정한다. 결과를 인용할 때는 그 조건을 같이 적는다.

직접 해 보기

CPI 계산, 암달의 법칙 표, 반복 측정을 한 번에 해 본다. python3 로 실행해 확인했다. 명령어 비율과 CPI 값은 설명용 가정값이다.

import statistics, timeit

# 1. CPU 시간 = 명령어 수 x CPI x 클록 주기
mix = {  # 명령어 종류: (비율, CPI)
    "ALU":    (0.50, 1),
    "load":   (0.20, 5),
    "store":  (0.10, 3),
    "branch": (0.20, 2),
}
cpi = sum(f * c for f, c in mix.values())
ic, ghz = 2e9, 3.0
print(f"avg CPI = {cpi:.2f},  CPU time = {ic * cpi / (ghz * 1e9):.3f} s")

mix2 = dict(mix, load=(0.20, 2))           # load 의 CPI 를 5 -> 2 로 (캐시 개선)
cpi2 = sum(f * c for f, c in mix2.values())
print(f"after cache fix: CPI = {cpi2:.2f}, speedup = {cpi / cpi2:.2f}x")

# 2. 암달의 법칙
def amdahl(p, s):            # p: 개선되는 비율, s: 그 부분의 속도 향상
    return 1 / ((1 - p) + p / s)

for p in (0.5, 0.9, 0.95, 0.99):
    row = "  ".join(f"{amdahl(p, n):6.2f}" for n in (2, 4, 16, 64, 1024))
    print(f"p={p:<4}  {row}   limit {1 / (1 - p):.0f}x")

# 3. 측정은 여러 번: 분포를 본다
stmt = "sum(i * i for i in range(10000))"
runs = timeit.repeat(stmt, number=100, repeat=7)
per = [r / 100 * 1e6 for r in runs]
print("per-call us:", " ".join(f"{x:.0f}" for x in per))
print(f"min {min(per):.0f}  median {statistics.median(per):.0f}  max {max(per):.0f}")

출력:

avg CPI = 2.20,  CPU time = 1.467 s
after cache fix: CPI = 1.60, speedup = 1.38x
p=0.5     1.33    1.60    1.88    1.97    2.00   limit 2x
p=0.9     1.82    3.08    6.40    8.77    9.91   limit 10x
p=0.95    1.90    3.48    9.14   15.42   19.64   limit 20x
p=0.99    1.98    3.88   13.91   39.26   91.18   limit 100x
per-call us: 2315 3857 4952 5301 5130 8989 5778
min 2315  median 5130  max 8989

읽을 것이 세 가지다.

  • 적재 명령은 20% 뿐인데 그 CPI 를 5 에서 2 로 줄이자 전체가 1.38배 빨라졌다. CPI 가 큰 종류는 비율이 작아도 시간을 많이 차지한다.
  • 표의 열은 2, 4, 16, 64, 1024 코어다. p = 0.9 면 코어를 1,024개 써도 9.91배다. 코어를 늘리기 전에 순차 부분을 줄이는 것이 먼저다.
  • 같은 코드를 7번 쟀는데 최솟값과 최댓값이 4배 가까이 차이 났다. 다른 작업이 함께 돌던 노드였기 때문이다. 이런 환경에서 한 번 잰 숫자로 “20% 개선” 을 말하면 잡음을 보고하는 셈이다. 파이썬 공식 문서도 timeit.repeat 결과에서 평균보다 최솟값을 보라고 권한다. 최솟값이 기계가 낼 수 있는 속도에 가장 가깝고, 나머지는 다른 프로세스의 간섭이기 때문이다.

현업에서는

  • 최적화 우선순위: 프로파일러(perf, py-spy, async-profiler 등)로 시간 비중 p 가 큰 곳부터 고친다. 전체의 2% 인 함수를 아무리 고쳐도 2% 이상은 줄지 않는다.
  • 수평 확장의 한계: 쿠버네티스에서 레플리카를 늘려도 처리량이 늘지 않는다면 공유 DB, 락, 단일 리더 같은 순차 구간이 p 를 깎고 있는 것이다. 암달의 법칙은 분산 시스템에도 그대로 적용된다.
  • 벤치마크 환경: 홈랩처럼 여러 워크로드가 한 노드에 섞인 환경에서는 측정값이 크게 흔들린다. 같은 노드에서, 같은 조건으로, 여러 번 재고, 분포를 함께 기록한다. 가능하면 CPU 를 고정하거나 다른 부하가 적은 시간대를 고른다.
  • IPC 로 병목 분류: perf stat 의 IPC 가 낮고 캐시 미스가 많으면 메모리 바운드, IPC 는 높은데 명령어 수가 많으면 알고리즘이나 코드 경로를 줄일 차례다. 공식의 어느 항이 문제인지 알면 처방이 달라진다.

확인 문제

  1. 명령어 수 10억, 평균 CPI 1.5, 클록 2GHz 인 프로그램의 CPU 시간은.
  2. 클록이 더 높은 CPU 가 더 느릴 수 있는 이유를 성능 공식으로 설명하라.
  3. 실행 시간의 40% 를 차지하는 부분을 4배 빠르게 하면 전체 속도 향상은.
  4. 병렬화 가능 비율이 95% 인 프로그램의 이론상 최대 속도 향상은.
  5. 성능 측정을 한 번만 하면 안 되는 이유는.

풀이

  1. 10^9 × 1.5 / (2 × 10^9) = 0.75초.
  2. CPU 시간은 IC × CPI × 주기의 곱이라, 주기가 짧아도 ISA·컴파일러 차이로 명령어 수가 많거나 마이크로아키텍처 차이로 CPI 가 높으면 전체 시간이 길어질 수 있다.
  3. 1 / (0.6 + 0.4/4) = 1 / 0.7 ≈ 1.43배.
  4. 1 / (1 − 0.95) = 20배.
  5. 캐시 상태, 주파수 변화, 다른 프로세스의 간섭 등으로 실행마다 시간이 달라지므로, 한 번의 값은 잡음일 수 있다. 여러 번 재 분포를 봐야 한다.

더 읽을거리 (References)