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

Другие уже ответили на большую часть вопроса, но я хотел бы указать на некоторые конкретные случаи, когда определенный тип планирования подходит больше, чем другие. Расписание контролирует, как итерации цикла распределяются между потоками. Выбор правильного расписания может оказать большое влияние на скорость работы приложения. Статический" график означает, что блоки итераций статически распределяются между потоками выполнения по кругу. Приятной особенностью статического планирования является то, что время выполнения OpenMP гарантирует, что если у вас есть два отдельных цикла с одинаковым количеством итераций и они выполняются одинаковым количеством потоков с использованием статического планирования, то каждый поток получит точно такой же диапазон(ы) итераций в обоих параллельных регионах. Это очень важно для 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.5x - 1.9x медленнее на 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. Это так, потому что разные части обнуляются разными потоками, и эти потоки находятся на разных ядрах, и существует нечто, называемое политикой NUMA first touch, которая означает, что страницы памяти выделяются на том узле 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]  

Я думаю, что непонимание происходит из-за того, что вы упускаете суть 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
https://stackoverflow.com/questions/4261087/difference-between-static-and-dynamic-schedule-in-openmp-in-c
http://openmp.blogspot.se/

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

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

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