시간 지역성을 위한 캐시 재배치

c = (double *) calloc(sizeof(double), n*n);
/* Multiply n x n matrices a and b */
void mmm(double *a, double *b, double *c, int n) { int i, j, k;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        	for (k = 0; k < n; k++)
            		c[i*n + j] += a[i*n + k] * b[k*n + j];
}

다음의 코드가 있다고 가정하자. 

그리고 이해의 편의를 위해 추가적으로 다음도 가정한다.

• 각 배열은 double의 n x n 배열이며, sizeof(double) == 8 이다.
• 32바이트 블록 크기를 갖는 (B = 32) 단일 캐시를 가지고 있다.
• 배열 크기 n은 매우 커서 단일 행렬의 행은 L1 캐시에 들어가지 않는다.
• 컴파일러는 지역변수를 레지스터에 저장하고, 따라서 루프 내 지역변수에 대한 참조는 load나 store 연산을 사용하지 않는다(지역 변수의 load에는 메모리의 개입이 없다).

이때 A는 행 우선으로 stride-1 접근 패턴을 통해 스캔이 이뤄지는 반면, B는 열 우선으로 stride-n 접근 패턴으로 캐시의 의미가 퇴색된다.

때문에 A는 n / 8의 miss rate를 갖게 되며, B는 1의 miss rate를 갖게 된다. 총 9/8의 miss rate를 갖는다.

대신 내부적으로 mini block을 만들어서, 시간적으로 더 근처에 접근될 수 있도록 구성한다.

c = (double *) calloc(sizeof(double), n*n);
/* Multiply n x n matrices a and b */
void mmm(double *a, double *b, double *c, int n) { 
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            for (k = 0; k < n; k++)
                for (i1 = 0; i1 < i + B; i1++)
                    for (j1 = 0; j1 < j + B; j1++)
                        for (k1 = 0; k1 < k + B; k1++)
                            c[i1 * n + j1] += a[i1 * n + k1] * b[k1 * n + j1];
}

 

 

이렇게 되면 총 mini block이 n / B개가 생긴다. 또한 각각의 블록이 B / 8 * B 번의 miss가 발생하여 B^2 / 8 번의 miss가 발생한다.

최초 루프에서 (2n / B) * (B^2 / 8) 해서 nB/4의 miss rate가 나온다. 이후 second block iteration에서도 nB / 4 가 나오고 이는 블록의 수만큼 반복된다. 

블록의 수는 (n / B) * (n / B) 이므로 최종적으로 블록의 수 x 초기 반복의 miss rate 해서 n^3 / 4B가 최종 miss rate가 된다.