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