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值得吗？有更好的选择吗？

回答

相关问题