x86汇编中的高效复杂算法

Question

考虑以下程序:

for i=1 to 10000000 do
  z <- z*z + c

在哪里z和c是复杂的数字.

使用x87 vs SSE和单对双精度算法,该程序的高效x86汇编程序实现是什么？

编辑我知道我可以用另一种语言编写这个并信任编译器为我生成最佳的机器代码,但我这样做是为了学习如何自己编写最佳的x86汇编程序.我已经查看了生成的代码gcc -O2,我的猜测是有很大的改进空间,但我不够熟练自己编写最佳的x86汇编程序,所以我在这里寻求帮助.

Answer 1

看看你最喜欢的编译器的反汇编。如果您希望对zand 的几个值执行此计算c（例如计算 mandelbrot 图像），我建议您一次处理四个值并将它们放在 SSE 寄存器中。如果您查看 Paul R's answer 中的代码，您可以一次对四个值进行所有这些计算：

__m128 z_im, z_re, c_im, c_re; //Four z and c values packed
__m128 re = _mm_sub_ps(_mm_mul_ps(z_re, z_re), _mm_mul_ps(z_im, z_im));
__m128 im = _mm_mul_ps(z_re, z_im);
im = _mm_add_ps(im, im); // Multiply by two
z_re = _mm_add_ps(re, c_re);
z_im = _mm_add_ps(im, c_im);

Answer 2

您不需要在汇编程序本身中执行此操作- 您可以通过内在函数使用SSE来实现高效实现,尤其是在您可以使用单精度的情况下.

temp.re = z.re * z.re - z.im * z.im;
temp.im = 2.0 * z.re * z.im;
z.re = temp.re + c.re;
z.im = temp.im + c.im;

如果适当地改变输入向量,则可以在一条指令(_mm_mul_ps)中获得所有乘法,并在第二条指令(_mm_hadd_ps)中添加.

如果你需要双精度,那么同样的一般原则适用,但你需要两个乘法和两个水平加法.

请注意,大多数现代x86 CPU都有两个标量FPU,因此SSE的双精度优势可能不值得 - 单精度肯定是一个胜利.

这是使用SSE的初始工作实现 - 我认为现在调试较少 - 性能并不比使用gcc -O3编译的标量代码好很多,因为gcc在为此生成SSE代码方面做得非常好:

static Complex loop_simd(const Complex z0, const Complex c, const int n)
{
    __m128 vz = _mm_set_ps(z0.im, z0.re, z0.im, z0.re);
    const __m128 vc = _mm_set_ps(0.0f, 0.0f, c.im, c.re);
    const __m128 vs = _mm_set_ps(0.0f, 0.0f, -0.0f, 0.0f);
    Complex z[2];
    int i;

    for (i = 0; i < n; ++i)
    {
        __m128 vtemp;

        vtemp = _mm_shuffle_ps(vz, vz, 0x16); // temp = { z.re, z.im, z.im, z.re }
        vtemp = _mm_xor_ps(vtemp, vs);        // temp = { z.re, -z.im, z.im, z.re }
        vtemp = _mm_mul_ps(vtemp, vz);        // temp = { z.re * z.re, - z.im * z.im, z.re * z.im, z.im * z.re }
        vtemp = _mm_hadd_ps(vtemp, vtemp);    // temp = { z.re * z.re - z.im * z.im, 2 * z.re * z.im, ... }
        vz = _mm_add_ps(vtemp, vc);           // temp = { z.re * z.re - z.im * z.im + c.re, 2 * z.re * z.im + c.im, ... }
    }
    _mm_storeu_ps(&z[0].re, vz);
    return z[0];
}

请注意,内部循环只有6个SSE指令(它应该是5)+循环本身的一点管家:

L4:
    movaps  %xmm0, %xmm1
    shufps  $22, %xmm0, %xmm1
    xorps   %xmm3, %xmm1
    mulps   %xmm1, %xmm0
    haddps  %xmm0, %xmm0
    addps   %xmm2, %xmm0
    incl    %eax
    cmpl    %edi, %eax
    jne L4
L2: