캐시 적중률 (r1)

CPU가 필요한 데이터를 요청할 때, 캐시 메모리에 접근하여 그 데이터를 찾는 과정에서 두 가지 결과가 발생한다. 데이터가 캐시 내에 존재하여 바로 제공될 수 있는 경우를 캐시 적중(cache hit)이라고 한다. 이는 CPU가 매우 빠른 캐시 메모리에서 직접 데이터를 읽어 처리할 수 있음을 의미하며, 시스템의 전반적인 처리 속도를 높이는 핵심 원리이다.

반대로, 요청한 데이터가 캐시 메모리에 존재하지 않아 상대적으로 느린 DRAM이나 메인 메모리에서 데이터를 가져와야 하는 경우를 캐시 부적중(cache miss)이라고 부른다. 캐시 부적중이 발생하면 데이터를 가져오기 위한 추가 시간이 소요되어 처리 지연이 생기며, 이는 시스템 성능에 부정적인 영향을 미친다.

캐시 적중의 빈도를 수치화한 지표가 캐시 적중률(cache hit ratio)이다. 이는 전체 캐시 접근 횟수 중 캐시 적중이 발생한 비율을 백분율로 나타낸다. 반대로, 캐시 부적중이 발생한 비율은 캐시 부적중률(cache miss ratio)이라고 하며, 이 두 지표의 합은 100%가 된다. 성능 분석 시에는 절대적 개선치가 작아 보이는 적중률 상승보다, 상대적으로 큰 폭으로 감소하는 부적중률에 더 주목하는 경우가 많다.

캐시 부적중은 그 발생 원인에 따라 크게 세 가지 종류로 구분된다. 강제 부적중(Compulsory miss)은 특정 데이터를 최초로 접근할 때 불가피하게 발생한다. 충돌 부적중(Conflict miss)은 서로 다른 데이터가 캐시 메모리 내 같은 위치에 배치되어야 할 때 발생하며, 캐시 배치 정책과 깊은 연관이 있다. 마지막으로 용량 부적중(Capacity miss)은 처리해야 할 데이터의 총량이 캐시 메모리의 물리적 저장 공간을 초과할 때 발생한다.

캐시 적중률은 캐시 메모리의 성능을 평가하는 핵심 지표이다. 이는 CPU가 데이터를 요청했을 때, 그 데이터가 캐시 메모리에 존재하여 빠르게 접근할 수 있는 비율을 의미한다. 반대로 요청한 데이터가 캐시에 없어 상대적으로 느린 DRAM(메인 메모리)에서 가져와야 하는 경우를 캐시 부적중이라고 한다.

캐시 적중률은 일반적으로 백분율(%)로 표현되며, 계산식은 다음과 같다. 캐시 적중률은 (캐시 적중 횟수)를 (캐시 적중 횟수 + 캐시 부적중 횟수)로 나눈 값에 100을 곱하여 구한다. 이때 분모인 '캐시 적중 횟수 + 캐시 부적중 횟수'는 CPU가 캐시에 대해 수행한 전체 접근 또는 요청 횟수와 동일하다.

이 계산식에서 파생되는 반대 개념이 캐시 부적중률이다. 캐시 부적중률은 1에서 캐시 적중률을 뺀 값, 즉 (캐시 부적중 횟수 / 전체 접근 횟수)로 계산된다. 성능 분석 시에는 절대적 개선치보다 상대적 개선치가 두드러지기 때문에, 예를 들어 적중률이 95%에서 97%로 향상되면 부적중률은 5%에서 3%로 40%나 감소한 것으로 해석할 수 있어, 종종 부적중률에 더 주목하기도 한다.

이러한 적중률과 부적중률은 캐시 크기, 캐시 배치 정책, 사용된 캐시 교체 알고리즘, 그리고 프로그램이 갖는 지역성 등의 요소에 의해 크게 영향을 받는다.

