Cache

Cache

Cache란

데이터나 값을 미리 복사해 저장하는 하드웨어 혹은 소프트웨어 구성 요소.

캐시에서 데이터를 읽는 것이 원래 저장소에서 값을 읽는 것 보다 빠름.

Cache 종류

  1. HW cache
  2. In-network cache
  3. SW cache

동작 방식

  • 캐시는 여러 항목의 목록으로 구성됨. 각 항목은 원래 데이터의 복사본을 가지고 있고, 원래 데이터의 ID를 나타내는 태그도 있음.
  • Cache hit: 데이터를 원래 저장소에서 찾기 전에 캐시를 확인하고, 캐시의 항목중에 데이터가 있으면 이를 사용하는 상황.
  • Cache miss: 캐시의 모든 항목에 데이터가 없는 상황. 원래 저장소에 접근해서 데이터를 가져와야 하고, 이 데이터를 통해 캐시에 복사함.
  • Hit ratio: 데이터의 전체 접근 중 cache hit이 일어난 비율.

Cache Replacement Policy

Cache miss가 발생한 경우, 기존 캐시 항목 중 하나가 캐시에서 제거되고 새로 찾은 데이터를 넣어야 함. 이 때 제거할 항목을 선택하는 알고리즘.

  • Belady’s algorithm: 가장 오랫동안 사용되지 않을 항목 제거 (구현 불가)
  • Random Replacement: 랜덤한 항목 제거
  • First In First Out: 들어온 순서대로 항목 제거
  • Least Recently Used: 가장 최근에 사용되지 않은 항목 제거

Writing Policy - HIT

Cache hit이 발생한 상태에서 캐시에 있는 값을 변경하는 경우, 원래 저장소에도 이 변경사항이 반영되어야 함. 언제 이를 반영할지는 두 가지 policy 존재.

  1. Write-through: 변경됨과 동시에 원래 저장소에 쓰기.
  2. Write-back: 변경된 내용은 캐시에만 기록하고, 캐시에서 제거될 때 원래 저장소에 쓰기.

Writing Policy - MISS

값을 변경하려고 하는 데 그 값이 캐시에 없어서 Cache miss가 발생하는 경우 역시 두 가지 policy 존재.

  1. Write allocate: 캐시에 원래 저장소의 데이터를 올리고, 캐시에 값을 쓰기. Write back과 같이 사용.
  2. No-write allocate: 캐시에 접근하지 않고 원래 저장소의 값에 쓰기. Write through와 같이 사용.

보통 write allocate + write back 조합을 사용함.

HW Cache

  • CPU cahce
  • Transition lookaside buffer: MMU가 가진 캐시로, virtual address를 physical address로 변환한 정보를 저장.

CPU Cache

  • CPU가 메인 메모리에 빠르게 접근하기 위해 사용하는 캐시. 메인 메모리보다 훨씬 빠른 대신 작음.
  • SRAM으로 구현되며, 단계에 따라 L1, L2, L3 등이 존재.
  • CPU 캐시는 여러 개의 세트로 이루어져있고, 각 세트마다 여러개의 항목을 가짐.
  • 각각의 메인 메모리는 하나의 세트와 연결되게 됨.

CPU Cache 항목 구조

각 캐시 항목은 다음과 같이 구성됨.

| Tag | Data block | Flag bits |

  • Tag: 메인 메모리 주소의 일부분, 이를 통해 주소를 찾을 수 있다.
  • Data block: 메인 메모리에서부터 가져온 데이터.
  • Flag bits: 현재 캐시 항목에 데이터가 있는지 여부.

반면 메모리 주소는 다음과 같이 구성됨.

| Tag | Index | Block offset |

  • Index: 어떤 캐시 세트에 들어갈지를 결정하는 부분. 이 길이는 lg(캐시 세트의 개수)
  • Block offset: 한 data block 내에서의 위치를 특정. 이 길이는 lg(데이터 블록의 크기)

Cache Placement Policy

캐시의 각 세트와 세트의 항목이 몇 개 있는지에 따라 다음과 같은 캐시 종류 존재.

  • Direct-mapped cache
  • Fully-associative cache
  • (N-way) Set-associative cache

Direct-mapped Cache

캐시의 각 세트마다 1개의 항목을 가지는 경우. 메모리 주소의 Index를 통해 세트를 찾으면 바로 항목을 찾을 수 있다.

  • 장점: 캐시 위치 찾기가 빠르고, 교체 알고리즘이 필요 없음.
  • 단점: 한 세트에 한 개의 항목밖에 없기 때문에 hit ratio가 낮음, 저장하는 데 시간이 걸림.

Fully-associative Cache

캐시의 세트가 1개이고 해당 세트에 모든 항목을 가지는 경우. 각 메모리 주소는 모든 항목을 선택 가능하다. Index 부분이 없고, Tag를 통해 원하는 값을 바로 찾을 수 있다.

  • 장점: 캐시에 유동성을 줘서 캐시 활용률이 높음. 저장하기도 빠름.
  • 단점: 데이터를 찾기 위해 모든 캐시를 다 순회해야 하기 때문에 굉장히 느리고 무거움.

Set-associative Cache

Fully-associative cache와 direct-mapped의 결합. 캐시는 여러개의 세트를 가지고, 각 세트는 N개의 항목을 가지는 경우.

  • Direct-mapped 보다 저장 속도는 빠르지만 검색 속도는 느림.
  • Fully-associative보다 저장 속도는 느리지만 검색 속도는 빠름.

Web Cache

SW cache의 일종으로 웹 브라우저 혹은 웹 프록시 서버가 사용. 웹 서버로부터 응답받은 웹 페이지 혹은 이미지 등을 저장. 웹 서버와의 통신을 줄여주고, 사용자에게 빠른 응답을 제공.

ISP가 caching proxy server를 통해 네트워크 사용자들에게 캐시를 제공하기도 함.

Locality of references

캐시가 강력한 성능을 내는 이유는 다음과 같은 참조 지역성 때문.

  • Temporal locality: 특정 위치의 메모리를 참조했다면, 해당 위치는 가까운 시간 내에 다시 참조될 확률이 높음.
  • Spatial locality: 특정 위치의 메모리를 참조했다면, 해당 위치 근처의 메모리들은 가까운 시간내에 참조될 확률이 높음.

References

  1. https://en.wikipedia.org/wiki/Cache_(computing)
  2. https://en.wikipedia.org/wiki/Cache_placement_policies
  3. https://en.wikipedia.org/wiki/Cache_replacement_policies
  4. https://en.wikipedia.org/wiki/Locality_of_reference