优化n体模拟
优化n体模拟
提问于 2019-12-17 21:06:03
我试图优化n-body算法，我看到了最昂贵的函数是：
real3 bodyBodyInteraction(real iPosx, real iPosy, real iPosz,
real jPosx, real jPosy, real jPosz, real jMass)
{
real rx, ry, rz;
rx = jPosx - iPosx;
ry = jPosy - iPosy;
rz = jPosz - iPosz;
real distSqr = rx*rx+ry*ry+rz*rz;
distSqr += SOFTENING_SQUARED;
real s = jMass / POW(distSqr,3.0/2.0); //very expensive
real3 f;
f.x = rx * s;
f.y = ry * s;
f.z = rz * s;
return f;
}使用perf记录，我可以看到除法是最昂贵的指令，这个指令具有O(n^2)的复杂性，但我不知道如何优化它。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-12-17 21:12:49
转换
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)转到
for(int i=0; i<N;i++)
for(int j=i+1;j<N;j++)重组以利用SIMD运营商，这可以使您的吞吐量翻两番。
使用OpenMP将循环并行化，或者跨CPU并行化，或者将循环卸载到GPU (OpenMP 4.5+)。
了解Barnes-Hut算法，它将粒子分组以实现O(N log N)复杂性(从O(N^2)降下来)。
Stack Overflow用户
发布于 2019-12-17 23:59:41
这对SIMD来说是个不错的选择。值得注意的是：
real s = jMass / POW(distSqr,3.0/2.0);如果你否定权力：(移除一个除法)，则可以将其重新分解到其中。
real s = jMass * POW(distSqr, -3.0/2.0);现在值得注意的是，您可以在这里完全删除对pow的调用，因为您处理的是一个非常简单的指数。所以..。
real s = jMass * std::sqrt(distSqr) / (distSqr * distSqr);如果你知道你的权力法则，你可以在这里做一个额外的重构步骤：
real s = jMass / (std::sqrt(distSqr) * distSqr);如果幸运的话，您的编译器应该已经在为您执行此转换了(您通常需要-O2和-ffast-数学)。示例：https://godbolt.org/z/8YqFYA
之所以这样做很好，是因为现在您已经从代码中完全删除了cmath调用。这使得它很容易下降到类似simd，非常容易，如果你碰巧使用clang或gcc。例如：
#include <immintrin.h>
typedef __m256 real;
struct real3 { real x, y, z; };
// i had to make up a value
const __m256 SOFTENING_SQUARED = _mm256_set1_ps(1.23f);
real3 bodyBodyInteraction(real iPosx, real iPosy, real iPosz,
real jPosx, real jPosy, real jPosz, real jMass)
{
real rx, ry, rz;
rx = jPosx - iPosx;
ry = jPosy - iPosy;
rz = jPosz - iPosz;
real distSqr = rx*rx+ry*ry+rz*rz;
distSqr += SOFTENING_SQUARED;
real s = jMass / (_mm256_sqrt_ps(distSqr) * distSqr);
real3 f;
f.x = rx * s;
f.y = ry * s;
f.z = rz * s;
return f;
}在“哥德波特”中：
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59382071
复制相关文章
相似问题
腾讯云开发者
