프로세서 기술의 발전으로 지난 수십 년 동안 CPU 성능은 크게 향상되었지만 메모리 기술은 같은 속도로 향상되지 않았다. 따라서 메모리로부터의 로드 요청을 수행할 때마다 상당한 오버헤드가 발생한다. 이런 메모리 액세스에 의한 성능 저하를 줄이기 위해 캐시 구조의 혁신과 개선을 가져왔으며 효율적인 LLC(Last Level Cache) 교체 정책은 프로세서 성능에 중요하기 때문에 지속적인 연구의 중심에 있다.

일반적으로 캐시 용량은 응용 프로그램의 작업셋(working set)보다 훨씬 작으므로 캐시 블록 교체를 피할 수 없다. 가장 효율적인 교체 정책은 장래에 가장 오랫동안 필요하지 않은 데이터 블록을 캐시로부터 퇴출하고 가까운 장래에 사용될 블록들로 캐시를 유지하는 것이다.

기존 프로세서들은 LRU(Least Recently Used) 교체 정책의 변형을 사용하여 희생자를 결정하였다[1-10]. LRU 교체 정책은 메모리 집중적이지 않은 응용 프로그램에서는 잘 수행되지만 작업 셋이 캐시 용량보다 큰 메모리 집중적인 응용 프로그램에서는 빈약하게 수행된다. 또한 상위 레벨 캐시(L1, L2)가 대부분의 지역성을 걸러 내기 때문에 상위레벨 캐시에 사용하는 전통적인 교체 정책들은 LLC에서 빈약하게 수행된다[5-8]. 예를 들어, 응용 프로그램의 작업 셋이 캐시 용량보다 크다면 LRU정책은 재사용되지 않는 블록들이 캐시에 삽입되고 유용한 캐시 블록들을 퇴출시킨다면 불필요한 블록들로 캐시 공간을 차지하기 때문에 스래싱(thrashing) 및 성능 절벽을 유발한다.

이전 연구들은 LRU를 개선하거나 최적의 교체를 시도하는 여러 방법들을 제안했다. 이들 방법은 크게 세 가지 광범위한 기술을 사용한다는 것을 관찰했다. 첫째, 최근성(recency)은 오래 전에 사용된 라인보다 최근에 사용된 라인을 우선한다. LRU정책에서 최근성만의 사용은 스래싱을 유발한다. 따라서 대부분의 고성능 정책은 최근성을 다른 기술과 결합한다[1-6]. 둘째, 보호(protection)는 작업셋의 일부를 퇴출로부터 보호한다. 작업 셋의 크기가 캐시 용량을 초과하면 스래싱이 발생할 수 있다. 작업 셋의 일부를 퇴출로부터 보호하여 스래싱을 방지한다[7,8]. 셋째, 분류(classification)는 액세스들을 여러 부류로 나누고, 각 부류의 블록을 다르게 처리한다. 즉, 블록들을 재사용 또는 바이패싱으로 분류한다. 재사용되는 블록만 캐시에 저장하고 바이패싱 블록은 캐시에 있는 동안 재사용되지 않으므로 캐시를 바이패스 시킨다. 분류는 블록이 현저하게 다른 액세스 패턴을 가질 때 잘 작동한다[9,10].

Belady’s MIN[11]은 미래에 대한 지식을 가지고 최적의 교체를 제공한다. 그러나 미래 참조에 대한 지식을 필요로 하기 때문에 실제 구현하는 것은 현실적이지 않다.

Hawkeye[12]는 과거 액세스에 대해 Belady’ MIN을 재구성하고 향후 액세스의 캐싱 동작을 예측하기 위해 최적 솔루션을 학습한다. 과거 액세스에 대한 최적의 솔루션을 계산하기 위해 메모리 액세스 명령이 캐시 친화적 블록을 액세스하는지 혹은 캐시 반-친화적 블록을 액세스하는 경향이 있는지를 학습하는 프로그램카운터 기반 예측기를 사용한다. 캐시 친화적인 것으로 예상된 블록은 캐시에 높은 우선순위로 삽입시키고, 캐시 반-친화적으로 예상되는 블록은 낮은 우선순위로 삽입시킨다.

SHiP(Signature-based Hit-Predictor)[4]는 블록의 시그네처(미스의 원인인 프로그램 카운터)를 기반으로 블록의 재사용 패턴을 학습하여 재사용의 가능성을 예측한다. SHiP++[5]는 SHiP를 다음과 같이 몇 가지 개선시켰다. 캐시 삽입 및 캐시 적중 시에 재사용 예측을 개선시키고, 캐시 적중 시 SHCT(Signature History Counter Table)에 대한 학습을 개선시키고, 마지막으로 모든 캐시 액세스 유형에 대해 단일 재사용 예측을 사용하는 대신 캐시 액세스 유형을 분석하여 재사용 예측을 수행하도록 개선시켰다.

