Инфраструктура OpenMP позволяет эффективно реализовывать технологии параллельного программирования на C, C++ и Fortran. Компилятор GNU Compiler Collection (GCC) версии 4.2 поддерживает спецификацию OpenMP 2.5, а GCC версии 4.4 – самую последнюю спецификацию OpenMP 3. Другие компиляторы, включая Microsoft® Visual Studio, также поддерживают OpenMP. Эта статья научит вас использовать прагмы компилятора OpenMP; также она содержит информацию о некоторых API-интерфейсах OpenMP и раскрывает некоторые приемы параллельных вычислений с использованием OpenMP. Во всех примерах этой статьи используется компилятор GCC 4.2.

Начало работы

Огромным достоинством OpenMP является отсутствие необходимости в дополнительных действиях, за исключением стандартной инсталляции компилятора GCC. Компиляция OpenMP-приложений должна выполняться с опцией -fopenmp .

Создаем первое OpenMP-приложение

Начнем с написания простого приложения Hello, World! , содержащего дополнительную прагму. Код этого приложения представлен в листинге 1.

Листинг 1. Программа "Hello World", написанная с использованием OpenMP

#include int main() { #pragma omp parallel { std::cout << "Hello World!\n"; } }

После компиляции и запуска этого кода с помощью g++ вы увидите на экране надпись Hello, World! . Теперь перекомпилируем код с опцией -fopenmp . Результат работы программы представлен в листинге 2.

Листинг 2. Компиляция и запуск кода с использованием опции -fopenmp

tintin$ g++ test1.cpp -fopenmp tintin$ ./a.out Hello World! Hello World! Hello World! Hello World! Hello World! Hello World! Hello World! Hello World!

Что же произошло? Когда вы используете опцию компилятора -fopenmp , в дело вступает директива #pragma omp parallel . В процессе компиляции внутренние механизмы GCC создают столько параллельных потоков, сколько могут выполняться при условии оптимальной загрузки системы (в зависимости от конфигураций аппаратного обеспечения и операционной системы), при этом в каждом создаваемом потоке выполняется код, заключенный в блоке после прагмы. Такое поведение называется неявным распараллеливанием , а ядро OpenMP состоит из набора мощных прагм, избавляющих вас от написания множества типовых фрагментов кода (для интереса вы можете сравнить приведенный кода с реализацией этой же задачи с помощью POSIX-потоков ). Я использую компьютер с процессором Intel® Core i7 с 4 физическими ядрами по 2 логических ядра в каждом, что объясняет результаты, полученные в листинге 2 (8 потоков = 8 логических ядер).

Возможности OpenMP parallel

Количеством потоков можно легко управлять с помощью прагмы с аргументом num_threads . Ниже представлен код из листинга 1 с заданным количеством потоков (5 потоков):

Листинг 3. Управление количеством потоков с помощью num_threads

#include int main() { #pragma omp parallel num_threads(5) { std::cout << "Hello World!\n"; } }

Вместо аргумента num_threads можно воспользоваться альтернативным способом для задания количества потоков выполнения кода. Здесь мы подошли к рассмотрению первого API-интерфейса OpenMP под названием omp_set_num_threads . Эта функция определяется в файле заголовка omp.h. Для выполнения кода из листинга 4 не требуется использовать какие-либо дополнительные библиотеки, – просто используйте опцию -fopenmp .

Листинг 4. Точное управление потоками с помощью omp_set_num_threads

#include #include int main() { omp_set_num_threads(5); #pragma omp parallel { std::cout << "Hello World!\n"; } }

Наконец, для управления работой OpenMP можно использовать внешние переменные среды. Можно исправить код из листинга 2 и просто напечатать фразу Hello World! шесть раз, задав для переменной OMP_NUM_THREADS значение 6, как показано в листинге 5.

Листинг 5. Переменные среды для настройки OpenMP

tintin$ export OMP_NUM_THREADS=6 tintin$ ./a.out Hello World! Hello World! Hello World! Hello World! Hello World! Hello World!

Мы рассмотрели три стороны OpenMP: прагмы компилятора, API-интерфейсы времени выполнения и переменные среды. Что произойдет, если использовать переменные среды вместе с API-интерфейсами времени выполнения? API-интерфейсы имеют более высокий приоритет.

Практический пример

В OpenMP используются технологии неявного распараллеливания, и для передачи инструкций компилятору можно использовать прагмы, явные функции и переменные среды. Давайте рассмотрим пример, наглядно демонстрирующий пользу от применения OpenMP. Посмотрите на код, представленный в листинге 6.

Листинг 6. Последовательная обработка в цикле for

