Введение в OpenMP: параллельное программирование на C++

Введение

Не секрет, что «гонка мегагерц», которая на протяжении многих лет оставалась главным способом повышения производительности процессоров, сменилась на тенденцию увеличения числа ядер. Грубо говоря, производители процессоров научились помещать на одном чипе несколько процессоров. Сейчас практически любой компьютер оборудован многоядерным процессором. Даже настольные системы начального уровня имеют два ядра - стоит ли говорить, что на подходе четырёх- и восьмиядерные системы. Если Закон Мура не утратит своей силы, в течение 5 лет средний компьютер будет иметь 16, или даже 32 ядра на чипе.

Проблема заключается в том, что программная индустрия пока не успевает за аппаратной, и только часть приложений способна эффективно использовать ресурсы многоядерных процессоров. Каждая программа имеет один главный поток выполнения - набор инструкций, которые выполняются последовательно одна за другой. Естественно, в этом случае задействовано одно ядро процессора. Программист должен позаботиться о загрузке остальных ядер работой, иными словами, он должен сделать так, чтобы некоторые инструкции выполнялись не последовательно, а одновременно - в параллельном режиме.

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

Каким образом программисты могут управлять потоками, чтобы задействовать всю мощь процессора? Как сделать так, чтобы приложение работало максимально быстро, масштабировалось с увеличением числа ядер, и чтобы написать такое приложение не было ночным кошмаром программиста? Один из вариантов - вручную создавать потоки в программном коде, отдавать им задачи на выполнение, затем удалять. Но в данном случае нужно позаботиться об одной очень важной вещи - синхронизации. Если одной задаче необходимы данные, которые обсчитываются другой задачей, ситуация усложняется. Трудно понять, что происходит, когда разные потоки в одно и то же время пытаются поменять значения общих переменных. Да и не хочется вручную создавать потоки и делегировать им задания. На помощь приходят различные библиотеки и стандарты для параллельного программирования. Рассмотрим подробнее наиболее распространённый стандарт для распараллеливания программ на языках C, C++, Fortran - OpenMP.

OpenMP


OpenMP

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

В OpenMP вы «не увидите» потоки в коде. Вместо этого, вы сообщаете компилятору с помощью директив #pragma, что блок кода может быть распараллелен. Зная данную информацию, компилятор в состоянии сгенерировать приложение, состоящее из одного главного потока, который создаёт множество других потоков для параллельного блока кода. Эти потоки синхронизируются в конце параллельного блока кода, и мы снова возвращаемся к одному главному потоку.


Использование OpenMP

Так как OpenMP контролируется #pragma, то код на C++ корректно скомпилируется любым компилятором C++, потому что неподдерживаемые #pragma должны игнорироваться. Однако OpenMP API содержит также несколько функций, и, чтобы ими воспользоваться, необходимо подключить заголовочный файл. Самый легкий способ определить, поддерживает ли компилятор OpenMP - попробовать подключить файл omp.h: #include <omp.h>

Если OpenMP поддерживается, нужно его включить с помощью специальных флагов компилятора:

gcc	-fopenmp

Intel	-openmp (Linux, MacOSX), -Qopenmp (Windows)

Microsoft	-openmp (Настройки проекта в Visual Studio)

Синтаксис

Директивы OpenMP начинаются с #pragma omp.

parallel

Данная директива создаёт группу из N потоков. N определяется во время выполнения, обычно это число ядер процессора, но также можно задать N вручную. Каждый из потоков в группе выполняет следующую за директивой команду (или блок команд, определённый в {}-скобках). После выполнения, потоки «сливаются» в один.


#pragma omp parallel  {

    // Код внутри блока выполняется параллельно.

    printf("Hello!n");

  }

Пример выведет текст “Hello!” с переносом строки столько раз, сколько потоков было создано в группе. Для двухъядерных систем, текст напечатается дважды. (Замечание: может быть выведено что-нибудь типа “HeHlellolo”, потому что вывод происходит параллельно.)


Принцип fork/join в OpenMP

Если посмотреть, как это устроено, то можно увидеть, что GCC создаёт специальную функцию и перемещает код блока в эту функцию, таким образом, все переменные внутри блока становятся локальными переменными данной функции (соответственно, локальными переменными каждого потока). С другой стороны, ICC использует механизм, напоминающий fork(), и не создаёт специальной функции. Обе реализации, конечно, правильны и семантически идентичны.

Параллелизм может быть условным, если использовать выражение if:

extern int parallelism_enabled;

  #pragma omp parallel for if(parallelism_enabled)

  for(int c=0; c<n; ++c)

    handle(c);

В данном случае, если parallelism_enabled равно нулю, цикл будет обработан только одним (главным) потоком.

for

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

#pragma omp for

 for(int n=0; n<10; ++n)

 {

   printf(" %d", n);

 }

 printf(".n");

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


0 5 6 7 1 8 2 3 4 9.

Данный код будет преобразован компилятором в нечто подобное:

int this_thread = omp_get_thread_num(), num_threads = omp_get_num_threads();

  int my_start = (this_thread  ) * 10 / num_threads;

  int my_end   = (this_thread+1) * 10 / num_threads;

  for(int n=my_start; n<my_end; ++n)

    printf(" %d", n);


Таким образом, каждый поток обрабатывает свою часть цикла параллельно с остальными потоками.

