C 캐시 레벨 및 크기 결정을 위한 프로그램

C 캐시 레벨 및 크기 결정을 위한 프로그램

명확성을 위해 전체 다시 쓰기/업데이트(그리고 당신의 제정신, 그것은 너무 깁니다)... (Old Post)

과제를 위해서는 각 캐시의 레벨(L1,L2,...)과 크기를 찾아야 합니다.힌트와 지금까지 발견한 내용을 보면, 다양한 크기의 배열을 만들어 읽는 것이 아이디어라고 생각합니다.작업 타이밍:

sizes = [1k, 4k, 256K, ...]
foreach size in sizes 
    create array of `size`

    start timer
    for i = 0 to n // just keep accessing array
        arr[(i * 16) % arr.length]++ // i * 16 supposed to modify every cache line ... see link
    record/print time

업데이트됨 (9월 6일 28일:57)PM UTC+8)

전체 출처 참고

도 있습니다.을 맞추는 @mah 의 SNR ratio ...). 그리고 코드 타이밍을 맞추는 방법을 찾았습니다.wall_clock_time예를 들어 실험실 코드에서)

하지만 결과가 잘못된 것 같습니다.Intel Core i32100: [SPECs]

• L1: 2 x 32K
• L2: 2 x 256K
• L3: 3MB

그래프로 얻은 결과:

lengthMod: 1KB ~ 512K

첫번째 피크의 베이스는 32K...합당한...두번째는 384K입니다... 왜죠?256개를 기대하고 있나요?

길이모드 : 512k~4MB

그럼 왜 이 범위가 엉망진창이 될 수도 있는 거지?

---

프리페칭이나 다른 애플리케이션의 간섭에 대해서도 읽었으므로 스크립트가 실행되는 동안 최대한 많은 것을 닫았는데, 1MB 이상의 데이터가 항상 너무 지저분한 것처럼 일관되게(다중 실행을 통해) 나타납니다.

인텔 사용 설명서를 10분간 검색하고 코딩을 10분간 더 한 후에 다음과 같은 내용을 생각해 냈습니다(인텔 기반 프로세서의 경우).

void i386_cpuid_caches () {
    int i;
    for (i = 0; i < 32; i++) {

        // Variables to hold the contents of the 4 i386 legacy registers
        uint32_t eax, ebx, ecx, edx; 

        eax = 4; // get cache info
        ecx = i; // cache id

        __asm__ (
            "cpuid" // call i386 cpuid instruction
            : "+a" (eax) // contains the cpuid command code, 4 for cache query
            , "=b" (ebx)
            , "+c" (ecx) // contains the cache id
            , "=d" (edx)
        ); // generates output in 4 registers eax, ebx, ecx and edx 

        // See the page 3-191 of the manual.
        int cache_type = eax & 0x1F; 

        if (cache_type == 0) // end of valid cache identifiers
            break;

        char * cache_type_string;
        switch (cache_type) {
            case 1: cache_type_string = "Data Cache"; break;
            case 2: cache_type_string = "Instruction Cache"; break;
            case 3: cache_type_string = "Unified Cache"; break;
            default: cache_type_string = "Unknown Type Cache"; break;
        }

        int cache_level = (eax >>= 5) & 0x7;

        int cache_is_self_initializing = (eax >>= 3) & 0x1; // does not need SW initialization
        int cache_is_fully_associative = (eax >>= 1) & 0x1;

        // See the page 3-192 of the manual.
        // ebx contains 3 integers of 10, 10 and 12 bits respectively
        unsigned int cache_sets = ecx + 1;
        unsigned int cache_coherency_line_size = (ebx & 0xFFF) + 1;
        unsigned int cache_physical_line_partitions = ((ebx >>= 12) & 0x3FF) + 1;
        unsigned int cache_ways_of_associativity = ((ebx >>= 10) & 0x3FF) + 1;

        // Total cache size is the product
        size_t cache_total_size = cache_ways_of_associativity * cache_physical_line_partitions * cache_coherency_line_size * cache_sets;

        printf(
            "Cache ID %d:\n"
            "- Level: %d\n"
            "- Type: %s\n"
            "- Sets: %d\n"
            "- System Coherency Line Size: %d bytes\n"
            "- Physical Line partitions: %d\n"
            "- Ways of associativity: %d\n"
            "- Total Size: %zu bytes (%zu kb)\n"
            "- Is fully associative: %s\n"
            "- Is Self Initializing: %s\n"
            "\n"
            , i
            , cache_level
            , cache_type_string
            , cache_sets
            , cache_coherency_line_size
            , cache_physical_line_partitions
            , cache_ways_of_associativity
            , cache_total_size, cache_total_size >> 10
            , cache_is_fully_associative ? "true" : "false"
            , cache_is_self_initializing ? "true" : "false"
        );
    }
}

참조: Intel® 64 및 IA-32 Architectures 개발자 설명서: Vol. 2A, 3-190페이지, CPUID—CPU 식별

이것은 현대 프로세서에서 캐시 프리페칭을 끄는 것이 거의 불가능하기 때문에 캐시 지연 시간을 측정하는 것보다 훨씬 더 안정적입니다.다른 프로세서 아키텍처에 대해 유사한 정보가 필요한 경우 해당 설명서를 참조해야 합니다.

하는 데 하는 데 (, () ) () 를 하는 데 시간보다 많은 수( 수)arr[(i*16)&lengthMod]++. 이와 같이 매우 낮은 신호 대 잡음비(다른 가능성이 있는 함정 중에서도)는 계획을 실행할 수 없게 만듭니다.문제의 대부분은 단일 반복을 측정하려고 한다는 것입니다. 연결한 샘플 코드는 반복의 전체 집합을 측정하려고 합니다(루프를 시작하기 전에 클럭을 읽고 루프에서 나온 후 다시 읽고 루프 내부에서 printf()를 사용하지 않음).

