[01-10] Cache miss 간단 정리

1월 11일에 쓰는 10일 글이다.

오늘 배포를 너무 열심히 해서 패스할까 하다가 금요일에 쉴거기 때문에 간단하게나마 글을 쓴다. 오늘도 빙글빙글 돌아가는 배포... deployparrot

오늘은 이번 인턴 면접 때 공통 질문으로 사용했던 Cache miss의 세 가지 타입과 해결법에 대해 간단하게 정리하고 넘어갈까한다.

캐시 메모리의 구조

우선 이 Cache miss가 일어나는 공간에 대해서 알아보자. 말그대로 Cache에서 발생한다.

캐시는 CPU process가 빠르게 데이터를 주고 받을 수 있도록 임시 저장소의 역할을 한다.

그렇다보니 메인 메모리에 비해서 사이즈가 작은데, 효율적으로 자주 사용할 것이라 생각하는 데이터를 저장하기 위해서 principle of locality를 사용한다.

시간 지역성 : 한번 참조된 데이터는 잠시 후에 또 참조될 가능성이 높다(for, while문 등의 반복문)
공간 지역성 : 참조된 데이터 근처의 데이터가 잠시 후에 조회될 가능성이 높다. (배열접근)

캐시 메모리는 cache block이라는 data group unit을 가진다. 각각의 block에 데이터를 담아 cache tag를 달아서 하나의 cache entry를 구성한다. 이 사이에 Validation bit가 있는데 이 비트가 0이면 cache data가 유효하지 않다는 뜻이다.

캐시 메모리의 size는 이 cache block의 전체 개수와 블록 하나 당의 size로 계산한다.

이러한 캐시 메모리 구조는 여러 종류가 있는데 그 중 세 가지를 살펴보자.

Direct Mapped Cache

가장 기본적인 캐시 구조다. memory block 하나에 cache의 block 한 개가 1:1 매핑되는 구조다. cache에 접근했는지 판단하기 위해서 하나의 cache block만 확인하면 된다. 메모리가 캐시보다 사이즈가 크기 때문에 여러 개의 memory block은 하나의 cache block을 공유한다. 이 여러개의 memory block은 tag로 구분한다.

캐시 메모리를 valid, tag, data로 구성한다.

Fully Associative Cache 1번과 정반대의 개념으로 memory block은 캐시 메모리의 빈 block이면 어디에든 저장될 수 있다. 그렇기 때문에 모든 cache의 block을 확인해야 hit인지 miss인 지 확인할 수 있다.
N-way Set Associative Cache 그 중간 어딘가다. 캐시 메모리를 N개의 block으로 구성된 set으로 나누고, memory block을 set 중 한 곳에 저장하는 것이다. N 값에 따라 조회해야하는 block의 개수가 달라진다.

추가로 cache가 데이터를 어떻게 조회하는지도 알아두면 좋은데 나중에 기회가 되면 다뤄보겠다. 그냥 메모리 주소값을 이리 저리 활용한다. modulo 연산이 사용된다.

Cache Hit & Miss

오늘의 메인이다.

CPU는 필요한 데이터가 있을 때마다 해당 데이터의 메모리 주소를 이용해서 캐시를 조회한다. 하드웨어 장치에서 물리적인 메모리 주소로 바로 연결해주기때문에 이 주소는 별도의 공간이 필요하지 않다.

Hit : CPU가 읽어오려고 하는 데이터가 캐시에 있는 경우

Hit rate : CPU가 요청한 데이터 중 캐시에 저장된 비율 Hit time : 캐시에서 데이터를 읽어오는 데 필요한 시간 Miss : CPU가 읽어오려고 하는 데이터가 캐시에 없는 경우

Miss rate : CPU가 요청한 데이터가 캐시에 없는 경우 (= 1 - Hit rate) Miss penalty : miss가 발생해 데이터를 block만큼 메인 메모리에서 캐시 메모리로 가져오는 데 필요한 시간

그리고 여기서 cache miss에는 여러 원인이 있다.

Compulsory miss 다른 이름은 Cold Start Miss다. 캐시가 모두 비어있을 때 최초로 데이터를 올릴 때 발생한다.
Capacity miss 말그대로 캐시의 용량이 부족해 발생한다. 접근하는 데이터 양이 캐시 블록의 사이즈를 넘기면 발생한다. 위의 구조를 보면 블록이 클 때는 공간 지역성을 활용할 수 있기 때문에 실패율은 감소하겠지만 전송해야하는 블럭 양이 많아지기 때문에 miss penalty는 증가할 수 있다. 그렇지만 반대로 블록이 작으면 조회를 더 많이 해야하기 때문에 miss rate가 증가하지만 전송해야하는 블럭 양이 적어지니 miss penalty는 감소한다고 본다.

블록이 너무 커진다면 캐시 내의 블록 개수가 적어지기 때문에 블록 내의 리소스를 많이 사용하지 못해도 쫓겨나버릴 수 있다.

Conflict miss. 다른 주소값을 가지더라도 index 8bit이 같다면 같은 set에 위치하게 되는데, 우연히 동일한 set에 여러번 접근되면 특정 set에 way가 부족해져서 cache miss가 발생한다.
Coherence miss 이건 멀티코어를 많이 사용하게 되면서 생긴 원인인데, 멀티코어는 각 코어마다 캐시가 있다. 그렇다면 이 캐시 간 consistency가 보장되어야하는데, 한 코어에서 cache line을 업데이트하면 다른 코어의 cache는 invalidate상태가 된다. 이 데이터를 재 접근하면 발생한다.

이러한 cache miss들은 여러 방법으로 조치될 수 있다.

cold start miss를 제외하고 가장 쉬운 방법은 capacity 를 늘리는 방법이다.

way 높이기
victim cache를 만들어서 primary cache 아래에 붙인다. primary cache에 miss되더라도 victim cache가 hit이라면 두 line을 swap해서 hit으로 판정하게 한다. 이렇게 되면 부족한 way를 늘려줄 수 있다.
pseudo-associative cache를 사용하면 conflict miss를 줄일 수 있지만 용량 문제가 발생할 수 있다. 하나의 index를 두번 비교해서 hit 된 line을 swap하는 방식이다.

그리고 1, 2, 3 cache miss는 동시에 발생할 수 있기 때문에 주의가 필요하다.

평상시 개발할 땐 하드웨어 단에서 캐시를 관리해주니 어플리케이션단의 캐시만 생각했었는데 오랜만에 컴퓨터구조 공부를 하니 새로웠다.

사실 cold start miss는 어쩔 수 없는데 다른 cache miss들은 해소할 수 있는 방법이 상당히 많아서 여러 가지를 고려해볼 수 있을 것 같다. 2-way associative cache 구조가 제일 괜찮아보이는데 복잡도가 어떨런지 모르겠다.

dev-writeup-2024 / january

[01-10] Cache miss 간단 정리 #49

캐시 메모리의 구조

Cache Hit & Miss