关联性使我们具有可并行性.但是,交换性给了什么？

Question

亚历山大·斯捷潘诺夫在A9的一篇精彩讲座(强烈推荐,顺便说一句)中指出,关联属性为我们提供了可并行性 - 这些日子是编译器,CPU和程序员自己可以利用的非常有用和重要的特性:

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

但是,交换性财产给我们带来了什么？重新排序？乱序执行？

Answer 1

一些架构,x86是一个主要的例子,有一些指令,其中一个源也是目的地.如果在操作后仍需要目标的原始值,则需要额外的指令将其复制到另一个寄存器.

交换操作使您(或编译器)可以选择将哪个操作数替换为结果.例如,编译(gcc 5.3 -O3用于x86-64 Linux调用约定):

// 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操作很糟糕:它必须执行读取 - 修改 - 写入.)交换操作为执行此操作提供了更多空间.

x86的avx扩展(在Sandybridge,2011年1月)添加了使用向量寄存器的每个现有指令的非破坏性版本(相同的操作码但具有多字节VEX前缀替换所有先前的前缀和转义字节).其他指令集扩展(如BMI/BMI2)也使用VEX编码方案引入3操作数非破坏性整数指令,例如PEXT r32a, r32b, r/m32: 使用r/m32中的掩码从r32b并行提取位.结果写入r32a.

AVX还将向量扩展到256b并添加了一些新指令.不幸的是,它无处不在,甚至Skylake Pentium/Celeron CPU也不支持它.在发布假定AVX支持的二进制文件之前,将会很长时间.:(

添加-march=native到上面的godbolt链接中的编译选项,看看AVX让编译器甚至只使用3条指令hard().(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

Answer 2

这是一个更抽象的答案,不太强调指令级并行性,更多的是线程级并行性.

并行性的一个共同目标是减少信息.一个简单的例子是两个数组的点积

for(int i=0; i<N; i++) sum += x[i]*[y];

如果操作是关联的,那么我们可以让每个线程计算一个部分和.然后,最后的总和是每个部分和的总和.

如果操作是可交换的,则可以按任何顺序完成最终总和.否则,部分总和必须按顺序求和.

一个问题是我们不能让多个线程同时写入最终总和,否则会产生竞争条件.因此,当一个线程写入最终总和时,其他线程必须等待.因此,以任何顺序求和都可以更有效,因为通常很难让每个线程按顺序完成.

我们来选一个例子吧.假设有两个线程,因此有两个部分和.

如果操作是可交换的,我们可能会遇到这种情况

thread2 finishes its partial sum
sum += thread2's partial sum
thread2 finishes writing to sum   
thread1 finishes its partial sum
sum += thread1's partial sum

但是,如果操作不通勤,我们就必须这样做

thread2 finishes its partial sum
thread2 waits for thread1 to write to sum
thread1 finishes its partial sum
sum += thread1's partial sum
thread2 waits for thread1 to finish writing to sum    
thread1 finishes writing to sum   
sum += thread2's partial sum

以下是OpenMP的点积示例

#pragma omp parallel for reduction(+: sum)
for(int i=0; i<N; i++) sum += x[i]*[y];

该reduction条款假定操作(+在这种情况下)是可交换的.大多数人认为这是理所当然的.

如果操作不是可交换的,我们就必须做这样的事情

float sum = 0;
#pragma omp parallel
{
    float sum_partial = 0 
    #pragma omp for schedule(static) nowait
    for(int i=0; i<N; i++) sum_partial += x[i]*[y];
    #pragma omp for schedule(static) ordered
    for(int i=0; i<omp_get_num_threads(); i++) {
        #pragma omp ordered
        sum += sum_partial;
    }
}

该nowait子句告诉OpenMP不要等待每个部分和完成.该ordered子句告诉OpenMP只sum按增加的线程数顺序写入.

该方法线性地进行最终求和.但是,它可以log2(omp_get_num_threads())分步进行.

例如,如果我们有四个线程,我们可以在三个连续步骤中进行减少

1. 并行计算四个部分和: s1, s2, s3, s4
2. 并行计算:s5 = s1 + s2使用thread1和s6 = s3 + s4thread2
3. s5 + s6用thread1 计算sum =

这是使用该reduction子句的一个优点,因为它是一个黑盒子,它可以减少log2(omp_get_num_threads())步骤.OpenMP 4.0允许定义自定义缩减.但是,它仍然假设操作是可交换的.所以它对于例如链矩阵乘法来说并不好.我不知道OpenMP log2(omp_get_num_threads())在操作不通勤时减少步骤的简单方法.