CPU cache

CPU 캐시(CPU cache)는 CPU 구조에 메모리로 사용하도록 구성되었다. CPU 캐시는 메인 메모리에서 가장 자주 사용되는 위치의 데이터를 갖고 있는 크기는 작지만 빠른 메모리이다. 대부분의 메모리 접근은 특정한 위치의 근방에서 자주 일어나는 경향이 있기 때문에, 데이터를 크기는 작지만 속도가 빠른 캐시메모리에 복사해 두면 평균 메모리 접근 시간을 아낄 수 있다.

프로세서가 메인 메모리를 읽거나 쓰고자 할 때는, 먼저 그 주소에 해당하는 데이터가 캐시에 존재하는지를 살핀다. 만약 그 주소의 데이터가 캐시에 있으면 데이터를 캐시에서 직접 읽고, 그렇지 않으면 메인 메모리에 직접 접근한다. 이때 대부분의 프로세서는 메인 메모리에 직접 접근해서 전송된 데이터를 캐시에 복사해 넣음으로써 다음번에 같은 주소에 프로세서가 접근할 때 캐시에서 직접 읽고 쓸 수 있도록 한다.

Locality of reference (데이터의 지역성)

만일 캐쉬가 어떤 별도의 알고리즘 없이 단순히 중간속도의 매개체로 덩그라니 놓여 있다면 어떻게 될까요. 그렇다면 이러한 캐쉬메모리가 있으나 없으나 CPU가 데이터를 읽어 오는 속도나 쓰는 속도는 메인메모리에 읽고 쓰는 속도와 마찬가지가 될 뿐입니다. 즉, 캐쉬메모리가 있으나 없으나 같은 셈이 됩니다.

캐쉬메모리가 제 역할을 하는 것은 데이터의 지역성(localty)을 이용하기 때문입니다. 데이터의 지역성은 다음의 세가지로 나뉩니다.

공간적 지역성 (spartial locality)
시간적 지역성 (temporal locality)
순차적 지역성 (sequential locality)

캐시의 원리

캐시 라인과 태그 (데이터 묶음과 내용을 나타내는 작은 데이터)
- 메모리와 캐시 간 데이터 전송은 캐시 라인 단위.
캐시 데이터 저장구조
- Full Associative 방식
- Set Associative 방식
- Direct Map 방식

aligned_malloc

C++:alignas항목을 참조.

Thrashing

캐시 라인 쟁탈에 의한 성능 저하 현상을 Thrashing 이라 한다.

최적화 방법

Direct Map 방식에서 캐시의 데이터 묶음이 64Byte 단위로 256 라인만큼 있다면 16Kb(8byte * 2048) 단위로 동일한 캐시 라인을 사용하게 된다. ¹

이 경우 아래와 같은 코드가 있다고 가정한다.

double a[2048], b[2048];
for (i=0; i<N; i++) { a[i] = b[i]; }

위 코드는 동일한 캐시 라인을 사용하게 되어, 라인 쟁탈을 위한 빈번한 교체가 발생된다. 이 Thrashing현상은 아래와 같이 수정하여, 다른 캐시 라인을 참조하게 할 수 있다.

double a[2048], dummy[8], b[2048];
for (i=0; i<N; i++) { a[i] = b[i]; }

캐시의 성능 요소들

위에서 대략 살펴본 바를 토대로 생각을 해본다면, 좋은 캐쉬메모리는 항상 CPU가 원하는 데이터를 담고 그때그때 빠르게 CPU에게 공급을 해 줄 수 있는 녀석이어야 할 것입니다.

이렇게 CPU가 데이터를 원할때 캐쉬 메모리 내에 해당 데이터가 존재할 때를 우리는 캐쉬 적중(cache hit)이라고 합니다. 그리고 이렇게 적중하는 정도를 캐쉬적중율(hit rate)라고 부릅니다.

반면에 해당 데이터가 캐쉬 내에 존재하지 않는 경우, CPU는 원하는 데이터를 찾기 위해 높은 레이턴시를 감수하고 메인메모리에서 데이터를 읽어오게 됩니다. 이렇듯 원하는 데이터가 캐쉬메모리 내에 존재하지 않는 경우를 우리는 miss되었다고 부르며, 이러한 실패율을 miss rate라고 부릅니다.

Cache line

컴퓨터 시스템: 캐시 메모리 ²

Get cache line

Stackoverflow - Programmatically get the cache line size?

#ifndef GET_CACHE_LINE_SIZE_H_INCLUDED
#define GET_CACHE_LINE_SIZE_H_INCLUDED

// Author: Nick Strupat
// Date: October 29, 2010
// Returns the cache line size (in bytes) of the processor, or 0 on failure

#include <stddef.h>
size_t cache_line_size();

#if defined(__APPLE__)

#include <sys/sysctl.h>
size_t cache_line_size() {
    size_t line_size = 0;
    size_t sizeof_line_size = sizeof(line_size);
    sysctlbyname("hw.cachelinesize", &line_size, &sizeof_line_size, 0, 0);
    return line_size;
}

#elif defined(_WIN32)

#include <stdlib.h>
#include <windows.h>
size_t cache_line_size() {
    size_t line_size = 0;
    DWORD buffer_size = 0;
    DWORD i = 0;
    SYSTEM_LOGICAL_PROCESSOR_INFORMATION * buffer = 0;

    GetLogicalProcessorInformation(0, &buffer_size);
    buffer = (SYSTEM_LOGICAL_PROCESSOR_INFORMATION *)malloc(buffer_size);
    GetLogicalProcessorInformation(&buffer[0], &buffer_size);

    for (i = 0; i != buffer_size / sizeof(SYSTEM_LOGICAL_PROCESSOR_INFORMATION); ++i) {
        if (buffer[i].Relationship == RelationCache && buffer[i].Cache.Level == 1) {
            line_size = buffer[i].Cache.LineSize;
            break;
        }
    }

    free(buffer);
    return line_size;
}

#elif defined(linux)

#include <stdio.h>
size_t cache_line_size() {
    FILE * p = 0;
    p = fopen("/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size", "r");
    unsigned int i = 0;
    if (p) {
        fscanf(p, "%d", &i);
        fclose(p);
    }
    return i;
}

#else
#error Unrecognized platform
#endif

#endif

AMAT

대개의 경우, 캐쉬의 성능을 나타내는 것으로 AMAT(Average Memory Access Time : 평균 메모리 접근 시간)를 사용합니다.

캐쉬메모리의 경우 이 AMAT는 다음과 같은 공식으로 나타내어집니다.

AMAT = Hit Rate x Hit Time + (1 - Hit Rate) x Miss Penalty

Documentation

Windows 구조와 원리 - 12장. 프로세서 내의 캐시 관리: Windows_Architecture_and_Principles_-_Chapter_12._Cache_management_within_the_processor.pdf

Favorite site

References

("프로세서를 지탱하는 기술 - ISBN 6788994506241" 123페이지 참조) ↩
Computer_system_-_cache_memory.pdf ↩
Leojesus_-_what_is_cache_01.pdf ↩
Leojesus_-_what_is_cache_02.pdf ↩
Library_of_Ezbeat_-_Principles_of_CPU_Cache.pdf ↩
ARM9_cache.pdf ↩
For_effective_multi-threaded_programming.pdf ↩