csapp 6단원 마무리

6.4 캐시 메모리

6.4.1 일반적인 캐시 메모리 구성

캐시는 S=2s개의 캐시 집합의 배열로 구성

각 집합은 E개의 캐시라인,

각 라인은 B=2b바이트듸 데이터 블록, 유효비트, 태그 비트로 구성된다

[ Valid(유효비트) | Tag(태그 비트들) | Data Block(데이터 블록 B바이트) ]

• 데이터 블록
  메모리에서 가져온 연속된 B바이트 실제 데이터
  CPU를 위한 데이터

• 유효 비트
  현재 유효한지 표기하는 1비트
  • 0이면 무효 -> 미스로 처리
  • 1이면 사용 가능 -> 태그 비교로 최종 확인

• 태그 비트
  어느 메모리 블록을 담고 있는지 식별용 라벨
  같은 세트의 주소들 중 정확히 내 주소의 블록인지 판별 할 때 사용

6.4.2 직접 매핑 캐시

각 집합에 라인 하나만 있는 가장 간단한 캐시다

주소는 태그, 집합 인덱스¹, 블록 오프셋²으로 분할되어 사용

[ Tag(20) | Set Index(8) | Block Offset(4) ]

미스가 발생하기 쉬우며
미스 발생시, 새 블록은 주소의 집합 인덱스에 따라 결정된 집합의 유일한 라인에 저장

접근 예시

32-bit 주소, 직접 매핑

• 총 캐시 용량 C = 4KB, 블록 크기 B = 16B → b = log2(16)=4

• 세트 수 S = 4096 / 16 = 256 → s = log2(256)=8

• 태그 비트 수 t = 32 - (8+4) = 20

[ Tag(20) | Set Index(8) | Block Offset(4) ]

예) 주소 0xCAFEBABE를 쪼개면

• Block Offset = 하위 4비트 = 0xE (블록 내부 14번째 바이트)

• Set Index = 그 다음 8비트 = 0xAB (세트 171번)

• Tag = 상위 20비트 = 0xCAFEB

즉 이 주소는 세트 0xAB로 가고, 그 세트의 유일한 라인에 Tag 0xCAFEB가 저장돼 있어야 히트

6.4.3 집합-연관 캐시

각 집합에 E개 이상의 라인이 있는 캐시

집합 선택은 직접 매핑 캐시와 동일

라인 매칭 시 확인해야 할 라인이 늘어 더 복잡해짐

미스 발생 시 교체 정책이 필요함

(예: LRU³, LFU⁴)

6.4.4 완전-연관 캐시

오직 하나의 집합(S=1)만 있는 캐시

집합이 하나기에 집합 인덱스 비트 같은 건 없고

주소는 태그와 블록 오프셋으로만 구성

크고 빠른 캐시를 만들기 불리해 작은 캐시에 사용됨

6.4.5 쓰기 문제 (Issues with Writes)

• 쓰기 히트(Write hits) 처리:

  • 쓰기-통과(Write-through):
    캐시와 다음 하위 레벨 모두에 즉시 데이터를 쓴다

  • 쓰기-뒤로(Write-back):
    캐시에만 쓰고, 라인이 교체될 때까지 기다렸다가 다음 하위 레벨에 쓴다

• 쓰기 미스(Write misses) 처리:

  • 쓰기-할당(Write-allocate):
    미스된 블록을 하위 레벨에서 가져와 캐시에 로드하고 캐시에 쓴다

  • 비-쓰기-할당(No-write-allocate):
    미스된 블록을 캐시에 로드하지 않고 하위 레벨에 직접 쓴다

이 2가지-2가지를 조합해 4가지 조합 사용가능하다

6.4.6 실제 캐시 계층 구조의 해부

캐시는 데이터 뿐만이 아닌 명령어도 저장한다

i/d로 분리해서 말이다

• 명령어만 저장하는 케시는 i-cache

• 데이터만 저장하는 캐시는 d-cache

• 둘을 함께 저장 하는 캐시는 통합(unifided) 캐시

Intel Core i7을 예시로 캐시 계층을 설명한다

• cpu 칩에 4개 코어

  • 각 코어에 L1 i-cache, L1 d-cache, L2 통합 캐시

    • 모든 코어가 칩 위의 L3 통합 캐시 공유

SRMA캐시 전부 CPU칩 내부에 있음

분리형 L1의 이유