강제 부적중은 캐시 메모리에 처음 접근하는 데이터를 요청할 때 발생하는 캐시 부적중의 한 종류이다. 해당 메모리 주소의 데이터가 캐시에 한 번도 로드된 적이 없기 때문에 발생하며, 이는 캐시가 '차갑게(cold)' 시작하는 상태에서 필연적으로 일어나는 현상이다. 예를 들어 프로그램을 처음 실행하거나 새로운 데이터 세트를 처리하기 시작할 때 나타난다.

이러한 부적중은 해당 데이터 블록을 주기억장치(DRAM)에서 가져와 캐시에 적재해야만 해결된다. 강제 부적중은 캐시의 동작 원리상 근본적으로 피할 수 없는 부적중으로 간주되며, 프리페칭 등의 기술로 일부 완화할 수 있지만 완전히 제거하는 것은 불가능하다. 그러나 프로그램의 전체 실행 시간에 비해 상대적으로 초기에만 집중적으로 발생하는 경향이 있어, 전체적인 시스템 성능에 미치는 영향은 제한적이다.

강제 부적중은 충돌 부적중 및 용량 부적중과 함께 캐시 부적중을 분석하는 주요 세 가지 범주 중 하나를 이룬다. 캐시의 성능을 평가할 때는 이러한 부적중의 원인을 구분하여 이해하는 것이 중요하며, 강제 부적중의 빈도는 주로 프로그램의 참조 지역성과 초기화 패턴에 의해 결정된다.

충돌 부적중은 캐시 메모리의 캐시 배치 정책에 의해 발생하는 캐시 부적중의 한 종류이다. 이는 캐시 메모리에 여유 공간이 남아 있음에도 불구하고, 서로 다른 두 데이터가 동일한 캐시 메모리 주소에 할당되어야 해서 발생한다. 즉, 데이터를 저장할 물리적 공간은 있지만, 주소 사상 규칙에 따라 그 공간을 사용할 수 없어 생기는 문제이다.

이 현상은 직접 사상 캐시에서 가장 빈번하게 발생한다. 직접 사상 방식은 각 메인 메모리 주소가 캐시 내 오직 하나의 특정 위치에만 대응되도록 설계되어 있어, 서로 다른 메모리 주소의 데이터가 같은 캐시 인덱스를 가질 경우 충돌이 일어난다. 충돌이 발생하면 기존에 저장되어 있던 데이터는 쫓겨나고, 새로운 데이터로 교체된다. 이후 다시 원래의 데이터가 필요해지면 캐시에 없어 부적중이 발생하게 되며, 이는 성능 저하로 이어진다.

충돌 부적중을 완화하기 위한 일반적인 방법은 연관 사상 정도를 높이는 것이다. 집합 연관 캐시나 완전 연관 캐시는 하나의 인덱스에 여러 개의 캐시 라인을 두어, 동일한 인덱스를 가진 여러 데이터를 동시에 저장할 수 있도록 한다. 예를 들어, 4-way 집합 연관 캐시는 하나의 인덱스에 최대 4개의 데이터 블록을 저장할 수 있어, 직접 사상 방식에 비해 충돌 가능성이 현저히 낮아진다. 그러나 연관도를 높이면 캐시 탐색 시간이 증가하고 설계가 복잡해지며 전력 소모가 커지는 트레이드오프가 존재한다.

용량 부적중은 캐시 메모리의 전체 저장 공간이 부족하여 발생하는 캐시 부적중의 한 종류이다. 강제 부적중이나 충돌 부적중과 달리, 이는 캐시 메모리의 물리적 용량 한계로 인해 필요한 모든 데이터를 동시에 보관할 수 없을 때 일어난다. 프로그램이 사용하는 작업 세트가 캐시 메모리의 총 용량을 초과하게 되면, 일부 데이터는 캐시에서 밀려나게 되고, 이후 해당 데이터에 다시 접근할 때 용량 부적중이 발생한다.

이러한 부적중은 캐시의 배치 정책이나 주소 충돌과 관계없이 순수히 공간이 부족해서 생긴다. 따라서 직접 사상 캐시, 완전 연관 사상 캐시, 집합 연관 사상 캐시 등 어떤 캐시 배치 정책을 사용하더라도 발생할 수 있는 근본적인 문제이다. 용량 부적중을 줄이는 가장 직접적인 방법은 캐시 메모리의 크기를 늘리는 것이지만, 이는 비용 증가와 접근 속도 저하라는 트레이드오프를 동반한다.

