[OS] Cache hit rate

Memory Hierachy를 통해 Cache의 동작 방식과 Cache hit rate 또한 이를 높일 수 있는 방법을 알아보자.

Compuert's Memory

메모리란 프로그램(명령어와 데이터)을 저장하는 공간이다. 메모리의 가격, 크기, 속도를 따졌을 때, SRAM은 DRAM보다 빠르지만 비싸고 용량이 작다. DRAM은 느리지만 용량이 크고 가격이 싸다.
많은 조건이 있기 때문에 컴퓨터를 구성할 때 하나의 기술에만 의존할 수 없다. 이들을 계층 관계로 조화롭게 구성하여 더 효율적인 방법을 찾아야 한다.

게다가 메모리는 프로세서의 속도와 중심을 맞춰야 성능에 문제가 일어나지 않는다.
둘 다 느리다면 상관없겠지만 차이가 존재한다면 문제가 된다.

Memory Hierarchy

더 빠른 메모리일수록 processor와 물리적으로 가까이 있어야한다. 물리적 위치에 따라 가까우면Upper Level, 멀다면 Lower level이라 칭한다.

여기서 전략은 processor와 가깝고 더 빠른 Upper level의 접근 빈도를 높히고, Lower level의(메모리) 접근 빈도를 낮춰야 한다.
이를 위해 빈번하게 접근하는 data를 Upper level에 저장해야한다. 이러한 데이터를 hot data라 칭한다.

이의 근간은 참조 지역성(Locality of reference)이다
주어진 시간에 프로그램에서 자주 접근되는 데이터가 존재하고 이는 시간에 따라 바뀐다.

두 가지의 지역성이 존재하며 이는 다음과 같다.

• Temporal locality: 시간적 지역성은 반복문과 같다. 한 번 접근한 reference는 가까운 미래에 접근될 확률이 높다.
• Spatial locality: 어떤 reference가 접근됐을 때, 공간적으로 근처에 있는 data들이 참조될 확률이 높다. ex) array, table
  
  시간에 따라 자주 접근되는 메모리 location을 시각화한 것이다.

Average Access Time

upper level의 메모리에 접근하는 시간을 T1 lower level을 T2라고 하자.
여기서 hit라는 용어는 상위계층에서 처리할 데이터를 찾는 것을 의미한다. miss는 하위계층에서 발견하는 것을 의미한다.
hit rate(H)는 상위 계층에서 데이터를 발견할 확률이다.

example 1

• T1: 0.1
• T2: 1us
• H: 0.95
• M: 0.05

이 때 메모리 접근의 평균 시간은 다음과 같다. T = (0.95)(0.1 us) + (0.05)(0.1 us + 1 us) = 0.15 us

hit ratio가 높으니, 용량은 커지며 메모리 접근이 상위 계층에서만 일어날 것 같은 효과가 나타난다.

example 2

H_1: 0.97, H_2: 0.99
hit: 1 cycle
miss: 100 cycle
T_1: 4 cycle T_2: 2 cycle
약 두 배 차이가 나는 것 같다.
miss rate는 각각 0.03, 0.01 이므로 이것으로 보면 3배차이가 난다.

평균 접근 시간에 대한 그래프이다.
$T = H\times T1 + (1- H)(T1 + T2)$
$T = - T2 H + (T1 + T2)$

Cache Memory

위에서 확인한 가장 상위계층의 대표적인 메모리가 cache memory이다. locality에 충족하는 데이터를 이 메모리에 저장하자라는 목표를 가진 메모리이다.

공간적 지역성: 특정 데이터에 접근했을 때, 근처에 있는 데이터들도 접근할 가능성 높다 했다.
그럼 특정 데이터(word)를 접근했다면 그 근처에 있는 데이터들도 접근해야하기 때문에 block 단위로 데이터를 저장하게 된다.

시간적 지역성: 레퍼런스가 한 번 참조되면 그 레퍼런스가 미래에 참조될 가능성이 높다. 이를 cache에 저장한다.

Cache Design

예를 통해, cache 메모리의 구조와 원리를 알아보자.

