Tại sao transposing một ma trận 512x512 chậm hơn nhiều so với transposing một ma trận 513x513?

Question

Sau khi tiến hành một số thí nghiệm trên các ma trận vuông có kích thước khác nhau, một mô hình đã xuất hiện. Không thay đổi, chuyển đổi ma trận có kích thước 2^n chậm hơn so với việc chuyển đổi một trong các kích thước 2^n+1. Đối với các giá trị nhỏ của n, sự khác biệt không lớn.

khác biệt lớn xảy ra tuy nhiên so với giá trị là 512. (ít nhất là đối với tôi)

Disclaimer: Tôi biết các chức năng không thực sự transpose ma trận vì sự hoán đổi đôi của các yếu tố, nhưng nó làm cho không có Sự khác biệt.

Làm theo mã:

#define SAMPLES 1000 
#define MATSIZE 512 

#include <time.h> 
#include <iostream> 
int mat[MATSIZE][MATSIZE]; 

void transpose() 
{ 
    for (int i = 0 ; i < MATSIZE ; i++) 
    for (int j = 0 ; j < MATSIZE ; j++) 
    { 
     int aux = mat[i][j]; 
     mat[i][j] = mat[j][i]; 
     mat[j][i] = aux; 
    } 
} 

int main() 
{ 
    //initialize matrix 
    for (int i = 0 ; i < MATSIZE ; i++) 
    for (int j = 0 ; j < MATSIZE ; j++) 
     mat[i][j] = i+j; 

    int t = clock(); 
    for (int i = 0 ; i < SAMPLES ; i++) 
     transpose(); 
    int elapsed = clock() - t; 

    std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed/SAMPLES; 
} 

Thay đổi MATSIZE cho phép chúng ta thay đổi kích thước (duh!). Tôi gửi hai phiên bản trên ideone:

• kích thước 512 - trung bình 2,46 ms - http://ideone.com/1PV7m
• kích thước 513 - trung bình 0,75 ms - http://ideone.com/NShpo

Trong môi trường của tôi (MSVS 2010, tối ưu hóa đầy đủ), sự khác biệt là tương tự:

• kích thước 512 - trung bình 2.19 ms
• kích thước 513 - trung bình 0,57 ms

Tại sao điều này xảy ra?

Answer 1

Giải thích đến từ Agner Fog trong Optimizing software in C++ và giảm dữ liệu được truy cập và lưu trữ trong bộ nhớ cache như thế nào.

Để biết các điều khoản và thông tin chi tiết, hãy xem wiki entry on caching, tôi sẽ thu hẹp nó xuống đây.

Bộ nhớ cache được sắp xếp theo số đặt và dòng. Tại một thời điểm, chỉ có một bộ được sử dụng, trong đó bất kỳ bộ nào mà nó chứa có thể được sử dụng. Bộ nhớ một dòng có thể nhân bản lần số lượng đường cung cấp cho chúng tôi kích thước bộ nhớ cache.

Đối với một địa chỉ bộ nhớ đặc biệt, chúng tôi có thể tính toán mà thiết lập nó nên được nhân đôi với công thức:

set = (address/lineSize) % numberOfsets 

loại này của công thức là cho phân phối lý tưởng thống nhất trên toàn bộ, bởi vì mỗi địa chỉ nhớ là như có khả năng được đọc (tôi đã nói lý tưởng là).

Rõ ràng là các trùng lặp có thể xảy ra.Trong trường hợp thiếu bộ nhớ cache, bộ nhớ được đọc trong bộ nhớ cache và giá trị cũ được thay thế. Hãy nhớ rằng mỗi bộ có một số dòng, trong đó một số dòng được sử dụng gần đây nhất được ghi đè bằng bộ nhớ mới được đọc.

Tôi sẽ cố gắng phần nào làm theo ví dụ từ Agner:

Giả sử mỗi bộ có 4 dòng, mỗi dòng chứa 64 byte. Trước tiên, chúng tôi cố đọc địa chỉ 0x2710, được đặt theo số 28. Và sau đó chúng tôi cũng cố gắng đọc địa chỉ 0x2F00, 0x3700, 0x3F00 và 0x4700. Tất cả đều thuộc về cùng một bộ. Trước khi đọc 0x4700, tất cả các dòng trong tập hợp sẽ bị chiếm đóng. Đọc bộ nhớ gợi lên dòng hiện tại trong tập hợp, dòng ban đầu đang giữ 0x2710. Vấn đề nằm ở thực tế là chúng tôi đọc các địa chỉ (ví dụ này) cách nhau 0x800. Đây là stride quan trọng (một lần nữa, ví dụ này).