용량 부적중은 프로그램의 지역성 특성과도 깊은 연관이 있다. 시간 지역성과 공간 지역성이 높은 프로그램은 상대적으로 적은 캐시 공간으로도 높은 캐시 적중률을 유지할 수 있어 용량 부적중이 덜 발생한다. 반면, 매우 큰 데이터 세트를 불규칙하게 접근하는 프로그램은 용량 부적중이 빈번하게 나타나 성능 저하의 주요 원인이 될 수 있다.

캐시 크기는 캐시 메모리가 한 번에 저장할 수 있는 데이터의 총량을 의미한다. 일반적으로 캐시 크기가 클수록 더 많은 데이터를 보관할 수 있어 캐시 적중률을 높이는 데 유리하다. 이는 용량 부적중의 발생 빈도를 줄이는 직접적인 방법이기 때문이다. 특히 데이터 접근 패턴이 복잡하거나 처리해야 하는 워크로드의 양이 많은 애플리케이션에서는 큰 캐시 크기의 이점이 두드러진다.

그러나 캐시 크기를 무작정 키우는 것에는 한계와 단점이 존재한다. 캐시 메모리는 일반적으로 SRAM으로 구성되며, 이는 DRAM이나 SSD보다 훨씬 빠르지만 제조 단가가 높고 물리적 공간을 많이 차지한다. 또한 캐시 크기가 증가하면 탐색해야 하는 주소 공간이 넓어져 접근 레이턴시가 증가할 수 있으며, 소비 전력도 함께 늘어나는 문제가 발생한다. 따라서 CPU 설계에서는 제한된 실리콘 다이 면적 내에서 캐시 크기와 속도, 전력 효율 사이의 최적 균형점을 찾는 것이 중요하다.

실제 마이크로프로세서에서는 L1 캐시, L2 캐시, L3 캐시와 같이 여러 계층의 캐시를 두어 크기와 속도의 절충안을 구현한다. 작고 빠른 L1 캐시는 가장 빈번히 사용되는 데이터를, 크고 상대적으로 느린 L3 캐시는 더 많은 데이터를 백업 저장하는 역할을 한다. 이러한 계층적 설계는 전체적인 캐시 적중률을 유지하면서 시스템 성능을 최적화하는 핵심 기법이다.

캐시 배치 정책은 메인 메모리의 특정 주소 데이터를 캐시 메모리의 어느 위치에 저장할지 결정하는 규칙이다. 이 정책은 캐시 적중률에 직접적인 영향을 미치며, 특히 충돌 부적중의 발생 빈도를 결정하는 핵심 요소이다. 주요 배치 정책으로는 직접 사상 캐시, 완전 연관 사상 캐시, 그리고 집합 연관 사상 캐시가 있다.

직접 사상 캐시는 메인 메모리의 각 블록이 캐시 내 오직 한 곳에만 매핑되는 방식이다. 구조가 단순하고 탐색 속도가 빠르다는 장점이 있지만, 서로 다른 메모리 블록이 같은 캐시 위치를 사용하려 할 때 발생하는 충돌 부적중이 잦아 성능 저하의 주요 원인이 될 수 있다. 이에 비해 완전 연관 사상 캐시는 메모리 블록이 캐시 내 빈 공간 어디에나 자유롭게 위치할 수 있다. 이 방식은 공간 활용도가 높고 충돌 부적중이 거의 발생하지 않지만, 데이터를 찾기 위해 모든 캐시 엔트리를 동시에 검색해야 하므로 하드웨어 복잡도와 비용이 크게 증가한다는 단점이 있다.