명령어 페치i와 데이터 접근d를 동시에 수행

읽기 중심i과 읽기/쓰기 혼합d으로 각기 최적화

계층별 성격

• L1: 매우 작고 빠름(≈4 cyc). 코어 전용, 레이턴시 최소화

• L2: 코어 전용 통합 캐시, 용량↑ 레이턴시↑ (≈10 cyc). L1 완충

• L3: 칩 내 공유 통합 캐시(≈40–75 cyc). 코어 간 데이터 공유/재사용 비용 절감

• 전부 온칩 SRAM → DRAM 왕복보다 훨씬 빠름

6.4.7 캐시 파라미터가 성능에 미치는 영향

캐시 성능 주요 평가 기준:

• 히트율(Hit rate): 메모리 참조 중 히트의 비율

• 미스율(Miss rate): 메모리 참조 중 미스의 비율

• 미스 페널티(Miss penalty): 미스 때문에 추가로 필요한 시간

캐시크기가 클수록 히트율🔺 히트시간🔺

블록 크기가 크고 공간지역성 활용시
라인수🔻 히트율🔺 전송량🔺 패널티🔺

연관도(한 세트 안에 들어갈 수 있는 캐시 라인 수)
높아지면 충돌 미스🔻 히트시간🔺 패널티🔺

6.5 캐시 친화적인 코드 작성

프로그램 지역성 개선을 통해 캐시 미스율을 낮출 수 있다

• 지역 변수의 반복 참조:
  컴파일러가 이들을 레지스터 파일에 캐시해 시간 지역성 🔺

• 스트라이드-1 참조 패턴⁵:
  캐시가 데이터를 연속적 블록으로 저장해 공간 지역성 🔺

6.6 프로그램 성능에 미치는 캐시의 영향

요점 :

코드가 메모리를 “가깝고(캐시), 연속적으로(Stride-1), 작게(작업 집합)” 쓰도록 만들면 성능이 급격히 좋아진다

6.6.1 메모리 산

• 의미: 크기(size)와 스트라이드(stride)에 따른 읽기 처리량(MB/s) 지형도

• 시간 지역성의 능선: 작업 집합이 L1/L2/L3/DRAM에 들어맞는 구간에서 처리량이 급변(예시 수치: L1 구간 수십 GB/s vs DRAM 하한 수백 MB/s)

• 공간 지역성의 경사: 스트라이드가 커질수록 처리량이 감소. Stride-1일 때 프리페처가 가장 잘 작동

• 해석: “작게 읽고, 자주 재사용하며, 연속으로 접근” 할수록 산의 높은 지대를 밟음

6.6.2 공간 지역성을 높이기 위한 루프 재배열

• 6가지 루프 순서 (i, j, k의 순열)는 기능은 같지만 캐시 거동⁶이 다르다

• 내부 루프에서 어떤 배열 쌍을 주로 읽느냐에 따라 AB / AC / BC 세 클래스로 묶인다

• 각 클래스는 반복당 로드/스토어/미스 특성이 달라 성능 차이가 크다 실측에선 최고/최저가 ~40× 차이 난다

• 원칙

  • 내부 루프는 Stride-1이 되도록 인접한 메모리를 훑게 만들 것(행 우선인 C에서는 보통 열보다 행을 안쪽)

  • 불필요한 쓰기(store)와 미스를 최소화

  • 필요 시 블로킹/타일링⁷ 으로 작업 집합을 L1/L2에 머무르게 한다

6.6.3 프로그램에서 지역성 활용하기

• 메모리 계층: 작고 빠른 캐시 ↔ 크고 느린 DRAM. 실질 접근 속도는 지역성에 좌우됨

• 좋은 지역성 = 낮은 미스율 = 빠른 실행

• 체크리스트

  1. Stride-1 순회(배열은 인접 원소부터)

  2. 루프 교환(loop interchange)⁸ 으로 안쪽 루프를 연속 접근으로

  3. 블로킹(tiling) 으로 작업 집합을 캐시에 맞추기

  4. 누적 변수로 메모리 쓰기 횟수 감소

  5. 데이터 구조 개선: SoA(배열의 구조)로 필요한 필드만 연속하게

  6. 불필요한 임시/큰 객체 생성 자제, 재사용 증가

  7. 측정-검증: 실제 머신에서 처리량/미스율을 계측해 선택 확인

둘의 차이