strided prefetching이있을 때 루프 순서가 중요한 이유는 무엇입니까?

Question

C에서는 배열이 후드 아래에 저장되고 행 반복이 전체 캐시 라인을 사용하므로 캐시 미스가 적어 행렬 순서로 행렬을 반복해야한다고 들었습니다. 실제로 필자는 컴퓨터에서 행 주요 열과 열 주요 반복 사이에 엄청난 성능 차이가 있음을 확인했습니다. 테스트 코드 :

#include <stdio.h> 
#include <stdlib.h> 

#include <time.h> 
#include <sys/resource.h> 

int getTime() 
{ 
    struct timespec tsi; 

    clock_gettime(CLOCK_MONOTONIC, &tsi); 
    double elaps_s = tsi.tv_sec; 
    long elaps_ns = tsi.tv_nsec; 
    return (int) ((elaps_s + ((double)elaps_ns)/1.0e9) * 1.0e3); 
} 

#define N 1000000 
#define M 100 

void main() 
{ 
    int *src = malloc(sizeof(int) * N * M); 
    int **arr = malloc(sizeof(int*) * N); 
    for(int i = 0; i < N; ++i) 
    arr[i] = &src[i * M]; 

    for(int i = 0; i < N; ++i) 
    for(int j = 0; j < M; ++j) 
     arr[i][j] = 1; 

    int total = 0; 

    int pre = getTime(); 


    for(int j = 0; j < M; ++j) 
    for(int i = 0; i < N; ++i) 
     total += arr[i][j]; 

    /* 
    for(int i = 0; i < N; ++i) 
    for(int j = 0; j < M; ++j) 
     total += arr[i][j]; 
    */ 

    int post = getTime(); 

    printf("Result: %d, took: %d ms\n", total, post - pre); 
} 

그러나, 현대 메모리 시스템은 스트라이드 액세스를 예측할 수 있으며,이 칼럼을 통해 반복 할 때 매우 규칙적인 패턴을 따르고 있습니다 프리 페 처가 있습니다. 이것은 열 - 주요 반복이 행 - 주요 반복과 유사하게 수행되도록 허용해서는 안됩니까?

Answer 1

캐시 라인은 특정 크기 (예 : 64 바이트)를 가지며 프로세서는 완전한 캐시 라인을 읽고 씁니다. 처리되는 바이트 수와 읽고 쓰여진 바이트 수를 비교하십시오.