현대 CPU의 캐시 계층에서 가장 널리 채택되는 방식은 집합 연관 사상 캐시이다. 이는 앞서 언급한 두 방식의 절충안으로, 캐시를 여러 개의 세트로 나누고, 각 세트 내에는 여러 개의 캐시 라인을 두는 구조이다. 메모리 블록은 특정 세트로만 매핑되지만, 그 세트 내에서는 어떤 라인에든 저장될 수 있다. 이는 직접 사상 방식에 비해 충돌 부적중을 현저히 줄이면서도, 완전 연관 방식보다 하드웨어 구현이 간단하고 탐색 속도가 빠르다는 장점을 제공한다. 일반적으로 "n-way 세트 연관"이라고 표현하며, 여기서 n은 한 세트 내에 포함된 캐시 라인의 개수를 의미한다.

캐시 교체 알고리즘은 캐시 메모리가 가득 찼을 때, 어떤 기존 데이터를 내보내고 새로운 데이터를 저장할지 결정하는 규칙이다. 이 알고리즘의 선택은 캐시 적중률에 직접적인 영향을 미치며, 캐시 부적중 중 용량 부적중을 최소화하는 데 핵심적인 역할을 한다. 효율적인 교체 알고리즘은 향후 사용될 가능성이 가장 낮은 데이터를 선별해 제거함으로써 제한된 캐시 공간을 최적으로 활용하게 한다.

주요 교체 알고리즘으로는 무작위 교체, FIFO, LRU, LFU 등이 있다. 무작위 교체 알고리즘은 구현이 단순하고 빠르지만 성능 예측이 어렵다. FIFO 알고리즘은 가장 오래된 데이터를 제거하지만, 자주 사용되는 데이터라도 오래되었다는 이유만으로 제거될 수 있다는 단점이 있다. 이에 비해 LRU 알고리즘은 가장 최근에 사용된 시점을 기준으로, 가장 오랫동안 사용되지 않은 데이터를 제거한다. 이는 지역성 원리를 잘 반영하여 일반적으로 높은 적중률을 보여주지만, 사용 이력을 추적하는 오버헤드가 발생한다. LFU 알고리즘은 사용 빈도가 가장 낮은 데이터를 제거하는 방식으로, 장기적인 접근 패턴에 효과적일 수 있으나, 갑자기 많이 사용되기 시작한 새로운 데이터가 쉽게 제거될 수 있다.

현대 CPU의 캐시 메모리는 대부분 집합 연관 사상 방식을 사용하며, 이 경우 각 캐시 세트 내에서만 교체 알고리즘이 동작한다. 알고리즘의 선택은 하드웨어 복잡도, 성능 목표, 워크로드의 특성에 따라 이루어진다. LRU에 근사한 알고리즘이나 이들의 변형이 성능과 구현 비용의 균형을 고려해 널리 채택되는 편이다.

프로그램의 지역성은 캐시 메모리의 성능, 특히 캐시 적중률에 직접적인 영향을 미치는 핵심적인 프로그램 특성이다. 지역성은 프로그램이 짧은 시간 동안 특정 범위의 메모리 주소를 집중적으로 참조하는 경향을 의미하며, 이는 CPU의 메모리 접근 패턴이 무작위적이지 않고 일정한 규칙을 가짐을 나타낸다. 높은 지역성을 가진 프로그램은 캐시에 저장된 데이터를 재사용할 가능성이 높아져 캐시 적중 횟수를 증가시키고, 결과적으로 캐시 부적중으로 인한 메인 메모리 접근을 줄여 전체 시스템 성능을 향상시킨다.

지역성은 주로 시간적 지역성과 공간적 지역성으로 구분된다. 시간적 지역성은 최근에 접근한 메모리 위치가 가까운 미래에 다시 접근될 가능성이 높은 특성이다. 예를 들어, 루프 내에서 사용되는 변수나 함수 호출이 반복되는 경우가 이에 해당한다. 공간적 지역성은 특정 메모리 주소에 접근할 때 그 주변의 메모리 주소들도 곧 접근될 가능성이 높은 특성을 말한다. 이는 배열이나 연속된 데이터 구조를 순차적으로 처리할 때 두드러지게 나타난다.

