컴퓨터 구조 07 - 메모리 계층 구조

빠른 메모리는 왜 비싼가?

이상적인 메모리는 CPU만큼 빠르면서도 용량은 무한하고 가격은 저렴한 것일 것이다. 그러나 현실에서는 이 세 가지 조건을 동시에 만족시키는 메모리 기술이 존재하지 않는다. 빠른 메모리일수록 비트당 단가가 높고, 단가가 낮은 메모리일수록 접근 속도가 느리다. 이것은 물리적 제약이다. SRAM은 하나의 비트를 저장하는 데 6개의 트랜지스터가 필요하지만, DRAM은 트랜지스터 1개와 커패시터 1개만으로 충분하다. 트랜지스터 수가 적을수록 집적도가 높아지고 가격은 내려가지만, 그만큼 접근 속도는 느려지는 것이다.

과연 이 물리적 한계를 완전히 극복할 방법이 있는가? 극복할 수는 없지만, 우회할 수는 있다. 그 전략이 바로 메모리 계층 구조(memory hierarchy)이다.

메모리 계층 피라미드

메모리 계층 구조는 속도, 용량, 비용이 다른 여러 수준의 메모리를 계층적으로 배치하여, 전체적으로 빠르고 큰 메모리의 환상을 만들어 내는 설계 전략이다.

          ┌─────────┐
          │레지스터  │  ~ 1 ns     수십~수백 바이트
          │         │
         ┌┴─────────┴┐
         │  L1 캐시   │  ~ 1 ns     32-64 KB
         │           │
        ┌┴───────────┴┐
        │   L2 캐시    │  ~ 3-10 ns   256 KB - 1 MB
        │             │
       ┌┴─────────────┴┐
       │    L3 캐시     │  ~ 10-30 ns  4-64 MB
       │               │
      ┌┴───────────────┴┐
      │     DRAM        │  ~ 50-100 ns  8-128 GB
      │                 │
     ┌┴─────────────────┴┐
     │      SSD          │  ~ 25-100 μs  256 GB - 4 TB
     │                   │
    ┌┴───────────────────┴┐
    │       HDD           │  ~ 3-10 ms   1-20 TB
    └─────────────────────┘

피라미드의 꼭대기에 있는 레지스터는 CPU 클럭 속도와 동일하게 동작하지만, 그 수는 수십 개에 불과하다. 바닥에 있는 HDD는 테라바이트 단위의 용량을 제공하지만, 접근 시간이 밀리초 단위이다. 레지스터와 HDD 사이에는 약 백만 배의 속도 차이가 존재한다.

이 계층 구조가 효과적인 이유는 프로그램이 메모리에 접근하는 패턴에 특정한 규칙성이 있기 때문이다.

참조의 지역성

대부분의 프로그램은 메모리 전체를 균일하게 사용하지 않는다. 특정 시점에 접근하는 메모리 주소는 최근에 접근했던 주소 또는 그 근처에 집중되는 경향이 있다. 이를 참조의 지역성(locality of reference)이라고 한다.

시간적 지역성(temporal locality)은 최근에 접근한 데이터가 가까운 미래에 다시 접근될 가능성이 높다는 것이다. 루프 안에서 같은 변수를 반복적으로 읽고 쓰는 것이 전형적인 예이다. 루프 카운터, 누적 합산 변수, 조건 플래그 등은 루프가 실행되는 동안 계속해서 참조된다.

공간적 지역성(spatial locality)은 접근된 주소 근처의 데이터도 곧 접근될 가능성이 높다는 것이다. 배열을 순차적으로 순회하는 것이 대표적이다. arr[0]에 접근했다면 arr[1], arr[2]도 곧 접근될 것이라는 예측은 대부분 맞는다.

메모리 계층 구조의 각 수준은 바로 이 지역성을 활용한다. 자주 사용되는 데이터를 더 빠른 계층에 유지함으로써, CPU가 느린 메모리까지 내려가야 하는 횟수를 최소화한다.

캐시의 구조

캐시는 CPU와 메인 메모리 사이에 위치하여 자주 사용되는 데이터의 복사본을 보관하는 소규모 고속 메모리이다. CPU가 데이터를 요청하면 먼저 캐시를 확인하고, 원하는 데이터가 있으면 캐시 히트(cache hit)로 빠르게 반환하며, 없으면 캐시 미스(cache miss)로 하위 계층에서 가져온다.

캐시는 바이트 단위가 아니라 캐시 라인(cache line) 단위로 데이터를 관리한다. 현대 프로세서에서 캐시 라인 크기는 보통 64바이트이다. 메모리에서 1바이트만 필요하더라도 64바이트 전체를 가져오는 이유는 공간적 지역성을 활용하기 위함이다. 근처의 데이터도 곧 필요해질 가능성이 높으므로, 미리 함께 가져오는 것이 효율적인 것이다.

그렇다면 특정 메모리 주소의 데이터가 캐시의 어느 위치에 저장되는지는 어떻게 결정되는가? 이를 캐시 매핑 방식이라 하며, 세 가지 기본 전략이 있다.

