В чем разница между "статическим" и "динамическим" расписанием в OpenMP?

Question

Я начал работать с OpenMP, используя C++.

У меня есть два вопроса:

1. Что такое #pragma omp for schedule?
2. В чем разница между dynamic а также static?

Пожалуйста, объясните примерами.

Answer 1

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

static schedule означает, что блоки итераций статически отображаются в потоки выполнения циклически. Хорошая вещь со статическим планированием состоит в том, что среда выполнения OpenMP гарантирует, что если у вас есть два отдельных цикла с одинаковым числом итераций и выполняете их с одинаковым числом потоков с использованием статического планирования, то каждый поток получит точно такой же диапазон итераций (s) в обеих параллельных областях. Это очень важно в системах NUMA: если вы коснетесь некоторой памяти в первом цикле, она будет находиться на узле NUMA, где находился исполняющий поток. Затем во втором цикле тот же поток может быстрее получить доступ к той же области памяти, поскольку он будет находиться на том же узле NUMA.

Представьте, что есть два узла NUMA: узел 0 и узел 1, например, двухпроцессорная плата Intel Nehalem с 4-ядерными процессорами в обоих сокетах. Тогда потоки 0, 1, 2 и 3 будут находиться на узле 0, а потоки 4, 5, 6 и 7 - на узле 1:

|             | core 0 | thread 0 |
| socket 0    | core 1 | thread 1 |
| NUMA node 0 | core 2 | thread 2 |
|             | core 3 | thread 3 |

|             | core 4 | thread 4 |
| socket 1    | core 5 | thread 5 |
| NUMA node 1 | core 6 | thread 6 |
|             | core 7 | thread 7 |

Каждое ядро ​​может получать доступ к памяти с каждого узла NUMA, но удаленный доступ медленнее (в 1,5- 1,9 раза медленнее, чем у Intel), чем доступ к локальному узлу. Вы запускаете что-то вроде этого:

char *a = (char *)malloc(8*4096);

#pragma omp parallel for schedule(static,1) num_threads(8)
for (int i = 0; i < 8; i++)
   memset(&a[i*4096], 0, 4096);

В этом случае 4096 байт - это стандартный размер одной страницы памяти в Linux на x86, если огромные страницы не используются. Этот код обнулит весь массив 32 КиБ a, malloc() call просто резервирует виртуальное адресное пространство, но на самом деле не "касается" физической памяти (это поведение по умолчанию, если только какая-то другая версия malloc используется, например, тот, который обнуляет память как calloc() делает). Теперь этот массив является смежным, но только в виртуальной памяти. В физической памяти половина этого будет лежать в памяти, присоединенной к сокету 0, и половина в памяти, присоединенной к сокету 1. Это происходит потому, что разные части обнуляются разными потоками, и эти потоки находятся на разных ядрах, и существует нечто, называемое первым касанием. Политика NUMA, которая означает, что страницы памяти размещаются на узле NUMA, в котором находится поток, который первым "коснулся" страницы памяти.

|             | core 0 | thread 0 | a[0]     ... a[4095]
| socket 0    | core 1 | thread 1 | a[4096]  ... a[8191]
| NUMA node 0 | core 2 | thread 2 | a[8192]  ... a[12287]
|             | core 3 | thread 3 | a[12288] ... a[16383]

|             | core 4 | thread 4 | a[16384] ... a[20479]
| socket 1    | core 5 | thread 5 | a[20480] ... a[24575]
| NUMA node 1 | core 6 | thread 6 | a[24576] ... a[28671]
|             | core 7 | thread 7 | a[28672] ... a[32768]

Теперь давайте запустим еще один цикл:

#pragma omp parallel for schedule(static,1) num_threads(8)
for (i = 0; i < 8; i++)
   memset(&a[i*4096], 1, 4096);

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

Теперь представьте, что для второго цикла используется другая схема планирования: schedule(static,2), Это разделит пространство итераций на блоки по две итерации, и всего будет 4 таких блока. То, что произойдет, это то, что у нас будет следующий поток на отображение местоположения памяти (через номер итерации):

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory

|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

Здесь происходят две плохие вещи:

• потоки с 4 по 7 остаются бездействующими, и половина вычислительных возможностей теряется;
• потоки 2 и 3 обращаются к нелокальной памяти, и для их завершения потребуется примерно вдвое больше времени, в течение которого потоки 0 и 1 будут простаивать.

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

