메모리 접근 시간은 이론과 실전에서 O(N^(1/3))에 가깝다는 주장과 그 근거(물리적 한계와 실제 측정), 캐시·DRAM 지연/대역폭 스케일링, 그리고 사전 계산 테이블 최적화 같은 실용적 사례 및 ASIC/GPU 설계 함의를 다룹니다.
다크 모드 전환
2025년 10월 05일 모든 글 보기
메모리 접근은 O(N^⅓)
컴퓨터 과학에서는 알고리즘의 효율을 입력 크기의 함수로서 실행 시간을 표현해 비교하곤 합니다. 정렬은 O(n * log(n))로, N개의 항목을 정렬하는 데 걸리는 시간은 항목 수에 그 로그를 곱한 값에 비례합니다. 행렬 곱셈의 복잡도는 알고리즘에 따라 2.37과 2.8 사이입니다. 하지만 이런 추정치는 모두 기본 연산을 수행하는 데 걸리는 시간을 어떻게 가정하느냐에 상대적입니다. 보통은 고정 크기 수에 대한 산술 연산(덧셈, 곱셈, 나눗셈 등)은 한 단위 시간으로, 메모리 접근도 한 단위 시간으로 간주합니다.
이 글에서는 메모리 접근에 대한 이 가정이 잘못되었다고 주장합니다. 이론과 실전 모두에서 메모리 접근 시간은 O(N^⅓)입니다. 즉, 메모리가 8배 커지면 그 메모리에 대해 읽기나 쓰기를 하는 데 2배 더 오래 걸립니다. 또한 이것이 실제로 중요한 응용 사례 하나를 보여드리겠습니다.
프로세서가 메모리 덩어리의 한가운데에 놓여 있다고 상상해 봅시다. 프로세서가 어떤 특정 메모리 조각과 통신하는 능력은 빛의 속도라는 한계에 묶여 있으므로, 지연은 거리와 비례합니다. 3차원 세계에서는 자신으로부터의 거리를 두 배로 늘리면 그 안에 담을 수 있는 메모리 용량은 8배가 됩니다.
거리를 두 배로 하면, 메모리는 여덟 배.
이는 순차 접근을 설명합니다. 물론 현실에서 CPU가 균질한 메모리 큐브 내부에 물리적으로 자리 잡고 있는 것은 아니고, 전기 신호가 정확히 직선으로 이동하지도 않으며(게다가 빛보다 느립니다). 하지만 뒤에서 보겠듯이, 이 모델은 실제와 놀랍도록 가깝습니다.
병렬 접근의 경우는 매체에 따라 좀 더 미묘합니다. 읽기와 쓰기를 필요한 길이의 "와이어"가 일정 시간 동안 점유하는 것으로 생각하면 같은 결론이 나옵니다. 메모리가 8배면, 와이어 길이 * 시간은 2배가 됩니다. 이를 일정 에너지를 쓰는 빛의 신호로 생각하고, 강도가 확산을 고려해야 한다면, 메모리 8배는 길이 2배를 뜻하고, 한 번의 접근에 필요한 에너지는 4배가 됩니다. 중간에서 신호를 반복 증폭하는 리피터로 이를 완화할 수 있지만, 그러면 다시 와이어 모델에 가까워집니다. 따라서 O(N^⅓)이 더 좋은 모델일 가능성이 큽니다.
현실의 컴퓨터에는 레지스터, 여러 단계의 캐시, RAM 등 다양한 종류의 메모리가 있습니다. SSD/HDD는 여기서 제외하겠습니다. 이들은 비휘발성(전력 없이도 데이터 유지)과 낮은 비트당 비용 같은 추가 요구 사항이 있기 때문입니다.
다음과 같은 질문을 해 봅시다. 보통의 랩톱이 N 바이트 정도 보유하는 어떤 메모리 유형에 접근하는 데(나노초 기준) 얼마나 걸릴까요? 다음은 GPT의 답변입니다:
접근 시간을 해당 메모리 용량의 세제곱근에 비례한다고 보는 단순한 공식이 놀랄 만큼 실제와 가깝습니다.
대역폭에 대해서도 같은 작업을 해 볼 수 있습니다:
여기서는 적합도가 훨씬 나쁜데, 이는 예상 가능한 일입니다. 지연(latency)과 비교하면 대역폭은 물리 법칙의 근본적 적용보다는 아키텍처 선택에 더 좌우됩니다. L3 캐시는 DRAM처럼 대량 처리량을 목표로 설계되지 않았기 때문에, 연산에 훨씬 더 가깝게 위치해 있음에도 총 처리량은 대략 비슷합니다.
1년 전 제가 직접 겪었던 구체적 사례가 있습니다. 바로 사전 계산한 중간 값들을 재사용하는 여러 알고리즘의 최적화 구현입니다. 종종, 특히 암호 분야에서는 N 단계의 수학적 절차가 있고, 각 단계에서 입력의 한 비트에 따라 어떤 값을 "섞어 넣을지" 말지를 결정합니다. 이 "섞어 넣기"는 대개 결합법칙이 성립하는 연산입니다. 이런 절차는 순진하게 하면 N 단계가 필요하지만, 각 단계마다 256개 값을 사전 계산해 두면 N/8 단계, 65,536개 값을 사전 계산하면 N/16 단계로 줄일 수 있습니다. 예로는 타원곡선 스칼라 곱셈, 이진 체 연산(예: 제 구현) 등 많은 알고리즘이 있습니다.
암호를 최적화하는 놀라울 정도로 널리 적용 가능한 방법.
사전 계산 테이블은 어느 정도 크기가 적절할까요? 메모리 접근을 O(1)로 가정하면 답은 명확합니다. 머신 메모리가 허용하는 한 최대한 크게 만들면 됩니다. 하지만 메모리 접근을 O(N^⅓)로 보면 훨씬 미묘한 균형 문제가 됩니다. N^⅓ / log(N)을 최적화해야 하며, 최적 값은 항상 어떤 "내부 최적해"(즉, 1도 아니고 "가능한 한 크게"도 아님)가 되고, 정확한 위치는 관련 상수들에 좌우됩니다.
제 이진 체 코드에서는 8비트 사전 계산 테이블(그 맥락에서는 2^24개 항목, 128 MB)이 16비트 사전 계산 테이블(2^32개 항목, 8 GB)보다 계산을 더 빠르게 해 준다는 것을 확인했습니다. 후자는 RAM에는 들어가지만 전자는 캐시에 들어가고, 전자의 더 빠른 접근 시간이 결정적이었습니다.
장기적으로 우리는 지금 범용 CPU의 한계에 근접하는 시대에 있으며, 다양한 작업을 위해 ASIC을 점점 더 탐색하고 있습니다. 여기서는 ASIC의 구조가 중요합니다. **작업을 매우 국소적인 여러 부분으로 쪼갤 수 있다면, 각 부분의 메모리 접근은 O(1)**이 됩니다. GPU는 이미 바로 이런 종류의 효율을 매우 잘 끌어내는 경우가 많습니다. 하지만 작업에 많은 메모리 상호의존성이 필요하면 O(N^⅓) 항들이 잔뜩 생깁니다. 단순하면서도 이러한 미묘함을 잘 포착하는 계산의 수학적 모델을 고안하는 것은 열려 있는 과제입니다.