프로그램의 지역성은 캐시 크기, 캐시 배치 정책, 캐시 교체 알고리즘과 함께 캐시 적중률을 결정하는 주요 요소이다. 지역성이 뛰어난 프로그램은 상대적으로 작은 캐시로도 높은 적중률을 달성할 수 있는 반면, 지역성이 낮은 프로그램은 데이터 접근이 예측하기 어렵고 분산되어 있어 캐시 부적중이 빈번하게 발생한다. 특히 강제 부적중 이후에도 동일 데이터를 재사용하지 않거나, 메모리를 넓은 범위에 걸쳐 불규칙하게 접근하는 알고리즘은 캐시의 효율을 크게 떨어뜨린다.

따라서 소프트웨어를 설계하고 알고리즘을 최적화할 때 지역성을 고려하는 것은 매우 중요하다. 데이터를 연속적으로 배치하거나, 필요한 데이터를 미리 프리페칭하며, 루프를 재구성하여 캐시 친화적인 접근 패턴을 만드는 기법들은 모두 프로그램의 지역성을 높여 캐시 적중률을 개선하고, 궁극적으로 응용 프로그램의 실행 속도를 가속화하는 데 기여한다.

프리페칭은 캐시 적중률을 높이기 위해 사용되는 예측 기반의 성능 향상 기법이다. 이 기법은 CPU가 명시적으로 요청하기 전에, 향후 필요할 것으로 예상되는 데이터나 명령어를 미리 캐시 메모리로 가져오는(prefetch) 동작을 수행한다. 이를 통해 프로그램 실행 중 발생하는 캐시 부적중의 일부, 특히 강제 부적중을 사전에 줄여 전체적인 메모리 접근 지연 시간을 단축시킨다.

프리페칭의 효과는 프로그램이 보이는 지역성에 크게 의존한다. 순차적 지역성이 높은 프로그램, 예를 들어 배열을 순차적으로 탐색하는 코드의 경우, 다음에 접근할 주소를 비교적 쉽게 예측할 수 있어 프리페칭의 성공률이 높다. 반면, 접근 패턴이 불규칙하거나 분기 예측이 어려운 코드에서는 필요하지 않은 데이터를 캐시로 불러와 오히려 유용한 데이터를 밀어내는 부작용을 초래할 수도 있다.

이 기법은 주로 하드웨어와 소프트웨어 두 수준에서 구현된다. 하드웨어 프리페칭은 CPU 내부의 전용 프리페처가 실행 패턴을 분석하여 자동으로 데이터를 미리 가져오는 방식이다. 소프트웨어 프리페칭은 프로그래머나 컴파일러가 프로그램 코드에 특수 명령어를 삽입하여 명시적으로 프리페칭을 요청하는 방식으로, 더 정교한 제어가 가능하지만 구현 복잡도가 증가한다는 단점이 있다.

캐시 일관성은 멀티코어 프로세서나 멀티프로세서 시스템에서 발생하는 중요한 문제이다. 각 CPU 코어는 자신만의 로컬 캐시를 가지고 있어 성능을 향상시키지만, 여러 코어가 동일한 메인 메모리 주소의 데이터를 캐싱할 경우 데이터의 불일치가 발생할 수 있다. 예를 들어, 한 코어가 캐시에 저장된 데이터를 갱신했지만, 다른 코어의 캐시에는 이전 데이터가 남아 있는 경우가 있다. 이러한 캐시 간의 데이터 불일치 문제를 해결하고 일관된 상태를 유지하는 것이 캐시 일관성의 핵심 목표이다.

캐시 일관성을 유지하기 위한 주요 방법으로는 스누핑 프로토콜과 디렉터리 기반 프로토콜이 있다. 스누핑 방식에서는 모든 코어의 캐시가 공유 버스에 연결되어 있으며, 한 캐시에서 쓰기 작업이 발생하면 이 사실을 버스를 통해 모든 다른 캐시에 알린다(브로드캐스트). 다른 캐시들은 자신이 가진 해당 데이터의 복사본을 무효화하거나 갱신하는 방식으로 대응한다. 이 방식은 비교적 간단하지만, 버스 트래픽이 증가할 수 있다는 단점이 있다. 반면, 디렉터리 기반 방식은 중앙 디렉터리에 어떤 코어가 어떤 데이터 블록의 복사본을 가지고 있는지 정보를 저장하여, 필요할 때만 해당 코어들에게 통지하는 방식으로 동작한다.

