05-1 메모리 계층구조

0. 학습 목표

• 지역성(Locality)이 왜 메모리 계층구조를 가능하게 하는지 설명한다.
• 캐시의 핵심 설계 요소(배치/탐색/교체/쓰기 정책)를 정의하고, 성능 지표(AMAT, CPI 영향)를 계산한다.
• 연관도, 블록 크기, 다단 캐시, TLB/가상메모리, 일관성(coherence) 문제를 큰 그림으로 연결한다.

1. 지역성의 원리(Principle of Locality)

1.1. 프로그램은 항상 전체 메모리를 쓰지 않는다

• 프로그램은 어느 시점이든 주소공간의 일부만 집중적으로 접근한다.

1.2. 두 종류의 지역성

• 시간적 지역성(Temporal locality): 최근 접근한 항목은 곧 다시 접근될 가능성이 높다.

  • 예: 루프의 명령어, 반복적으로 갱신되는 변수(Induction variable)

• 공간적 지역성(Spatial locality): 최근 접근한 위치 근처도 곧 접근될 가능성이 높다.

  • 예: 순차적 명령어 인출, 배열 데이터 순회

2. 지역성을 계층구조로 활용하기

2.1. 메모리 계층 구조의 직관

• 느리지만 큰 저장장치(디스크)에 모든 것을 두고,
• 최근(그리고 근처) 데이터를 더 작은 DRAM(메인 메모리)로 복사,
• 더 최근(그리고 근처) 데이터를 SRAM(캐시, CPU 근접)으로 복사한다.

2.2. 계층에서의 기본 용어

• 블록(block/line): 계층 간 복사의 최소 단위(보통 여러 워드 포함)
• 상위 계층에 있으면 히트(hit), 없으면 미스(miss)
• 히트율(hit ratio) = hits/accesses
• 미스율(miss ratio) = misses/accesses = 1 − hit ratio
• 미스 패널티(miss penalty): 하위 계층에서 블록을 가져오는데 드는 시간

3. 메모리 기술(Technology) 개요

3.1. SRAM vs DRAM vs 디스크 (속도·가격 스케일)

• SRAM: 0.5–2.5ns, 매우 비쌈(GB당 수백~천 달러)
• DRAM: 50–70ns, 상대적으로 저렴
• 디스크: 5–20ms, 매우 저렴(GB당 센트 단위)
• 이상적 메모리는 SRAM의 속도 + 디스크의 용량/가격을 동시에 갖는 것(현실적으로 불가)

3.2. DRAM 동작 핵심

• 캐패시터에 전하로 저장, 트랜지스터 1개로 접근
• 주기적 리프레시(refresh) 필요(행(row) 단위로 읽고 다시 씀)

3.3. DRAM 고급 조직

• 비트는 2D 배열(행/열)
• DRAM은 보통 행 전체(row) 활성화
• 버스트 모드(burst mode): 한 행에서 연속 워드를 더 낮은 지연으로 공급
• DDR: 상승/하강 에지 모두 전송, QDR: DDR 입출력 분리

3.4. DRAM 세대(용량 증가, $/GB 하락)

• 1980년대 Kibibit → 2010s Gibibit로 급격한 집적도 증가 및 가격 변화

3.5. DRAM 성능 요인

• Row buffer(병렬 read/refresh), Synchronous DRAM(연속 burst), Banking(병렬 접근) → 주로 대역폭 개선

4. 플래시와 디스크(저장장치 관점)

4.1. 플래시(Flash)

• 비휘발성, 디스크보다 100~1000배 빠름, 작고 저전력·견고
• 단, $/GB는 디스크보다 비싸고 DRAM보다는 쌈(중간 지대)

4.2. 플래시 타입

• NOR: 랜덤 읽기/쓰기, 임베디드 instruction memory
• NAND: 더 고밀도, 블록 단위 접근, GB당 저렴(USB/스토리지)
• 마모(wear-out) 문제 → wear leveling 필요

4.3. 디스크 접근 시간 구성요소

