C 에서 행렬 곱셈 을 실현 하 는 효율 적 인 방법

행렬 곱셈 을 어떻게 계산 하 는 지 는 모두 가 알 고 있다.일반적으로 우 리 는 다음 과 같은 코드 로 이 루어 진다.

for(i=0;i<n;++i)
    for(j=0;j<n;++j){
        sum=0;
        for(k=0;k<n;++k)
            sum+=A[i][k]*B[k][j];
        C[i][j]+=sum;
}

그러나 고속 캐 시 문 제 를 고려 한 후에 사실은 더 좋 은 실현 방식 이 있다.

for(i=0;i<n;++i)
    for(k=0;k<n;++k){
        r=A[i][k];
        for(j=0;j<n;++j)
            C[i][j]+=r*B[k][j];
}

한 번 자세히 보면 이 두 가지 실현 의 미 는 등가 이지 만 후자 의 실제 운행 효율 은 전자 보다 높다 는 것 을 알 수 있다.
그런데 왜 그 럴 까?
CPU 가 데 이 터 를 읽 을 때 메모리 에 직접 접근 하 는 것 이 아니 라 캐 시 에 데이터 가 있 는 지 확인 하고 있 으 면 캐 시 에서 직접 읽 기 때 문 입 니 다.캐 시 에서 데 이 터 를 읽 는 것 이 메모리 에서 데 이 터 를 읽 는 것 보다 훨씬 빠르다.
데이터 가 캐 시 에 없 을 때 CPU 는 데 이 터 를 포함 한 데이터 블록 을 캐 시 에 읽 습 니 다.프로그램 이 좋 은 공간 부분 성 을 가지 고 있다 면 첫 번 째 cache miss 이후 몇 번 의 데이터 접근 은 캐 시 에서 직접 완성 할 수 있 습 니 다.공간 국부 성(프로그램 은 현재 데이터 와 가 까 운 데 이 터 를 인용 하 는 경향 이 있 음)을 제외 하고 시간 국부 성(프로그램 은 최근 에 인 용 된 데 이 터 를 인용 하 는 경향 이 있 음)도 있다.
행렬 곱셈 으로 돌아가다.우 리 는 내부 순환 만 을 생각한다)
전 자 는 행렬 A 에 대해 좋 은 공간 국부 성 을 가지 고 한 번 에 네 개의 요 소 를 캐 시 할 수 있다 고 가정 하면 매번 교체 할 때마다 A 에 대해 0.25 번 miss 만 있 지만 B 에 대해 서 는 그렇지 않 기 때문에 B 는 열 에 따라 방문 하고 매번 방문 할 때마다 miss 가 있 기 때문에 매번 교체 할 때마다 총 miss 수 는 1.25 이다.
후 자 는 행렬 C 와 행렬 B 에 대해 좋 은 국 지성 을 가지 고 매번 교체 할 때마다 0.25 단어 miss 만 있 기 때문에 전체적인 miss 수 는 0.5 이다.후 자 는 매번 한 번 씩 저장(C[i][j]에 대한 기록)을 더 했 지만 그래도 후자 의 운행 효율 은 전자 보다 높다.
한 마디 로 하면 프로그램 이 빨리 달 리 려 면 프로그램 에서 국 지성 을 많이 이용 하여 캐 시 hold 가 데 이 터 를 잡 고 방문 횟수 를 줄 여야 합 니 다.CPU 가 3 개의 시계 주기 내 에 L1 cache 에 접근 할 수 있 고 10 개의 시계 주기 정도 의 시간 이 L2 cache 에 접근 할 수 있다 는 것 을 알 아야 한다.메모리 에 접근 하려 면 백 개의 시계 주기 가 필요 합 니 다.어느 것 이 빠 르 고 어느 것 이 느 린 지 잘 알 고 있 죠?