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

Я начал работать с OpenMP с использованием C ++.

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

What is #pragma omp for schedule? What is the difference between dynamic and static?

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

 Walter01 июн. 2012 г., 14:54
Я думаю, у вас есть трудности с английским значением расписания. Это относится к тому, как работа, то есть отдельные значения переменной цикла, распределяется по потокам.static означает, что в начале решено, какой поток будет выполнять какие значения, где какdynamic означает, что каждый поток будет работать с порцией значений, а затем брать следующий блок, с которым не работал ни один поток. Последнее позволяет улучшить балансировку (в случае, если работа варьируется между различными значениями для переменной цикла), но требует некоторых накладных расходов на связь.

Ответы на вопрос(3)

Решение Вопроса

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

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() Вызов только резервирует виртуальное адресное пространство, но на самом деле не "трогает" физическая память (это поведение по умолчанию, если какая-то другая версияmalloc используется, например, тот, который обнуляет память какcalloc() делает). Теперь этот массив является непрерывным, но только в виртуальной памяти. В физической памяти половина этого будет лежать в памяти, присоединенной к сокету 0, и половина в памяти, присоединенной к сокету 1. Это происходит потому, что разные части обнуляются разными потоками, и эти потоки находятся на разных ядрах, и есть нечто, называемоеfirst touch Политика 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>

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

threads 4 to 7 remain idle and half of the compute capability is lost; threads 2 and 3 access non-local memory and it will take them about twice as much time to finish during which time threads 0 and 1 will remain idle.

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

dynamic планирование работ по принципу «первым пришел, первым обслужен» основа. Два запуска с одинаковым количеством потоков могут (и, скорее всего, будут) создавать совершенно другое «пространство итераций» - & GT; & Quot; резьба & Quot; сопоставления, которые можно легко проверить:

$ 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, Это позволяет тестировать различные типы планирования без перекомпиляции приложения, а также позволяет конечному пользователю точно настроить свою платформу.

 02 сент. 2016 г., 16:46
NUMA означает неравномерный доступ к памяти?
 02 сент. 2016 г., 16:52
Да, это означает именно это.
 02 мая 2017 г., 00:33
@HristoIliev, если вы установите OMP_PROC_BIND = TRUE с динамическим расписанием, это сохранит локальность доступа к памяти?
 02 мая 2017 г., 23:24
@Marouen,OMP_PROC_BIND предотвращает миграцию потоков с одного процессора на другой. Это обычно улучшает локальность для случая предсказуемых шаблонов доступа к памяти, например, со статическим планированием цикла. Динамическое планирование обычно приводит к непредсказуемым схемам доступа, и локальность редко сохраняется, за исключением (потоковых) частных данных.

Я думаю, что недоразумение происходит из-за того, что вы упускаете суть 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/

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

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

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

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

 01 июн. 2012 г., 14:43
Используете расписание? Потому что, если я просто использую параллель для, индекс будет общим, не так ли?
 01 июн. 2012 г., 14:33
Если цикл распараллеливается OpenMP, то это происходит, когда разные потоки работают на разных частях цикла, например, Поток 1 будет работать с индексами [0..32) [64..96), а поток будет работать с [32..64) [96..128).
 Lücks01 июн. 2012 г., 14:51
Я могу разделить вектор Que между потоками? Например, у меня есть размер вектора 20. Я хочу параллельную пузырьковую сортировку. Итак, я даю 5 элементов для каждого потока, и после всех потоков пузырьковой сортировки, я объединяю все по вектору. Я & APOS; действительно запутать насчет графика :(
 01 июн. 2012 г., 14:44
Нет, индекс всегда должен быть закрытым для потока, потому что каждому потоку нужен отдельный счетчик.
 Lücks01 июн. 2012 г., 14:28
Делить цикл, вы имели в виду индекс цикла?

Ваш ответ на вопрос