如何緩解轉置陣列訪問順序對性能的影響？

我有一個算法，用C編寫，它處理一對二維數組（例如，大小爲Y x X）以產生另一個相同大小的二維數組。所有三個數組都包含32位浮點數並且具有相同的大小Y x X，其中Y可能是幾十，但X是一百萬左右。如何緩解轉置陣列訪問順序對性能的影響？

不幸的是：

所有陣列必須是row-major order（掃描通過X訪問連續的存儲器），
算法需要最內層循環掃描整個Y維度。

也許不出所料，以非連續方式訪問數據相對較慢。所以...

我能做些什麼來緩解非連續內存訪問對性能的影響？

（特別注意這是一個long shot，但我試過的預取指令的各種圖案在即將到來的欄目帶來，但都無濟於事）

以下（更新）代碼演示此問題：

#include <stdio.h> 
#include <stdlib.h> 

#define NX 1000000 
#define NY 30 

int main() { 
    float *a = malloc(sizeof(float) * NY * NX); 
    float *b = malloc(sizeof(float) * NY * NX); 
    float *c = malloc(sizeof(float) * NY * NX); 

    size_t y, x, offset; 
    float v; 

    for(x=0; x<NX; x++) { 
     v = 1; 
     for(y=0; y<NY; y++) { 
      offset = x + NX * y; 
      if(a[offset] < 0) { 
       v = 2; 
      } 
      c[offset] = v * b[offset]; 
     } 
    } 

    free(a); 
    free(b); 
    free(c); 
}

在配備E5520 CPU @ 2.27 GHz的測試機器上，即使只讀取〜220 MB並寫入〜110 MB，執行時間也需要1秒。

來源

2015-06-11 Colonel Mustard

如果你可以將你的數據分解成尺寸合理的chuncks/blocks，使它可以共存於緩存中的雙重循環中，這可以提供幫助。這當然取決於你的算法（和問題）如何合併結果塊。在上面的添加這樣簡單的事情中，這不需要進一步的工作。 –

取決於你的循環體是什麼，迭代之間有什麼依賴關係。切換循環順序將是最佳選擇，但可能需要一些輔助存儲。阻塞/平鋪算法也是一個不錯的選擇，但是在給定機器的特定參數的情況下，您必須小心瓷磚尺寸（例如，在3MB緩存中效果良好的瓷磚尺寸可能無法很好地發揮作用在具有512K緩存的系統上運行）。我想我們需要更多關於你的實際算法的信息，而不是上面的玩具測試用例... – twalberg

我已經更新了示例代碼，試圖說明處理的列順序性質。 –

它看起來像你的訪問模式不應該是有害的。這讓我懷疑branch prediction是否是你真正的問題。

通常轉置的數據訪問是以塊來完成的，以保持緩存的健康，但是您的輸入在內循環軸上很短，以至於第一行的緩存讀取在您重新訪問時仍然有效外環。

你有三個數組30個元素，高達128個字節的高速緩存線寬（我預計更小，但事情發生變化）。這隻有12kB的緩存，您需要頂級行才能保持駐留。

儘管如此，您可以嘗試將v更改爲小陣列並以垂直條紋進行處理。即使這實際上並沒有幫助你的緩存利用率，它至少會給編譯器一個提示，說它可以用SIMD進行優化。

你也可以試試這個危險的優化以消除分支：

for(x=0; x<NX; x++) { 
    uint32_t v = 0; 
    for(y=0; y<NY; y++) { 
     offset = x + NX * y; 
     v |= (((uint32_t *)a)[offset] & 0x80000000) >> 8; 
     ((uint32_t *)c)[offset] = ((uint32_t *)b)[offset] + v; 
    } 
}

這確實算術在對數域中，以浮點值的符號位，並直接將其添加到指數和假設它不會溢出。另外假定內存中的格式與兼容。

來源

2015-06-12 15:08:48 sh1

如何緩解轉置陣列訪問順序對性能的影響？

回答

相關問題