SIMD值得嗎？有更好的選擇嗎？

我有一些代碼運行得很好，但我想讓它運行得更好。我對它的主要問題是它需要嵌套for循環。外層是用於迭代（它必須連續發生），內層是針對每個點粒子的考慮。我知道有沒有什麼我可以做外一個，但我不知道是否有優化類似的方式：SIMD值得嗎？有更好的選擇嗎？

void collide(particle particles[], box boxes[], 
     double boxShiftX, double boxShiftY) {/*{{{*/ 
      int i; 
      double nX; 
      double nY; 
      int boxnum; 
      for(i=0;i<PART_COUNT;i++) { 
        boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+ 
         BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
         //copied and pasted the macro which is why it's kinda odd looking 

        particles[i].vX -= boxes[boxnum].mX; 
        particles[i].vY -= boxes[boxnum].mY; 
        if(boxes[boxnum].rotDir == 1) { 
          nX = particles[i].vX*Wxx+particles[i].vY*Wxy; 
          nY = particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } else { //to make it randomly pick a rot. direction 
          nX = particles[i].vX*Wxx-particles[i].vY*Wxy; 
          nY = -particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } 
        particles[i].vX = nX + boxes[boxnum].mX; 
        particles[i].vY = nY + boxes[boxnum].mY; 
      } 
    }/*}}}*/

我已經看了SIMD，雖然我不能找到太多有關它並且我不完全確定，正確提取和打包數據所需的處理值得獲得執行一半指令的收益，因爲顯然一次只能使用兩個雙打。

我試圖用shm和pthread_barrier將它分解成多個線程（同步上面的代碼是不同的階段），但它讓它變慢了。

我目前的代碼確實很快;每10M粒子*次迭代次數爲1秒，從gprof中我可以看出，30％的時間僅用於該函數（5000次調用; PART_COUNT = 8192次粒子耗時1.8秒）。我並不擔心小的恆定時間的事情，只是512K粒子* 50K迭代* 1000次實驗上次超過一週。

我想我的問題是，如果有任何處理這些長矢量的方法比循環遍歷它們更有效。我覺得應該有，但我找不到它。

來源

2010-07-18 zebediah49

我不確定多少SIMD會受益;內部循環非常小且簡單，所以我猜測（只是通過查看）你可能比其他任何東西都更有內存限制。考慮到這一點，我想嘗試重寫循環的主要部分不碰粒子陣列比需要更多：

const double temp_vX = particles[i].vX - boxes[boxnum].mX; 
const double temp_vY = particles[i].vY - boxes[boxnum].mY; 

if(boxes[boxnum].rotDir == 1) 
{ 
    nX = temp_vX*Wxx+temp_vY*Wxy; 
    nY = temp_vX*Wyx+temp_vY*Wyy; 
} 
else 
{ 
    //to make it randomly pick a rot. direction 
    nX = temp_vX*Wxx-temp_vY*Wxy; 
    nY = -temp_vX*Wyx+temp_vY*Wyy; 
} 
particles[i].vX = nX; 
particles[i].vY = nY;

這有沒有做額外加入在最後的小潛在副作用。

另一個潛在的加速比。將顆粒陣列上使用__restrict，以便編譯器可以更好地優化寫入到速度。另外，如果Wxx等是全局變量，它們可能必須每次通過循環重新加載，而不是可能存儲在寄存器中;使用__restrict也會有幫助。

既然你訪問，以便顆粒，可以嘗試預取（例如__builtin_prefetch在GCC）未來幾顆粒，以減少高速緩存未命中。由於您以不可預知的順序訪問它們，因此預取盒子會有點困難;你可以嘗試像

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc... 
// prefetch boxes[nextBoxnum]

，我只注意到最後一個一個 - 如果盒子:: rotDir總是+/- 1.0，那麼你就可以消除這樣的內環比較分支：

const double rot = boxes[boxnum].rotDir; // always +/- 1.0 
nX =  particles[i].vX*Wxx + rot*particles[i].vY*Wxy; 
nY = rot*particles[i].vX*Wyx +  particles[i].vY*Wyy;

當然，分析的前比平時警告後適用。但我認爲所有這些都可能有所幫助，無論您是否切換到SIMD，都可以完成。

來源

2010-07-18 21:49:29 celion

感謝您接受我的回答。這些幫助有多少？ – celion 2010-07-21 19:48:03

您是否有足夠的分析來告訴您在該功能中花費的時間？

例如，你確定它不是你的divs和mods在boxnum計算中花費的時間嗎？有時編譯器無法發現可能的轉換/替代選擇，即使在人類（或至少知道BOX_SIZE和BWIDTH/BHEIGHT，我不知道的人）可能能夠做到的情況下。

這將是一個可惜花費大量的時間在SIMDifying代碼的錯誤有點...

這可能是值得研究的是，如果工作可以被強制到一些東西，可以工作，其他的事情有像IPP這樣的圖書館，它將做出關於如何最好地使用處理器的明智決定。

來源

2010-07-18 19:02:41

老實說，它可能是* div和mods，但不是;我還沒有找到一個可以告訴我的分析器。對於我目前的實驗，BOX_SIZE已經是1，並且你有一個好點：BWIDTH，BHEIGHT已經是兩個冪。你有建議更精細的分析器嗎？ – zebediah49 2010-07-18 19:05:20

我期望任何採樣分析器都能夠給你每行信息，當然編譯器優化使行匹配有點不準確。英特爾vTune將爲您提供比單個彙編程序指令更細緻的信息，因此，如果您覺得您想要查看的內容可能是順利通過的。個人而言，對於像這樣簡單（即小）的事情，我傾向於將代碼花費在大量運行上，然後利用它來查看需要花費的時間。 – 2010-07-18 22:02:00

((int)(particles[i].sX+boxShiftX))/BOX_SIZE

如果sX是一個int（不能說），那麼這很貴。在進入循環之前將boxShiftX/Y截斷爲int。

來源

2010-07-18 19:40:22

不幸的是，sX和boxShiftX都是雙打，並且它的要點是有效地隨機舍入（boxShiftX在[-.5，.5]範圍內） – zebediah49 2010-07-18 20:55:01

我不知道，當浮點數需要時我通常會去wtf截斷並取模。這是一個整數問題被認爲準確性混淆的標誌。一旦你到達那裏，通過縮放將浮點數轉換爲整數通常會帶來巨大的回報。這樣的代碼的最終結果往往是整數，也許是屏幕上的一個像素。整數結果應該有整數數學。對不起，我只是不知道你真的想要做些什麼來提高幫助。 – 2010-07-18 21:55:17

我有這套粒子，並將它們分類爲「盒子」。由於模擬的奇怪，盒子的位置必須在每個時間步驟周圍跳躍，這就是爲什麼會發生這種情況。 – zebediah49 2010-07-18 21:56:09

只是爲了記錄，還有libSIMDx86！

http://simdx86.sourceforge.net/Modules.html

（在編譯你也可以試試：gcc的-O3 -msse2或類似）。

來源

2010-07-19 08:33:21 cigit

你的算法有太多的內存，整數和分支指令有足夠的獨立觸發器從SIMD中獲利。管道將不斷停滯。

尋找一種更有效的隨機化方式將成爲列表的首選。然後，嘗試以float或int方式工作，但不能同時工作。重算條件爲算術，或至少作爲選擇操作。只有這樣，SIMD纔會成爲一個現實主張

來源

2013-05-27 13:26:27 mabraham

SIMD值得嗎？有更好的選擇嗎？

回答

相關問題