c - SIMD 值得吗？有更好的选择吗？

Question

我有一些代码运行得相当好，但我想让它运行得更好。我遇到的主要问题是它需要有一个嵌套的 for 循环。外层用于迭代(必须连续发生)，内层用于考虑中的每个点粒子。我知道对于外部的我无能为力，但我想知道是否有一种优化方法，例如:

    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，虽然我找不到太多相关信息，而且我不完全确定正确提取和打包数据所需的处理是否值得执行一半的指令，因为显然一次只能使用两个 double 。

我尝试使用 shm 和 pthread_barrier 将它分解为多个线程(以同步不同阶段，上面的代码就是其中之一)，但它只会让速度变慢。

我当前的代码执行得非常快；它大约是每 10M 粒子*迭代一秒，从 gprof 可以看出，我 30% 的时间都花在了这个函数上(5000 次调用；PART_COUNT=8192 个粒子花费了 1.8 秒)。我不担心小的、恒定时间的事情，只是上次 512K 粒子 * 50K 迭代 * 1000 次实验花了一个多星期。

我想我的问题是，是否有任何方法可以比循环处理这些长 vector 更有效。感觉应该有，就是找不到。

Answer 1

我不确定 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 也会对此有所帮助。

---

由于您正在按顺序访问粒子，因此您可以尝试预取(例如 GCC 上的 __builtin_prefetch)一些粒子提前以减少缓存未命中。预取盒子有点困难，因为您以不可预测的顺序访问它们；你可以尝试类似的东西

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

---

我刚刚注意到的最后一个 - 如果 box::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，都可以完成。