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

Ответ 1

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

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

Представьте, что есть два узла NUMA: node 0 и node 1, например. двухпроцессорную плату Intel Nehalem с 4-ядерными процессорами в обоих гнездах. Затем потоки 0, 1, 2 и 3 будут находиться на node 0, а потоки 4, 5, 6 и 7 будут находиться на node 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 node, но удаленный доступ медленнее (на 1,5x - 1,9 раза медленнее на Intel), чем локальный доступ node. Вы запускаете что-то вроде этого:

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

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

Ответ 2

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

[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/

Ответ 3

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

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

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