[CS] 캐시 적중률

캐시 메모리는 작업에 필요한 메모리를 읽고 쓰는데 필요한 존재입니다. 아래는 C스타일의 버블 정렬 프로그램 코드입니다.

#include <iostream>

#define ARR_LEN 5

void bubblesort(int srcArr[], int n)
{
    int i, j, temp;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n - 1; j++)
        {
            if (srcArr[j - 1] > srcArr[j])
            {
                temp = srcArr[j - 1];
                srcArr[j - 1] = srcArr[j];
                srcArr[j] = temp;
            }
        }
    }
}

int main() 
{
    int arr[ARR_LEN] = {5, 3, 7, 6, 9};
    bubblesort(arr, ARR_LEN);

    for (int i = 0; i < ARR_LEN; i++)
    {
        std::cout << arr[i] << std::endl;
    }

    return 0;
}

 

 

[템퍼럴 로컬리티(Temporal Locality)]

 

위의 버블 정렬 코드에서, 함수를 살펴보면 지역 변수로 i, j, temp가 존재합니다. 이 변수들은 연산을 위해 자주 활용되는데, 이렇게 지역적(스코프)으로 자주 사용되는 특성을 템퍼럴 로컬리티(Temporal Locality)라고 합니다. 프로그램 실행 시 한 번 접근이 이뤄진 주소의 메모리 영역은 자주 접근하게 된다는 프로그램의 특성을 표현할 때 자주 사용되는 단어입니다.

 

 

[스페이셜 로컬리티(Special Locallity)]

 

버블 정렬 함수 중간에 다음과 같은 코드가 존재합니다.

srcArr[j - 1] = srcArr[j];

 

여기서 중요한 점은 j값의 변화입니다. j는 0부터 배열 크기만큼 증가하는 값입니다. 이 증가된 값은 배열의 인덱스 접근 연산에 활용되고, 이 대 메모리의 주소값은 4byte씩 증가하게 됩니다. 이러한 특성을 가리켜 스페이셜 로컬리티(Special Locality)라고 합니다.

 

프로그램 실행 시 접근하는 메모리 영억은 이미 접근이 이뤄진 영억 근처일 확률이 높다는 프로그램 특성을 지칭할 때 사용되는 단어입니다. 만약 현재 연산에 필요한 주소가 0x001B라면, 다음 메모리 접근은 그 주소와 굉장히 가까운 곳일 확률이 높다는 것입니다.

 

 

[캐시 적중(Cache hit)과  캐시 미스(Cache miss)]

 

아래의 그림은 ALU와 레지스터, 메모리들에 대한 그림입니다.

 

ALU는 연산 시 데이터가 필요하고, 이 데이터는 레지스터에 존재합니다. 하지만 레지스터에 데이터가 존재하지 않을 경우, 가장 가까운 메모리를 확인하게 되는데, 그림에서는 L1 캐시가 가장 가까운 메모리가 됩니다. L1 캐시에 데이터가 존재할 경우를 캐시 히트(캐시 적중; Cache Hit)라고 합니다. 물론 없을 경우네는 캐시 미스(Cache Miss)라고 하겠죠.

 

캐시 미스가 발생할 경우에는 다음 메모리인 L2 캐쉬, 여기에서도 캐시 미스가 발생하면 메인 메모리, 끝으로는 하드 디스크까지 데이터를 찾아보는 작업을 수행하게 됩니다. 그렇다면 ALU가 연산을 수행할 때 당연히 레지스터에 데이터가 있으면 좋을 것이고, 여기에도 없다면 그 다음에는 데이터가 있는 것이 원할한 작업 수행에 도움이 될 것입니다.

 

+) 순차적으로 데이터를 찾다가, 그 다음의 메모리에 데이터가 존재하면 캐시 교체를 실시하게 됩니다. 여기서 꽉 찬 L1 캐시 데이터를 사용하려면 당연히 이미 들어있던 데이터를 밀어내야만 하는데, 아무런 규칙없이 데이터를 밀어내는 것은 아닙니다. 여기서는 블록 교체 알고리즘을 활용하여 데이터 교환을 실시합니다. 블록 교체 알고리즘은 캐시 교체 정책에 따라 여러 가지가 존재하지만, 운영체제론에서 가장 대표적인 알고리즘으로는 LRU(Least-Recently Used) 알고리즘을 활용합니다

 

+) LRU 알고리즘 : 최근에 가장 적게 사용한 캐시를 교체하는 알고리즘