• 섹터: ID + 데이터(512B, 4096B 제안) + ECC + 동기화 필드/갭
• 접근 비용: 큐잉 지연 + 탐색(seek) + 회전 지연 + 전송 + 컨트롤러 오버헤드
• 예제(15000rpm 등)에서 평균 읽기 시간이 6.2ms로 계산됨
• 실제 시스템은 지역성과 스케줄링으로 평균 seek가 더 작아질 수 있으며, 디스크 내부 캐시/프리패치도 활용

5. 캐시의 기본(Basics of Caches)

5.1. 캐시는 CPU에 가장 가까운 계층

• 캐시 설계의 첫 질문 두 가지
  1. 데이터가 캐시에 있는지 어떻게 아는가?
  2. 어디를 찾아봐야 하는가?

5.2. Direct-mapped cache

• 각 메모리 블록은 캐시의 딱 1곳에만 들어갈 수 있음
• 매핑: (블록 주소) mod (캐시 블록 수)
• 블록 수는 2의 거듭제곱 → 하위 비트로 index 구성

5.3. Tag와 Valid bit

• 같은 index로 여러 메모리 블록이 충돌할 수 있으므로, 어떤 블록이 들어있는지 식별 필요
• 블록 주소의 상위 비트를 tag로 저장
• 해당 라인이 비어있는지 확인하는 valid bit(초기 0)

5.4. 예제로 보는 direct-mapped 동작 흐름

• 8블록 캐시, 1 word/block 예시에서
  • 첫 접근은 miss → 해당 index에 (tag, data) 채움
  • 이후 같은 블록 재접근은 hit
  • 같은 index에 다른 tag가 들어오면 기존 내용이 교체됨(충돌)

5.5. 주소 분해(Address subdivision)

• 주소는 일반적으로 Tag | Index | Offset으로 분해
• offset은 블록 내부 바이트/워드 위치 결정
• 슬라이드 도식(페이지 25)에서 tag 비교 후 hit 여부 결정 흐름 제시

6. 블록 크기(Block size) 트레이드오프

6.1. 큰 블록은 언제 좋은가?

• 공간적 지역성 덕분에 큰 블록은 보통 미스율 감소에 유리

6.2. 하지만 캐시가 고정 크기라면

• 블록이 커지면 블록 개수 감소 → 경쟁 증가 → 미스율이 오히려 증가 가능
• 큰 블록은 pollution(불필요 데이터 유입) 증가
• 그리고 미스 시 한 번에 가져올 데이터가 많아져 미스 패널티 증가
• 완화 기법: early restart, critical-word-first

6.3. 계산 예시(블록 매핑)

• 64블록, 16B/block에서 주소 1200은
  • 블록 주소 ⌊1200/16⌋ = 75
  • 캐시 블록 번호 = 75 mod 64 = 11
  • Tag/Index/Offset 비트수도 함께 제시됨

7. 미스가 발생하면 CPU는?

• hit: 정상 진행
• miss: 파이프라인 stall + 하위 계층에서 블록 fetch
• I-cache miss: 인스트럭션 fetch 재시작
• D-cache miss: 데이터 접근 완료까지 대기

8. 쓰기 정책(Write policy)

8.1. Write-through

• 캐시 히트에서 캐시만 갱신하면 메모리와 불일치
• write-through: 캐시 + 메모리 둘 다 갱신
• 문제: 메모리 쓰기가 느리면 CPI가 폭증 가능
• 해법: write buffer(CPU는 즉시 진행, 버퍼가 찼을 때만 stall)

8.2. Write-back

• 히트 시 캐시만 갱신, 블록이 교체될 때 메모리에 반영
• 블록이 수정되었는지 dirty bit로 추적
• 교체 중 write-back도 write buffer로 숨길 수 있음

8.3. Write miss 정책(Write allocation)

• write-through에서 선택지

  • write allocate: 미스 시 블록을 가져와 캐시에 올린 뒤 씀
  • write around: 블록을 안 가져오고 하위 계층에 바로 씀

