Ассоциативность дает нам параллелизуемость. Но что дает коммутативность?

Ответ 1

Некоторые архитектуры, x86, являющиеся ярким примером, имеют инструкции, в которых одним из источников является также пункт назначения. Если вам по-прежнему требуется исходное значение адресата после операции, вам потребуется дополнительная инструкция для его копирования в другой регистр.

Коммутативные операции дают вам (или компилятору) выбор того, какой операнд заменяется на результат. Например, компиляция (с gcc 5.3 -O3 для соглашения о вызове Linux x86-64):

// 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 с местом назначения памяти отстой: он должен делать чтение-изменение-запись.) Коммутативные операции дают больше возможностей для этого.

x86 avx расширение (в Sandybridge, Jan 2011) добавили неразрушающие версии каждой существующей инструкции, которая использовала векторные регистры (одинаковые коды операций, но с многобайтовым префиксом VEX, заменяющим все предыдущие префиксы и escape-байты). Другие расширения набора инструкций (например, BMI/BMI2) также используют схему кодирования VEX для введения 3-операндовых неразрушающих целых инструкций, таких как PEXT r32a, r32b, r/m32: Параллельный извлечение бит из r32b с использованием маски в r/m32. Результат записывается в r32a.

AVX также расширил векторы до 256b и добавил несколько новых инструкций. Это, к сожалению, почти не повсеместно, и даже процессоры Skylake Pentium/Celeron не поддерживают его. Это будет долгое время, прежде чем безопасно отправлять двоичные файлы, которые предполагают поддержку 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

Ответ 2

Вот более абстрактный ответ с меньшим акцентом на уровне инструкции parallelism и больше на уровне нитей parallelism.

Общей целью в parallelism является сокращение информации. Простым примером является точечный продукт двух массивов

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

Если операция ассоциативна, мы можем каждый поток рассчитать частичную сумму. Тогда окончательная сумма представляет собой сумму каждой частичной суммы.

Если операция коммутативна, окончательная сумма может быть выполнена в любом порядке. В противном случае частичные суммы должны быть суммированы по порядку.

Одна из проблем заключается в том, что мы не можем иметь несколько потоков, записывающих окончательную сумму, в то же время в противном случае она создает условие гонки. Поэтому, когда один поток записывает в итоговую сумму, остальные должны ждать. Таким образом, суммирование в любом порядке может быть более эффективным, потому что часто бывает трудно выполнить каждую нить в порядке.

Выберем пример. Пусть говорят, что есть два потока и, следовательно, две частичные суммы.

Если операция коммутативна, мы могли бы иметь этот случай

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

Однако, если операция не коммутирует, нам нужно будет делать

thread2 finishes its partial sum
thread2 waits for thread1 to write to sum
thread1 finishes its partial sum
sum += thread1 partial sum
thread2 waits for thread1 to finish writing to sum    
thread1 finishes writing to sum   
sum += thread2 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()).

Например, если бы у нас было четыре потока, мы могли бы сделать сокращение на три последовательных этапа

• вычислять четыре частичные суммы параллельно: s1, s2, s3, s4
• вычислять параллельно: s5 = s1 + s2 с thread1 и s6 = s3 + s4 с thread2
• вычислить сумму = s5 + s6 с помощью thread1

Это одно преимущество использования предложения reduction, так как это черный ящик, он может уменьшить количество шагов log2(omp_get_num_threads()). OpenMP 4.0 позволяет определять пользовательские сокращения. Но тем не менее он все же предполагает, что операции являются коммутативными. Так что это не хорошо для, например, цепное матричное умножение. Я не знаю, как легко с OpenMP сделать сокращение в шагах log2(omp_get_num_threads()), когда операции не коммутируют.