Cache Hit, Cache Miss 개념, Cache Miss의 종류

Cache Hit

어떤 프로그램이 레벨 k + 1로부터 특정 데이터 객체 d를 필요로 할 때, 먼저 현재 레벨 k에 저장된 블록들 중 하나에서 d를 찾는다. 만일 d가 레벨 k에서 우연히 캐시되어 있다면, 이 경우를 캐시 적중이라고 부른다. 프로그램은 d를 레벨 k에서 직접 읽으며 이는 k + 1에서 데이터를 읽는 것보다 빠르게 된다. (실제 캐시 적중이 되는 과정는 다음 글에서 자세히 다룬다. https://mydailylogs.tistory.com/31)

Cache Miss

반면, 만일 데이터 객체 d가 레벨 k에서 캐시되지 않았다면 캐시 미스가 발생한 것이다. 미스가 존재할 때, 레벨 k에서의 캐시는 레벨 k + 1에 있는 캐시로부터 d를 포함하는 블록을 가져오며, 만일 레벨 k 캐시가 이미 꽉 찬 상태라면 기존 블록에 덮어 쓰기도 한다.

이와 같이 기존 블록을 덮어 쓰는 과정은 블록을 교체하거나 축출하는 것으로 알려져 있느며 이때 축출되는 블록은 희생 블록(Victim Block)이라고 부른다. 어떤 블록을 교체할 지에 대한 결정은 캐시의 교환 정책에 의해 정해진다. 예를 들어, 랜덤 교체 정책을 사용하는 캐시는 랜덤으로 희생 블록을 선택한다. 최근에 가장 덜 사용한 (LRU) 교체 정책을 갖는 캐시는 가장 과거에 접근한 블록을 선택할 것이다.

Cache Miss의 종류

때때로 여러 종류의 캐시 미스들을 구별하는 것이 유용한 경우가 있다. 만일 레벨 k에서 캐시가 비어있다면 모든 데이터 객체를 접근하려는 시도는 미스를 유발하게 된다. 비어 있는 캐시는 종종 cold cache라고 불리우며, 이런 종류의 미스들은 강제적인 미스 또는 콜드 미스(cold miss)라고 부른다. 캐시가 반복된 메모리 접근으로 준비가 된 이후의 콜드미스는 종종 안정화 상태에서는 발생하지 않는 유동적인 이벤트이기 때문에 중요하다.

미스가 있을 때마다 레벨 k에서의 캐시는 레벨 k + 1로부터 가져온 블록을 어디에 저장할지를 결정하는 배치 정책을 구현해야만 한다. 가장 유연한 배치 정책은 레벨 k + 1로부터 가져온 모든 블록을 레벨 k의 어떤 블록에도 저장될 수 있도록 하는 것이다. 하드웨어로 구현되었고 속도가 가장 중요한 메모리 계층 구조의 높은 곳에 위치한 캐시에 대해서 이러한 정책은 대개 구현하는데 비용이 너무 많이 드는데, 이는 랜덤으로 배치한 블록들의 위치를 찾는 것이 상당한 연산을 수행하기 때문이다.

그래서 하드웨어 캐시는 일반적으로 레벨 k + 1에서 특정 블록을 레벨 k에 있는 블록의 작은 부분 집합으로 제한하는 보다 제한적인 배치 정책을 구현한다. 예를 들어, 레벨 k + 1의 블록 i가 레벨 k에 있는 블록을 (i mod 4)로 배치할지 여부를 결정해야 할 수도 있다. 우리 그림에서 볼 경우, 레벨 k + 1의 블록 0, 4, 8, 12는 블록 0에 매핑되게 될 것이고, 블록 1, 5, 9, 13은 블록 1로 매핑될 것이다.

이러한 종류의 제한적인 배치 전략은 충돌 미스(conflict miss)라고 알려진 유형으로 유도된다. 이는 계속해서 동일한 캐시 블록으로 하위 레벨의 블록들이 매핑되게 하면서, 캐시가 미스되기 때문이다. 예를 들어 만일 프로그램이 0을 요청하고 다음엔 블록 8, 다음에 또 0 그리고 다시 12를 요청한다면 이 두 개의 블록에 대한 참조는 k에 있는 캐시에서 미스하게 되고, 비록 이 캐시가 전체 네 개의 블록을 저장할 수 있다고 하더라도 계속해서 미스가 발생하게 된다.

프로그램들은 종종 일련의 단계로 실행되며 각 단계는 캐시 블록의 합리적인 상수 집합을 접근한다. 예를 들어 연속된 루프는 동일한 배열의 원소들을 반복적으로 접근할 수 있다. 이러한 블록들의 집합은 이 단계의 동작집합이라고 부른다. 동작 집합의 크기가 캐시 크기보다 더 클 때, 캐시는 용량 미스(capacity miss)라고 알려진 미스를 경험하게 된다. 다른 말로 캐시가 너무 작아서 이러한 동작 집합을 처리할 수 없는 경우이다. 캐시의 용량이 부족하여 발생하는 미스이다. 즉, 프로그램 수행 시 접근하는 데이터의 양이 캐시의 사이즈를 넘어갈 경우 발생한다. 예를들어 32k direct mapped cache를 달고 있는 컴퓨터에서 128k array data를 접근하는 경우 캐시는 array data를 모두 저장할 수 없으므로 용량 부족에 의한 캐시 미스가 발생한다.