Các sải chân quan trọng cũng có thể được tính toán:

criticaStride = numberOfSets * lineSize 

biến cách nhau criticalStride hoặc nhiều ngoài tranh cho các dòng bộ nhớ cache tương tự.

Đây là phần lý thuyết. Tiếp theo, lời giải thích (cũng Agner, tôi đang theo dõi nó chặt chẽ để tránh phạm sai lầm):

Giả sử một ma trận 64x64 (nhớ, hiệu ứng khác nhau tùy theo bộ đệm) với bộ đệm 8kb, 4 dòng mỗi bộ * kích thước dòng 64 byte. Mỗi dòng có thể chứa 8 phần tử trong ma trận (64-bit int).

Mức độ quan trọng sẽ là 2048 byte, tương ứng với 4 hàng ma trận (liên tục trong bộ nhớ).

Giả sử chúng tôi đang xử lý hàng 28. Chúng tôi đang cố gắng lấy các phần tử của hàng này và trao đổi chúng với các phần tử từ cột 28. 8 phần tử đầu tiên của hàng tạo thành một dòng bộ nhớ cache, nhưng chúng sẽ đi vào 8 dòng bộ nhớ cache khác nhau trong cột 28. Hãy nhớ, stride quan trọng là 4 hàng ngoài (4 yếu tố liên tiếp trong một cột).

Khi phần tử 16 đạt được trong cột (4 dòng bộ nhớ cache trên mỗi bộ & 4 hàng cách nhau = sự cố) phần tử ex-0 sẽ bị xóa khỏi bộ nhớ cache. Khi chúng tôi đến cuối cột, tất cả các dòng bộ nhớ cache trước đó sẽ bị mất và cần tải lại khi truy cập vào phần tử tiếp theo (toàn bộ dòng được ghi đè).

Có kích thước không phải là bội số quan trọng gây rối lên trường hợp hoàn hảo vì thảm họa này, vì chúng tôi không còn xử lý các yếu tố quan trọng. bị giảm nghiêm trọng.

Tuyên bố từ chối trách nhiệm khác - Tôi vừa mới giải thích và hy vọng tôi đã đóng đinh, nhưng có thể tôi đã nhầm. Dù sao, tôi đang chờ phản hồi (hoặc xác nhận) từ Mysticial. :)

Answer 2

Luchian giải thích về lý do tại sao hành vi này xảy ra, nhưng tôi nghĩ đó là một ý tưởng hay để hiển thị một giải pháp có thể cho vấn đề này và đồng thời hiển thị một chút về thuật toán không rõ ràng của bộ nhớ cache.

thuật toán của bạn cơ bản nào:

for (int i = 0; i < N; i++) 
    for (int j = 0; j < N; j++) 
     A[j][i] = A[i][j]; 

mà chỉ là khủng khiếp cho một CPU hiện đại. Một giải pháp là biết chi tiết về hệ thống bộ nhớ cache của bạn và tinh chỉnh thuật toán để tránh những vấn đề đó. Hoạt động tuyệt vời miễn là bạn biết những chi tiết đó .. không đặc biệt là di động.

Chúng ta có thể làm tốt hơn thế không? Vâng, chúng tôi có thể: Một cách tiếp cận chung cho vấn đề này là cache oblivious algorithms mà như tên gọi của mình tránh bị lệ thuộc vào kích thước bộ nhớ cache cụ thể [1]

Các giải pháp sẽ trông như thế này:

void recursiveTranspose(int i0, int i1, int j0, int j1) { 
    int di = i1 - i0, dj = j1 - j0; 
    const int LEAFSIZE = 32; // well ok caching still affects this one here 
    if (di >= dj && di > LEAFSIZE) { 
     int im = (i0 + i1)/2; 
     recursiveTranspose(i0, im, j0, j1); 
     recursiveTranspose(im, i1, j0, j1); 
    } else if (dj > LEAFSIZE) { 
     int jm = (j0 + j1)/2; 
     recursiveTranspose(i0, i1, j0, jm); 
     recursiveTranspose(i0, i1, jm, j1); 
    } else { 
    for (int i = i0; i < i1; i++) 
     for (int j = j0; j < j1; j++) 
      mat[j][i] = mat[i][j]; 
    } 
} 

