Автоматическое распараллеливание цикла for

 

В алгоритме, реализующем виртуальную ПЦР, в основном цикле происходит выборка строк, содержащих последовательность праймера, из массива. Далее, уже во вложенных циклах, ищутся точки входа этих строк в геномную последовательность и определяется длина теоретических ПЦР-фрагментов. При этом вычисления и их результаты для каждой конкретной строки не зависят друг от друга. Таким образом этот цикл является «идеальным», то есть способен к неограниченному распораллеливанию, когда число параллельно выполняющихся операций может быть равно числу итераций цикла при последовательном выполнении. А так как данный алгоритм оказался наиболее затратным по времени выполнения, то распораллеливание его при наличии многоядерной или многопоточной процессорной архитектуры является актуальным.

OpenMP (Open Multi-Processing) - открытый стандарт для распараллеливания программ на языках Си, Си++ и Фортран. Основная возможность OpenMP – распределение нагрузки между потоками при обработке циклов. Компилятор GCC поддерживает стандарт OpenMP 2.5 начиная с версии 4.2, OpenMP 3.0 с версии 4.4 и OpenMP 3.1 с версии 4.7. Активация поддержки OpenMP в компиляторе GCC включается путём использования ключа –fopenmp.

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

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

· переменная цикла должна иметь тип signed integer. Беззнаковые целые числа, такие как DWORD, работать не будут.

· операция сравнения должна иметь следующий формат: переменная_цикла <, ≤, >, ≥ инвариант_цикла_целого_типа;

· третье выражение (или инкрементная часть цикла for) должно являться либо целочисленным сложением, либо целочисленным вычитанием и должно практически совпадать со значением инварианта цикла;

· если используется операция сравнения < или ≤, переменная цикла должна увеличиваться при каждой итерации, а при использовании операции > или ≥ переменная цикла должна уменьшаться.

· цикл должен являться базовым блоком. Это означает, что не разрешены переходы из цикла, за исключением оператора exit, который завершает работу всего приложения. Если используются операторы goto или break, они должны приводить к переходам внутри цикла, а не вне его. То же самое относится к обработке исключений; исключения должны перехватываться внутри цикла.

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

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

Конструкция #pragma в языке Си используется для задания дополнительных указаний компилятору. С помощью этих конструкций можно указать как осуществлять выравнивание данных в структурах, запретить выдавать определенные предупреждения и так далее. Форма записи директив:

#pragma директивы

Использование специальной ключевой директивы «omp» указывает на то, что команды относятся к OpenMP. Таким образом директивы #pragma для работы с OpenMP имеют следующий формат:

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

Как и любые другие директивы #pragma, они игнорируются теми компиляторами, которые не поддерживают данную технологию. При этом программа компилируется без ошибок как последовательная. Это особенность позволяет создавать хорошо переносимый код на базе технологии OpenMP. Код содержащий директивы OpenMP может быть скомпилирован Си компилятором, который ничего не знает об этой технологии. Код будет выполнятся как последовательный, но это лучше, чем делать две ветки кода или расставлять множество #ifdef. OpenMP поддерживает директивы private, parallel, for, section, sections, single, master, critical, flush, ordered и atomic и ряд других, которые определяют механизмы разделения работы или конструкции синхронизации.

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

#pragma omp parallel [другие директивы]

структурированный блок

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

Для того, чтобы распараллелить цикл нам необходимо использовать директиву разделения работы «for». Директива #pragma omp for сообщает, что при выполнении цикла for в параллельном регионе итерации цикла должны быть распределены между потоками группы. При этом в конце параллельного региона выполняется барьерная синхронизация. Иначе говоря, достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу.

Относительно параллельных регионов данные могут быть общими (shared) или частными (private). Частные данные принадлежат потоку и могут быть модифицированы только им. Общие данные доступны всем потокам. Если переменная объявлена вне параллельного региона, то по умолчанию она считается общей, а если внутри то частной.

Для того чтобы сделать переменную для каждого потока частной (private) существуют два способа: первый - объявить переменную внутри параллельного региона, и второй - воспользоваться директивой private. Помимо директивы private, существует и директива shared. Но эту директиву обычно не используют, так как и без нее все переменные объявленные вне параллельного региона будут общими.

Также в OpenMP существует функция omp_set_num_threads, позволяющая непосредственно задавать количество параллельных процессов.

 

В нашей программе распараллеливание было организовано следующим образом:

 

#include <omp.h>

…

int main(int args, char ** argv){

cpu=atoi(argv[1]);

omp_set_num_threads(cpu);

…

#pragma omp parallel for private(penter), private(pend), private(pp), private(p)

for (j=0; j<lenf; j=j+32){

…

}

}

 

Эффективность распараллеливания оценивали при тех же условиях, что и работу алгоритмов поиска подстроки в строке, то есть для первых 100 строк из массива. Оценка эффективности проводилась для каждого алгоритма поиска подстроки. Основным критерием успешности распараллеливания, было совпадение результатов последовательного и параллельного вычислений. Запуск каждой программы повторяли трижды. Среде время выполнения программ с распараллеленным циклом приведено в таблице 2.2.

 

Таблица 2.2.

Время выполнения программы с распараллеленным циклом for.

Кол-во потоков	Время выполнения программы, сек.
strstr	Примитивный алгоритм	Алгоритм КМП	Примитивный алгоритм (ассемблер)	Алгоритм КМП (ассемблер)	Алгоритм Бойера-Мура	Турбо алгоритм Бойера-Мура	Алгоритм Чжу-Такаоки	Алгоритм GRASPM	Алгоритм быстрого поиска	Алгоритм сдвига-или	Алгоритм Карпа-Рабина
	64,323	101,514	76,813	55,174	47,168	17,847	26,049	11,890	24,391	23,945	51,475	54,067
	35,366	58,654	43,141	34,541	26,899	10,025	15,849	7,567	15,259	14,482	31,349	31,833

 

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