• 이유: 초기화처럼 한 블록을 쓴 뒤 읽는 패턴이면 write around가 유리할 수 있음

• write-back은 보통 블록을 가져오는 쪽(allocate)을 사용

9. 캐시 성능 측정: CPI/AMAT

9.1. CPU 시간 구성

• 실행 사이클(히트 시간 포함) + 메모리 스톨 사이클(주로 미스)

• 단순화하면

  • Memory stall cycles ≈ (Memory accesses / Program) × Miss rate × Miss penalty

9.2. CPI 예제

• I-miss=2%, D-miss=4%, miss penalty=100 cycles, base CPI=2, load/store=36%
• I쪽 미스 비용: 0.02×100 = 2 cycles/inst
• D쪽 미스 비용: 0.36×0.04×100 = 1.44 cycles/inst
• 실제 CPI = 2 + 2 + 1.44 = 5.44

9.3. AMAT(Average Memory Access Time)

• AMAT = Hit time + Miss rate × Miss penalty
• 예: hit 1cycle, miss penalty 20cycles, miss rate 5% → AMAT = 1 + 0.05×20 = 2 cycles(=2ns)

9.4. 핵심 메시지

• CPU가 빨라질수록(클럭↑, base CPI↓) 미스 패널티의 상대적 영향이 더 커짐
• 따라서 시스템 평가에서 캐시/메모리 거동을 무시하면 안 됨

10. 연관도(Associativity): direct ↔ set associative ↔ fully associative

10.1. 정의와 비용

• Fully associative: 아무 엔트리나 배치 가능 → 모든 엔트리를 동시에 비교(비용 큼)
• n-way set associative: set을 먼저 정하고(set index), 그 set 안에서 n개를 병렬 비교(n개의 comparator)

10.2. 예제로 보는 효과(미스 감소, 수익 체감)

• 64KB D-cache, 16-word block, SPEC2000에서

  • 1-way 10.3% → 2-way 8.6% → 4-way 8.3% → 8-way 8.1%

• 연관도를 늘리면 미스는 줄지만 효과는 점점 작아짐

10.3. 교체 정책(Replacement policy)

• direct-mapped: 선택권 없음
• set associative: (1) invalid 엔트리 우선, (2) 아니면 교체 정책 적용
• LRU: 2-way는 간단, 4-way는 관리 가능, 그 이상은 복잡
• Random: 높은 연관도에서 LRU와 성능이 거의 비슷하며 구현 쉬움

11. 다단 캐시(Multilevel caches)

11.1. L1/L2/L3 구조

• L1(Primary): 작고 빠름, hit time 최소화
• L2: 더 크고 느리지만 DRAM보다 빠름, 미스율 최소화(특히 main memory로 가는 global miss rate)
• 고급 시스템은 L3도 포함

11.2. CPI 예시(왜 L2가 필요한가)

• base CPI=1, 4GHz(0.25ns/cycle), miss rate=2%, main memory=100ns
• L1만 있으면 miss penalty=100ns/0.25ns=400 cycles
• CPI = 1 + 0.02×400 = 9
• L2 추가: L2 access=5ns(=20 cycles), global miss=0.5%
• CPI = 1 + 0.02×20 + 0.005×400 = 3.4 → 9/3.4=2.6배 성능 개선

12. 고급 CPU/소프트웨어와의 상호작용

12.1. Out-of-order CPU

• 미스 동안에도 독립 명령어를 실행할 수 있어 미스의 영향이 단순 CPI/AMAT만으로는 분석 어려움
• 데이터 의존성에 좌우 → 보통 시뮬레이션 기반 평가

12.2. 소프트웨어 접근 패턴

• 미스는 알고리즘/컴파일러 최적화에 의해 크게 달라짐

12.3. Blocking 최적화(DGEMM)

• 목표: 데이터가 캐시에서 교체되기 전에 재사용을 최대화
• DGEMM 기본 루프(내부 루프)와, BLOCKSIZE 기반 cache blocking 코드
• 블로킹 전/후로 지역성이 개선되는 흐름