Ужасная производительность - простая проблема с накладными расходами, или есть программный недостаток?

Question

У меня есть то, что я понимаю как относительно простую конструкцию OpenMP. Проблема в том, что программа работает примерно на 100-300x быстрее с 1 потоком по сравнению с 2 потоками. 87% программы проводится в gomp_send_wait() и еще 9,5% в gomp_send_post.

Программа дает правильные результаты, но мне интересно, есть ли недостаток в коде, вызывающем некоторый конфликт ресурсов, или просто потому, что накладные расходы на создание потоков резко не стоят его для цикла цикла размер 4. p варьируется от 17 до 1000, в зависимости от размера молекулы, которую мы имитируем.

Мои номера относятся к наихудшему случаю, когда p равно 17 и размер куска 4. Производительность одинакова независимо от того, использую ли я статическое, динамическое или управляемое планирование. С p=150 и размером куска 75 программа по-прежнему на 75x100x медленнее, чем серийная.

... 
    double e_t_sum=0.0; 
    double e_in_sum=0.0; 

    int nthreads,tid; 

    #pragma omp parallel for schedule(static, 4) reduction(+ : e_t_sum, e_in_sum) shared(ee_t) private(tid, i, d_x, d_y, d_z, rr,) firstprivate(V_in, t_x, t_y, t_z) lastprivate(nthreads) 
    for (i = 0; i < p; i++){ 
     if (i != c){ 
      nthreads = omp_get_num_threads();    
      tid = omp_get_thread_num(); 

      d_x = V_in[i].x - t_x; 
      d_y = V_in[i].y - t_y; 
      d_z = V_in[i].z - t_z; 


      rr = d_x * d_x + d_y * d_y + d_z * d_z; 

      if (i < c){ 

       ee_t[i][c] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[i][c]; 
       e_in_sum += ee_in[i][c];  
      } 
      else{ 

       ee_t[c][i] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[c][i]; 
       e_in_sum += ee_in[c][i];  
      } 

      // if(pid==0){printf("e_t_sum[%d]: %f\n", tid, e_t_sum[tid]);} 

     } 
    }//end parallel for 


     e_t += e_t_sum; 
     e_t -= e_in_sum;    

... 

Answer 1

Я считаю, что вы должны попытаться двигаться все эти ветви (т.е. сослагательного наклонения) внутри цикла, и сделать это в двух отдельных петель, по одному для < я с, и один для I> с. Это очень пригодится даже для однопоточного кода, но это должно дать вам больше параллелизма, даже если, как вы сказали, накладные расходы на создание потоков могут быть больше, чем преимущества для небольших n.

Answer 2

Metiu это право. Вы не можете ожидать хорошей производительности из цикла, в котором есть условные операторы. Это просто плохое кодирование. Даже для скалярной производительности.

Ваш босс должен понимать, что OpenMP и распараллеливание вообще не являются магии. Чтобы получить хорошую производительность из параллельного кода, сначала необходимо оптимизировать базовый код для скалярной производительности.

Испытания не подлежат удалению. Цикл необходимо перестроить. И скалярная производительность также принесет пользу.

Answer 3

Вы, кажется, считаете, что это означает, что если вы запускаете серийный код в многозадачном режиме, он должен работать лучше. Это не данность. И это часто не так. Параллелирование цикла для работы в нескольких потоках или нескольких процессорах не всегда приводит к повышению производительности. В большинстве случаев необходима некоторая реструктуризация. В вашем случае код не является даже хорошим серийным кодом.

Любая книга по оптимизации последовательного кода имеет правило № 1 для циклов: удалите все условные операции. Стоимость тестов. Некоторые компиляторы (кстати, вы никогда не говорите, какой OS/компилятор/процессор вы используете .. это имеет значение) может попытаться оптимизировать условный код. Некоторые компиляторы (например, компилятор Sun's C) даже позволяют запускать программу в режиме «собирать», где она генерирует информацию профиля времени выполнения о том, как часто выполняются ветви условного выражения, а затем позволяет перекомпилировать в режиме, который использует собранные данные для оптимизации сгенерированного кода. (См. Параметр -xprofile)

Первое правило для оптимизации параллельного кода - это, в первую очередь, наилучшая последовательная оптимизация. Затем распараллелите петли.

Перемещая условные выражения за пределы цикла, и, как предполагает Мети, переписывание кода как двух отдельных циклов, вы даете оптимизатору лучший источник для работы. Серийный код работает лучше, а параллелизованный код неловко параллелен.

Тем не менее результаты могут различаться в зависимости от ОС/компилятора/платформы.

См Using OpenMP и Solaris Application Programming

Answer 4

Это выглядит как вопрос с реализацией OpenMP ГНУ компилятора. Попробуйте другой компилятор. У Intel есть компилятор Linux, который вы можете загрузить и попробовать здесь.

Еще одна вещь, которую я заметил, это то, что первые переменные, которые вам кажутся совершенно ненужными. Могут возникнуть значительные накладные расходы при создании частных копий массива V_in, которые могут быть вашей проблемой.

Я бы сказал, что это одна из двух проблем, которая является вашей проблемой.

Answer 5

Во-первых, попробуйте перекачивать кусок размером больше. Создание темы несет накладные расходы, и для каждой работы также требуется новая работа, и размер зерна должен быть достаточно большим, чтобы подавить это.

Дополнительная информация: Реализация GOMP редукции может быть очень низкой (предлагается данными вашего профиля), и она генерирует сообщения после каждого блока, а не накапливается в каждом потоке, а затем собирает их в конце. Попробуйте выделить e_t_sum и e_in_sum как массивы с nthreads элементами каждый и добавив в цикл цикл e_t_sum[tid], а затем перейдя через них, чтобы вычислить глобальную сумму после завершения параллельного цикла.

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

Другая возможность: Возможно, вы испытываете ложное совместное использование в своих обновлениях элементов ee_t. Обеспечьте выравнивание этого массива и попробуйте размеры блоков, кратные размеру вашей линии кэша. Один тонкий намек на эту патологию был бы частью петли, где i > c, занимая непропорционально длиннее, чем часть, где i < c.

Answer 6

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

IMO существует три возможных объяснения замедления:

1. Это можно объяснить замедление легко. Элементы массива ee_t приводят к ложному совместному использованию в пределах строки кэша. Ложное совместное использование заключается в том, что ядра заканчивают запись в одну и ту же строку кэша не потому, что они фактически делят данные, но когда то, что записывает ядро, просто находится в одной и той же строке кэша (поэтому его называют false). Я могу объяснить больше, если вы не найдете ложного обмена в google. Выравнивание строки кеша ee_t элементов может сильно помочь.

2. Накладные работы нереста выше, чем преимущество параллелизма. Вы пробовали менее 8 ядер? Как производительность на 2 ядра?

3. Общее число итераций невелико, скажем, мы возьмем 17 в качестве примера.Если вы разделите его на 8 ядер, это вызовет проблемы дисбаланса нагрузки (особенно, поскольку некоторые из ваших итераций практически не выполняют никакой работы (когда i == c). По крайней мере, одному ядру придется выполнять 3 итерации, в то время как все остальные будут do 2. Это не объясняет медленную, но, безусловно, одну из причин, почему ускорение не так высоко, как вы можете ожидать. Поскольку ваши итерации имеют разную длину, я бы использовал динамическое расписание с размером блока 1 или с использованием openmp. Эксперимент с размером блока, кусок слишком мал, также приведет к замедлению.

Позвольте мне знать, как она идет.