Cải thiện hiệu suất hoạt động của C với vị trí bộ nhớ cache?

Question

Tôi phải tìm ra sự khác biệt chéo trong một ma trận biểu diễn dưới dạng mảng 2ngày và nguyên mẫu chức năng là

int diagonal_diff(int x[512][512]) 

tôi phải sử dụng một mảng 2d, và các dữ liệu là 512x512. Điều này được thử nghiệm trên một máy SPARC: thời gian hiện tại của tôi là 6ms nhưng tôi cần phải dưới 2ms.

dữ liệu

mẫu:

[3][4][5][9] 
[2][8][9][4] 
[6][9][7][3] 
[5][8][8][2] 

Sự khác biệt là:

|4-2| + |5-6| + |9-5| + |9-9| + |4-8| + |3-8| = 2 + 1 + 4 + 0 + 4 + 5 = 16 

Để làm được điều đó, tôi sử dụng các thuật toán sau đây:

int i,j,result=0; 
for(i=0; i<4; i++) 
    for(j=0; j<4; j++) 
     result+=abs(array[i][j]-[j][i]); 

return result; 

Nhưng thuật toán này giúp truy cập cột, hàng, cột, hàng, v.v ... làm cho việc sử dụng bộ đệm không hiệu quả.

Có cách nào để cải thiện chức năng của tôi không?

Answer 1

EDIT: Tại sao phương pháp tiếp cận theo khối được định hướng nhanh hơn? Chúng tôi đang tận dụng bộ nhớ cache dữ liệu của CPU bằng cách đảm bảo rằng chúng ta lặp qua một khối theo hàng hoặc theo cột, chúng tôi đảm bảo rằng toàn bộ khối khớp với bộ nhớ cache.

Ví dụ: nếu bạn có một dòng bộ nhớ cache 32 byte và int là 4 byte, bạn có thể phù hợp với ma trận 8x8 int thành 8 dòng bộ nhớ cache. Giả sử bạn có một bộ nhớ cache dữ liệu đủ lớn, bạn có thể lặp qua ma trận đó theo hàng hoặc theo cột và được đảm bảo rằng bạn không thrash cache. Một cách khác để suy nghĩ về nó là nếu ma trận của bạn phù hợp trong bộ nhớ cache, bạn có thể đi qua nó bất kỳ cách nào bạn muốn.

Nếu bạn có ma trận lớn hơn nhiều, hãy nói 512x512, thì bạn cần điều chỉnh quá trình truyền tải ma trận sao cho bạn không làm hỏng bộ nhớ cache. Ví dụ, nếu bạn đi qua ma trận theo thứ tự ngược lại của bố trí của ma trận, bạn sẽ hầu như luôn luôn bỏ lỡ bộ nhớ cache trên mọi phần tử bạn truy cập.

Cách tiếp cận theo hướng khối đảm bảo rằng bạn chỉ bị thiếu bộ nhớ cache cho dữ liệu mà cuối cùng bạn sẽ truy cập trước khi CPU phải xóa dòng bộ nhớ cache đó. Nói cách khác, một phương pháp tiếp cận theo định hướng khối được điều chỉnh theo kích thước đường bộ nhớ cache sẽ đảm bảo bạn không làm đổ bộ nhớ cache.

Vì vậy, nếu bạn đang cố gắng để tối ưu hóa cho kích thước dòng bộ nhớ cache của máy bạn đang chạy trên, bạn có thể lặp qua các ma trận ở dạng khối và đảm bảo bạn chỉ ghé thăm mỗi phần tử ma trận một lần:

int sum_diagonal_difference(int array[512][512], int block_size) 
{ 
    int i,j, block_i, block_j,result=0; 

    // sum diagonal blocks 
    for (block_i= 0; block_i<512; block_i+= block_size) 
     for (block_j= block_i + block_size; block_j<512; block_j+= block_size) 
      for(i=0; i<block_size; i++) 
       for(j=0; j<block_size; j++) 
        result+=abs(array[block_i + i][block_j + j]-array[block_j + j][block_i + i]); 

    result+= result; 

    // sum diagonal 
    for (int block_offset= 0; block_offset<512; block_offset+= block_size) 
    { 
     for (i= 0; i<block_size; ++i) 
     { 
      for (j= i+1; j<block_size; ++j) 
      { 
       int value= abs(array[block_offset + i][block_offset + j]-array[block_offset + j][block_offset + i]); 
       result+= value + value; 
      } 
     } 
    } 

    return result; 
} 

Bạn nên thử nghiệm với các giá trị khác nhau cho block_size. Trên máy của tôi, 8 dẫn đến tốc độ lớn nhất lên (2.5x) so với block_size của 1 (và ~ 5x so với phiên bản gốc trên toàn bộ ma trận). block_size lý tưởng là cache_line_size_in_bytes/sizeof(int).

Answer 2

Với một thay đổi nhỏ, bạn có thể có vòng lặp của bạn chỉ hoạt động trên các chỉ mục mong muốn. Tôi vừa thay đổi khởi tạo vòng lặp j.

int i, j, result = 0; 
for (i = 0; i < 4; ++i) { 
    for (j = i + 1; j < 4; ++j) { 
     result += abs(array[i][j] - array[j][i]); 
    } 
} 

Answer 3

Nếu bạn có thư viện vector/ma trận tốt như intel MKL, hãy thử cách vectorized.

rất đơn giản trong MATLAB: result = sum (sum (abs (x-x ')));

tôi sao chép phương pháp Hans và phương pháp của MSN trong matlab quá, và kết quả là:

Elapsed time is 0.211480 seconds. (Hans) 

Elapsed time is 0.009172 seconds. (MSN) 

Elapsed time is 0.002193 seconds. (Mine)