В чем разница между "статическим" и "динамическим" расписанием в OpenMP?
Я начал работать с OpenMP, используя C++.
У меня есть два вопроса:
- Что такое
#pragma omp for schedule? - В чем разница между
dynamicиstatic?
Пожалуйста, объясните на примерах.
Другие уже ответили на большую часть вопроса, но я хотел бы указать на некоторые конкретные случаи, когда определенный тип планирования подходит больше, чем другие. Расписание контролирует, как итерации цикла распределяются между потоками. Выбор правильного расписания может оказать большое влияние на скорость работы приложения. Статический" график означает, что блоки итераций статически распределяются между потоками выполнения по кругу. Приятной особенностью статического планирования является то, что время выполнения 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] <- 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 будут простаивать. Таким образом, одним из преимуществ использования статического планирования является то, что оно улучшает локальность доступа к памяти. Недостатком является то, что неправильный выбор параметров планирования может испортить производительность. Динамическое планирование работает по принципу "первым пришел - первым обслужен". Два запуска с одинаковым количеством потоков могут (и, скорее всего, будут) производить совершенно разные "итерационные пространства" -> "потоки" отображения, в чем можно легко убедиться:
$ 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%) шанс, что удаленный доступ будет иметь место. Этот факт часто упускается из виду, и, следовательно, достигается неоптимальная производительность.
Есть еще одна причина выбирать между статическим и динамическим планированием - балансировка рабочей нагрузки. Если каждая итерация занимает время, значительно отличающееся от среднего времени, то в статическом случае может возникнуть большой дисбаланс работы. Возьмем в качестве примера случай, когда время завершения итерации растет линейно с ростом числа итераций. Если пространство итерации статически разделить между двумя потоками, то второй поток будет иметь в три раза больше работы, чем первый, и, следовательно, в течение 2/3 времени вычислений первый поток будет простаивать. Динамическое расписание влечет за собой дополнительные накладные расходы, но в данном конкретном случае приводит к гораздо лучшему распределению нагрузки. Особым видом динамического планирования является управляемое, когда каждой задаче по мере выполнения работы предоставляются все меньшие и меньшие блоки итераций.
Поскольку предварительно скомпилированный код может выполняться на различных платформах, было бы неплохо, если бы конечный пользователь мог контролировать планирование. Именно поэтому OpenMP предоставляет специальный пункт schedule(runtime). При runtime планировании тип берется из содержимого переменной окружения OMP_SCHEDULE. Это позволяет тестировать различные типы планирования без перекомпиляции приложения, а также дает конечному пользователю возможность тонкой настройки под свою платформу.
Я думаю, что непонимание происходит из-за того, что вы упускаете суть 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 элементов.
Динамический подход вычисляет размер подмножеств на лету, что может быть полезно, если время вычисления подмножеств меняется.
Статический подход следует использовать, если время вычислений меняется незначительно.
