Учебное пособие саранск издательство свмо 2013 2 удк 004. 42 Ббк з97 Авторский знак о753
 Скачать 6.58 Mb.
|
|
Процессоры номер и тип итерации 1 2 3 4 Исходные данные 13 55 59 88 29 43 71 85 2 18 40 75 4 14 22 43 1 нечет (1, 2), 13 55 59 88 29 43 71 85 2 18 40 75 4 14 22 43 44 (3, 4) 13 29 43 55 59 71 85 88 2 4 14 18 22 40 43 75 13 29 43 55 59 71 85 88 2 4 14 18 22 40 43 75 2 чет (2, 3) 13 29 43 55 2 4 14 18 59 71 85 88 22 40 43 75 13 29 43 55 2 4 14 18 59 71 85 88 22 40 43 75 3 нечет (1, 2), (3, 4) 2 4 13 14 18 29 43 55 22 40 43 59 71 75 85 88 2 4 13 14 18 29 43 55 22 40 43 59 71 75 85 88 4 чет (2, 3) 2 4 13 14 18 22 29 40 43 43 55 59 71 75 85 88 45 3. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ТЕХНОЛОГИИ OPENMP 3.1 Введение в технологию OpenMP Технология OpenMP является одним из наиболее популярных средств программирования для компьютерных систем с общей памятью, базирующихся на традиционных языках программирования. OpenMP состоит из набора директив для компиляторов и библиотек специальных функций [1,4,5]. Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), в которую вошли представители крупнейших компаний - разработчиков SMP-архитектур и программного обеспечения. Спецификации для языков Fortran и C/C++ появились соответственно в октябре 1997 года и октябре 1998 года. До появления OpenMP не было подходящего стандарта для эффективного программирования на SMP-системах. Наиболее гибким, переносимым и общепринятым интерфейсом параллельного программирования является MPI (интерфейс передачи сообщений). Однако модель передачи сообщений 1) недостаточно эффективна на SMP- системах; 2) относительно сложна в освоении, так как требует мышления в "невычислительных" терминах. Проект стандарта X3H5 провалился, так как был предложен во время всеобщего интереса к MPP-системам, а также из-за того, что в нем поддерживается только параллелизм на уровне циклов. OpenMP развивает многие идеи X3H5. POSIX-интерфейс для организации нитей (Pthreads) поддерживается широко (практически на всех UNIX-системах), однако по многим причинам не подходит для практического параллельного программирования: - нет поддержки Fortran-а - слишком низкий уровень - нет поддержки параллелизма по данным - механизм нитей изначально разрабатывался не для целей организации параллелизма. OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (или аналогичными библиотеками нитей). Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживают спецдирективыдля распараллеливания циклов. Однако эти наборы директив, как правило, весьма ограничены и несовместимы между собой, в результате чего разработчикам приходится распараллеливать приложение отдельно для каждой платформы. OpenMP 46 является во многом обобщением и расширением упомянутых наборов директив. В настоящее время OpenMP поддерживается большинством разработчиков параллельных вычислительных систем: компаниями Intel, Hewlett-Packard, Silicon Graphics, Sun, IBM, Fujitsu, Hitachi, Siemens, Bull и другими. Многие известные компании в области разработки системного программного обеспечения такие, как Intel, KAI, PGI, PSR, APR, Absoft, также уделяют значительное внимание разработке системного программного обеспечения с OpenMP. Одним из важных достоинств технологии OpenMP является реализация идеи «инкрементального программирования», когда разработчик постепенно находит участки в программе, содержащие ресурс параллелизма, с помощью предоставляемых механизмов делает их параллельными и затем переходит к анализу следующих участков. Таким образом данный подход упрощает процесс адаптации последовательных программ к параллельным ЭВМ. OpenMP может использоваться совместно с другими технологиями параллельного программирования, например, с MPI. Обычно в этом случае MPI используется для распределения работы между несколькими вычислительными узлами, а OpenMP затем используется для распараллеливания на одном узле. 3.2 Основные понятия 3.2.1 Модель параллельной программы В OpenMP распараллеливание выполняется при помощи вставки в текст программы специальных директив, вызова вспомогательных функций и использования переменных окружения. При использовании OpenMP предполагается SPMD-модель (Single ProgramMultiple Data) параллельного программирования, в рамках которой для всех параллельных нитей используется один и тот же код. При выполнении параллельной программы работа начинается с инициализации и выполнения главного потока (процесса), который по мере необходимости создает и выполняет параллельные потоки, передавая им необходимые данные. Параллельные потоки из одной параллельной области программы могут выполняться как независимо друг от друга, так и с пересылкой и получением сообщений от других параллельных потоков. Последнее обстоятельство усложняет разработку программы, поскольку в этом случае программисту приходится заниматься планированием, организацией и синхронизацией посылки сообщений между параллельными потоками. Таким образом, при разработке 47 параллельной программы желательно выделять такие области распараллеливания, в которых можно организовать выполнение независимых параллельных потоков. Для обмена данными между параллельными процессами (потоками) в OpenMP используются общие переменные. При обращении к общим переменным в различных параллельных потоках возможно возникновение конфликтных ситуаций при доступе к данным. Для предотвращения конфликтов можно воспользоваться процедурой синхронизации. При этом надо иметь в виду, что процедура синхронизации - очень дорогая операция по временным затратам и желательно по возможности избегать ее или применять как можно реже. Выполнение параллельных потоков в параллельной области программы начинается с их инициализации. Она заключается в создании дескрипторов порождаемых потоков и копировании всех данных из области данных главного потока в области данных создаваемых параллельных потоков. После порождения потоки нумеруются последовательными натуральными числами, причем главный поток имеет номер 0. После завершения выполнения параллельных потоков управление программой вновь передается главному потоку. При этом возникает проблема корректной передачи данных от параллельных потоков главному. Здесь важную роль играет синхронизация завершения работы параллельных потоков, поскольку в силу целого ряда обстоятельств время выполнения даже одинаковых по трудоемкости параллельных потоков непредсказуемо (оно определяется как историей конкуренции параллельных процессов, так и текущим состоянием вычислительной системы). При выполнении операции синхронизации параллельные потоки, уже завершившие свое выполнение, простаивают и ожидают завершения работы самого последнего потока. Естественно, при этом неизбежна потеря эффективности работы параллельной программы. Для того чтобы получить параллельную версию, сначала необходимо определить ресурс параллелизма программы, то есть, найти в ней участки, которые могут выполняться независимо разными нитями. Если таких участков относительно немного, то для распараллеливания чаще всего используются конструкции, задающие конечный (неитеративный) параллелизм. Однако, как показывает практика, наибольший ресурс параллелизма в программах сосредоточен в циклах. Поэтому наиболее распространенным способом распараллеливания является то или иное распределение итераций циклов. Если между итерациями некоторого цикла нет информационных зависимостей, то их можно каким-либо 48 способом раздать разным процессорам для одновременного исполнения. Различные способы распределения итераций позволяют добиваться максимально равномерной загрузки нитей, между которыми распределяются итерации цикла. Статический способ распределения итераций позволяет уже в момент написания программы точно определить, какой нити достанутся какие итерации. Однако он не учитывает текущей загруженности процессоров, соотношения времён выполнения различных итераций и некоторых других факторов. Эти факторы в той или иной степени учитываются динамическими способами распределения итераций. Кроме того, возможно отложить решение по способу распределения итераций на время выполнения программы (например, выбирать его, исходя из текущей загруженности нитей) или возложить выбор распределения на компилятор и/или систему выполнения. Обмен данными в OpenMP происходит через общие переменные. Это приводит к необходимости разграничения одновременного доступа разных нитей к общим данным. Для этого предусмотрены достаточно развитые средства синхронизации. При этом нужно учитывать, что использование излишних синхронизаций может существенно замедлить программу [3,11]. Программа, созданная с использованием технологии OpenMP, может быть использована и в качестве последовательной программы. Таким образом, нет необходимости поддерживать последовательную и параллельную версии. Директивы OpenMP просто игнорируются последовательным компилятором, а для вызова функций OpenMP могут быть подставлены специальные «заглушки» (stubs), текст которых приведен в описании стандарта. Они гарантируют корректную работу программы в последовательном случае – нужно только перекомпилировать программу и подключить другую библиотеку. 3.2.2 Директивы и функции Значительная часть функциональности OpenMP реализуется при помощи директив компилятору. Они должны быть явно вставлены пользователем, что позволит выполнять программу в параллельном режиме. Директивы OpenMP в программах на языке Си являются указаниями препроцессору, начинающимися с #pragma omp. Формат директивы на Си/Си++: #pragma omp <имя директивы> [опция [[, ] опция …] 49 Объектом действия большинства директив является один оператор или блок, перед которым расположена директива в исходном тексте программы. В OpenMP такие операторы или блоки называются ассоциированными с директивой. Ассоциированный блок должен иметь одну точку входа в начале и одну точку выхода в конце. Порядок опций в описании директивы несущественен, в одной директиве большинство опций может встречаться несколько раз. После некоторых опций может следовать список переменных, разделяемых запятыми. Каждая директива может иметь несколько дополнительных атрибутов – опций (clause). Отдельно специфицируются опции для назначения классов переменных, которые могут быть атрибутами различных директив. Опция (clause) – это необязательный модификатор директивы, влияющий на ее поведение. Списки опций, поддерживаемые каждой директивой, различаются, а пять директив (master, critical, flush, ordered и atomic) вообще не поддерживают опции. OpenMP поддерживает директивы parallel, for, parallelfor, section, sections, single, master, critical, flush, ordered и atomic, и ряд других, которые определяют механизмы разделения работы или конструкции синхронизации. Все директивы OpenMP можно разделить на 3 категории: определение параллельной области, распределение работы, синхронизация. Чтобы задействовать функции библиотеки OpenMP периода выполнения (исполняющей среды), в программу нужно включить заголовочный файл omp.h. Если вы используете в приложении только OpenMP-директивы, включать этот файл не требуется. Функции назначения параметров имеют приоритет над соответствующими переменными окружения. Все функции, используемые в OpenMP, начинаются с префикса omp_. Если пользователь не будет использовать в программе имён, начинающихся с такого префикса, то конфликтов с объектами OpenMP заведомо не будет. В языке Си, кроме того, является существенным регистр символов в названиях функций. Названия функций OpenMP записываются строчными буквами [1,6]. 3.3 Основные конструкции OpenMP 3.3.1 Параллельные секции, переменные среды и замер времени Параллельная область задается при помощи директивы parallel: 50 #pragma omp parallel [опция [[, ] опция …] Рассмотрим возможные опции данной директивы. num_threads (целочисленное выражение) – задание количества нитей, которые будут выполнять параллельную область; по умолчанию выбирается последнее значение, установленное с помощью функции omp_set_num_treads(), или значение переменной OMP_NUM_THREADS. Пример 3.1. int main() { omp_set_num_threads(4); #pragma omp parallel { printf ("Hello, world!"); } return 0; } В данном примере создается 4 нити, каждая из которых выводит на экран строку «Hello, world!». if(условие) – определяет условие выполнения параллельных потоков в последующем параллельном структурном блоке; если условие принимает значение истина, то потоки в последующем параллельном структурном блоке выполняются, в противном случае не выполняются. shared(список) – задает список переменных, размещающихся в одной и той же области памяти для всех потоков. private(список) – задает список переменных, локальных для каждого из параллельных потоков; в каждом из потоков эти переменные имеют собственные значения и относятся к различным областям памяти: локальным областям памяти каждого конкретного параллельного потока. default(shared | none) – всем переменным параллельной области, которым явно не назначен класс shared; none означает, что всем переменным параллельной области должен быть явно назначен класс. firstprivate(список) – задает список переменных, для которых порождается локальная копия для каждой нити, значения этих переменных инициализируются их значениями в нити-мастере. copyin(список) – определяет список локальных переменных, которым присваиваются значения из одноименных общих переменных, заданных в глобальном потоке. 51 reduction(оператор: список) – определяется оператор - операции ( +, -, *, / и т. п.) или функции, для которых будут вычисляться соответствующие частичные значения в параллельных потоках последующего параллельного структурного блока; кроме того, определяется список локальных переменных, в котором будут сохраняться соответствующие частичные значения; после завершения всех параллельных процессов частичные значения складываются (вычитаются, перемножаются и т. п.), и результат сохраняется в одноименной общей переменной [3,5]. Пример 3.2. int main() { int n = 0; #pragma omp parallel reduction (+: count) { n++; printf("Текущее значение n: %d\n", count); } return 0; } В данном примере каждая нить инициализирует переменную n значением 0. Затем все нити увеличивают это значение на 1. При выходе из параллельной области значение n будет равно количеству порожденных нитей. В OpenMP предусмотрены функции для работы с системным таймером. Функция omp_get_wtime()возвращает в вызвавшей нити астрономическое время в секундах (вещественное число двойной точности), прошедшее с некоторого момента в прошлом. Если некоторый участок программы окружить вызовами данной функции, то разность возвращаемых значений покажет время работы данного участка. Гарантируется, что момент времени, используемый в качестве точки отсчета, не будет изменён за время существования процесса. Таймеры разных нитей могут быть не синхронизированы и выдавать различные значения. Функция omp_get_wtick()возвращает в вызвавшей нити разрешение таймера в секундах. Это время можно рассматривать как меру точности таймера. Пример 3.3. #include 52 #include int main() { double start, end; start= omp_get_wtime(); end= omp_get_wtime(); printf("Время выполнения %lf\n", end_time-start_time); return 0; } В примере происходит замер начального времени, а затем конечного. Результатом программы является время на замер времени, которое дает разность времен. В параллельной области каждой имеющейся нитью может быть порождена параллельная секция и последующее их соединение с сохранением главенства порождающей нити. Число нитей в параллельной секции можно задавать с помощью функции omp_set_num_threads(). Эта функция устанавливает значение переменной OMP_NUM_THREADS. Пример 3.4. int main() { omp_set_num_threads(3); int thread; #pragma omp parallel { thread=omp_get_thread_num(); printf (thread); } return 0; } В примере каждая из порожденных нитей выводит на экран свой номер. В некоторых случаях система может динамически изменять количество нитей, используемых для выполнения параллельной области, например, для оптимизации использования ресурсов системы. Это разрешено делать, если значение переменной среды OMP_DYNAMIC установлено в 1, что можно сделать с помощью функции omp_set_dynamic(). Получить значение переменной OMP_DYNAMIС можно с помощью функции omp_get_dynamic(). 53 Пример 3.5. #include #include int main() { omp_set_dynamic(1); printf("Значение OMP_DYNAMIC: %d\n", omp_get_dynamic()); #pragma omp parallel num_threads(100) { #pragma omp master { printf("Параллельная область, %d нитей\n", omp_get_num_threads()); } } return 0; } В примере сначала устанавливается значение переменной OMP_DYNAMIC в true.Затем порождается параллельная область со 100 потоками, в которой главным потоком выводится реальное число выполняющих операцию нитей. Стратегию обработки вложенных секций можно менять с помощью задания значений переменной среды |