2013-03-06 95 views
1

我正在嘗試構建求和區域表,以便以後在自適應閾值例程中使用。由於該代碼將用於時間關鍵型軟件,因此我試圖儘可能多地從中擠出循環。高效地構建求和區域表

對於性能,該表是無符號整數的每個像素。

當我附上我的分析器時,我發現執行x遍時發生了最大的性能瓶頸。

用於計算中的簡單的數學表達式爲:

sat_[y * width + x] = sat_[y * width + x - 1] + buff_[y * width + x] 
where the running sum resets at every new y position. 

在這種情況下,sat_是表示SAT無符號整數的1-d指針,並且buff_是一個8位的無符號的單色緩衝器。

我的實現如下所示:因爲我的編譯器(VC11)並沒有爲我做

uint *pSat = sat_; 
char *pBuff = buff_; 

for (size_t y = 0; y < height; ++y, pSat += width, pBuff += width) 
{ 
    uint curr = 0; 
    for (uint x = 0; x < width; x += 4) 
    { 
     pSat[x + 0] = curr += pBuff[x + 0]; 
     pSat[x + 1] = curr += pBuff[x + 1]; 
     pSat[x + 2] = curr += pBuff[x + 2]; 
     pSat[x + 3] = curr += pBuff[x + 3]; 
    } 
} 

環路手動展開。我遇到的問題是,整個分段例程花費了大量的時間,只是在循環中運行,我想知道是否有人對可能加速的內容有任何想法。我可以訪問所有SSE的設置,而AVX可以運行這個例程將運行的任何機器,所以如果有什麼東西的話,那將非常有用。另外,一旦我擠出最後的週期,然後計劃將其擴展到多核,但是我希望在使模型更復雜之前儘可能地使單線程計算更緊密。

+0

你的代碼沒有實現你在第一個表達式中寫的東西......具體來說,你在每一行的開始處重置'curr',但這並不是表達式所暗示的。 – 2013-03-06 23:01:05

+0

你說得對,我在數學上玩的很快而且鬆懈。如果你有一個關於如何重寫x傳球數學的建議,我就是比賽。該算法的實現是正確的,但是,只是沒有我希望實現的那麼快。 – Mranz 2013-03-06 23:06:32

+0

好的。我問的原因是因爲這個代碼是否可以被矢量化/並行化是至關重要的。這聽起來像是你運氣不錯,因爲重置在每一行打破了依賴鏈。 – 2013-03-06 23:07:31

回答

2

您有沿每行運行的依賴鏈;每個結果取決於前一個結果。所以你不能在這個方向上進行矢量化/平行化。

但是,它聽起來像每一行都獨立於所有其他行,所以您可以通過同時計算多行來矢量化/並行化。你需要調換你的數組,以便讓矢量指令訪問內存中的相鄰元素。 *

但是,這會產生問題。從緩存的角度來看,沿着行走現在將是絕對可怕的(每次迭代都會導致緩存未命中)。解決這個問題的方法是交換循環順序。

但是請注意,每個元素只能精確讀取一次。而且你對每個元素的計算量非常小。因此,在達到100%的CPU使用率之前,基本上會受到主內存帶寬的限制。


*此限制可能AVX2被取消,我不知道...

+0

有趣的,所以它可以矢量化,而不必運行轉置。 – Mranz 2013-03-06 23:46:31

+1

對於SSE實現,您可能需要考慮處理16x16切片,而不是轉換整個圖像。你可以做一個快速的16x16轉置,主要是基於寄存器的,然後遍歷16個結果向量累加16個部分和。 – 2013-03-07 07:53:05

+0

@PaulR我試過了,這是一個有趣的方法。不幸的是,平均每個測試圖像的速度慢了約1ms。謝謝你的提示。 – Mranz 2013-03-07 21:33:09

1

算法上,我不認爲有什麼可以做,以進一步優化本。儘管您在描述中沒有使用術語OLAP多維數據集,但您基本上只是構建了一個OLAP多維數據集。您擁有的代碼是構建OLAP多維數據集的標準方法。

如果您提供有關正在使用的硬件的詳細信息,則可能會提供一些優化。例如,有一種GPU編程方法可能會或可能不會更快。注意:該線程的另一篇文章提到並行化是不可能的。這不一定是真的......你的算法不能並行實現,但有些算法可以保持數據級並行性,這可以通過GPU方法加以利用。

+0

我可以通過簡單地將行的前半部分交給線程A,而將另一半交給線程B進行X遍來使算法平行。當我實現這一點時,我在per-frame perf中獲得了小幅增益,這使我相信我並不是100%的帶寬受限,只是大部分。我已經看到使用遞歸加倍的GPU方法,但我發現來回移動數據的開銷是我的限制因素。 – Mranz 2013-03-07 21:35:35