使用緩存局部性改進C函數性能？

我必須找到在表示爲2D陣列和函數原型的矩陣的對角線的區別是使用緩存局部性改進C函數性能？

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

我必須使用一個二維數組，並且數據是512×512。這是在SPARC機器上測試的：我目前的時間是6ms，但我需要在2ms以下。

的樣本數據：

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

的區別是：

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

爲了做到這一點，我用下面的算法：

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;

但這種算法保持訪問列，行，列，行等，導致緩存使用效率低下。

有沒有辦法改善我的功能？

來源

2011-10-12 Christoper Hans

你有沒有基準或資料這個？真正的矩陣有多大？任何4乘4矩陣都適用於緩存，並且與訪問項目的順序無關。 –

即使您每秒執行50,000,000次這樣的操作，即使是低端的現代CPU也不會打破汗水。即使函數調用abs（）也會被大多數編譯器（包括GCC和VC++）固有的優化掉。 –

array的大小是512x512，我必須使用2D數組。接口規範是固定的，我只需要填寫implements.int diagonal_diff（int x [512] [512]，int y [512] [512]） –

編輯：爲什麼面向塊的方法更快？我們利用CPU的數據高速緩存確保我們是否按行或按列迭代，我們保證整個塊適合緩存。例如，如果你有一個32字節的緩存行，並且int是4個字節，那麼你可以將一個8×8的int矩陣放入8個緩存行中。假設您擁有足夠大的數據緩存，則可以按行或按列遍歷該矩陣，並保證不會顛簸緩存。另一種思考方式是如果你的矩陣適合緩存，你可以以任何你想要的方式遍歷它。

如果你有一個更大的矩陣，比如512x512，那麼你需要調整你的矩陣遍歷，這樣你纔不會顛簸緩存。例如，如果以與矩陣佈局相反的順序遍歷矩陣，則幾乎總是會錯過您訪問的每個元素的緩存。

面向塊的方法可確保您只有在CPU必須刷新該緩存行之前最終訪問的數據的緩存未命中。換句話說，調整到緩存行大小的面向塊的方法將確保您不會顛簸緩存。

所以，如果你想優化你的機器上運行的高速緩存行的大小，你可以遍歷塊形式的矩陣，並確保你只能訪問每個元素一次：

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

您應該嘗試使用block_size的各種值。在我的機器上，8導致最大加速（2.5x），而block_size爲1（與整個矩陣的原始迭代相比約爲5x）。理想情況下，block_size應該是cache_line_size_in_bytes/sizeof(int)。

來源

2011-10-12 04:44:14 MSN

在我的特定機器上，這個速度比擁有'blocksize = 8'的非緩存感知（Blastfurnace's）版本快了50％，這是我能夠獲得的最快速度。還有不到半毫秒的時間來執行。 –

此方法有效！非常感謝！有幾個結果錯誤，造成：結果+ =結果; in line 12 and： result + = value + value; 在第22行。我改變它使用單一的結果，而不是雙倍（這是@MSN做的），它完美的作品。 –

在我的測試中，block_size = 16是我能得到的最快速度。該方法比原始方法快80％。 –

有了一個小的改變，你可以讓你的循環只對所需的索引進行操作。我剛更改了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]); 
    } 
}

來源

2011-10-12 03:41:36 Blastfurnace

我做到了，但這並沒有太大的改善。我也嘗試在比較之前將列複製到另一個1維數組。定時約4ms –

這裏'i！= j'是不必要的。因爲你初始化'j = i + 1'，j永遠不可能等於i。 –

@Mike Bantegui，你是對的，我覺得有點愚蠢。謝謝。 – Blastfurnace

如果您有像英特爾MKL那樣的優秀矢量/矩陣庫，也可以嘗試矢量化的方式。

在matlab中非常簡單： result = sum（sum（abs（x-x'）））;

我在MATLAB轉載漢斯的方法和MSN的方法也一樣，其結果是：

Elapsed time is 0.211480 seconds. (Hans) 

Elapsed time is 0.009172 seconds. (MSN) 

Elapsed time is 0.002193 seconds. (Mine)

來源

2012-12-12 11:01:46 Desmond

使用緩存局部性改進C函數性能？

回答

相關問題