math - 关联性使我们具有可并行性。但是可交换性给什么呢？

Question

亚历山大·斯蒂芬诺夫（Alexander Stepanov）在他的brilliant lectures at A9（强烈建议）中指出，关联属性为我们提供了可并行性-如今，编译器，CPU和程序员本身可以利用的极其有用和重要的特征：

// expressions in parentheses can be done in parallel
// because matrix multiplication is associative
Matrix X = (A * B) * (C * D);

但是，交换性给我们什么（如果有的话）呢？重新排序？乱序执行？

Answer 1

一些体系结构（x86是一个很好的例子）在其中一个来源也是目的地的地方有指令。如果操作后仍然需要目标的原始值，则需要一条额外的指令将其复制到另一个寄存器。

交换操作使您（或编译器）可以选择将哪个操作数替换为结果。因此，例如，compiling (with gcc 5.3 -O3 for x86-64 Linux calling convention）：

// FP: a,b,c in xmm0,1,2.  return value goes in xmm0
// Intel syntax ASM is  op  dest, src
// sd means Scalar Double (as opposed to packed vector, or to single-precision)
double comm(double a, double b, double c) { return (c+a) * (c+b); }
    addsd   xmm0, xmm2
    addsd   xmm1, xmm2
    mulsd   xmm0, xmm1
    ret
double hard(double a, double b, double c) { return (c-a) * (c-b); }
    movapd  xmm3, xmm2    ; reg-reg copy: move Aligned Packed Double
    subsd   xmm2, xmm1
    subsd   xmm3, xmm0
    movapd  xmm0, xmm3
    mulsd   xmm0, xmm2
    ret
double easy(double a, double b, double c) { return (a-c) * (b-c); }
    subsd   xmm0, xmm2
    subsd   xmm1, xmm2
    mulsd   xmm0, xmm1
    ret

x86还允许将内存操作数用作源，因此您可以将负载折叠到ALU操作中，例如 addsd xmm0, [my_constant]。 （将ALU op与内存目标一起使用很烂：它必须执行read-modify-write。）交换操作为执行此操作提供了更大的空间。

x86的 avx扩展名（在Sandybridge，2011年1月）为使用矢量寄存器的所有现有指令添加了非破坏性版本（相同的操作码，但使用多字节VEX前缀替换了所有先前的前缀和转义字节）。其他指令集扩展（例如 BMI/BMI2）也使用VEX编码方案来引入3个操作数的非破坏性整数指令，例如 PEXT r32a, r32b, r/m32： Parallel extract of bits from r32b using mask in r/m32. Result is written to r32a。

AVX还将向量扩展到256b，并增加了一些新指令。不幸的是，它无处不在，甚至Skylake Pentium / Celeron CPU也不支持它。要安全地运送假定具有AVX支持的二进制文件还需要很长时间。 :(

在上面的Godbolt链接中将 -march=native添加到编译选项中，可以看到AVX允许编译器甚至对 hard()使用3条指令。 （godbolt在Haswell服务器上运行，因此包括AVX2和BMI2）：

double hard(double a, double b, double c) { return (c-a) * (c-b); }
        vsubsd  xmm0, xmm2, xmm0
        vsubsd  xmm1, xmm2, xmm1
        vmulsd  xmm0, xmm0, xmm1
        ret