직접 매핑(direct-mapped) 캐시에서는 각 메모리 주소가 캐시의 정확히 하나의 위치에만 대응된다. 주소의 일부 비트를 인덱스로 사용하여 캐시 라인을 결정한다. 구현이 단순하고 조회가 빠르지만, 서로 다른 주소가 같은 캐시 위치에 매핑되면 반복적으로 서로를 밀어내는 충돌 미스(conflict miss)가 발생할 수 있다.

메모리 주소:  [  태그  |  인덱스  |  오프셋  ]
                │         │          │
                │         │          └─▶ 캐시 라인 내 바이트 위치
                │         └────────────▶ 캐시 세트 선택
                └──────────────────────▶ 저장된 데이터의 출처 확인

완전 연관(fully-associative) 캐시에서는 데이터가 캐시의 어느 위치에나 저장될 수 있다. 충돌 미스가 발생하지 않지만, 데이터를 찾기 위해 모든 캐시 라인의 태그를 동시에 비교해야 하므로 하드웨어 비용이 매우 높다. 소규모 TLB(Translation Lookaside Buffer) 같은 특수 목적에만 사용된다.

집합 연관(set-associative) 캐시는 이 두 방식의 절충이다. 캐시를 여러 세트로 나누고, 각 메모리 주소는 하나의 세트에 매핑되지만 그 세트 안에서는 여러 위치(way) 중 하나에 저장될 수 있다. 8-way 집합 연관 캐시라면 하나의 세트에 8개의 캐시 라인이 있어서, 같은 세트에 매핑되는 주소 8개까지는 충돌 없이 공존할 수 있다. 현대 L1 캐시는 보통 4-way 또는 8-way 집합 연관 구조를 사용한다.

캐시 미스의 유형

캐시 미스는 세 가지로 분류된다. 냉시작 미스(cold/compulsory miss)는 해당 데이터에 처음 접근할 때 발생하는 불가피한 미스이다. 용량 미스(capacity miss)는 캐시의 전체 크기가 작업 집합(working set)보다 작아서 발생한다. 충돌 미스(conflict miss)는 캐시 용량은 충분하지만 매핑 충돌 때문에 발생하는 것으로, 직접 매핑이나 집합 연관 캐시에서만 나타난다.

성능에 민감한 코드에서는 이 세 가지 유형 중 어떤 미스가 발생하는지를 파악하는 것이 최적화의 출발점이다. 용량 미스라면 데이터 구조를 압축하거나 작업 집합을 줄여야 하고, 충돌 미스라면 데이터 배치를 변경하거나 캐시 연관도가 높은 수준의 캐시에 데이터를 올려야 한다.

쓰기 정책

CPU가 데이터를 수정할 때, 캐시와 메인 메모리의 일관성을 유지하는 방식에도 선택이 필요하다.

즉시 쓰기(write-through) 정책은 캐시에 쓸 때 메인 메모리에도 동시에 쓰는 방식이다. 메모리의 데이터가 항상 최신 상태를 유지하므로 구현이 단순하지만, 매 쓰기마다 느린 메모리 접근이 발생하여 성능에 불리하다. 쓰기 버퍼(write buffer)를 두어 CPU가 메모리 쓰기 완료를 기다리지 않게 하는 최적화가 일반적이다.

후기입(write-back) 정책은 캐시에만 쓰고, 해당 캐시 라인이 교체될 때 비로소 메인 메모리에 반영하는 방식이다. 수정된 캐시 라인에는 더티 비트(dirty bit)가 설정되어, 교체 시 메모리에 써야 함을 표시한다. 메모리 쓰기 횟수를 크게 줄여 성능이 우수하지만, 메모리와 캐시 사이의 데이터가 일시적으로 불일치할 수 있다. 현대 프로세서의 L1, L2 캐시는 대부분 후기입 정책을 사용한다.

캐시 일관성 문제

단일 코어에서는 캐시와 메모리의 불일치가 하드웨어 내부에서 투명하게 관리된다. 그러나 멀티코어 환경에서는 문제가 복잡해진다. 코어 A가 변수 x를 자신의 캐시에서 수정했는데, 코어 B가 같은 변수 x를 자신의 캐시에서 읽으면 오래된 값을 보게 되기 때문이다.

이 문제를 캐시 일관성(cache coherence) 문제라고 하며, 하드웨어가 자동으로 해결해야 하는 영역이다. 가장 널리 사용되는 프로토콜은 MESI 프로토콜로, 각 캐시 라인을 네 가지 상태 중 하나로 관리한다.

상태	의미
Modified (M)	이 코어만 가지고 있으며, 메모리보다 새로운 값
Exclusive (E)	이 코어만 가지고 있으며, 메모리와 동일한 값
Shared (S)	여러 코어가 가지고 있으며, 메모리와 동일한 값
Invalid (I)	유효하지 않은 데이터

