cache phương pháp thân thiện với nhân hai ma trận

Question

tôi dự định để nhân 2 ma trận bằng cách sử dụng phương pháp bộ nhớ cache thân thiện (mà sẽ dẫn đến ít số bỏ lỡ)

tôi phát hiện ra rằng điều này có thể được thực hiện với một chức năng transpose thân thiện với bộ nhớ cache .

Nhưng tôi không thể tìm thấy thuật toán này. Tôi có thể biết cách đạt được điều này không?

Answer 1

Từ bạn đang tìm kiếm là đập. Tìm kiếm phép nhân bản ma trận trong Google yields more results.

Một thuật toán nhân tiêu chuẩn cho c = a * b sẽ trông như thế

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]; 
} 

Về cơ bản, điều hướng các bộ nhớ nhanh chóng tiện lợi trong bước lớn là gây phương hại đến hiệu suất. Mẫu truy cập cho k trong B [k, j] đang thực hiện chính xác điều đó. Vì vậy, thay vì nhảy xung quanh trong bộ nhớ, chúng tôi có thể sắp xếp lại các hoạt động như vậy mà vòng bên trong hầu hết các hoạt động duy nhất trên chỉ số truy cập thứ hai của các ma trận:

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; 
     } 
    } 
} 

Đây là ví dụ đưa ra trên trang đó. Tuy nhiên, một tùy chọn khác là sao chép nội dung của B [k, *] vào một mảng trước và sử dụng mảng này trong các tính toán vòng lặp bên trong. Cách tiếp cận này thường là nhanh hơn nhiều so với các lựa chọn thay thế, ngay cả khi nó liên quan đến việc sao chép dữ liệu xung quanh. Ngay cả khi điều này có vẻ phản trực giác, xin vui lòng thử cho chính mình.

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

@ Câu trả lời của Cesar là không chính xác. Ví dụ: vòng lặp bên trong

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

đi qua cột thứ i của a.

Mã sau phải đảm bảo chúng tôi luôn truy cập hàng dữ liệu theo hàng.

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; 
      } 
     } 
    } 
}