본 논문에서는 캐시 블록의 적중 수는 이전에 캐시에 거주했을 때의 평균 적중 수와 비슷하다는 관찰을 이용하여 캐시 블록의 적중 수를 예측하고이를 실제 수행되는 동안 적중 수와 비교하여 그 차이가 가장 적은 블록을 교체 대상으로 선택한다. 즉 제안한 교체 정책은 예상 적중 수를 블록과 연관시키고 남은 적중 수가 더 적은 블록을 퇴출시키는 효율적인 교체 정책이다. 또한 재사용되지 않는 것으로 예측되는 블록은 바이패스 시켜 캐시 효율성을 향상시킨다. 제안 방법은 베이스라인 LRU 교체 정책에 비해 5.8%의 미스 감소와 4.8%의 성능 향상을 제공한다.

본 논문의 구성은 다음과 같다. 2장에서는 연구동기, 3장에서는 제안방법, 4장에서는 실험환경, 5장에서는 성능평가, 6장에서는 결론을 맺는다.

데드 블록 예측기(Dead Block Predictor)는 시기 적절하고 정확한 방식으로 데드 블록을 식별하고 퇴출함으로써 유효 수명이 끝나지 않은 블록들을 캐시에 유지하여 더 많은 적중을 유도한다[13-18]. 응용 프로그램들에서 캐시 블록들은 재사용 패턴의 다양성을 보임에 따라 데드 블록 예측기의 임무는 복잡해졌다. 다양성의 원인은 모험적 수행(speculation)과 같은 마이크로 아키텍처 노이즈, 제어 흐름 다양성, 다른 스레드들의 캐시 압력 등 수없이 많다. 다양성은 한 캐시 수명에서 다음 캐시 수명까지 개별 캐시 블록들의 일관성 없는 동작으로 나타난다. 이러한 비일관성은 데드 블록 예측기가 블록의 유효 수명의 끝을 안정적으로 식별하는데 있어서 문제가 되고, 결과로 예측 정확도나 커버리지 또는 둘 모두를 낮추게 한다. 교체 결정을 내리기 위해 데드 블록 예측기를 사용하는 이전 방법들은 기본적으로 라이브 블록을 실수로 데드로 식별하면 캐시 미스가 불가피하다는 문제점과셋(set)의 모든 블록이 라이브 블록으로 예상될 때마다 교체 정책은 가장 적합한 희생자를 효과적으로 선택할 수 없다는 문제점을 갖는다.

본 제안은 남은 적중 수가 0인 데드 블록에 의존하는 대신, 이전에 캐시에 거주했을 때 적중 수에 대한 정보를 활용하여 캐시 블록의 예상 적중 수를 추정하고 희생자 결정 과정에서 그 정보를 이용한다. 즉, 일반적으로 캐시 블록의 적중 수는 그 블록이 이전에 캐시에 거주했을 때 평균 적중수와 유사한 경향을 가지므로 현 거주에서 남은 적중 수가 가장 적은 블록을 희생자로 선택한다.

<그림 1>은 LLC에 Belady’s MIN의 교체 알고리즘을 적용했을 때 실제 적중 수와 이전 캐시 거주할 때 평균 적중 수의 차가 1이하인 것이 평균85%임을 보여준다. 차이가 0인 것이 약 68%이고 차가 1인 것이 약 17%이다. 이는 블록의 실제 적중 수는 이전에 캐시에 거주했을 때 평균 적중 수와 비슷하다는 것을 의미한다. 이와 같은 분석을 이용하여 본 논문에서는 캐시 블록의 적중 수를 예측하고 이를 실제 수행되는 동안의 적중 수와 비교하여 그 차이가 가장 적은 블록을 교체 대상으로 선택하고, 또한 예상 적중 수가 0인 블록은 캐시를 바이패스 시키는 LLC를 위한 효율적인 교체 및 바이패스 정책을 제안한다.

본 논문에서는 캐시에 이전 거주할 때 블록의 평균 적중 수를 예측하기 위해 적중 카운트 예측기(Hit Count Predictor, HCP)를 제안한다. 제안 방법의 구조는 <그림 2>와 같다.