코어 A가 Shared 상태의 캐시 라인을 수정하려 하면, 먼저 다른 코어에 무효화(invalidate) 메시지를 보내 해당 캐시 라인을 Invalid로 만든다. 그런 다음 자신의 캐시 라인을 Modified 상태로 변경하고 값을 수정한다. 이후 코어 B가 같은 주소를 읽으려 하면, 코어 A의 Modified 캐시 라인에서 최신 값을 가져오게 된다.

이 과정은 하드웨어가 자동으로 수행하지만, 공짜는 아니다. 코어 간 메시지 교환에는 수십 클럭 사이클이 소요된다. 멀티스레드 프로그램에서 여러 코어가 같은 캐시 라인의 데이터를 빈번하게 수정하면 무효화 메시지가 쏟아져 성능이 급격히 저하된다. 이를 거짓 공유(false sharing)라고 하며, 서로 다른 변수가 우연히 같은 캐시 라인에 위치할 때 발생한다.

DRAM의 내부 구조

메인 메모리로 사용되는 DRAM은 내부적으로 2차원 배열 형태로 구성된다. 각 비트는 하나의 커패시터에 전하의 유무로 저장되며, 행(row)과 열(column)의 좌표로 접근한다.

DRAM 접근은 두 단계로 이루어진다. 먼저 행 주소를 RAS(Row Address Strobe) 신호와 함께 보내면, 해당 행 전체가 센스 앰프(sense amplifier)라 불리는 행 버퍼로 복사된다. 이 과정을 행 활성화(row activation)라 한다. 그 후 열 주소를 CAS(Column Address Strobe) 신호와 함께 보내면, 행 버퍼에서 해당 열의 데이터가 출력된다.

이미 활성화된 행에서 다른 열을 읽는 것은 빠르다. CAS 지연만 소요되기 때문이다. 그러나 다른 행에 접근하려면 현재 행을 닫고 새 행을 활성화해야 하므로 훨씬 오래 걸린다. 이 때문에 메모리 접근 패턴에 따라 DRAM의 실효 성능이 크게 달라지는 것이다. 순차 접근이 랜덤 접근보다 빠른 이유가 바로 여기에 있다.

DRAM의 또 다른 특성은 리프레시(refresh)가 필요하다는 것이다. 커패시터의 전하는 시간이 지나면 자연스럽게 방전되므로, 보통 64밀리초마다 모든 행을 한 번씩 읽고 다시 써서 전하를 복원해야 한다. 리프레시 중에는 해당 뱅크에 접근할 수 없으므로, 이것도 성능에 영향을 미친다.

숫자로 보는 메모리 지연 시간

메모리 계층 각 수준의 접근 시간을 비교하면 캐시의 중요성이 명확해진다.

동작	대략적 시간
L1 캐시 히트	1 ns
L2 캐시 히트	3-10 ns
L3 캐시 히트	10-30 ns
DRAM 접근	50-100 ns
NVMe SSD 랜덤 읽기	25-100 μs
SATA SSD 랜덤 읽기	100-200 μs
HDD 랜덤 읽기	3-10 ms

L1 캐시 히트와 DRAM 접근 사이에 약 100배의 차이가 있다. DRAM과 HDD 사이에는 약 10만 배의 차이가 있다. 프로그램의 작업 집합이 L1 캐시에 들어가느냐, L3까지 내려가느냐, DRAM까지 내려가느냐에 따라 성능이 극적으로 달라지는 것이다.

이 숫자들은 왜 데이터 구조의 메모리 레이아웃이 알고리즘의 시간 복잡도만큼이나 중요한지를 설명한다. 이론적으로 더 효율적인 알고리즘이라도 캐시 미스를 많이 유발하면, 단순하지만 캐시 친화적인 알고리즘보다 실제 성능이 떨어질 수 있다. 연결 리스트보다 배열이 대부분의 경우 빠른 이유가 바로 공간적 지역성의 차이에서 비롯된다.

메모리 대역폭

접근 지연 시간과 함께 중요한 지표가 메모리 대역폭(bandwidth)이다. 대역폭은 단위 시간당 전송할 수 있는 데이터의 양을 의미하며, 현대 DDR5 메모리는 채널당 약 50-60 GB/s의 이론적 대역폭을 제공한다. 듀얼 채널 구성이면 이것이 두 배가 된다.

그러나 실제로 이 대역폭을 온전히 활용하기는 쉽지 않다. 랜덤 접근 패턴에서는 행 활성화 오버헤드 때문에 실효 대역폭이 크게 줄어든다. 대역폭을 최대한 활용하려면 순차 접근 패턴을 유지하고, 프리페치를 활용하며, 여러 메모리 요청을 병렬로 발생시키는 것이 필요하다. CPU의 하드웨어 프리페처는 접근 패턴을 감지하여 필요할 것으로 예측되는 데이터를 미리 캐시로 가져오는데, 순차 접근이나 일정한 스트라이드 접근에서 가장 효과적으로 동작한다.

다음 글에서는 가상 메모리를 다룬다.