微软加速器比C#串行实现慢

Question

我用C#在空闲时间写了一个有趣的2D N体模拟程序。串行实现时，它表现良好，帧率高达1000个实体，但超过这个数量就开始出现滞后问题。

我修改了算法，将位置和速度更新分开进行，并在CPU的不同核心上运行，发现效果略有提升。

需要注意的是，大部分时间都用于数学计算，绘制场景所需的时间很少。

我刚刚下载了Microsoft Accelerator V2库，并从头开始重写代码。虽然功能还是一样的，但是速度慢得多了！之前可以流畅运行近1000个点，现在只能运行10个点。

这里是我的代码：点击此处。由于这是我第一次使用Accelerator，因此很可能出现了错误。

这个类名叫做Test，因为这是我的第一个测试。构造函数只是简单地创建了长度为n的数组，包括实体的x和y位置、它们的x和y速度以及它们的质量。dec只是一个阻尼系数，使得舍入误差导致系统崩溃而不是爆炸；g是万有引力常数，我仅仅将其设置为1.0f。

Tick()函数执行所有更新操作。首先考虑任何给定点的所有点，找到半径，构造一个指向其他点方向的单位向量，将该单位向量按阻尼系数和万有引力常数缩放，然后将其总和作为x和y速度更新到该点。

然后我更新所有速度和位置，并转换回float[]数组。

正如我所说，代码在技术上确实是有效的。结果与串行实现完全相同，除了大幅降低的速度。

你有什么想法可能我做错了什么吗？

我感觉问题可能出在第85和86行——我在求点i的x和y速度更新时累加起来，存储到我的float数组中，这意味着我需要调用Target.ToArray1D()[0]来获取总和。我之所以这样做是因为我希望先获得所有点的更新，然后更新点，再根据速度变化应用位置变化。

也就是说，我不希望发生这样的情况：在时间t+1，我将点0与其他点一起更新到时间t，然后下次更新时再更新点1，而点0使用新的t+1。如果这样讲有意义的话。

public void Tick()
{
    FPA fxPos = new FPA(xPos);
    FPA fyPos = new FPA(yPos);
    FPA fxVel = new FPA(xVel);
    FPA fyVel = new FPA(yVel);
    FPA fMass = new FPA(mass);

    float[] xUpd = new float[n]; // x-update for velocity
    float[] yUpd = new float[n]; // y-update for velocity

    for (int i = 0; i < n; i++)
    {
        // x- and y-pos about point i:
        FPA ixPos = PA.Subtract(fxPos, xPos[i]);
        FPA iyPos = PA.Subtract(fyPos, yPos[i]);

        // radius from point i:
        FPA iRad = PA.Sqrt(PA.Add(PA.Multiply(ixPos, ixPos), PA.Multiply(iyPos, iyPos)));

        // x- and y-pos are now unit vectors:
        ixPos = PA.Divide(ixPos, iRad);
        iyPos = PA.Divide(iyPos, iRad);

        // vectors are now scaled by mass:
        ixPos = PA.Multiply(fMass, ixPos);
        iyPos = PA.Multiply(fMass, iyPos);

        // vectors are now scaled by G and deceleration:
        ixPos = PA.Multiply(dec * g, ixPos);
        iyPos = PA.Multiply(dec * g, iyPos);

        // sum to get ith update value:
        xUpd[i] = target.ToArray1D(PA.Sum(ixPos))[0];
        yUpd[i] = target.ToArray1D(PA.Sum(iyPos))[0];
    }

    FPA fxUpd = new FPA(xUpd);
    FPA fyUpd = new FPA(yUpd);

    // update velocities:
    fxVel = PA.Add(fxUpd, fxVel);
    fyVel = PA.Add(fyUpd, fyVel);

    // update positions:
    fxPos = PA.Add(fxVel, fxPos);
    fyPos = PA.Add(fyVel, fyPos);

    xPos = target.ToArray1D(fxPos);
    yPos = target.ToArray1D(fyPos);
    xVel = target.ToArray1D(fxVel);
    yVel = target.ToArray1D(fyVel);
}

- Ozzah

---

请注意，代码的外部链接很少被查看。请尽量压缩您的问题和代码，以便所有内容都适合在SO上。如果文本和代码变得太大，则需要重新考虑您的问题。 - Macke

除了已发布的解决方案，另一个选择是探索替代算法。对于二维N-Body问题，您可以尝试使用四叉树数据结构来加速力计算。这将时间复杂度从O(N^2)降至O(N log N)。 - Mike Bailey

Answer 1

您应该重新考虑使用并行计算的逻辑。您仍然一次只处理一个点。为了利用库的优势，您应该考虑对整个元素数组执行一个操作。

- Dmitrii Dovgopolyi

---

我的串行实现使用了一个双重循环，因为n-body是O(n²)。使用并行库，可以使用单个循环。我认为这种情况下没有其他方法了？ - Ozzah