캐시 두 행렬 I 캐시 친화적 인 방법을 사용하여 두 행렬 곱하려는

Question

를 거는 친화적 인 방법

(즉, 미스의 적은 숫자로 이어질 것이다) 나는이이 캐시 친화적 인 트랜스 기능을 수행 할 수 있다는 것을 발견 .

그러나이 알고리즘을 찾을 수 없습니다. 이 방법을 알 수 있습니까?

Answer 1

찾으시는 단어는 입니다.입니다. Google에서 쓰레싱 행렬 곱셈을 찾으십시오.

C에 대한 표준 승산 알고리즘 = A * B는 큰 단계 fastly 메모리 탐색 기본적

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      for (int k = 0; k < n; k++) 
       C[i, j] += a[i, k] * b[k, j]; 
} 

같을 것이다 것은 성능에 불리하다. k에 대한 액세스 패턴은 [k, j]입니다. 그래서 그 대신 메모리에 주위 점프, 우리는 가장 내부 루프는 행렬의 제 2 액세스 인덱스에서 작동하도록 작업을 재 배열 할 수 있습니다

void multiply(double[,] a, double[,] B, double[,] c) 
{ 
    for (i = 0; i < n; i++) 
    { 
     double t = a[i, 0]; 
     for (int j = 0; j < n; j++) 
     c[i, j] = t * b[0, j]; 

     for (int k = 1; k < n; k++) 
     { 
     double s = 0; 
     for (int j = 0; j < n; j++) 
      s += a[i, k] * b[k, j]; 
     c[i, j] = s; 
     } 
    } 
} 

이 해당 페이지에 주어진 예였다. 그러나 다른 옵션은 B [k, *]의 내용을 미리 배열에 복사하고이 배열을 내부 루프 계산에 사용하는 것입니다. 이 방법은 대개 데이터를 복사하는 경우에도 대체 방법보다 훨씬 더 빠르게 입니다.보다 빠릅니다. 이것이 직관에 반하는 것처럼 보일지라도 스스로 자유롭게 시도하십시오.

void multiply(double[,] a, double[,] b, double[,] c) 
{ 
    double[] Bcolj = new double[n]; 
    for (int j = 0; j < n; j++) 
    { 
     for (int k = 0; k < n; k++) 
      Bcolj[k] = b[k, j]; 

     for (int i = 0; i < n; i++) 
     { 
      double s = 0; 
      for (int k = 0; k < n; k++) 
       s += a[i,k] * Bcolj[k]; 
      c[j, i] = s; 
     } 
    } 
} 

Answer 2

@ Cesar의 대답이 정확하지 않습니다. 예를 들어, 내부 루프

for (int k = 0; k < n; k++) 
    s += a[i,k] * Bcolj[k]; 

은 a의 i 열을 통과합니다.

다음 코드는 항상 데이터를 행 단위로 방문해야합니다.

void multiply(const double (&a)[I][K], 
       const double (&b)[K][J], 
       const double (&c)[I][J]) 
{ 
    for (int j=0; j<J; ++j) { 
     // iterates the j-th row of c 
     for (int i=0; i<I; ++i) { 
     c[i][j] = 0; 
     } 

     // iterates the j-th row of b 
     for (int k=0; k<K; ++k) { 
      double t = b[k][j]; 
      // iterates the j-th row of c 
      // iterates the k-th row of a 
      for (int i=0; i<I; ++i) { 
      c[i][j] += a[i][k] * t; 
      } 
     } 
    } 
}