캐시 일관성이 제대로 유지되지 않으면 프로그램 실행에 치명적인 오류를 초래할 수 있다. 따라서 현대 CPU는 MESI 프로토콜이나 그 변형과 같은 하드웨어 기반의 캐시 일관성 프로토콜을 내장하고 있다. 이 프로토콜들은 캐시 라인의 상태(Modified, Exclusive, Shared, Invalid)를 추적하고 관리함으로써, 소프트웨어의 추가 개입 없이도 데이터 일관성을 투명하게 보장한다. 이러한 일관성 유지 메커니즘은 병렬 처리의 정확성과 시스템 성능을 좌우하는 핵심 요소로 작동한다.

캐시 레이턴시는 프로세서가 데이터를 요청한 시점부터 해당 데이터를 실제로 사용할 수 있을 때까지 걸리는 시간을 의미한다. 이는 캐시 메모리의 성능을 평가하는 핵심 지표 중 하나로, 캐시 적중률과 함께 시스템의 전반적인 속도에 큰 영향을 미친다. 캐시 적중 시의 레이턴시는 매우 짧지만, 캐시 부적중이 발생하여 주기억장치나 더 낮은 계층의 캐시에서 데이터를 가져와야 할 경우 레이턴시는 급격히 증가한다.

현대 CPU는 일반적으로 멀티 레벨 캐시 구조를 채택하고 있으며, 각 레벨별 레이턴시가 크게 다르다. L1 캐시는 가장 빠르고 레이턴시가 가장 짧으며, L2 캐시와 L3 캐시로 갈수록 용량은 커지지만 접근 속도는 느려져 레이턴시가 길어진다. 이는 캐시 메모리의 물리적 크기가 커질수록 데이터를 찾고 검증하는 데 더 많은 시간이 소요되기 때문이다. 따라서 캐시 설계는 높은 적중률과 낮은 레이턴시 사이의 균형을 찾는 과정이다.

실제 시스템에서 관측되는 유효 레이턴시는 캐시 적중률, 프리페칭 효율, 메모리 수준 병렬 처리 능력 등 여러 요소에 의해 결정된다. 예를 들어, 분기 예측기와 프리페칭 기술이 효과적으로 작동하면 필요한 데이터를 미리 캐시에 로드하여 캐시 부적중 횟수를 줄이고, 결과적으로 평균 레이턴시를 낮출 수 있다. 반면, 랜덤 액세스 패턴이 많은 작업은 지역성이 낮아 캐시 적중률이 떨어지고, 이로 인해 유효 레이턴시가 증가하게 된다.

캐시 대역폭은 캐시 메모리가 단위 시간당 처리할 수 있는 데이터 전송량을 의미한다. 이는 메인 메모리의 대역폭과 개념적으로 유사하지만, CPU에 더 가까운 고속 메모리 계층에서의 데이터 처리 능력을 나타낸다. 높은 캐시 대역폭은 프로세서가 필요한 데이터를 빠르게 공급받을 수 있게 하여 전체 시스템 성능 향상에 기여한다.

캐시 대역폭의 실제 효용은 캐시 적중률에 크게 의존한다. 캐시 적중률이 낮아 캐시 부적중이 빈번하게 발생하면, 데이터를 느린 메인 메모리에서 가져와야 하므로 유효 대역폭이 크게 저하된다. 따라서 캐시의 이론적 최대 대역폭보다는 캐시 적중률을 고려한 '유효 대역폭'이 실질적인 성능 지표로 중요하게 여겨진다.

캐시 대역폭은 캐시 메모리의 물리적 설계, 예를 들어 데이터 버스의 폭과 클럭 속도에 의해 결정된다. 또한 현대 멀티코어 프로세서에서는 여러 코어와 스레드가 캐시에 동시에 접근하는 병렬 처리 환경에서의 대역폭 관리도 성능에 중요한 영향을 미친다.