Важно, что директива #pragma omp лишь делегирует порции цикла разным потокам в текущей группе потоков. В момент запуска программы группа из единственного (главного) потока. Чтобы создать новую группу потоков, необходимо использовать ключевое слово parallel:

#pragma omp parallel

 {

  #pragma omp for

  for(int n=0; n<10; ++n) printf(" %d", n);

 }

 printf(".n");


Можно написать короче:

#pragma omp parallel for

 for(int n=0; n<10; ++n) printf(" %d", n);

 printf(".n");

Обе записи эквиваленты.

Чтобы задать количество потоков в группе, можно воспользоваться параметром num_threads:

#pragma omp parallel num_threads(3)

 {

   // Данный код будет выполнен тремя потоками.

   // Части цикла будут поделены между

   // тремя потоками текущей группы потоков.

   #pragma omp for

   for(int n=0; n<10; ++n) printf(" %d", n);

 }


В OpenMP 2.5, итерационная переменная цикла должна быть типа signed. В OpenMP 3.0. она также может иметь тип unsigned integer, может быть указателем или constant-time random access итератором. В последнем случае, для определения количества итераций цикла будет использоваться std::distance().

Краткое резюме: parallel, for и группа потоков

Ещё раз отметим разницу между parallel, parallel for и for:

    • Группа потоков – те потоки, которые выполняются в данный момент.

    • При запуске программы, группа содержит один поток.

    • Директива parallel разделяет текущий поток в новую группу потоков, пока не будет достигнут конец следующего выражения/блока выражений, затем группа потоков сливается в один поток.

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

  • parallel for - краткая запись двух команд: parallel и for. Parallel создаёт новую группу потоков, затем for раздает каждому потоку из этой группы часть цикла.

Если программа не содержит директивы parallel, то она выполняется единственным потоком.

scheduling (планирование)

Программист может контролировать то, каким образом потоки будут загружаться работой при обработке цикла. Существует несколько вариантов.

#pragma omp for schedule(static)

 for(int n=0; n<10; ++n) printf(" %d", n);

 printf(".n");

static является вариантом по умолчанию. Ещё до входа в цикл каждый поток «знает», какие части цикла он будет обрабатывать.

Второй вариант - ключевое слово dynamic:

#pragma omp for schedule(dynamic)

 for(int n=0; n<10; ++n) printf(" %d", n);

 printf(".n");

В данном случае невозможно предсказать порядок, в котором итерации цикла будут назначены потокам. Каждый поток выполняет указанное число итераций. Если это число не задано, по умолчанию оно равно 1. После того как поток завершит выполнение заданных итераций, он переходит к следующему набору итераций. Так продолжается, пока не будут пройдены все итерации. Последний набор итераций может быть меньше, чем изначально заданный. Такой вариант очень полезен, когда разные итерации цикла обсчитываются разное время. Можно также указать количество итераций, после выполнения которых поток «попросит» у OpeMP следующие:

#pragma omp for schedule(dynamic, 3)

 for(int n=0; n<10; ++n) printf(" %d", n);

 printf(".n");

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

Существует также вариант guided. Он похож на dynamic, но размер порции уменьшается экспоненциально. Если указать директиву #pragma omp for schedule(dynamic, 15), цикл for из 100 итераций может быть выполнен четырьмя потоками следующим образом:

Поток 0 получает право на выполнение итераций 1-15

Поток 1 получает право на выполнение итераций 16-30

Поток 2 получает право на выполнение итераций 31-45

Поток 3 получает право на выполнение итераций 46-60

Поток 2 завершает выполнение итераций

Поток 2 получает право на выполнение итераций 61-75

Поток 3 завершает выполнение итераций

Поток 3 получает право на выполнение итераций 76-90

Поток 0 завершает выполнение итераций

Поток 0 получает право на выполнение итераций 91-100


А вот каким может оказаться результат выполнения того же цикла четырьмя потоками, если будет указана директива #pragma omp for schedule(guided, 15):

Поток 0 получает право на выполнение итераций 1-25

Поток 1 получает право на выполнение итераций 26-44

Поток 2 получает право на выполнение итераций 45-59

Поток 3 получает право на выполнение итераций 60-64

Поток 2 завершает выполнение итераций

Поток 2 получает право на выполнение итераций 65-79

Поток 3 завершает выполнение итераций

Поток 3 получает право на выполнение итераций 80-94

Поток 2 завершает выполнение итераций

Поток 2 получает право на выполнение итераций 95-100


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

ordering (упорядочивание)

Порядок, в котором будут обрабатываться итерации цикла, вообще говоря, непредсказуем. Тем не менее, возможно «заставить» OpenMP выполнять выражения в цикле по порядку. Для этого существует ключевое слово ordered:

#pragma omp for ordered schedule(dynamic)

 for(int n=0; n<100; ++n)

 {

   files[n].compress();


   #pragma omp ordered

   send(files[n]);

 }

Цикл «сжимает» 100 файлов в параллельном режиме, но «посылает» их строго в последовательном порядке. Если, например, поток «сжал» седьмой файл, но шестой файл к этому моменту ещё не был «отправлен», поток будет ожидать «отправки» шестого файла. Каждый файл «сжимается» и «посылается» один раз, но «сжатие» может происходить в параллельном режиме. Разрешено использовать только один ordered блок на цикл.


Дальнейшее чтение





For more complete information about compiler optimizations, see our Optimization Notice.