在C程序用於加速

Question

刪除條件我有一個數字運算的C程序，其涉及一個主循環有兩個條件語句：

for (i = 0; i < N; i++) { 
for (j = 0; j < N; j++) { 
    for (k = 0; k < N; k++) { 
    if (k == i || k == j) continue; 
    ...(calculate a, b, c, d (depending on k) 
    if (a*a + b*b + c*c < d*d) {break;} 
    } //k 
} //j 
} //i 

這裏的硬件是Cell處理器的SPE，其中有一個大在使用分支時會受到懲罰。所以爲了優化我的加速程序，我需要刪除這兩個條件，你知道這個好策略嗎？

Answer 1

對於第一個，你可以分解成多個迴路，例如改變：

for(int i = 0; i < 1000; i++) 
    for(int j = 0; j < 1000; j++) { 
    for(int k = 0; k < 1000; k++) { 
     if(k==i || k == j) continue; 
     // other code 
    } 
    } 

到：

for(int i = 0; i < 1000; i++) 
    for(int j = 0; j < 1000; j++) { 
    for(int k = 0; k < min(i, j); k++) { 
     // other code 
    } 
    for(int k = min(i, j) + 1; k < max(i, j); k++) { 
     // other code 
    } 
    for(int k = max(i, j) + 1; k < 1000; k++) { 
     // other code 
    } 
    } 

刪除第二，你可以存儲以前的總，並用它在for循環條件下，即：

int left_side = 1, right_side = 0; 
for(int i = 0; i < N; i++) 
    for(int j = 0; j < N; j++) { 
    for(int k = 0; k < min(i, j) && left_side >= right_side; k++) { 
     // other code (calculate a, b, c, d) 
     left_side = a * a + b * b + c * c; 
     right_side = d * d; 
    } 
    for(int k = min(i, j) + 1; k < max(i, j) && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    for(int k = max(i, j) + 1; k < N && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    } 

實施min和沒有分支的max也可能會很棘手。也許這個版本更好：

int i, j, k, 
    left_side = 1, right_side = 0; 
for(i = 0; i < N; i++) { 
    // this loop covers the case where j < i 
    for(j = 0; j < i; j++) { 
    k = 0; 
    for(; k < j && left_side >= right_side; k++) { 
     // other code (calculate a, b, c, d) 
     left_side = a * a + b * b + c * c; 
     right_side = d * d; 
    } 
    k++; // skip k == j 
    for(; k < i && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    k++; // skip k == i 
    for(; k < N && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    } 
    j++; // skip j == i 
    // and now, j > i 
    for(; j < N; j++) { 
    k = 0; 
    for(; k < i && left_side >= right_side; k++) { 
     // other code (calculate a, b, c, d) 
     left_side = a * a + b * b + c * c; 
     right_side = d * d; 
    } 
    k++; // skip k == i 
    for(; k < j && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    k++; // skip k == j 
    for(; k < N && left_side >= right_side; k++) { 
     // same as in previous loop 
    } 
    } 
} 

Answer 2

我同意'sje397'。

除此之外，您提供的問題信息太少。你說分支是昂貴的。但實際發生的頻率如何？也許你的問題是編譯器生成的代碼在常見的場景中分支？

也許你可以重新安排你的if-S。 if的實現實際上是依賴於編譯器的，很多編譯器都以一種直接的方式對待它。即：if - 普通 - else - 罕見（跳躍）。

然後嘗試以下操作：

for (i = 0; i < N; i++) { 
for (j = 0; j < N; j++) { 
    for (k = 0; k < N; k++) { 
    if (k != i && k != j) 
    { 
     ...(calculate a, b, c, d) 
     if (a*a + b*b + c*c >= d*d) 
     { 
     ... 
     } else 
     break; 
    } 
    } //k 
} //j 
} //i 

編輯：

當然，你可以進入彙編級別，以確保產生正確的代碼。

Answer 3

我會先看看你的calculate代碼，因爲這可能會讓所有這些分支問題陷入困境。有些抽樣會肯定發現。

但是，它看起來像你正在做的，對於每個i,j，線性搜索球內的第一個點。你可以有3個數組，每個X，Y和Z軸有一個數組，並且每個數組中的所有原始點的索引都按該軸的升序排列？這可能有利於最近鄰居搜索。此外，您可能可以使用in-cube測試，而不是使用球內測試，因爲您不是在尋找最近的點，而只是尋找附近的點。

Answer 4

你確定你確實需要第一個if語句嗎？即使它在k等於i或j時跳過一個計算，每次迭代檢查它的代價都很昂貴。另外，請記住，如果N不是常量，編譯器可能無法展開for循環。

儘管如果它是一個單元處理器，編譯器甚至可能嘗試矢量化循環。

如果for循環編譯正常循環迭代它可能是一個想法，使它們與零比較，而不是作爲遞減操作往往會爲你做比較，當它擊中零。

for (i = 0; i < N; i++) { 

...可以成爲...

for (i = N; i != 0; i--) { 

雖然，在「i」作爲索引或在計算的變量，你可能會得到性能下降，你將獲得緩存未命中。