Проблемы с производительностью #pragma omp atomic с OMP_NUM_THREADS = 1

Question

Я заметил неожиданное (для меня!) Поведение кода openmp, который я пишу. Структура кода заключается в следующем:

#pragma omp parallel for 
for(int i=0;i<N;i++){ 
// lots of calculations that produce 3 integers i1,i2,i3 and 3 doubles d1,d2,d3 
#pragma omp atomic 
J1[i1] += d1; 
#pragma omp atomic 
J2[i2] += d2; 
#pragma omp atomic 
J3[i3] += d3; 
} 

Я составил три различные версии этого кода:

1) с OpenMP (-fopenmp)

2) без OpenMP

3) с openmp, но без 3-х атомных операций (точно так же, как испытание, поскольку необходимы атомные операции)

Когда я запускаю версию 1) с переменной окружения O MP_NUM_THREADS = 1, я наблюдаю значительное замедление относительно версии 2); в то время как версия 3) работает так же быстро, как версия 2).

Я хотел бы знать причину такого поведения (почему атомные операции замедляют работу кода даже при однократном исключении ?!), и если можно скомпилировать/переписать код таким образом, что версия 1) работает так же быстро, как версия 2).

В конце вопроса я добавляю рабочий пример, который показывает вышеупомянутое поведение. Я составил 1) с:

g++ -fopenmp -o toy_code toy_code.cpp -std=c++11 -O3 

2) с:

g++ -o toy_code_NO_OMP toy_code.cpp -std=c++11 -O3 

и 3) с:

g++ -fopenmp -o toy_code_NO_ATOMIC toy_code_NO_ATOMIC.cpp -std=c++11 -O3 

версия компилятора GCC версии 5.3.1 20160519 (Debian 5.3.1-20). Время выполнения 3-х версий:

1) 1 мин 24 сек

2) 51 сек

3) 51 сек

Заранее спасибо за любые советы!

// toy_code.cpp 
#include <stdio.h> 
#include <iostream> 
#include <stdlib.h> 
#include <cmath> 
#include <omp.h> 
#define Np 1000000 
#define N 1000 

int main(){ 
     double* Xp, *Yp, *J,*Jb; 
     Xp = new double[Np]; 
     Yp = new double[Np]; 
     J = new double [N*N]; 
     Jb = new double [N*N]; 

     for(int i=0;i<N*N;i++){ 
      J[i]=0.0; 
      Jb[i]=0.0; 
     } 

     for(int i=0;i<Np;i++){ 
      Xp[i] = rand()*1.0/RAND_MAX - 0.5; 
      Yp[i] = rand()*1.0/RAND_MAX - 0.5; 
     } 

     for(int n=0; n<2000; n++){ 
     #pragma omp parallel for 
     for(int p=0;p<Np;p++){ 
      double rx = (Xp[p]+0.5)*(N-1); 
      double ry = (Yp[p]+0.5)*(N-1); 
      int xindex = (int)floor(rx+0.5); 
      int yindex = (int)floor(ry+0.5); 
      int k; 
      k=xindex*N+yindex; 

      #pragma omp atomic 
      J[k]+=1; 
      #pragma omp atomic 
      Jb[k]+=1; 
     } 
     } 

     delete[] Xp; 
     delete[] Yp; 
     delete[] J; 
     delete[] Jb; 

return 0; 
} 

Answer 1

Если включить OpenMP, НКУ должен генерировать различный код, который работает для любого числа потоков, которые известны только во время выполнения.

В этом конкретном случае обратите внимание на вывод gcc -S (слегка укороченный листами).

Без OpenMP:

.loc 1 38 0 discriminator 2 # Line 38 is J[k]+=1; 
movsd 8(%rsp), %xmm1 
cvttsd2si %xmm0, %edx 
cvttsd2si %xmm1, %eax 
movsd .LC3(%rip), %xmm0 
imull $1000, %eax, %eax 
addl %edx, %eax 
cltq 
salq $3, %rax 
leaq 0(%r13,%rax), %rdx 
.loc 1 40 0 discriminator 2 # Line 40 is Jb[k]+=1; 
addq %r12, %rax 
.loc 1 29 0 discriminator 2 
cmpq $8000000, %r15 
.loc 1 38 0 discriminator 2 
addsd (%rdx), %xmm0 
movsd %xmm0, (%rdx) 
.loc 1 40 0 discriminator 2 
movsd .LC3(%rip), %xmm0 
addsd (%rax), %xmm0 
movsd %xmm0, (%rax) 

Петля разматывается делает это довольно сложно.

С -fopenmp:

movsd (%rsp), %xmm2 
cvttsd2si %xmm0, %eax 
cvttsd2si %xmm2, %ecx 
imull $1000, %ecx, %ecx 
addl %eax, %ecx 
movslq %ecx, %rcx 
salq $3, %rcx 
movq %rcx, %rsi 
addq 16(%rbp), %rsi 
movq (%rsi), %rdx 
movsd 8(%rsp), %xmm1 
jmp .L4 
movq %rax, %rdx 
movq %rdx, (%rsp) 
movq %rdx, %rax 
movsd (%rsp), %xmm3 
addsd %xmm1, %xmm3 
movq %xmm3, %rdi 
lock cmpxchgq %rdi, (%rsi) 
cmpq %rax, %rdx 
jne .L9 
.loc 1 40 0 
addq 24(%rbp), %rcx 
movq (%rcx), %rdx 
jmp .L5 
.p2align 4,,10 
.p2align 3 
movq %rax, %rdx 
movq %rdx, (%rsp) 
movq %rdx, %rax 
movsd (%rsp), %xmm4 
addsd %xmm1, %xmm4 
movq %xmm4, %rsi 
lock cmpxchgq %rsi, (%rcx) 
cmpq %rax, %rdx 
jne .L10 
addq $8, %r12 
cmpq %r12, %rbx 
jne .L6 

Я не буду пытаться объяснить или понять все подробности того, что здесь происходит, но то не нужно для сообщения: компилятор должен использовать различные атомные инструкции которые, вероятно, более дорогостоящие, особенно lock cmpxchgq.

Помимо этой фундаментальной проблемы, OpenMP может испортить оптимизатор любым возможным способом, например. препятствовать разворачиванию. Я также видел любопытный случай, когда компилятор Intel фактически генерирует более эффективный серийный код для цикла OpenMP.

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