• $2^n$개의 word을 가진 DRAM이 있다. k개의 word의 집합을 하나의 block으로 보자.($2^n/k$)
• C(C < M)개의 메모리 블럭을 가진 SRAM이 있다.(block 크기가 SRAM과 같다.)

Mapping function

mapping function을 통해 어떤 cache의 어디에 block 단위 data가 저장될 지 알아보자.
Tag는 어떤 특정 block이 저장되어 있는지 나타낸다.

쉬운 이해를 위해 word=block으로 본다.

Direct Mapped

Main memory

8개의 저장공간이 있는 cache와 32개의 memory가 있다.
memory의 주소를 모듈러 연산을 통해 나온 값을 cache의 line에 저장한다. 이를 식별할 수 있는 데이터가 tag이고, 이는 나누기 연산의 결과값을 통해 식별한다.
값 참조시 miss가 났을 때, main메모리에서 cache에 저장한다.
값 참조시 hit일 경우, cache에서 바로 읽는다.

miss일 경우 저장해야하지만 이미 값이 존재할 경우 이를 처리할 다양한 방법이 있다.

이에 대한 단점은 한 칸밖에 저장하지 못하여 race condition 문제가 있다.

이에 대한 해결책은 다음과 같다.

2-way Set-Associative

main memory

이전의 Direct mapped 방식은 한 공간에 네 개의 block이 들어갈 수 있었다. 하지만 이번엔 race condition을 완화하기 위해 각 8개의 block을 두 개의 공간으로 관리한다.(총 4개의 block)
8개의 block을 식별해야 하므로 3개의 비트가 필요하게 된다. 저장할 block은 4공간으로 분류하므로 모듈러 연산을 4로 수행한다. 값을 읽거나 저장할 때, 두 개의 공간이 있으므로 두 번 확인해야한다. 이는 hit rate를 높힐 수 있지만, 두 자리 scan을 위한 cost가 올라간다.

cache의 설계에 따라 생기는 효과를 알아보자.

• 더 유연하게 mapping function을 만들어 block의 단위를 크게 만든다면 탐색할 때 scan 횟수가 늘어나기 때문에 회로 구성이 복잡해진다.
• cache의 크기가 늘어난다면 cache hit rate가 늘어나겠지만, 크면 클수록 block을 탐색하는데에 시간이 많이 걸린다.
• block의 크기가 크다면 일시적으론 공간적 지역성으로 인해 초반에 cache hit rate가 늘어나겠지만 시간의 흐름에 따라 block이 달라지기 때문에 큰 block들이 miss 난다면 성능이 급격하게 안 좋아질 수 있다.

Cache read operation

CPU에서 메모리 주소를 통해 데이터 접근 하려함 -> 캐쉬를 먼저 봄

성공 시:저 주소를 포함한 데이터가 있다? CPU로 바로 전달함
실패 시: 메모리에서 찾음 -> cache에 저장하기 위해 탐색 -> 꽉 차있으면 캐시 삭제(아님 저장) -> CPU에 전달

Cache write operation

read는 hit이면 메모리를 신경쓸 필요가 없다. 하지만 write는 cache에 있어도 메모리에 update 해야한다. wrtie 연산이 왔을 때 바로 메모리에 접근할까?(write-through) 아님 미뤘다가 한 번에 할까?(write-back) 메모리 접근 시점이 중요하다.

write-back은 성능이 좋아지겠지만, 일관성 문제가 일어난다. 멀티코어 환경에서 각각 프로세서의 cache의 값이 메모리와 모두 같지 않을 수 있다.

miss가 난다면 메모리에서 값을 캐쉬로 가져와 변경하는 것을 write-allocate라 한다.(메모리를 언제 수정할지는 컴퓨터 구조에서 배운다.)
바로 memory에 write하는 것을 No-write-allocate라 한다.

대개 wrtie-back과 wrtie-allocate를 사용한다

Example

CPU 1, CPU 2가 모두 X를 cache로 read해 오고, CPU 1이 32로 write한다. 메모리와 CPU 2는 여전히 24를 가지고 있다.(이의 해결책은 컴퓨터 구조에서 배우자.)