루프가 충분히 크다면 신호 대 잡음비 문제를 극복할 수 있을 것입니다.

"" 에 는,arr는 1MB입니다입니다.arr[(i * 16) & lengthMod]++;.(i * 16) * lengthMod해당 주소에서 오프셋을 생성합니다. 해당 오프셋은 증분되는 int의 주소입니다.시프트를 수행하는 중입니다(i * 16은 CPU에 따라 i << 4>, 논리적 및 추가로 읽기/추가/쓰기 또는 단일 증분으로 바뀝니다).

편집: 설명한 바와 같이 코드는 메모리 액세스의 상대적인 속도(캐시 또는 캐시 없음)와 시간 측정을 위한 호출 기능으로 인해 SNR(신호 대 잡음비)이 좋지 않습니다.현재 받는 시간을 파악하기 위해 코드를 다음과 같이 수정했다고 가정합니다.

int main() {
    int steps = 64 * 1024 * 1024;
    int arr[1024 * 1024];
    int lengthMod = (1024 * 1024) - 1;
    int i;
    double timeTaken;
    clock_t start;

    start = clock();
    for (i = 0; i < steps; i++) {
        arr[(i * 16) & lengthMod]++;
    }
    timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC;
    printf("Time for %d: %.12f \n", i, timeTaken);
}

하면 (합니다) 합니다를 입니다.steps접근할 수.

당신은 증가할 자유가 있습니다.steps필요에 따라 이것은 당신의 타이밍에 직접적인 영향을 미칠 것입니다.이 있는 에 시간이 이동함)에 따라로,며다,다),고의 해 볼 도 있습니다.steps.256 * 1024 * 1024더 크거나 더 크거나.

참고: 다음을 만들 수 있습니다.steps논리적이고 버퍼에서 랩어라운드를 수행하도록 보장하기 때문에 서명된 int에 들어갈 수 있는 만큼의 크기(충분히 커야 함)입니다.

알고 있습니다! (사실 프리페칭 때문에 굉장히 복잡합니다)

 for (times = 0; times < Max; time++) /* many times*/
     for (i=0; i < ArraySize; i = i + Stride)
           dummy = A[i]; /* touch an item in the array */

보폭을 변경하면 캐시의 속성을 테스트할 수 있습니다.그래프를 보면 답을 얻을 수 있습니다.

슬라이드 35-42 http://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf 보기

Erik Haggersten은 정말 좋은 선생님이고 (또한 정말 유능하고, 한때 태양 아래에서 수석 건축가였습니다), 더 좋은 설명을 위해 그의 나머지 슬라이드들을 보세요.

1MB 이상의 이상한 숫자에 대한 질문에 답하려면 매우 간단합니다. 캐시 제거 정책은 분기 예측과 L3 캐시가 코어 간에 공유된다는 사실과 관련이 있습니다.

코어 i3는 매우 흥미로운 캐시 구조를 가지고 있습니다.실제로 현대 프로세서라면 누구나 가능합니다.위키피디아에서 이들에 대해 읽어보셔야 합니다. "글쎄요, 저는 아마 이것이 필요하지 않을 겁니다.." 그러면 "피해자 현금에 넣어둘게요"라고 쓰여있거나 여러 가지를 말할 수 있습니다.L1-2-3 캐시 타이밍은 많은 수의 요인과 개별적인 설계 결정에 따라 매우 복잡할 수 있습니다.

또한 이러한 결정 및 기타 사항(이 주제에 대한 위키피디아 기사 참조)은 두 코어의 캐시 간에 동기화되어야 합니다.공유 L3 캐시를 개별 L1 및 L2 캐시와 동기화하는 방법은 추악할 수 있으며 역추적 및 재실행 계산 또는 다른 방법을 수반할 수 있습니다.두 번째 코어가 완전히 비어 있고 L3 캐시 공간을 놓고 경쟁하는 것이 없으므로 동기화 이상 현상이 발생할 가능성이 매우 낮습니다.

일반적으로 커널을 컨볼루션하는 것과 같이 데이터를 작업하는 경우 L1 캐시 내에 적합한지 확인하고 이를 중심으로 알고리즘을 형성하기를 원합니다.L3 캐시는 사용자가 수행하는 방식으로 데이터 세트를 작업하기 위한 것이 아닙니다(주 메모리보다 더 낫긴 하지만!).

캐시 알고리즘을 구현해야 하는 사람이 나였다면 나는 미쳐버렸을 것입니다.

다양한 진보를 가진 벤치마킹을 위해 lmbench 패키지에서 lat_mem_rd를 시도해 볼 수 있습니다. 오픈 소스: http://www.bitmover.com/lmbench/lat_mem_rd.8.html

Windows용 포트를 http://habrahabr.ru/post/111876/ 에 게시했습니다. 여기에 복사 붙여넣기를 하면 상당히 깁니다.그것은 2년 전의 것입니다, 저는 최신 CPU로 테스트하지 않았습니다.

창의 경우 GetLogical Processor Information 메서드를 사용할 수 있습니다.

리눅스의 경우 다음을 사용할 수 있습니다.sysconf(). 다음에 대한 유효한 인수를 찾을 수 있습니다.sysconf인에/usr/include/unistd.h아니면/usr/include/bits/confname.h

언급URL : https://stackoverflow.com/questions/12594208/c-program-to-determine-levels-size-of-cache