메모리 요청을 서비스하기 위해 LLC와 적중 카운트 예측기를 동시에 탐색한다. LLC에서 미스이면 요청은 메모리 제어기로 보내진다. 메모리로부터 미스 블록을 반입하는 동안 적중 카운트 예측기는 미스 블록에 대한 평균 적중 수를 예측하여 LLC로 보낸다. 예상 적중 수는 이전 LLC에 거주하는 동안 평균 적중 수를 나타내며 캐시 미스가 발생할 때 희생자를 선택할 때와 캐시에 있는 동안 재사용되지 않는 블록을 바이패스하는데 이용한다.

제안한 방법의 성능을 평가하기 위해 SimFlex[18]를 사용하였다. 제안 방법은 128-엔트리 ROB와 8-스태이지를 갖는 4-way 비순차적 슈퍼스칼라 프로세서를 모델링하였다.

<표 1>은 캐시 구성을 보여준다. L1 명령어 캐시는 32KB 4-way 셋 연관(set associative)이고, 데이터 캐시는 8-way 셋 연관이다. L2 캐시는 256KB 8-way 셋 연관이다. L3(LLC) 캐시는 2MB 16-way 셋 연관이고, 모든 레벨의 캐시는 64B 블록 크기를 사용한다. 표에서 LRU는 기존의 LRU 교체 정책을 의미한다. 캐시에 이전 거주할 때 블록의 평균 적중 수를 예측하기 위한 적중 카운트 예측기(HCP)는 128 엔트리 16-way 셋 연관이다.

제안한 방법을 평가하기 위해 SPEC CPU2006 벤치마크를 사용한다. 제안 방법은 효율성과 성능을 개선시키는 구조이기 때문에 LLC의 성능이 실행시간에 크게 영향을 주는 벤치마크에서 영향이 뚜렷하게 나타난다. 따라서 23개 SPEC CPU2006 벤치마크 중에서 LLC 크기를 1MB에서 4MB로 증가할 때 최소 10% 이상의 성능이 개선되는 LLC 성능에 종속적인 7개 벤치마크에 대해 평가한다. 이들 벤치마크는 콜드 스타트(cold start) 미스의 영향을 제거하기 위해 준비시간(warm-up)을 갖고 reference 입력을 사용하여 SimPoint[19]로 부터 각 벤치마크에 대해 250M명령어 트레이스를 얻었다.

본 연구에서는 제안한 교체 정책의 효율성을 측정하기 위해 최신의 교체 정책인 SHiP++, Hawkeye와 제안 방법이 베이스라인 LRU 교체 정책에 비해 미스 감소율과 성능 향상율을 비교한다.

<그림 4>는 베이스라인 LRU 교체 정책에 비해 평가된 정책들의 MPKI(Miss Per Kilo Instructions) 감소율을 보여준다. 그림에서 보듯이 제안 방법은 다른 정책보다 우수한 것으로 나타났다. 제안 방법은 LRU에 비해 MPKI를 평균 5.8% 감소시켰다. 이에 비해 최신의 교체 정책인 Hawkeye는 LRU에 비해 MPKI를 평균 1.5%를 감소시켰고, SHiP++는 평균 2.1% 감소시켰다.

<그림 5>는 베이스라인 LRU에 비해 평가된 정책들의 성능 향상을 비교하였다. 성능 측정 기준으로 IPC(Instruction Per Clock)를 사용한다. 본 제안의 성능은 mcf에서 IPC를 최대 10.5% 향상시켰고, 평균 4.8% 향상시켰다. 최신의 교체 정책인 Hawkeye, SHiP++는 IPC를 각각 평균 1%, 1.7% 향상시켰다.

LRU 교체 정책은 메모리 비집중적인 워크로드에서는 잘 수행되지만 워킹 셋이 캐시 용량보다 큰 메모리 집중적인 워크로드에서는 빈약하게 수행한다.

본 논문에서는 캐시 블록의 적중 수는 그 블록이 이전에 캐시에 거주했을 때 평균 적중 수와 비슷하다는 관찰을 이용하여 현 거주에서 남은 적중 수가 가장 적은 블록을 희생자로 선택하고, 재사용되지 않는 것으로 예상되는 블록은 바이패스 시켜 LLC의 효율성을 향상시키는 방법을 제안하였다. 제안 방법은 블록의 이전 거주 동안의 평균 적중 수를 저장하기 위해 16-way 연관 구조를 갖는 128셋의 적중 카운트 예측기를 사용하고, 블록이 LLC에 거주하는 동안 적중 수를 저장하기 위해 LLC의 각 블록에 3비트 CHC를 추가하였다.

실행 구동 시뮬레이션에 기초한 실험 결과, 제안한 교체 정책은 LRU 교체 정책에 비해 MPKI를 평균 5.8% 감소시켰고, 성능은 IPC를 평균 4.8% 향상시켰다.