Hơi phức tạp hơn, nhưng một bài kiểm tra ngắn cho thấy một cái gì đó khá thú vị trên E8400 xưa của tôi với VS2010 x64 phát hành, testcode cho MATSIZE 8192

int main() { 
    LARGE_INTEGER start, end, freq; 
    QueryPerformanceFrequency(&freq); 
    QueryPerformanceCounter(&start); 
    recursiveTranspose(0, MATSIZE, 0, MATSIZE); 
    QueryPerformanceCounter(&end); 
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart)/(double(freq.QuadPart)/1000)); 

    QueryPerformanceCounter(&start); 
    transpose(); 
    QueryPerformanceCounter(&end); 
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart)/(double(freq.QuadPart)/1000)); 
    return 0; 
} 

results: 
recursive: 480.58ms 
iterative: 3678.46ms 

Edit: về ảnh hưởng của kích thước: Nó được nhiều ít phát âm mặc dù vẫn còn đáng chú ý ở mức độ nào, đó là bởi vì chúng tôi đang sử dụng giải pháp lặp như nút lá thay vì đệ quy xuống 1 (tối ưu hóa thông thường cho các thuật toán đệ quy). Nếu chúng tôi đặt LEAFSIZE = 1, bộ nhớ cache không ảnh hưởng đến tôi [8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms - đó là bên trong lề lỗi, các biến động nằm trong khu vực 100ms; "điểm chuẩn" này không phải là điều mà tôi muốn quá thoải mái nếu chúng tôi muốn các giá trị hoàn toàn chính xác])

[1] Nguồn cho nội dung này: Tốt nếu bạn không thể thuyết trình từ một người đã làm việc với Leiserson và đồng ý điều này .. Tôi cho rằng giấy tờ của họ là một điểm khởi đầu tốt. Những thuật toán này vẫn còn khá hiếm khi được mô tả - CLR có một chú thích duy nhất về chúng. Tuy nhiên đó là một cách tuyệt vời để làm mọi người ngạc nhiên.

---

Sửa (lưu ý: Tôi không phải là một trong những người gửi câu trả lời này, tôi chỉ muốn thêm này):
Dưới đây là một C++ phiên bản hoàn chỉnh của đoạn code trên:

template<class InIt, class OutIt> 
void transpose(InIt const input, OutIt const output, 
    size_t const rows, size_t const columns, 
    size_t const r1 = 0, size_t const c1 = 0, 
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0, 
    size_t const leaf = 0x20) 
{ 
    if (!~c2) { c2 = columns - c1; } 
    if (!~r2) { r2 = rows - r1; } 
    size_t const di = r2 - r1, dj = c2 - c1; 
    if (di >= dj && di > leaf) 
    { 
     transpose(input, output, rows, columns, r1, c1, (r1 + r2)/2, c2); 
     transpose(input, output, rows, columns, (r1 + r2)/2, c1, r2, c2); 
    } 
    else if (dj > leaf) 
    { 
     transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2)/2); 
     transpose(input, output, rows, columns, r1, (c1 + c2)/2, r2, c2); 
    } 
    else 
    { 
     for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns); 
      i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns) 
     { 
      for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows); 
       j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows) 
      { 
       output[j2 + i1] = input[i2 + j1]; 
      } 
     } 
    } 
} 

Answer 3

Như một minh họa cho giải thích trong Luchian Grigore's answer, đây là những gì sự hiện diện bộ nhớ cache ma trận trông giống như đối với hai trường hợp ma trận 64x64 và 65x65 (xem liên kết ở trên để biết chi tiết về số).

Màu sắc trong các hình ảnh động dưới đây có nghĩa như sau:

• - không trong bộ nhớ cache,
• - trong bộ nhớ cache,
• - bộ nhớ cache hit,
• - chỉ cần đọc từ RAM ,
• - bộ nhớ cache bị bỏ lỡ.

Trường hợp 64x64:

Chú ý cách hầu hết quyền truy cập vào một kết quả hàng mới trong cache.Và bây giờ nó trông như thế đối với trường hợp bình thường, một ma trận 65x65:

Ở đây bạn có thể thấy rằng hầu hết các truy cập sau khi ban đầu nóng lên-up là hit cache. Đây là cách bộ nhớ cache CPU được thiết kế để làm việc nói chung.