int main() { int a, b; // ... код инициализации массивов a и b; int c; for (int i = 0; i < 1000000; ++i) c[i] = a[i] * b[i] + a * b; // ... выполняем некоторые действия с массивом c }

Очевидно, что цикл for можно распараллелить и обрабатывать сразу несколькими ядрами процессора, поскольку вычисление значения любого элемента c[k] никак не зависит от остальных элементов массива c . В листинге 7 показано, как можно это сделать с помощью OpenMP.

Листинг 7. Параллельная обработка в цикле for с помощью прагмы parallel for

int main() { int a, b; // ... код для инициализации массивов a и b; int c; #pragma omp parallel for for (int i = 0; i < 1000000; ++i) c[i] = a[i] * b[i] + a * b; // ... выполняем некоторые действия с массивом c }

Прагма parallel for помогает распределить рабочую нагрузку цикла for между несколькими потоками, каждый из которых может обрабатываться отдельным ядром процессора; таким образом общее время вычислений существенно снижается. Это подтверждается в листинге 8.

Листинг 8. Пример с использованием API-функции omp_get_wtime

#include #include #include #include int main(int argc, char *argv) { int i, nthreads; clock_t clock_timer; double wall_timer; double c; for (nthreads = 1; nthreads <=8; ++nthreads) { clock_timer = clock(); wall_timer = omp_get_wtime(); #pragma omp parallel for private(i) num_threads(nthreads) for (i = 0; i < 1000000; i++) c[i] = sqrt(i * 4 + i * 2 + i); std::cout << "threads: " << nthreads << " time on clock(): " << (double) (clock() - clock_timer) / CLOCKS_PER_SEC << " time on wall: " << omp_get_wtime() - wall_timer << "\n"; } }

В листинге 8 мы измеряем время выполнения внутреннего цикла for , увеличивая при этом количество потоков. API-функция omp_get_wtime возвращает затраченное фактическое время (в секундах), прошедшее с начала заданной точки отсчета. Таким образом, значение omp_get_wtime() - wall_timer возвращает фактическое время выполнения цикла for . Системный вызов clock() используется для оценки времени, затраченного центральным процессором на выполнение всей программы, т. е. прежде чем получить итоговый результат, мы суммируем все эти временные интервалы с учетом потоков. На моем компьютере с процессором Intel Core i7 я получил результаты, приведенные в листинге 9.

Листинг 9. Статистика выполнения внутреннего цикла for

threads: 1 time on clock(): 0.015229 time on wall: 0.0152249 threads: 2 time on clock(): 0.014221 time on wall: 0.00618792 threads: 3 time on clock(): 0.014541 time on wall: 0.00444412 threads: 4 time on clock(): 0.014666 time on wall: 0.00440478 threads: 5 time on clock(): 0.01594 time on wall: 0.00359988 threads: 6 time on clock(): 0.015069 time on wall: 0.00303698 threads: 7 time on clock(): 0.016365 time on wall: 0.00258303 threads: 8 time on clock(): 0.01678 time on wall: 0.00237703

Хотя время центрального процессора (time on clock) во всех случаях получилось примерно одинаковым (как и должно быть, не принимая во внимание дополнительное время, затраченное на создание потоков и контекстного переключателя), интересующее нас фактическое время (time on wall) постоянно уменьшалось при увеличении количества потоков, которые предположительно выполнялись параллельно отдельными процессорными ядрами. Итак, сделаем последнее замечание относительно синтаксиса прагмы: #pragma parallel for private(i) означает, что переменная цикла i рассматривается как локальная память потока; каждый поток содержит свою копию этой переменной. Локальная переменная потока не инициализируется.

Критические участки кода в OpenMP

Разумеется, вы понимаете, что нельзя полностью доверить OpenMP автоматически обрабатывать критические участки кода, не так ли? Конечно, вам не придется явным образом создавать взаимные исключения (мьютексы), тем не менее критические участки необходимо указывать. Синтаксис приводится в следующем примере:

#pragma omp critical (optional section name) { // 2 потока не могут выполнять этот блок кода одновременно }

Код, следующий после директивы pragma omp critical , может выполняться в заданный момент времени только в одном потоке. Кроме того, имя раздела optional section name является глобальным идентификатором, и критические участки с одинаковым идентификатором не могут обрабатываться одновременно двумя потоками. Рассмотрим код в листинге 10.

Листинг 10. Несколько критических участков с одинаковыми именами

#pragma omp critical (section1) { myhashtable.insert("key1", "value1"); } // ... здесь содержится какой-то другой код #pragma omp critical (section1) { myhashtable.insert("key2", "value2"); }

Посмотрев на код в этом листинге, можно предположить, что две операции вставки данных в хэш-таблицу никогда не будут выполняться одновременно, поскольку имена критических участков совпадают. Это немного отличается от того, к чему вы привыкли, обрабатывая критические участки в pthreads, для которых характерно использование большого количества блокировок (что может приводить к лишним сложностям).

Блокировки и мьютексы в OpenMP

Интересно, что OpenMP содержит свои версии мьютексов (в конце концов, OpenMP – это не только прагмы). Итак, познакомьтесь с типом omp_lock_t , определенным в заголовочном файле omp.h. Обычные мьютексные операции в стиле pthread-потоков содержат значение true, даже если имена API-функций одинаковы. Вот пять API-функций, о которых необходимо знать:

• omp_init_lock : эта API-функция должна использоваться первой при обращении к типу omp_lock_t и предназначена для инициализации. Необходимо отметить, что сразу после инициализации блокировка будет находиться в исходном (unset) состоянии.
• omp_destroy_lock : уничтожает блокировку. В момент вызова этой API-функции блокировка должна находиться в исходном состоянии; это означает, что нельзя вызвать функцию omp_set_lock , а затем уничтожить блокировку.
• omp_set_lock : устанавливает omp_lock_t , т. е. активирует мьютекс. Если поток не может установить блокировку, он продолжает ожидать до тех пор, пока такая возможность не появится.
• omp_test_lock : пытается установить блокировку, если она доступна; возвращает 1 в случае успеха и 0 в случае неудачи. Это функция является неблокирующей , т. е. она не заставляет поток ожидать установления блокировки.
• omp_unset_lock : сбрасывает блокировку в исходное состояние.

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

Листинг 11. Усовершенствование однопоточной очереди с помощью OpenMP

#include #include "myqueue.h" class omp_q: public myqueue { public: typedef myqueue base; omp_q() { omp_init_lock(&lock); } ~omp_q() { omp_destroy_lock(&lock); } bool push(const int& value) { omp_set_lock(&lock); bool result = this->base::push(value); omp_unset_lock(&lock); return result; } bool trypush(const int& value) { bool result = omp_test_lock(&lock); if (result) { result = result && this->base::push(value); omp_unset_lock(&lock); } return result; } // likewise for pop private: omp_lock_t lock; };

Вложенные блокировки

Другими типами блокировок в OpenMP являются различные варианты блокировки omp_nest_lock_t . Они похожи на omp_lock_t , но имеют дополнительное преимущество: такая блокировка может быть включена удерживающим ее потоком несколько раз. Каждый раз, когда вложенная блокировка активируется удерживающим ее потоком с помощью omp_set_nest_lock , увеличивается внутренний счетчик блокировок. Блокировка освобождается удерживающим потоком тогда, когда один или несколько вызовов omp_unset_nest_lock снижают значение внутреннего счетчика блокировок до 0 . Для работы с omp_nest_lock_t используются следующие API-функции:

• omp_init_nest_lock(omp_nest_lock_t*) : устанавливает внутренний счетчик вложенности в 0 .
• omp_destroy_nest_lock(omp_nest_lock_t*) : уничтожает блокировку. Вызов этой API-функции для блокировки со значением счетчика, отличного от нуля, приводит к непредсказуемым результатам.
• omp_set_nest_lock(omp_nest_lock_t*) : аналогична функции omp_set_lock за исключением того, что удерживающий поток может вызывать ее несколько раз.
• omp_test_nest_lock(omp_nest_lock_t*) : является неблокирующей версией API-функции omp_set_nest_lock .
• omp_unset_nest_lock(omp_nest_lock_t*) : освобождает блокировку при достижении внутренним счетчиком блокировок значения 0 . В остальных случаях каждый вызов этой API-функции уменьшает значение счетчика.

Детальный контроль выполнения заданий

Мы уже видели, что блок кода, который следует за директивой pragma omp parallel , обрабатывается параллельно всеми потоками. Код внутри этих блоков можно также разделить на категории, которые будут выполняться в указанных потоках. Рассмотрим код в листинге 12.

Листинг 12. Использование прагмы parallel sections

int main() { #pragma omp parallel { cout << "Это выполняется во всех потоках\n"; #pragma omp sections { #pragma omp section { cout << "Это выполняется параллельно\n"; } #pragma omp section { cout << "Последовательный оператор 1\n"; cout << "Это всегда выполняется после оператора 1\n"; } #pragma omp section { cout << "Это тоже выполняется параллельно\n"; } } } }

Код, предшествующий директиве pragma omp sections и следующий сразу за директивой pragma omp parallel , обрабатывается параллельно всеми потоками. При помощи директивы pragma omp sections код, следующий за ней, разбивается на отдельные подсекции. Каждый блок pragma omp section может выполняться отдельным потоком. Тем не менее отдельные операторы внутри блока section всегда выполняются последовательно. В листинге 13 показаны результаты выполнения кода из листинга 12.

Листинг 13. Результаты выполнения кода из листинга 12

tintin$ ./a.out Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется во всех потоках Это выполняется параллельно Последовательный оператор 1 Это тоже выполняется параллельно Это всегда выполняется после оператора 1

В листинге 13 мы снова видим 8 изначально созданных потоков. Для обработки блока pragma omp sections достаточно трех потоков из восьми. Внутри второй секции мы указали порядок, в котором выполняются операторы вывода текста. В этом и заключается смысл использования прагмы sections . При необходимости можно указывать порядок выполнения блоков кода.

Директивы firstprivate и lastprivate в связке с параллельными циклами

В этой статье я уже показывал, как объявить локальную память потока с помощью директивы private . Но как инициализировать локальные переменные потока? Может быть, синхронизировать их со значением переменной главного потока перед дальнейшими действиями? В таких случаях нам пригодится директива firstprivate .

Директива firstprivate

Используя директиву firstprivate(переменная) , можно инициализировать переменную в потоке, присвоив ей любое значение, которое она имела в главном потоке. Рассмотрим код из листинга 14.

Листинг 14. Использование локальной переменной потока, которая не синхронизирована с главным потоком

#include #include int main() { int idx = 100; #pragma omp parallel private(idx) { printf("В потоке %d idx = %d\n", omp_get_thread_num(), idx); } }

Вот что я получил в результате (ваши результаты могут быть другими).

В потоке 1 idx = 1 В потоке 5 idx = 1 В потоке 6 idx = 1 В потоке 0 idx = 0 В потоке 4 idx = 1 В потоке 7 idx = 1 В потоке 2 idx = 1 В потоке 3 idx = 1

В листинге 15 содержится код с использованием директивы firstprivate . Как и ожидалось, вывод результатов показывает, что переменная idx имеет значение 100 во всех потоках.

Листинг 15. Использование директивы firstprivate для инициализации локальных переменных потоков

#include #include int main() { int idx = 100; #pragma omp parallel firstprivate(idx) { printf("В потоке %d idx = %d\n", omp_get_thread_num(), idx); } }

Также обратите внимание на то, что для доступа к идентификатору потока был использован метод omp_get_thread_num() . Этот идентификатор отличается от идентификатора, выводимого командой top операционной системы Linux®, и эта схема является лишь способом, позволяющим OpenMP отслеживать количество потоков. Если вы планируете использовать директиву firstprivate в коде C++ , то обратите внимание на другую ее особенность: переменная, используемая директивой firstprivate , является копирующим конструктором для инициализации самой себя из переменной главного потока, поэтому если копирующий конструктор является приватным для вашего класса, это может привести к неприятным последствиям. Теперь перейдем к рассмотрению директивы lastprivate , которая во многом является обратной стороной монеты.

Директива lastprivate

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

Листинг 16. Параллельный цикл for без синхронизации данных с главным потоком

#include #include int main() { int idx = 100; int main_var = 2120; #pragma omp parallel for private(idx) for (idx = 0; idx < 12; ++idx) { main_var = idx * idx; printf("В потоке %d idx = %d main_var = %d\n", omp_get_thread_num(), idx, main_var); } printf("Возврат в главный поток со значением переменной main_var = %d\n", main_var); }

На моем компьютере с 8 ядрами OpenMP создает для блока parallel for шесть потоков. Каждый поток, в свою очередь, насчитывает по две итерации в цикле. Итоговое значение переменной main_var зависит от потока, который выполнился последним и, следовательно, от значения переменной idx в этом потоке. Другими словами, значение переменной main_var не зависит от последнего значения переменной idx , но зависит от значения, которое содержала переменная idx того потока, который был выполнен в последнюю очередь. Этот пример продемонстрирован в листинге 17.

Листинг 17. Зависимость значения переменной main_var от последнего выполненного потока

В потоке 4 idx = 8 main_var = 64 В потоке 2 idx = 4 main_var = 16 В потоке 5 idx = 10 main_var = 100 В потоке 3 idx = 6 main_var = 36 В потоке 0 idx = 0 main_var = 0 В потоке 1 idx = 2 main_var = 4 В потоке 4 idx = 9 main_var = 81 В потоке 2 idx = 5 main_var = 25 В потоке 5 idx = 11 main_var = 121 В потоке 3 idx = 7 main_var = 49 В потоке 0 idx = 1 main_var = 1 В потоке 1 idx = 3 main_var = 9 Возврат в главный поток со значением переменной main_var = 9

Запустите код из листинга 17 несколько раз, чтобы убедиться в том, что значение переменной main_var в главном потоке всегда зависит от значения переменной idx в последнем выполненном потоке. А что делать, если необходимо синхронизировать значение переменной главного потока с итоговым значением переменной idx в цикле? Здесь на помощь приходит директива lastprivate , работа которой продемонстрирована в листинге 18. Как и в предыдущем случае, запустите код из листинга 18 несколько раз, и вы увидите, что итоговое значение переменной main_var в главном потоке равно 121 (т.е. значению переменной idx в последней итерации цикла).

Листинг 18. Синхронизация с помощью директивы lastprivate

#include #include int main() { int idx = 100; int main_var = 2120; #pragma omp parallel for private(idx) lastprivate(main_var) for (idx = 0; idx < 12; ++idx) { main_var = idx * idx; printf("В потоке %d idx = %d main_var = %d\n", omp_get_thread_num(), idx, main_var); } printf("Возврат в главный поток со значением переменной main_var = %d\n", main_var); }

В листинге 19 представлены результаты выполнения кода из листинга 18.

Листинг 19. Результаты выполнения кода из листинга 18 (обратите внимание на то, что значение main_var always всегда равно 121 в главном потоке)

В потоке 3 idx = 6 main_var = 36 В потоке 2 idx = 4 main_var = 16 В потоке 1 idx = 2 main_var = 4 В потоке 4 idx = 8 main_var = 64 В потоке 5 idx = 10 main_var = 100 В потоке 3 idx = 7 main_var = 49 В потоке 0 idx = 0 main_var = 0 В потоке 2 idx = 5 main_var = 25 В потоке 1 idx = 3 main_var = 9 В потоке 4 idx = 9 main_var = 81 В потоке 5 idx = 11 main_var = 121 В потоке 0 idx = 1 main_var = 1 Возврат в главный поток со значением переменной main_var = 121

И последнее замечание: для поддержки оператора lastprivate объектом C++ требуется, чтобы соответствующий класс содержал доступный публичный метод operator= .

Сортировка слиянием в OpenMP

Рассмотрим реальный пример, в котором OpenMP сокращает время выполнения задачи. Возьмем не слишком оптимизированную версию процедуры merge sort , достаточную для демонстрации преимуществ от использования OpenMP. Этот пример приведен в листинге 20.

Листинг 20. Сортировка слиянием в OpenMP

#include #include #include using namespace std; vector merge(const vector& left, const vector& right) { vector result; unsigned left_it = 0, right_it = 0; while(left_it < left.size() && right_it < right.size()) { if(left < right) { result.push_back(left); left_it++; } else { result.push_back(right); right_it++; } } // Занесение оставшихся данных из обоих векторов в результирующий while(left_it < left.size()) { result.push_back(left); left_it++; } while(right_it < right.size()) { result.push_back(right); right_it++; } return result; } vector mergesort(vector& vec, int threads) { // Условие завершения: список полностью отсортирован, // если он содержит только один элемент. if(vec.size() == 1) { return vec; } // Определяем местоположение среднего элемента в векторе std::vector::iterator middle = vec.begin() + (vec.size() / 2); vector left(vec.begin(), middle); vector right(middle, vec.end()); // Выполнение сортировки слиянием над двумя меньшими векторами if (threads > 1) { #pragma omp parallel sections { #pragma omp section { left = mergesort(left, threads/2); } #pragma omp section { right = mergesort(right, threads - threads/2); } } } else { left = mergesort(left, 1); right = mergesort(right, 1); } return merge(left, right); } int main() { vector v(1000000); for (long i=0; i<1000000; ++i) v[i] = (i * i) % 1000000; v = mergesort(v, 1); for (long i=0; i<1000000; ++i) cout << v[i] << "\n"; }

При использовании 8 потоков для выполнения процедуры merge sort время выполнения сократилось с 3,7 (при использовании одного потока) до 2,1 секунды. Здесь необходимо лишь соблюдать осторожность с количеством потоков. Я начал с 8 потоков, но реальная отдача от их использования может варьироваться в зависимости от конфигурации системы. Если количество потоков не ограничено явным образом, то могут быть созданы сотни, если не тысячи потоков, что с очень высокой вероятностью приведет к снижению производительности системы. Кроме того, при работе с кодом merge sort полезно использовать прагму sections , которая была рассмотрена ранее.

Заключение

На этом я заканчиваю статью. Мы в достаточной мере рассмотрели прагмы parallel и способы создания потоков, убедились в том, что OpenMP уменьшает время выполнения задач и позволяет выполнять синхронизацию и гибкий контроль, а также рассмотрели практический пример с использованием merge sort . Конечно, вам еще предстоит изучить очень многое, и лучше всего поможет в этом Web-сайт проекта OpenMP. Всю дополнительную информацию вы можете найти в разделе .

Параллельное программирование на OpenMP

Введение..............................................................................................................................................
Параллельное программирование................................................................................................
Написание параллельных программ............................................................................................
Параллельные архитектуры..........................................................................................................
OpenMP................................................................................................................................................
Введение в OpenMP.......................................................................................................................
Программная модель OpenMP......................................................................................................
Как взаимодействуют потоки?.....................................................................................................
Основы OpenMP.................................................................................................................................
Синтаксис.......................................................................................................................................
Параллельные регионы.................................................................................................................
Модель исполнения.......................................................................................................................
Конструкции OpenMP........................................................................................................................
Условия выполнения.....................................................................................................................
Условия private, shared, default.................................................................................................
Условие firstprivate....................................................................................................................
Конструкции OpenMP для распределения работ........................................................................
Параллельный цикл for/DO....................................................................................................
Параллельные секции.............................................................................................................
Конструкция single..................................................................................................................
Условия выполнения (2)..............................................................................................................
Условие if.................................................................................................................................
Условие lastprivatе...................................................................................................................
Условие reduction....................................................................................................................
Условие schedule.....................................................................................................................
Условие ordered.......................................................................................................................
Переменные окружения OpenMP...............................................................................................
Библиотечные функции OpenMP ...................................................................................................
Зависимость по данным...................................................................................................................
Средства синхронизации в OpenMP...............................................................................................
Критическая секция.....................................................................................................................
Атомарна секция..........................................................................................................................
Барьеры.........................................................................................................................................
Фиксация порядка выполнения..................................................................................................
Конcтрукция flush........................................................................................................................
Расширенные возможности OpenMP..............................................................................................
Отладка OpenMP кода......................................................................................................................
Настройка производительности OpenMP кода..............................................................................
Основной подход.........................................................................................................................
Автоматическое расспаралеливание..........................................................................................
Профилирование программы......................................................................................................
Иерархия памяти..........................................................................................................................
Задачи................................................................................................................................................
Задача 1.........................................................................................................................................
Задача 2.........................................................................................................................................
Задача 3.........................................................................................................................................
Задача 4.........................................................................................................................................
Задача 5.........................................................................................................................................
Задача 6.........................................................................................................................................

Введение

Параллельное программирование

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

По сути весь вопрос заключается в минимизации соотношения цена/производительность. Ведь всегда можно построить (собрать) вычислительную систему, которая будет эффективно решать поставленную задачу, но адекватна ли будет при этом цена такого решения. Можно выделить два направления развития компьютерной техники: векторные машины (Cray) и кластеры (обычные компьютеры, стандартное ПО).

Написание параллельных программ

Разработка параллельных программ (ПП) состоит из трех основных этапов:

Декомпозиция задачи на подзадачи. Идеально, чтобы эти подзадачи работали независимо друг от друга (принцип локальности данных). Обмен данными между подзадачами является дорогой операцией, особенно, если это обмен по сети.

Распределение задачи по процессорам (виртуальным процессорам). В некоторых случаях решение этого вопроса можно оставить на усмотрение среды выполнения ПП.

Написание программы с использованием какой-либо параллельной библиотеки. Выбор библиотеки может зависеть от платформы, на которой программа будет выполняться, от требуемого уровня производительности и от природы самой задачи.

Параллельные архитектуры

В массе своей все вычислительные комплексы и компьютеры делятся на три группы:

Системы с распределенной памятью . Каждый процессор имеет свою память и не может напрямую доступаться к памяти другого процессора.

Разрабатывая программы подобные системы программист в явном виде должен задать всю систему коммуникаци (Передача сообщений – Message Passing). Библиотеки: MPI, PVM, Shmem (Cray only).

Системы с общей (разделяемой) памятью . Процессор может напрямую обращаться в память другого процессора. Процессоры могут сидеть на одной шине (SMP). Разделяемая память может быть физически распределенной, но тогда стоимость доступа к удаленной памяти может быть очень высока и это должен учитывать разработчик ПП.

Подходы к разработке ПО: Threads, директивы компилятора (OpenMP), механизм передачи сообщения.

Комбинированные системы . В кластерах могут объединяться компьютеры различной конфигурации.

• Канг Су Гэтлин
• Пит Айсенси

Реализация многопоточности без лишних усилий

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

Главные производители процессоров сместили акцент с повышения тактовых частот на реализацию параллелизма в самих процессорах за счет использования многоядерной архитектуры. Идея проста: интегрировать в один процессор более одного ядра. Система, включающая процессор с двумя ядрами, по сути, не отличается от двухпроцессорного компьютера, а система с четырехядерным процессором - от четырехпроцессорного. Этот подход позволяет избежать многих технологических проблем, связанных с повышением тактовых частот, и создавать при этом более производительные процессоры.

Все это прекрасно, но если ваше приложение не будет использовать несколько ядер, его быстродействие никак не изменится. Именно здесь и вступает в игру технология OpenMP, которая помогает программистам на C++ быстрее создавать многопоточные приложения.

Подробно описать OpenMP в одной статье просто немыслимо, так как это очень объемный и мощный API. Рассматривайте эту статью как введение, где демонстрируется применение различных средств OpenMP для быстрого написания многопоточных программ. Если вам понадобится дополнительная информация по этой тематике, мы рекомендуем обратиться к спецификации, доступной на сайте OpenMP (www.openmp.org), - она на удивление легко читается.

Активизация OpenMP в Visual C++

Стандарт OpenMP был разработан в 1997 г. как API, ориентированный на написание портируемых многопоточных приложений. Сначала он был основан на языке Fortran, но позднее включил в себя и C/C++. Последняя версия OpenMP - 2.0; ее полностью поддерживает Visual C++ 2005. Стандарт OpenMP поддерживается и платформой Xbox 360.

Прежде чем заниматься кодом, вы должны знать, как активизировать реализованные в компиляторе средства OpenMP. Для этого служит появившийся в Visual C++ 2005 параметр компилятора /openmp. (Вы можете активизировать директивы OpenMP на страницах свойств проекта, выбрав Configuration Properties, C/C++, Language и изменив значение свойства OpenMP Support.) Встретив параметр /openmp, компилятор определяет символ _OPENMP, с помощью которого можно выяснить, включены ли средства OpenMP. Для этого достаточно написать #ifndef _OPENMP.

OpenMP связывается с приложениями через библиотеку импорта vcomp.lib. Соответствующая библиотека периода выполнения называется vcomp.dll. Отладочные версии библиотек импорта и периода выполнения (vcompd.lib и vcompd.dll соответственно) поддерживают дополнительные сообщения об ошибках, генерируемых при некоторых недопустимых операциях. Имейте в виду, что Visual C++ не поддерживает статическое связывание с библиотекой OpenMP периода выполнения, хотя в версии для Xbox 360 это поддерживается.

Параллельная обработка в OpenMP

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

Параллельную обработку в OpenMP иллюстрирует рис. 1. Самая левая стрелка представляет основной поток, который выполняется в одиночестве, пока не достигает первого параллельного региона в точке 1. В этой точке основной поток создает группу потоков, и теперь все они одновременно выполняются в параллельном регионе.

В точке 2 три из этих четырех потоков, достигнув вложенного параллельного региона, создают новые группы потоков. Исходный основной и потоки, создавшие новые группы, становятся владельцами своих групп (основными в этих группах). Учтите, что потоки могут создавать новые группы в разные моменты или вообще не встретить вложенный параллельный регион.

В точке 3 вложенный параллельный регион завершается. Каждый поток вложенного параллельного региона синхронизирует свое состояние с другими потоками в этом регионе, но синхронизация разных регионов между собой не выполняется. В точке 4 заканчивается первый параллельный регион, а в точке 5 начинается новый. Локальные данные каждого потока в промежутках между параллельными регионами сохраняются.

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

Конструкции OpenMP

OpenMP прост в использовании и включает лишь два базовых типа конструкций: директивы pragma и функции исполняющей среды OpenMP. Директивы pragma, как правило, указывают компилятору реализовать параллельное выполнение блоков кода. Все эти директивы начинаются с #pragma omp. Как и любые другие директивы pragma, они игнорируются компилятором, не поддерживающим конкретную технологию - в данном случае OpenMP.

Функции OpenMP служат в основном для изменения и получения параметров среды. Кроме того, OpenMP включает API-функции для поддержки некоторых типов синхронизации. Чтобы задействовать эти функции библиотеки OpenMP периода выполнения (исполняющей среды), в программу нужно включить заголовочный файл omp.h. Если вы используете в приложении только OpenMP-директивы pragma, включать этот файл не требуется.

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

#pragma omp <директива> [раздел [ [,] раздел]...]

OpenMP поддерживает директивы parallel, for, parallel for, section, sections, single, master, critical, flush, ordered и atomic, которые определяют или механизмы разделения работы или конструкции синхронизации. В этой статье мы обсудим большинство директив.

Раздел (clause) - это необязательный модификатор директивы, влияющий на ее поведение. Списки разделов, поддерживаемые каждой директивой, различаются, а пять директив (master, critical, flush, ordered и atomic) вообще не поддерживают разделы.

Реализация параллельной обработки

Хотя директив OpenMP много, все они сразу нам не понадобятся. Самая важная и распространенная директива - parallel. Она создает параллельный регион для следующего за ней структурированного блока, например:

#pragma omp parallel [раздел[ [,] раздел]...] структурированный блок

Эта директива сообщает компилятору, что структурированный блок кода должен быть выполнен параллельно, в нескольких потоках. Каждый поток будет выполнять один и тот же поток команд, но не один и тот же набор команд - все зависит от операторов, управляющих логикой программы, таких как if-else.

В качестве примера рассмотрим классическую программу «Hello World»:

#pragma omp parallel { printf("Hello World\n"); }

В двухпроцессорной системе вы, конечно же, рассчитывали бы получить следующее:

Hello World Hello World

Тем не менее, результат мог бы оказаться и таким:

HellHell oo WorWlodrl d

Второй вариант возможен из-за того, что два выполняемых параллельно потока могут попытаться вывести строку одновременно. Когда два или более потоков одновременно пытаются прочитать или изменить общий ресурс (в нашем случае им является окно консоли), возникает вероятность гонок (race condition). Это недетерминированные ошибки в коде программы, найти которые крайне трудно. За предотвращение гонок отвечает программист; как правило, для этого используют блокировки или сводят к минимуму обращения к общим ресурсам.

Давайте взглянем на более серьезный пример, который определяет средние значения двух соседних элементов массива и записывает результаты в другой массив. В этом примере используется новая для вас OpenMP-конструкция #pragma omp for, которая относится к директивам разделения работы (work-sharing directive). Такие директивы применяются не для параллельного выполнения кода, а для логического распределения группы потоков, чтобы реализовать указанные конструкции управляющей логики. Директива #pragma omp for сообщает, что при выполнении цикла for в параллельном регионе итерации цикла должны быть распределены между потоками группы:

#pragma omp parallel { #pragma omp for for(int i = 1; i < size; ++i) x[i] = (y + y)/2; }

Если бы этот код выполнялся на четырехпроцессорном компьютере, а у переменной size было бы значение 100, то выполнение итераций 1-25 могло бы быть поручено первому процессору, 26-50 - второму, 51-75 - третьему, а 76-99 - четвертому. Это характерно для политики планирования, называемой статической. Политики планирования мы обсудим позднее.

Следует отметить, что в конце параллельного региона выполняется барьерная синхронизация (barrier synchronization). Иначе говоря, достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу.

Если из только что приведенного примера исключить директиву #pragma omp for, каждый поток выполнит полный цикл for, проделав много лишней работы:

#pragma omp parallel { for(int i = 1; i < size; ++i) x[i] = (y + y)/2; }

Так как циклы являются самыми распространенными конструкциями, где выполнение кода можно распараллелить, OpenMP поддерживает сокращенный способ записи комбинации директив #pragma omp parallel и #pragma omp for:

#pragma omp parallel for for(int i = 1; i < size; ++i) x[i] = (y + y)/2;

Обратите внимание, что в этом цикле нет зависимостей, т. е. одна итерация цикла не зависит от результатов выполнения других итераций. А вот в двух следующих циклах есть два вида зависимости:

For(int i = 1; i <= n; ++i) // цикл 1 a[i] = a + b[i]; for(int i = 0; i < n; ++i) // цикл 2 x[i] = x + b[i];

Распараллелить цикл 1 проблематично потому, что для выполнения итерации i нужно знать результат итерации i-1, т. е. итерация i зависит от итерации i-1. Распараллелить цикл 2 тоже проблематично, но по другой причине. В этом цикле вы можете вычислить значение x[i] до x, однако, сделав так, вы больше не сможете вычислить значение x. Наблюдается зависимость итерации i-1 от итерации i.

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

Кроме того, OpenMP налагает ограничения на циклы for, которые могут быть включены в блок #pragma omp for или #pragma omp parallel for block. Циклы for должны соответствовать следующему формату:

For([целочисленный тип] i = инвариант цикла; i {<,>,=,<=,>=} инвариант цикла; i {+,-}= инвариант цикла)

Эти требования введены для того, чтобы OpenMP мог при входе в цикл определить число итераций.

Сравнение поддержки потоков в OpenMP и Win32

Думаем, будет полезно сравнить только что приведенный пример, включающий директиву #pragma omp parallel for, с кодом, который пришлось бы написать для решения той же задачи на основе Windows API. Как видно в листинге 1, для достижения того же результата требуется гораздо больше кода, а за кулисами в этом варианте выполняются еще кое-какие операции. Так, конструктор класса ThreadData определяет, какими должны быть значения start и stop при каждом вызове потока. OpenMP обрабатывает все эти детали сам и предоставляет программисту дополнительные средства конфигурирования параллельных регионов и кода.

Листинг 1. Многопоточность в Win32

Class ThreadData { public: // Конструктор инициализирует поля start и stop ThreadData(int threadNum); int start; int stop; }; DWORD ThreadFn(void* passedInData) { ThreadData *threadData = (ThreadData *)passedInData; for(int i = threadData->start; i < threadData->stop; ++i) x[i] = (y + y) / 2; return 0; } void ParallelFor() { // Запуск групп потоков for(int i=0; i < nTeams; ++i) ResumeThread(hTeams[i]); // Для каждого потока здесь неявно вызывается // метод ThreadFn // Ожидание завершения работы WaitForMultipleObjects(nTeams, hTeams, TRUE, INFINITE); } int main(int argc, char* argv) { // Создание групп потоков for(int i=0; i < nTeams; ++i) { ThreadData *threadData = new ThreadData(i); hTeams[i] = CreateThread(NULL, 0, ThreadFn, threadData, CREATE_SUSPENDED, NULL); } ParallelFor(); // имитация OpenMP-конструкции parallel for // Очистка for(int i=0; i < nTeams; ++i) CloseHandle(hTeams[i]); }

Общие и частные данные

Разрабатывая параллельные программы, вы должны понимать, какие данные являются общими (shared), а какие частными (private), - от этого зависит не только производительность, но и корректная работа программы. В OpenMP это различие очевидно, к тому же вы можете настроить его вручную.

Общие переменные доступны всем потокам из группы, поэтому изменения таких переменных в одном потоке видимы другим потокам в параллельном регионе. Что касается частных переменных, то каждый поток из группы располагает их отдельными экземплярами, поэтому изменения таких переменных в одном потоке никак не сказываются на их экземплярах, принадлежащих другим потокам.

По умолчанию все переменные в параллельном регионе - общие, но из этого правила есть три исключения. Во-первых, частными являются индексы параллельных циклов for. Например, это относится к переменной i в коде, показанном в листинге 2. Переменная j по умолчанию не является частной, но явно сделана таковой через раздел firstprivate.

Листинг 2. Разделы директив OpenMP и вложенный цикл for

Float sum = 10.0f; MatrixClass myMatrix; int j = myMatrix.RowStart(); int i; #pragma omp parallel { #pragma omp for firstprivate(j) lastprivate(i) reduction(+: sum) for(i = 0; i < count; ++i) { int doubleI = 2 * i; for(; j < doubleI; ++j) { sum += myMatrix.GetElement(i, j); } } }

Во-вторых, частными являются локальные переменные блоков параллельных регионов. На рис. 3 такова переменная doubleI, потому что она объявлена в параллельном регионе. Любые нестатические и не являющиеся членами класса MatrixClass переменные, объявленные в методе myMatrix::GetElement, будут частными.

В-третьих, частными будут любые переменные, указанные в разделах private, firstprivate, lastprivate и reduction. В листинге 2 переменные i, j и sum сделаны частными для каждого потока из группы, т. е. каждый поток будет располагать своей копией каждой из этих переменных.

Каждый из четырех названных разделов принимает список переменных, но семантика этих разделов различается. Раздел private говорит о том, что для каждого потока должна быть создана частная копия каждой переменной из списка. Частные копии будут инициализироваться значением по умолчанию (с применением конструктора по умолчанию, если это уместно). Например, переменные типа int имеют по умолчанию значение 0.

У раздела firstprivate такая же семантика, но перед выполнением параллельного региона он указывает копировать значение частной переменной в каждый поток, используя конструктор копий, если это уместно.

Семантика раздела lastprivate тоже совпадает с семантикой раздела private, но при выполнении последней итерации цикла или раздела конструкции распараллеливания значения переменных, указанных в разделе lastprivate, присваиваются переменным основного потока. Если это уместно, для копирования объектов применяется оператор присваивания копий (copy assignment operator).

Похожая семантика и у раздела reduction, но он принимает переменную и оператор. Поддерживаемые этим разделом операторы перечислены в табл. 1, а у переменной должен быть скалярный тип (например, float, int или long, но не std::vector, int и т. д.). Переменная раздела reduction инициализируется в каждом потоке значением, указанным в таблице. В конце блока кода оператор раздела reduction применяется к каждой частной копии переменной, а также к исходному значению переменной.

Табл. 1. Операторы раздела reduction

В листинге 2 переменная sum неявно инициализируется в каждом потоке значением 0.0f (заметьте, что в таблице указано каноническое значение 0, но в данном случае оно принимает форму 0.0f, так как sum имеет тип float). После выполнения блока #pragma omp for над всеми частными значениями и исходным значением sum (которое в нашем случае равно 10.0f) выполняется операция +. Результат присваивается исходной общей переменной sum.

Параллельная обработка в конструкциях, отличных от циклов

Как правило, OpenMP используется для распараллеливания циклов, но OpenMP поддерживает параллелизм и на уровне функций. Этот механизм называется секциями OpenMP (OpenMP sections). Он довольно прост и часто бывает полезен.

Рассмотрим один из самых важных алгоритмов в программировании - быструю сортировку (quicksort). В качестве примера мы реализовали рекурсивный метод быстрой сортировки списка целых чисел. Ради простоты мы решили не создавать универсальную шаблонную версию метода, но суть дела от этого ничуть не меняется. Код нашего метода, реализованного с использованием секций OpenMP, показан в листинге 3 (код метода Partition опущен, чтобы не загромождать общую картину).

Листинг 3. Быстрая сортировка с использованием параллельных секций

Void QuickSort (int numList, int nLower, int nUpper) { if (nLower < nUpper) { // Разбиение интервала сортировки int nSplit = Partition (numList, nLower, nUpper); #pragma omp parallel sections { #pragma omp section QuickSort (numList, nLower, nSplit - 1); #pragma omp section QuickSort (numList, nSplit + 1, nUpper); } } }

В данном примере первая директива #pragma создает параллельный регион секций. Каждая секция определяется директивой #pragma omp section. Каждой секции в параллельном регионе ставится в соответствие один поток из группы потоков, и все секции выполняются одновременно. В каждой секции рекурсивно вызывается метод QuickSort.

Как и в случае конструкции #pragma omp parallel for, вы сами должны убедиться в независимости секций друг от друга, чтобы они могли выполняться параллельно. Если в секциях изменяются общие ресурсы без синхронизации доступа к ним, результат может оказаться непредсказуемым.

Обратите внимание на то, что в этом примере используется сокращение #pragma omp parallel sections, аналогичное конструкции #pragma omp parallel for. По аналогии с #pragma omp for директиву #pragma omp sections можно использовать в параллельном регионе отдельно.

По поводу кода, показанного в листинге 3, следует сказать еще пару слов. Прежде всего заметьте, что параллельные секции вызываются рекурсивно. Рекурсивные вызовы поддерживаются и параллельными регионами, и (как в нашем примере) параллельными секциями. Если создание вложенных секций разрешено, по мере рекурсивных вызовов QuickSort будут создаваться все новые и новые потоки. Возможно, это не то, что нужно программисту, так как такой подход может привести к созданию большого числа потоков. Чтобы ограничить число потоков, в программе можно запретить вложение. Тогда наше приложение будет рекурсивно вызывать метод QuickSort, используя только два потока.

При компиляции этого приложения без параметра /openmp будет сгенерирована корректная последовательная версия. Одно из преимуществ OpenMP в том, что эта технология совместима с компиляторами, не поддерживающими OpenMP.

Директивы pragma для синхронизации

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

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

Неявная барьерная синхронизация выполняется также в конце каждого блока #pragma omp for, #pragma omp single и #pragma omp sections. Чтобы отключить неявную барьерную синхронизацию в каком-либо из этих трех блоков разделения работы, укажите раздел nowait:

#pragma omp parallel { #pragma omp for nowait for(int i = 1; i < size; ++i) x[i] = (y + y)/2; }

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

Второй тип - явная барьерная синхронизация. В некоторых ситуациях ее целесообразно выполнять наряду с неявной. Для этого включите в код директиву #pragma omp barrier.

В качестве барьеров можно использовать критические секции. В Win32 API для входа в критическую секцию и выхода из нее служат функции EnterCriticalSection и LeaveCriticalSection. В OpenMP для этого применяется директива #pragma omp critical [имя]. Она имеет такую же семантику, что и критическая секция Win32, и опирается на EnterCriticalSection. Вы можете использовать именованную критическую секцию, и тогда доступ к блоку кода является взаимоисключающим только для других критических секций с тем же именем (это справедливо для всего процесса). Если имя не указано, директива ставится в соответствие некоему имени, выбираемому системой. Доступ ко всем неименованным критическим секциям является взаимоисключающим.

В параллельных регионах часто встречаются блоки кода, доступ к которым желательно предоставлять только одному потоку, - например, блоки кода, отвечающие за запись данных в файл. Во многих таких ситуациях не имеет значения, какой поток выполнит код, важно лишь, чтобы этот поток был единственным. Для этого в OpenMP служит директива #pragma omp single.

Иногда возможностей директивы single недостаточно. В ряде случаев требуется, чтобы блок кода был выполнен основным потоком, - например, если этот поток отвечает за обработку GUI и вам нужно, чтобы какую-то задачу выполнил именно он. Тогда применяется директива #pragma omp master. В отличие от директивы single при входе в блок master и выходе из него нет никакого неявного барьера.

Чтобы завершить все незавершенные операции над памятью перед началом следующей операции, используйте директиву #pragma omp flush, которая эквивалентна внутренней функции компилятора _ReadWriteBarrier.

Учтите, что OpenMP-директивы pragma должны обрабатываться всеми потоками из группы в одном порядке (или вообще не обрабатываться никакими потоками). Таким образом, следующий пример кода некорректен, а предсказать результаты его выполнения нельзя (вероятные варианты - сбой или зависание системы):

#pragma omp parallel { if(omp_get_thread_num() > 3) { #pragma omp single // код, доступный не всем потокам x++; } }

Подпрограммы исполняющей среды OpenMP

Помимо уже описанных директив OpenMP поддерживает ряд полезных подпрограмм. Они делятся на три обширных категории: функции исполняющей среды, блокировки/синхронизации и работы с таймерами (последние в этой статье не рассматриваются). Все эти функции имеют имена, начинающиеся с omp_, и определены в заголовочном файле omp.h.

Подпрограммы первой категории позволяют запрашивать и задавать различные параметры операционной среды OpenMP. Функции, имена которых начинаются на omp_set_, можно вызывать только вне параллельных регионов. Все остальные функции можно использовать как внутри параллельных регионов, так и вне таковых.

Чтобы узнать или задать число потоков в группе, используйте функции omp_get_num_threads и omp_set_num_threads. Первая возвращает число потоков, входящих в текущую группу потоков. Если вызывающий поток выполняется не в параллельном регионе, эта функция возвращает 1. Метод omp_set_num_thread задает число потоков для выполнения следующего параллельного региона, который встретится текущему выполняемому потоку. Кроме того, число потоков, используемых для выполнения параллельных регионов, зависит от двух других параметров среды OpenMP: поддержки динамического создания потоков и вложения регионов.

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

Вложение параллельных регионов также определяется булевым свойством, которое по умолчанию установлено в false. Вложение параллельных регионов происходит, когда потоку, уже выполняющему параллельный регион, встречается другой параллельный регион. Если вложение разрешено, создается новая группа потоков, при этом соблюдаются правила, описанные ранее. А если вложение не разрешено, формируется группа, содержащая один поток.

Для установки и чтения свойств, определяющих возможность динамического создания потоков и вложения параллельных регионов, служат функции omp_set_dynamic, omp_get_dynamic, omp_set_nested и omp_get_nested. Кроме того, каждый поток может запросить информацию о своей среде. Чтобы узнать номер потока в группе потоков, вызовите omp_get_thread_num. Помните, что она возвращает не Windows-идентификатор потока, а число в диапазоне от 0 до omp_get_num_threads - 1.

Функция omp_in_parallel позволяет потоку узнать, выполняет ли он в настоящее время параллельный регион, а omp_get_num_procs возвращает число процессоров в компьютере.

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

Листинг 4. Использование подпрограмм исполняющей среды OpenMP

#include #include int main() { omp_set_dynamic(1); omp_set_num_threads(10); #pragma omp parallel // параллельный регион 1 { #pragma omp single printf("Num threads in dynamic region is = %d\n", omp_get_num_threads()); } printf("\n"); omp_set_dynamic(0); omp_set_num_threads(10); #pragma omp parallel // параллельный регион 2 { #pragma omp single printf("Num threads in non-dynamic region is = %d\n", omp_get_num_threads()); } printf("\n"); omp_set_dynamic(1); omp_set_num_threads(10); #pragma omp parallel // параллельный регион 3 { #pragma omp parallel { #pragma omp single printf("Num threads in nesting disabled region is = %d\n", omp_get_num_threads()); } } printf("\n"); omp_set_nested(1); #pragma omp parallel // параллельный регион 4 { #pragma omp parallel { #pragma omp single printf("Num threads in nested region is = %d\n", omp_get_num_threads()); } } }

Скомпилировав этот код в Visual Studio 2005 и выполнив его на обычном двухпроцессорном компьютере, мы получили такой результат:

Num threads in dynamic region is = 2 Num threads in non-dynamic region is = 10 Num threads in nesting disabled region is = 1 Num threads in nesting disabled region is = 1 Num threads in nested region is = 2 Num threads in nested region is = 2

Для первого региона мы включили динамическое создание потоков и установили число потоков в 10. По результатам работы программы видно, что при включенном динамическом создании потоков исполняющая среда OpenMP решила создать группу, включающую всего два потока, так как у компьютера два процессора. Для второго параллельного региона исполняющая среда OpenMP создала группу из 10 потоков, потому что динамическое создание потоков для этого региона было отключено.

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

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

Omp_set_dynamic(0); omp_set_nested(1); omp_set_num_threads(10); #pragma omp parallel { #pragma omp parallel { #pragma omp single printf("Num threads in nested region is = %d\n", omp_get_num_threads()); } }

А происходит то, чего и следовало ожидать. Для первого параллельного региона создается группа из 10 потоков, затем при входе во вложенный параллельный регион для каждого из этих 10 потоков создается группа также из 10 потоков. В общей сложности вложенный параллельный регион выполняют 100 потоков:

Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10 Num threads in nested region is = 10

Методы синхронизации/блокировки

OpenMP включает и функции, предназначенные для синхронизации кода. В OpenMP два типа блокировок: простые и вкладываемые (nestable); блокировки обоих типов могут находиться в одном из трех состояний - неинициализированном, заблокированном и разблокированном.

Простые блокировки (omp_lock_t) не могут быть установлены более одного раза, даже тем же потоком. Вкладываемые блокировки (omp_nest_lock_t) идентичны простым с тем исключением, что, когда поток пытается установить уже принадлежащую ему вкладываемую блокировку, он не блокируется. Кроме того, OpenMP ведет учет ссылок на вкладываемые блокировки и следит за тем, сколько раз они были установлены.

OpenMP предоставляет подпрограммы, выполняющие операции над этими блокировками. Каждая такая функция имеет два варианта: для простых и для вкладываемых блокировок. Вы можете выполнить над блокировкой пять действий: инициализировать ее, установить (захватить), освободить, проверить и уничтожить. Все эти операции очень похожи на Win32-функции для работы с критическими секциями, и это не случайность: на самом деле технология OpenMP реализована как оболочка этих функций. Соответствие между функциями OpenMP и Win32 иллюстрирует табл. 2.

Табл. 2. Функции для работы с блокировками в OpenMP и Win32

Простая блокировка OpenMP	Вложенная блокировка OpenMP	Win32-функция
omp_lock_t	omp_nest_lock_t	CRITICAL_SECTION
omp_init_lock	omp_init_nest_lock	InitializeCriticalSection
omp_destroy_lock	omp_destroy_nest_lock	DeleteCriticalSection
omp_set_lock	omp_set_nest_lock	EnterCriticalSection
omp_unset_lock	omp_unset_nest_lock	LeaveCriticalSection
omp_test_lock	omp_test_nest_lock	TryEnterCriticalSection

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

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

Параллельная обработка структур данных

В листинге 5 показан код двух параллельно выполняемых циклов, в начале которых исполняющей среде неизвестно число их итераций. В первом примере выполняется перебор элементов STL-контейнера std::vector, а во втором - стандартного связанного списка.

Листинг 5. Выполнение заранее неизвестного числа итераций

#pragma omp parallel { // Параллельная обработка вектора STL std::vector::iterator iter; for(iter = xVect.begin(); iter != xVect.end(); ++iter) { #pragma omp single nowait { process1(*iter); } } // Параллельная обработка стандартного связанного списка for(LList *listWalk = listHead; listWalk != NULL; listWalk = listWalk->next) { #pragma omp single nowait { process2(listWalk); } } }

В примере с вектором STL каждый поток из группы потоков выполняет цикл for и имеет собственный экземпляр итератора, но при каждой итерации лишь один поток входит в блок single (такова семантика директивы single). Все действия, гарантирующие однократное выполнение блока single при каждой итерации, берет на себя исполняющая среда OpenMP. Такой способ выполнения цикла сопряжен со значительными издержками, поэтому он полезен, только если в функции process1 выполняется много работы. В примере со связанным списком реализована та же логика.

Стоит отметить, что в примере с вектором STL мы можем до входа в цикл определить число его итераций по значению std::vector.size, что позволяет привести цикл к канонической форме для OpenMP:

#pragma omp parallel for for(int i = 0; i < xVect.size(); ++i) process(xVect[i]);

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

Более сложные алгоритмы планирования

По умолчанию в OpenMP для планирования параллельного выполнения циклов for применяется алгоритм, называемый статическим планированием (static scheduling). Это означает, что все потоки из группы выполняют одинаковое число итераций цикла. Если n - число итераций цикла, а T - число потоков в группе, каждый поток выполнит n/T итераций (если n не делится на T без остатка, ничего страшного). Однако OpenMP поддерживает и другие механизмы планирования, оптимальные в разных ситуациях: динамическое планирование (dynamic scheduling), планирование в период выполнения (runtime scheduling) и управляемое планирование (guided scheduling).

Чтобы задать один из этих механизмов планирования, используйте раздел schedule в директиве #pragma omp for или #pragma omp parallel for. Формат этого раздела выглядит так:

Schedule(алгоритм планирования[, число итераций])

Вот примеры этих директив:

#pragma omp parallel for schedule(dynamic, 15) for(int i = 0; i < 100; ++i) ... #pragma omp parallel #pragma omp for schedule(guided)

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

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

Число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число итераций)

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

Если указать директиву #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

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

Последний подход - планирование в период выполнения - это скорее даже не алгоритм планирования, а способ динамического выбора одного из трех описанных алгоритмов. Если в разделе schedule указан параметр runtime, исполняющая среда OpenMP использует алгоритм планирования, заданный для конкретного цикла for при помощи переменной OMP_SCHEDULE. Она имеет формат «тип[,число итераций]», например:

Set OMP_SCHEDULE=dynamic,8

Планирование в период выполнения дает определенную гибкость в выборе типа планирования, при этом по умолчанию применяется статическое планирование.

Когда использовать OpenMP?

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

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

Приложение должно быть кроссплатформенным . OpenMP - кроссплатформенный и широко поддерживаемый API. А так как он реализован на основе директив pragma, приложение можно скомпилировать даже при помощи компилятора, не поддерживающего стандарт OpenMP.

Выполнение циклов нужно распараллелить . Весь свой потенциал OpenMP демонстрирует при организации параллельного выполнения циклов. Если в приложении есть длительные циклы без зависимостей, OpenMP - идеальное решение.

Перед выпуском приложения нужно повысить его быстродействие. Так как технология OpenMP не требует переработки архитектуры приложения, она прекрасно подходит для внесения в код небольших изменений, позволяющих повысить его быстродействие.

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

Создание как обычных потоков, так и параллельных регионов OpenMP имеет свою цену. Чтобы применение OpenMP стало выгодным, выигрыш в скорости, обеспечиваемый параллельным регионом, должен превосходить издержки на создание группы потоков. В версии OpenMP, реализованной в Visual C++, группа потоков создается при входе в первый параллельный регион. После завершения региона группа потоков приостанавливается, пока не понадобится вновь. За кулисами OpenMP использует пул потоков Windows. Рис. 2 иллюстрирует прирост быстродействия простой программы, приведенной в начале статьи, который достигается благодаря OpenMP на двухпроцессорном компьютере при различном числе итераций. Максимальный прирост быстродействия составляет примерно 1,7 от исходного, что типично для двухпроцессорных систем.

На данном графике ось y представляет отношение времени последовательного выполнения кода ко времени параллельного выполнения того же кода. Обратите внимание, что параллельная версия настигает по быстродействию последовательную примерно при 5000 итераций, но это почти что худший сценарий. Большинство параллельных циклов будут выполняться быстрее последовательных даже при значительно меньшем числе итераций. Это зависит от объема работы, выполняемой на каждой итерации. Как бы то ни было, этот график показывает, насколько важно оценивать производительность ПО. Само по себе применение OpenMP не гарантирует, что быстродействие вашего кода повысится.

OpenMP-директивы pragma просты в использовании, но не позволяют получать детальные сведения об ошибках. Если вы пишете критически важное приложение, которое должно определять ошибки и корректно восстанавливать нормальную работу, от OpenMP, пожалуй, следует отказаться (по крайней мере, пока). Например, если OpenMP не может создать потоки для параллельных регионов или критическую секцию, поведение программы становится неопределенным. В Visual C++ 2005 исполняющая среда OpenMP какое-то время продолжает пытаться выполнить нужную задачу, после чего сдается. В будущих версиях OpenMP мы помимо прочего собираемся реализовать стандартный механизм уведомления об ошибках.

Еще одна ситуация, в которой следует сохранять бдительность, имеет место при использовании потоков Windows вместе с потоками OpenMP. Потоки OpenMP создаются на основе потоков Windows, поэтому они прекрасно работают в одном процессе. Увы, OpenMP ничего не знает о потоках Windows, созданных другими модулями. Из этого вытекают две проблемы: во-первых, исполняющая среда OpenMP не ведет учет других потоков Windows, а во-вторых, методы синхронизации OpenMP не синхронизируют потоки Windows, потому что они не входят в группы потоков.

Ловушки, в которые можно попасть при использовании OpenMP

Хотя использовать OpenMP совсем несложно, некоторые моменты все же требуют к себе повышенного внимания. Например, индексная переменная самого внешнего параллельного цикла for является частной, а индексные переменные вложенных циклов for по умолчанию общие. При работе с вложенными циклами обычно требуется, чтобы индексы внутренних циклов были частными. Используйте для этого раздел private.

Разрабатывая приложения OpenMP, следует быть осторожным при генерации исключений C++. Если приложение генерирует исключение в параллельном регионе, оно должно быть обработано в том же регионе тем же потоком. Иначе говоря, исключение не должно покинуть регион. Как правило, все исключения, которые могут быть сгенерированы в параллельном регионе, следует перехватывать. Если не перехватить исключение в том же параллельном регионе, приложение скорее всего потерпит крах.

Чтобы можно было открыть структурированный блок, выражение

#pragma omp <директива> [раздел]

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

// Плохо #pragma omp parallel { // Ошибка компиляции } // Хорошо #pragma omp parallel { // Код }

Отлаживать приложения OpenMP в среде Visual Studio 2005 иногда трудно. В частности, определенные неудобства связаны со входом в параллельный регион и/или с выходом из него нажатием клавиши F10/F11. Это объясняется тем, что компилятор генерирует дополнительный код для вызова исполняющей среды и групп потоков. Отладчик об этом не знает, поэтому то, что вы увидите, может показаться вам странным. Мы рекомендуем установить точку прерывания в параллельном регионе и нажать F5, чтобы достичь ее. Чтобы выйти из параллельного региона, установите точку прерывания вне такого региона и нажмите F5.

При нахождении внутри параллельного региона в окне Threads Window отладчика будет отображаться информация о потоках, выполняемых в группе потоков. Идентификаторы этих потоков будут соответствовать не потокам OpenMP, а лежащим в их основе потокам Windows.

В настоящее время использовать с OpenMP оптимизацию, определяемую профилем (Profile Guided Optimization, PGO), нельзя. К счастью, технология OpenMP основана на директивах pragma, поэтому вы можете скомпилировать свое приложение с параметром /openmp и с PGO и узнать, какой подход более эффективен.

OpenMP и.NET

Высокопроизводительные вычисления мало у кого ассоциируются с.NET, но в Visual C++ 2005 эта ситуация улучшена. Особо стоит отметить то, что мы добились совместной работы OpenMP с управляемым C++-кодом. Для этого мы обеспечили совместимость параметра /openmp с /clr и /clr:OldSyntax. То есть вы можете использовать OpenMP для параллельного выполнения методов.NET-типов, которые подлежат сбору мусора. Учтите, что сейчас параметр /openmp не совместим ни с /clr:safe, ни с /clr:pure, но мы планируем исправить это.

Мы должны упомянуть одно важное ограничение, связанное с применением OpenMP в управляемом коде. Приложение, в котором задействованы средства OpenMP, следует использовать только в одном домене приложения. При загрузке другого AppDomain в процесс с уже загруженной исполняющей средой OpenMP приложение может потерпеть крах.

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