알고리즘 분석에서 메모리 접근 비용이 중요한 이유
전통적인 알고리즘 분석에서는 연산(operations)과 실행 단계(steps)의 수를 세어 성능을 평가해 왔습니다. 이 방식은 컴퓨터가 하나의 연산을 수행하는 데 걸리는 시간이 해당 연산에 필요한 데이터를 가져오는 시간보다 훨씬 길었던 과거에는 충분히 타당했습니다. 그러나 오늘날에는 연산을 수행하는 비용이 메모리에서 데이터를 가져오는 비용보다 훨씬 낮아졌습니다.
캐시 미스가 알고리즘 성능을 좌우한다
많은 알고리즘의 실행 시간은 연산의 개수보다 메모리 참조 횟수, 즉 캐시 미스(cache miss)의 수에 의해 지배됩니다. 따라서 알고리즘을 설계할 때는 연산 횟수를 줄이는 것뿐만 아니라 메모리 접근 횟수 자체를 줄이는 데도 집중해야 합니다. 아울러 데이터 로딩을 기다리는 동안 다른 유용한 작업을 수행함으로써 메모리 지연 시간(latency)을 효과적으로 숨길 수 있는 알고리즘을 설계하는 것도 중요합니다.
간단한 컴퓨터 모델: L1·L2 캐시와 메인 메모리
설명을 위해 간단한 컴퓨터 모델을 가정해 보겠습니다. 이 모델에서 컴퓨터의 메모리는 L1 캐시, L2 캐시, 메인 메모리로 구성되며, ALU(산술 논리 장치)는 레지스터(R)에 상주하는 데이터를 대상으로 산술 및 논리 연산을 수행합니다.
다음은 이 모델의 블록 다이어그램입니다.
메모리 계층별 크기
다이어그램에서 각 메모리 계층의 크기 차이도 확인할 수 있습니다.
- 메인 메모리: 수백 MB ~ 수천 MB
- L2 캐시: 수백 KB ~ 수 MB 수준
- L1 캐시: 수십 KB 수준
- 레지스터: 수십 비트(워드) 크기
프로그램 실행 흐름 예시
프로그램이 실행되면 모든 데이터는 메모리에 저장되어 있습니다. ADD 같은 연산을 수행한다고 가정하면, 먼저 첫 번째 피연산자가 레지스터로 적재되고, 레지스터에 있는 데이터들이 더해진 후, 그 결과가 다시 메모리에 기록됩니다.
사이클 기반 지연 시간 계산
레지스터에 이미 있는 데이터를 더하는 데 걸리는 시간을 1 사이클이라고 정의합니다. 이 모델에서 각 메모리 계층의 접근 비용은 다음과 같습니다.
- L1 캐시 → 레지스터: 2 사이클
- L1 캐시 미스 발생 시: 필요한 데이터가 L1에는 없지만 L2에 있다면, L2 캐시에서 L1 캐시와 레지스터까지 데이터를 가져오는 데 10 사이클 소요
- L2 캐시 미스 발생 시: 필요한 데이터가 L2에도 없다면, 메인 메모리에서 L2 캐시, L1 캐시, 레지스터까지 데이터를 가져오는 데 100 사이클 소요
한 가지 주목할 점은 쓰기(write) 연산입니다. 데이터가 메인 메모리에 기록되는 경우라도 쓰기는 1 사이클로 계산합니다. 다음 연산으로 넘어가기 전에 쓰기 작업이 완료될 때까지 기다리지 않기 때문입니다.
정리
이처럼 캐시 계층에서 한 단계 아래로 내려갈수록 접근 비용이 수 배에서 수십 배씩 증가합니다. 따라서 실제 알고리즘 설계에서는 캐시 지역성(locality)을 활용해 캐시 적중률(hit rate)을 높이고, 메모리 접근 패턴을 최적화하는 것이 실행 속도 향상의 핵심이 됩니다.