高效的訪問矩陣列

高效的訪問問題：我需要訪問一個大矩陣（大於2000x2000）列明智，我的算法需要1行通過和1列通過。行傳遞對於內存效率（高速緩存未命中）是正確的，但是如何減少列通過中的高速緩存未命中？我需要效率。高效的訪問矩陣列

我的嘛我是這樣的：聲明ñ局部變量（根據內存讀取大小），

int a1, a2, a3, a4; for (int j = 0 ; j < DIM_Y ; j+=4) for (int i = 0 ; i < DIM_X ; i++) a1 = matrix[i][j]; ... ; a4 = matrix[i][j+4]; // make the column processing on the 4 variables.

這是一個在C或C++，和數組或int或字符。

歡迎提出任何建議和意見。

謝謝。

來源

2013-02-02 user1479498

你在用什麼語言？請相應地標記問題。 – ja72

矩陣類型是什麼？很容易假設它是一個二維int數組，但也可能是一個int數組指針等。 – jimhark

存儲2D矩陣的有效方式，是使用C樣式陣列是這樣的：

| a11 a12 a13 | 
| a21 a22 a23 | -> memory: [a11,a12,a13,a21,a22,a23,a31,a32,a33] 
| a31 a32 a33 | 

Element(i,j) = memory[N_COL*i+j]

其中i是從0開始行號索引，和j列號索引也從0開始，和N_COL的列數。

希望編譯器/ jit將所有的值按順序放在內存中以便快速訪問。通常你試圖欺騙編譯器的次數越多（就像手動循環展開一樣），你越是在性能上受到傷害。編寫乾淨的代碼並讓編譯器完成它的工作。

來源

2013-02-02 21:58:11 ja72

如果N_COL在編譯時不知道，那麼這是一個好方法，否則C支持二維數組直接使用（在原始問題中明顯使用）。它們效率不低（儘管在編譯時你必須知道除了最後一個維度外的所有維度）。 – jimhark

嗨Ja72，謝謝，但我的輸入矩陣，它來自另一個應用程序，並轉換爲一個數組第一將不會記憶效率高，第二不會讓它更快，元素在N_COL距離將有相同的緩存缺失壞處。 – user1479498

兩種基本技術適用：

1）循環阻斷

代替

for (j=0;j<2000;j++) 
    for (i=0;i<2000;i++) 
    process_element(i,j);

使用

for (j=0;j<2000;j+=8) 
    for (i=0;i<2000;i+=8) 
    process_block_of_8x8(i,j);

2）非動力2行步幅（例如8192字節+ 64） - 必要時填充

在這種情況下，row [i] .. row [i + 7]不會爲同一高速緩存行作戰

數據應該位於手動計算的填充區的連續內存區域中。

來源

2013-02-04 10:41:17

這不會給出相同數量的緩存未命中，除非矩陣以塊方式存儲。 – user877329

高效的訪問矩陣列

回答

相關問題