Placement Policy

Cache Placement Policy는 캐시 메모리에서 특정 메모리 블록이 캐시에 저장될 위치를 결정하는 규칙을 의미한다.
이는 캐시의 구조와 데이터 접근 패턴에 따라 성능과 효율성에 큰 영향을 미친다. Placement Policy는 캐시 메모리의 설계와 운영에서 중요한 역할을 하며, 주로 다음 세 가지 주요 유형으로 나뉜다:

  • Direct-Mapped Cache
  • Fully Associative Cache
  • Set-Associative Cache.

Cache Placement Policy란?

  • 정의: Placement Policy는 특정 메모리 블록이 캐시에 저장될 때, 캐시 내에서 어느 위치(캐시 라인)에 저장될지를 결정하는 규칙이다.
  • 목적:
    • 캐시 메모리의 효율적인 사용.
    • 데이터 접근 속도 최적화.
    • 충돌(Collision) 관리: 동일한 캐시 라인에 여러 데이터가 매핑되는 상황을 최소화.

Cache Placement Policy는 데이터가 캐시에 저장되는 위치를 결정하며, 시스템 성능과 효율성에 직접적인 영향을 미친다.
Direct-Mapped, Fully Associative, Set-Associative 각각 장단점이 있으므로, 애플리케이션 요구사항과 하드웨어 제약 조건을 고려하여 적절한 정책을 선택해야 한다.
Set-Associative는 대부분의 현대 시스템에서 자주 사용되는 절충안으로, 성능과 비용 간 균형을 제공한다.

주요 Placement Policy 유형

Direct-Mapped Cache

특징
  • 각 메모리 블록은 캐시의 특정 위치(캐시 라인)에만 매핑된다.
  • 메모리 주소를 “오프셋(Offset)”, “인덱스(Index)”, “태그(Tag)“로 나누어, 인덱스를 사용해 특정 캐시 라인을 결정한다.
작동 방식
  1. 주소 분해:
    • 메모리 주소는 다음과 같은 세 부분으로 나뉜다:
      • Offset: 캐시 라인 내에서 특정 바이트를 지정.
      • Index: 캐시 내 특정 세트를 지정.
      • Tag: 동일 인덱스 내에서 데이터 구분.
  2. 매핑:
    • Index 값을 기반으로 해당 메모리 블록이 저장될 캐시 라인을 결정한다.
장점
  • 구현이 간단하고 빠르다.
  • 하드웨어 비용이 낮다.
단점
  • 충돌이 자주 발생할 수 있음(Collision): 서로 다른 메모리 블록이 동일한 캐시 라인에 매핑될 경우, 이전 데이터가 덮어씌워진다.
  • 충돌로 인해 캐시 미스(Cache Miss)가 증가할 수 있음.

Direct-Mapped Cache
https://en.wikipedia.org/wiki/Cache_placement_policies#/media/File:Direct-Mapped_Cache_Snehal_Img.png

Fully Associative Cache

특징
  • 메모리 블록은 캐시의 모든 라인에 저장될 수 있다(제한 없음).
  • 태그(Tag) 필드를 사용하여 특정 데이터를 식별한다.
작동 방식
  1. 주소 분해:
    • 메모리 주소는 “태그(Tag)“와 “오프셋(Offset)“으로만 구성됩니다(인덱스 없음).
  2. 매핑:
    • 모든 캐시 라인을 검색하여 태그가 일치하는 데이터를 찾는다.
장점
  • 매우 유연하며, 충돌 문제(Collision)가 발생하지 않는다.
  • 높은 히트율(Cache Hit Rate)을 기대할 수 있다.
단점
  • 태그 비교를 위해 모든 캐시 라인을 검색해야 하므로, 하드웨어 복잡성과 비용이 증가한다.
  • 검색 시간이 길어질 수 있다.

Fully Associative Cache
https://en.wikipedia.org/wiki/Cache_placement_policies#/media/File:Fully-Associative_Cache_Snehal_Img.png

Set-Associative Cache

특징
  • Direct-Mapped와 Fully Associative의 절충안이다.
  • 캐시는 여러 개의 “세트(Set)“로 나뉘며, 각 세트는 여러 개의 “캐시 라인"을 포함한다.
  • 메모리 블록은 특정 세트에만 매핑되지만, 세트 내에서는 어느 라인에든 저장될 수 있다.
작동 방식
  1. 주소 분해:
    • 메모리 주소는 “오프셋(Offset)”, “인덱스(Index)”, “태그(Tag)“로 구성된다.
      • Offset: 세트 내 특정 바이트를 지정.
      • Index: 특정 세트를 지정.
      • Tag: 동일 세트 내에서 데이터 구분.
  2. 매핑:
    • Index 값을 기반으로 특정 세트를 선택하고, 세트 내에서 태그 비교를 통해 데이터를 찾는다.
장점
  • 충돌 문제를 줄일 수 있다(Direct-Mapped보다 적음).
  • Fully Associative보다 하드웨어 복잡도가 낮다.
단점
  • Direct-Mapped보다 구현이 복잡하며, 비용이 증가할 수 있다.
  • 세트 내에서 태그 비교가 필요하므로 검색 시간이 늘어날 수 있다.

Set-Associative Cache
https://en.wikipedia.org/wiki/Cache_placement_policies#/media/File:Set-Associative_Cache_Snehal_Img.png

Placement Policy 예제

  • 예제 설정
    1. 메인 메모리 크기: 16KB (4바이트 블록 단위로 구성).
    2. 캐시 크기: 256바이트 (블록 크기 4바이트).
    3. 결과적으로 총 64개의 캐시 라인 존재 (256 / 4 = 64).

  1. Direct-Mapped

    • 각 메모리 블록은 고유한 인덱스를 기반으로 정확히 하나의 캐시 라인에 매핑된다.
    • 예: 주소 0x0000 → 인덱스 0, 주소 0x0100 → 인덱스 0 (충돌 발생 가능).

  2. Fully Associative

    • 모든 메모리 블록은 어떤 캐시 라인에도 저장될 수 있다.
    • 예: 주소 0x0000과 0x0100 모두 자유롭게 다른 라인에 저장 가능.

  3. Set-Associative (예: 2-Way Set Associative)

    • 총 32개의 세트로 나뉘며, 각 세트는 2개의 캐시 라인을 포함한다.
    • 예: 주소 0x0000과 0x0100 모두 같은 세트에 매핑되지만, 두 개의 다른 라인에 저장 가능.

Placement Policy 선택 시 고려사항

  1. 워크로드 특성:

    • 데이터 접근 패턴이 지역성을 가지는 경우 Set-Associative가 적합할 수 있음.
    • 랜덤 접근 패턴에서는 Fully Associative가 더 효과적일 수 있음.

  2. 하드웨어 비용:

    • Direct-Mapped는 가장 저렴하지만 충돌 문제 발생 가능성 높음.
    • Fully Associative는 가장 유연하지만 구현 비용이 높음.

  3. 성능 요구사항:

    • 높은 히트율을 요구하는 경우 Fully Associative 또는 Set-Associative가 더 적합함.

참고 및 출처