dynamic планирование работ по принципу "первым пришел - первым обслужен". Два запуска с одинаковым количеством потоков могут (и, скорее всего, будут) приводить к совершенно разным отображениям "пространство итерации" -> "потоки", что можно легко проверить:

$ cat dyn.c
#include <stdio.h>
#include <omp.h>

int main (void)
{
  int i;

  #pragma omp parallel num_threads(8)
  {
    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[1] iter %0d, tid %0d\n", i, omp_get_thread_num());

    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[2] iter %0d, tid %0d\n", i, omp_get_thread_num());
  }

  return 0;
}

$ icc -openmp -o dyn.x dyn.c

$ OMP_NUM_THREADS=8 ./dyn.x | sort
[1] iter 0, tid 2
[1] iter 1, tid 0
[1] iter 2, tid 7
[1] iter 3, tid 3
[1] iter 4, tid 4
[1] iter 5, tid 1
[1] iter 6, tid 6
[1] iter 7, tid 5
[2] iter 0, tid 0
[2] iter 1, tid 2
[2] iter 2, tid 7
[2] iter 3, tid 3
[2] iter 4, tid 6
[2] iter 5, tid 1
[2] iter 6, tid 5
[2] iter 7, tid 4

(такое же поведение наблюдается, когда gcc используется вместо)

Если образец кода из static раздел был запущен с dynamic вместо этого при планировании будет сохраняться только 1/70 (1,4%) вероятности сохранения первоначального местоположения и 69/70 (98,6%) вероятности удаленного доступа. Этот факт часто упускается из виду и, следовательно, достигается неоптимальная производительность.

Есть еще одна причина выбирать между static а также dynamic планирование - балансировка рабочей нагрузки. Если каждая итерация значительно отличается от среднего времени выполнения, то в статическом случае может возникнуть высокий рабочий дисбаланс. Возьмем в качестве примера случай, когда время завершения итерации растет линейно с номером итерации. Если пространство итераций разделено статически между двумя потоками, второй будет иметь в три раза больше работы, чем первый, и, следовательно, в течение 2/3 времени вычислений первый поток будет простаивать. Динамическое расписание вносит некоторые дополнительные издержки, но в этом конкретном случае приведет к гораздо лучшему распределению рабочей нагрузки. Особый вид dynamic планирование является guided где меньшие и меньшие блоки итерации даны каждой задаче в ходе работы.

Поскольку предварительно скомпилированный код можно запускать на разных платформах, было бы неплохо, если бы конечный пользователь мог контролировать планирование. Вот почему OpenMP предоставляет специальные schedule(runtime) пункт. С runtime планирование типа берется из содержимого переменной среды OMP_SCHEDULE, Это позволяет тестировать различные типы планирования без перекомпиляции приложения, а также позволяет конечному пользователю точно настроить свою платформу.

Answer 2

Я думаю, что недоразумение происходит из-за того, что вы упускаете суть OpenMP. В предложении OpenMP позволяет вам быстрее выполнять программу, включив параллелизм. В программе параллелизм может быть включен многими способами, и одним из них является использование потоков. Предположим, у вас есть и массив:

[1,2,3,4,5,6,7,8,9,10]

и вы хотите увеличить все элементы на 1 в этом массиве.

Если вы собираетесь использовать

#pragma omp for schedule(static, 5)

это означает, что каждому из потоков будет назначено 5 смежных итераций. В этом случае первый поток займет 5 чисел. Второй будет занимать еще 5 и так далее до тех пор, пока не останется больше данных для обработки или пока не будет достигнуто максимальное количество потоков (обычно равное количеству ядер). Распределение рабочей нагрузки выполняется во время компиляции.

В случае

#pragma omp for schedule(dynamic, 5)

Работа будет распределена между потоками, но эта процедура будет выполняться во время выполнения. Таким образом, привлекая больше накладных расходов. Второй параметр указывает размер фрагмента данных.

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

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

https://computing.llnl.gov/tutorials/parallel_comp/

Дополнительные ссылки:
http://en.wikipedia.org/wiki/OpenMP
Разница между статическим и динамическим расписанием в openMP в C
http://openmp.blogspot.se/

Answer 3

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

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

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