c - C 代码的优化

Question

我正在尝试优化 C 代码，特别是一个关键循环，它几乎占据了总执行时间的 99.99%。这是该循环:

#pragma omp parallel shared(NTOT,i) num_threads(4)
{
  # pragma omp for private(dx,dy,d,j,V,E,F,G) reduction(+:dU) nowait
  for(j = 1; j <= NTOT; j++){
    if(j == i) continue;
    dx = (X[j][0]-X[i][0])*a;
    dy = (X[j][1]-X[i][1])*a;
    d = sqrt(dx*dx+dy*dy);
    V = (D/(d*d*d))*(dS[0]*spin[2*j-2]+dS[1]*spin[2*j-1]);
    E = dS[0]*dx+dS[1]*dy;
    F = spin[2*j-2]*dx+spin[2*j-1]*dy;
    G = -3*(D/(d*d*d*d*d))*E*F;
    dU += (V+G);
  }
}

所有变量都是局部变量。对于 NTOT=3600，循环需要 0.7 秒，这是一个很大的时间，特别是当我必须在整个程序中执行 500,000 次时，导致这个循环花费了 97 个小时。我的问题是这个循环中是否还有其他需要优化的地方？

我的计算机的处理器是 Intel core i5，具有 4 个 CPU(4X1600Mhz) 和 3072K L3 缓存。

Answer 1

针对硬件或软件进行优化？

软:

摆脱耗时的异常，例如除以零:

d = sqrt(dx*dx+dy*dy   + 0.001f   );
V = (D/(d*d*d))*(dS[0]*spin[2*j-2]+dS[1]*spin[2*j-1]);

您还可以尝试 John Carmack、Terje Mathisen 和 Gary Tarolli 的 "Fast inverse square root"对于

   D/(d*d*d)

部分。你也摆脱了 split 。

  float qrsqrt=q_rsqrt(dx*dx+dy*dy + easing);
  qrsqrt=qrsqrt*qrsqrt*qrsqrt * D;

牺牲一些精度。

还有另一个部门需要取消:

(D/(d*d*d*d*d))

比如

 qrsqrt_to_the_power2 * qrsqrt_to_the_power3 * D

这是快速逆 sqrt:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what ?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

为了克服大数组的非缓存行为，您可以在较小的补丁/组中进行计算，特别是当它是多对多 O(N*N) 算法时。如:

get 256 particles.
compute 256 x 256 relations.
save 256 results on variables.

select another 256 particles as target(saving the first 256 group in place)
do same calculations but this time 1st group vs 2nd group.

save first 256 results again.

move to 3rd group

repeat.

do same until all particles are versused against first 256 particles.

Now get second group of 256. 

iterate until all 256's are complete.

您的CPU有大缓存，因此您可以直接尝试32k粒子与32k粒子。但 L1 可能不大，所以如果我是你，我会坚持使用 512 与 512(或 500 与 500 以避免缓存行 ---> 这将取决于架构)。

困难:

SSE、AVX、GPGPU、FPGA......

正如 @harold 所评论的，SSE 应该是比较的起点，并且您应该通过 4 包装 vector 指令进行矢量化或至少并行化，这些指令具有最佳内存获取能力和流水线的优势。当您需要 3 倍到 10 倍的性能时(在使用所有核心的 SSE 版本之上)，您将需要一个符合 opencl/cuda 的 GPU(与 i5 同等价格)和 opencl(或 cuda)api，或者您也可以学习 opengl，但似乎更难(也许 directx 更容易)。

尝试 SSE 是最简单的，应该比我上面提到的快速逆算法快 3 倍。对于数千个粒子，同等价格的 GPU 应该至少提供 3 倍的 SSE。当你充分优化它时(使其更少依赖于主内存)，对于这种类型的算法，超过 100k 粒子，整个 GPU 可以实现 cpu 单核性能的 80 倍。 Opencl 提供了地址缓存来保存数组的能力。因此您可以在其中使用 TB/秒的带宽。