캐쉬(cache)와 캐쉬 알고리즘

컴퓨터 프로그램의 일반적인 특성

컴퓨터 프로그램을 유심히 관찰해 보면, 공통적으로 지니는 일반적인 특성이 하나 존재한다.

 

대부분의 함수가 특정 연산을 하기위해 지역변수를 선언한다. 이러한 지역변수의 특성은 선언 및 초기화 이후 다양한 값으로 변경도 되고, 값을 얻기 위한 참조도 빈번하게 일어난다는 것이다. 이러한 특성을 템퍼럴 로컬리티(Temporal Locality)라 한다.

 

템퍼럴 로컬리티(Temporal Locality)란, 프로그램 실행시 한번 접근이 이뤄진 주소의 메모리 영역은 자주 접근하게 된다는 프로그램 특성을 표현할 때 사용하는 말이다.

 

스페이셜 로컬리티(Spatial Locality)란, 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영여그이 근처일 확률이 높다는 프로그램 성격을 표현할 때 사용하는 말이다.

즉 0x12번지 메모리에 접근 했다면, 다음번 메모리 접근은 그 주소(0x12 번지)에서 멀리 떨어지지 않은 곳일 확률이 높다는 프로그램의 성격을 표현한다.

 

위와같은 특성들을 고려하여 구현된 코드를 캐쉬 프렌드리 코드(Cache Friendly Code)라 한다.

 

캐쉬 알고리즘

 ALU연산 과정중 필요한 데이터가 있다면 이를 레지스터로 이동시켜야 한다. 필요한 데이터가 0x1000번지에 존재하는 데이터라면 이 주소에 해당하는 데이터를 레지스터로 가져오기 위해서 데이터가 존재하는 곳을 찾아봐야 한다. L1캐쉬에 해당 데이터가 존재하는 곳을 찾아봐야한다.

 

 L1캐쉬에 찾는 데이터가 존재할 경우 캐쉬 힛(Cache Hit)이 발생했다고 하며, 이 데이터를 레지스터로 이동시킨다.

L1캐쉬에 데이터가 존재하지 않을 경우 이를 가리켜 캐쉬 미스(Cache Miss)가 발생했다 하고, 캐쉬 미스가 발생하면 L2캐쉬에서 해당 데이터를 가져오게 된다.

(L2캐쉬에 존재하지 않으면 메인메모리에서, ->하드디스크까지 단계별로 탐색한다.)

 

 캐쉬와 메인메모리, 하드디스크 간에 데이터의 이동은 블록단위로 진행이 된다.

블록단위로 전송을 함으로써 스페이셜 로컬리티(Spatial Locality)의 특성을 성능 향상에 십분 활용하게 된다.

->블록 단위란 필요한 주소의 데이터만을 가져오는 것이 아니라 근처의 주소들을 포함하여 하나의 '블록'의 단위로 데이터를 전송하는 것이다.

 

위의 캐쉬 알고리즘 그림을 보면 메모리의 피라미드 구조상 아래로 내려갈수록 블록 크기는 커지게 된다. 이를 통해 아래에 존재하는 메모리 일수록 접근횟수를 줄이는 효과가 있다. 아래에 존재하는 메모리 일수록 속도가 느리기 때문에 접근 횟수를 줄이는 것이 성능향상에 많은 도움이 된다.

 

캐쉬미스가 발생할때 L1캐쉬에서  L2캐쉬로 부터 데이터 블록을 읽어 들일 때 저장할 공간이 없는 경우가 있다.

꽉차 있는 L1캐쉬에 데이터를 저장하려면 당연히 기존에 저장한 데이터를 밀어내야 하는데 이때 블록 교체 알고리즘에 의해서 데이터를 밀어내게 된다.

블록교체 알고리즘은 캐쉬 교체 정책(Cache's Replacement Policy)에 따라서 달라질 수 있다.

가장 보편적인 블록교체 알고리즘은 LRU(Least-Recently Used)알고리즘 이다. 이 알고리즘은 가장 오래전에 참조된 블록을 밀어내는 알고리즘이다.

 

캐쉬 프렌드리 코드(Cache Friendly Code)작성 기법

템퍼럴 로컬리티와 스페이셜 로컬리티의 특성을 이용해야한다.

ex)

...

int total = 0;

 

for(int i=0; i<10; i++)

{

    for(int j=0; j<10;j++)

    {

        total += arr[j][i];

    }

}

...

위 코드를 보면 10x10배열을 모두 더하는 코드라는 것을 알 수 있다.

 

변수 total의 값이 빈번하게 갱신되고 있다는 점에서 템퍼럴 로컬리티는 만족이된다.

그러나 배열의 접근이 열 단위로도 이루어지는 점에서 스페이셜 로컬리티를 만족시키지 못한것이다.

행 단위접근이던 열단위 접근이던 스페이셜 로컬리티를 어느정도 만족하지만, 배열의 크기가 커질수록 스페이셜 로컬리티의 만족도는 떨어지게 된다.

그러나 배열의 크기와 상관없이 행단위로 접근한다면 그것은 스페이셜 로컬리티를 만족시킨다.