Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

диссертация

на соискание степени магистра по направлению

Информатика и вычислительная техника» магистерская программа

Высокопроизводительные вычислительные системы

Решение задачи о ранце на многопроцессорных системах с общей памятью

Москва

Зеленоград, 2010г.

Введение

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

Структура и объем работы

Данная работа состоит из введения, дающего общие представления об основных задачах численного интегрирования, четырех глав, заключения и списка литературы.

Краткое содержание работы :

В первой главе рассмотрены технологии параллельного программирования, компилятор OpenMP (Open Multi-Processing) и MPI (Message Passing Interface).

Во второй главе рассматривается постановка задачи о ранце и пример решения задачи о ранце на С++.

Третья глава описывает решение задачи о ранце на OpenMP со многими потоками.

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

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

параллельное программирование задача ранец

1.1 Технологии параллельного программирования

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

Проектирование. Парадигмы и модели программирования, привязка будущих программ к аппаратной платформе.

Разработка. Средства разработки параллельных программ: коммуникационные интерфейсы, параллельные языки и расширения языков Fortran и C/C++, специализированные библиотеки, средства автоматического распараллеливания, инструментальные системы, специализированные прикладные пакеты.

Отладка и мониторинг. Средства анализа и мониторинга производительности параллельных программ.

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

MPI (Message Passing Interface)

OpenMP (стандарт для программирования в модели общей памяти)

Российские разработки:

V-Ray. Комплекс инструментальных средств, направленных на автоматизацию создания и оптимизацию параллельных программ для современных суперкомпьютерных систем. Разработка НИВЦ МГУ.

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

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

1.2 OpenMP (Open Multi-Processing)

OpenMP (Open Multi-Processing) это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с единой памятью на языках C, C++ и Fortran.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB). Детальная спецификация OpenMP находится на странице.

Архитектура OpenMP

1.3 Функция OpenMP

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

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка -- прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой:!$OMP PARALLEL PRIVATE(N)

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

Существующие реализации OpenMP

OpenMP поддерживается многими коммерческими компиляторами.

Компиляторы Sun Studio поддерживают официальную спецификацию -- OpenMP 2.5- с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.

Visual C++ 2005 поддерживает OpenMP в редакциях Professional и Team System.

GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.

Intel C Compiler

IBM XL compiler

PGI (Portland group)

Pathscale

HP

Модель выполнения приложения OpenMP

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

Модель выполнения OpenMP

Распараллеливание в OpenMP выполняется явно при помощи вставки в текст программы специальных директив, а также вызова вспомогательных функций. При использовании OpenMP предполагается SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных нитей используется один и тот же код.

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

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

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

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

Компиляция программы

Для использования механизмов OpenMP нужно скомпилировать программу компилятором, поддерживающим OpenMP, с указанием соответствующего ключа (например, в icc/ifort используется ключ компилятора -openmp, в gcc /gfortran -fopenmp, Sun Studio -xopenmp, в Visual С++ - /орепшр, в PGI -mp). Компилятор интерпретирует директивы OpenMP и создаёт параллельный код. При использовании компиляторов, не поддерживающих OpenMP, директивы OpenMP игнорируются без дополнительных сообщений.

Компилятор с поддержкой OpenMP определяет макрос _openmp, который может использоваться для условной компиляции отдельных блоков, характерных для параллельной версии программы. Этот макрос определён в формате yyyymm, где уууу и mm - цифры года и месяца, когда был принят поддерживаемый стандарт OpenMP. Например, компилятор, поддерживающий стандарт OpenMP 3.0, определяет _openmp в 200805.

Для проверки того, что компилятор поддерживает какую-либо версию OpenMP, достаточно написать директивы условной компиляции #ifdef или #ifndef. Простейшие примеры условной компиляции в программах на языках Си и Фортран приведены в примере 1.

#include<stdio.h>

int main()

{

#ifdef _OPENMP

printf("OpenMP is supported!\n");

#endif

}

Пример la. Условная компиляция на языке Си.

program examplelb

#ifdef _OPENMP

print *, "OpenMP is supported!"

#endif

end

Пример lb. Условная компиляция на языке Фортран.

Для условной компиляции программ на Фортране строки могут также начинаться с пары символов ! $, с$ или *$. В этом случае компилятор, поддерживающий OpenMP, заменит пару этих символов на два пробела, таким образом «раскомментировав» их. Пример 1с показывает использование такого варианта условной компиляции.

program examplelc

!$ print *, "OpenMP is supported!"

end

Пример lc. Условная компиляция на языке Фортран.

Директивы и функции

Значительная часть функциональности OpenMP реализуется при помощи директив компилятору. Они должны быть явно вставлены пользователем, что позволит выполнять программу в параллельном режиме. Директивы OpenMP в программах на языке Фортран оформляются комментариями и начинаются с комбинации символов ! $омр, с$омр или *$омр, а в языке Си -- указаниями препроцессору, начинающимися с #pragma omp. Ключевое слово ошр используется для того, чтобы исключить случайные совпадения имён директив OpenMP с другими именами.

Формат директивы на Си/Си++:

#pragma ошр directive-name [опция[[,] опция]...] Формат директивы на Фортране:

!$ОМР directive-name [опция[[,] опция]...] С$ОМР directive-name [опция[[,] опция]...] *$ОМР directive-name [опция[[,] опция]...]

Объектом действия большинства директив является один оператор или блок, перед которым расположена директива в исходном тексте программы. В OpenMP такие операторы или блоки называются ассоциированными с директивой. Ассоциированный блок должен иметь одну точку входа в начале и одну точку выхода в конце. Порядок опций в описании директивы несущественен, в одной директиве большинство опций может встречаться несколько раз. После некоторых опций может следовать список переменных (для Фортрана также и имён COMMON-блоков, заключённых в слеши), разделяемых запятыми.

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

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

Все функции, используемые в OpenMP, начинаются с префикса ошр_. Если пользователь не будет использовать в программе имён, начинающихся с такого префикса, то конфликтов с объектами OpenMP заведомо не будет. В языке Си, кроме того, является существенным регистр символов в названиях функций. Названия функций OpenMP записываются строчными буквами.

Для того чтобы программа, использующая функции OpenMP, могла оставаться корректной для обычного компилятора, можно прилинковать специальную библиотеку, которая определит для каждой функции соответствующую «заглушку» (stub). Например, в компиляторе Intel соответствующая библиотека подключается заданием ключа -openmp-stubs.

Выполнение программы

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

export OMP_NUM_THREADS=n

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

Замер времени

В OpenMP предусмотрены функции для работы с системным таймером.

Функция omp_get_wtime () возвращает в вызвавшей нити астрономическое время в секундах (вещественное число двойной точности), прошедшее с некоторого момента в прошлом.

Си:

double omp_get_wtime (void) ;

Фортран:

double precision function omp_get_wtime()

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

Функция omp_get_wtick () возвращает в вызвавшей нити разрешение таймера в секундах. Это время можно рассматривать как меру точности таймера.

Си:

double omp_get_wtick (void) ;

Фортран:

double precision function omp_get_vrtick ()

Пример 2: иллюстрирует применение функций omp_get_wtime () и omp_get_wtick () для работы с таймерами в OpenMP. В данном примере производится замер начального времени, затем сразу замер конечного времени. Разность времён даёт время на замер времени. Кроме того, измеряется точность системного таймера.

#include <stdio.h>

#include <omp.h>

int main(int argc, char *argv[])

{

double start_time, end_time, tick;

start_time = omp_get_wtime();

end_time = omp_get_wtime();

tick = omp_get_wtick();

printf("Время на замер времени %lf\n", end_time-start_time); printf("Точность таймера %lf\n", tick);

}

Пример 2a. Работа с системными таймерами на языке Си.

program example2b

include "omp_lib.h"

double precision start_time, end_time, tick

start_time = omp_get_wtime()

end_time = omp_get_wtime()

tick = omp_get_wtick()

print *, "Время на замер времени ", end_time-start_time

print *, "Точность таймера ", tick

end

Пример 2b. Работа с системными таймерами на языке Фортран.

Параллельные и последовательные области

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

Директива parallel

Параллельная область задаётся при помощи директивы parallel

(parallel . . . end parallel).

Си:

#pragma omp parallel [опция[[,] опция]...]

Фортран:

!$omp parallel [опция[[,] опция]...] <код параллельной области> !$omp end parallel

Возможные опции:

if (условие) - выполнение параллельной области по условию. Вхождение в параллельную область осуществляется только при выполнении некоторого условия. Если условие не выполнено, то директива не срабатывает и продолжается обработка программы в прежнем режиме;

num_threads (целочисленное выражение) -- явное задание количества нитей, которые будут выполнять параллельную область; по умолчанию выбирается последнее значение, установленное с помощью функции omp_set_num_threads (), или значение переменной OMP_NUM_THREADS;

default (private | firstprivate | shared | none) -- всем переменным в параллельной области, которым явно не назначен класс, будет назначен класс private, firstprivate или shared соответственно; none означает, что всем переменным в параллельной области класс должен быть назначен явно; в языке Си задаются только варианты shared или попе;

private (список) - задаёт список переменных, для которых порождается локальная копия в каждой нити; начальное значение локальных копий переменных из списка не определено;

firstprivate (список) - задаёт список переменных, для которых порождается локальная копия в каждой нити; локальные копии переменных инициализируются значениями этих переменных в нити-мастере;

shared (список) - задаёт список переменных, общих для всех нитей;

copy in (список) - задаёт список переменных, объявленных как threadprivate, которые при входе в параллельную область инициализируются значениями соответствующих переменных в нити-мастере;

reduction (оператор:список) - задаёт оператор и список общих переменных; для каждой переменной создаются локальные копии в каждой нити; локальные копии инициализируются соответственно типу оператора (для аддитивных операций - 0 или его аналоги, для мультипликативных операций - 1 или её аналоги); над локальными копиями переменных после выполнения всех операторов параллельной области выполняется заданный оператор; оператор это: для языка Си - +, , -, &, |,А, &&, | |, ДЛЯ языка Фортран-+,*,-, .and., .or., .eqv., .neqv., max, min, iand, ior, ieor; порядок выполнения операторов не опреде¬лён, поэтому результат может отличаться от запуска к запуску.

При входе в параллельную область порождаются новые omp_num_threads-1 нитей, каждая нить получает свой уникальный номер, причём порождающая нить получает номер 0 и становится основной нитью группы («мастером»). Остальные нити получают в качестве номера целые числа с 1 до omp_num_threads-1. Количество нитей, выполняющих данную параллельную область, остаётся неизменным до момента выхода из области. При выходе из параллельной области производится неявная синхронизация и уничтожаются все нити, кроме породившей.

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

Пример 3 демонстрирует использование директивы parallel. В результате выполнения нить-мастер напечатает текст "Последовательная область 1", затем по директиве parallel порождаются новые нити, каждая из которых напечатает текст "Параллельная область", затем порождённые нити завершаются и оставшаяся нить-мастер напечатает текст "Последовательная область 2".

#include <stdio.h>

int main(int argc, char *argv[])

{

printf("Последовательная область l\n");

#pragma omp parallel{

printf("Параллельная область\п");

}

printf("Последовательная область 2\n");

}

Пример За. Параллельная область на языке Си. program example3b

print *, "Последовательная область 1" !$omp parallel

print *, "Параллельная область" !$omp end parallel

print *, "Последовательная область 2" end

Пример ЗЬ. Параллельная область на языке Фортран.

Пример 4 демонстрирует применение опции reduction. В данном примере производится подсчет общего количества порождённых нитей. Каждая нить инициализирует локальную копию переменной count значением 0. Далее, каждая нить увеличивает значение собственной копии переменной count на единицу и выводит полученное число. На выходе из параллельной области происходит суммирование значений переменных count по всем нитям, и полученная величина становится новым значением переменной count в последовательной области.

#include <stdio.h>

int main(int argc, char *argv[]) {

int count = 0;

#pragma omp parallel reduction (+: count) {

count++;

printf("Текущее значение count: %d\n", count);

}

printf("Число нитей: %d\n", count);

}

Пример 4a. Опция reduction на языке Си.

program example4b integer count count=0

!$omp parallel reduction (+: count) count=count+1

print *, "Текущее значение count: ", count !$omp end parallel

print *, "Число нитей: count end

Пример 4b. Опция reduction на языке Фортран.

Сокращённая запись

Если внутри параллельной области содержится только один параллельный цикл, одна конструкция sections или одна конструкция workshare, то можно использовать укороченную запись: parallel for (parallel do для языка Фортран), parallel sections или parallel workshare. При этом допустимо указание всех опций этих директив, за исключением опции nowait.

Переменные среды и вспомогательные функции

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

export OMP_NUM_THREADS=n

Значение по умолчанию переменной omp_num_threads зависит от реализации. Из программы её можно изменить с помощью вызова функции omp_set_num_threads().

Си:

void omp_set_num_threads(int num);

Фортран:

subroutine omp_set_num_threads(num) integer num

Пример 5 демонстрирует применение функции omp_set_num_threads () и опции num_threads. Перед первой параллельной областью вызовом функции omp_set_num_threads (2) выставляется количество нитей, равное 2. Но к первой параллельной области применяется опция num_threads (3), которая указывает, что данную область следует выполнять тремя нитями. Следовательно, сообщение "Параллельная область 1" будет выведено тремя нитями. Ко второй параллельной области опция num_threads не применяется, поэтому действует значение, установленное функцией omp_set_num_threads (2), и сообщение "Параллельная область 2" будет выведено двумя нитями.

#include <stdio.h>

#include <omp.h>

int main(int argc, char *argv[])

{

omp_set_num_threads (2);

#pragma omp parallel num_threads(3)

{

printf("Параллельная область l\n");

}

#pragma omp parallel

{

printf("Параллельная область 2\n");

}

}

Пример 5a. Функция omp_set_num_threads() и опция num_threads на языке Си.

program example5b include "omp_lib.h" call omp_set_num_threads(2) ; !$omp parallel num_threads(3)

print *, "Параллельная область 1" !$omp end parallel !$omp parallel

print *, "Параллельная область 2" !$omp end parallel end

Пример 5b. Функция omp_set_num_threads() и опция num_threads на языке Фортран.

В некоторых случаях система может динамически изменять количество нитей, используемых для выполнения параллельной области, например, для оптимизации использования ресурсов системы. Это разрешено делать, если переменная среды omp_dynamiс установлена в true. Например, в Linux в командной оболочке bash её можно установить при помощи следующей команды:

export OMP_DYNAMIC=true

В системах с динамическим изменением количества нитей значение по умолчанию не определено, иначе значение по умолчанию: false.

Переменную omp_dynamic можно установить с помощью функции omp_set_dynamic().

Си:

void omp_set_dynamic(int num);

Фортран:

subroutine omp_set_dynamic(num) logical num

На языке Си в качестве значения параметра функции omp_set_dynamic () задаётся 0 или 1, а на языке Фортран - .false, или .true. Если система не поддерживает динамическое изменение количества нитей, то при вызове функции omp_set_dynamic () значение переменной omp_dynamiс не изменится.

Узнать значение переменной omp_dynamic можно при помощи функции omp_get_dynamic().

Си:

int omp_get_dynamic (void) ;

Фортран:

logical function omp_get_dynamic()

Пример 6 демонстрирует применение функций omp_set_dynamic () и omp_get_dynamic (). Сначала распечатывается значение, полученное функцией omp_get_dynamic () - это позволяет узнать значение переменной omp_d ynami с по умолчанию. Затем при помощи функции omp_set_dynamic () переменная omp_d ynami с устанавливается в true, что подтверждает выдача ещё один раз значения функции omp_get_dynamic (). Затем порождается параллельная область, выполняемая заданным количеством нитей (128). В параллельной области печатается реальное число выполняющих её нитей. Директива master позволяет обеспечить печать только процессом-мастером. В системах с динамическим изменением числа нитей выданное значение может отличаться от заданного (128).

#include <stdio.h>

#include <omp.h>

int main(int argc, char *argv[])

{

printf("Значение OMP_DYNAMIC:%d\n",omp_get_dynamic()); omp_set_dynamic(1);

printf("Значение OMP_DYNAMIC:%d\n",omp_get_dynamic());

#pragma omp parallel num_threads(128)

{

#pragma omp master

{

printf("Параллельная область,%dнитей\п",omp_get_num_threads());

}

}

}

Пример 6a. Функции omp_set_dynamic() и omp_get_dynamic() на языке Си.

program example6b include "omp_lib.h"

print *, "Значение OMP_DYNAMIC: ", omp_get_dynamic() call omp_set_dynamic(.TRUE.)

print *, "Значение OMP_DYNAMIC: ", omp_get_dynamic() !$omp parallel num_threads(128) !$omp master

print *, "Параллельная область,", omp_get_num_threads(), & " нитей"

!$omp end master !$omp end parallel end

Пример 6b. Функции omp_set_dynamic() и omp_get_dynamic() на языке Фортран.

Функция omp_get_max_threads () возвращает максимально допустимое число нитей для использования в следующей параллельной области.

Си:

int omp_get_max_threads (void) ;

Фортран:

integer function omp_get_max_threads()

Функция omp_get_num_procs () возвращает количество процессоров, доступных для использования программе пользователя на момент вызова. Нужно учитывать, что количество доступных процессоров может динамически изменяться.

Си:

int omp_get_num_procs (void) ;

Фортран:

integer function omp_get_num_procs()

Параллельные области могут быть вложенными; по умолчанию вложенная параллельная область выполняется одной нитью. Это управляется установкой переменной среды omp_nested. Например, в Linux в командной оболочке bash разрешить вложенный параллелизм можно при помощи следующей команды:

export OMP_NESTED=true

Изменить значение переменной omp_nested можно с помощью вызова функции omp_set_nested().

Си:

void omp_set_nested(int nested)

Фортран:

subroutine omp_set_nested(nested) logical nested

Функция omp_set_nested() разрешает или запрещает вложенный параллелизм. На языке Си в качестве значения параметра задаётся 0 или 1, а на языке Фортран - . false . или . true . Если вложенный параллелизм разрешён, то каждая нить, в которой встретится описание параллельной области, породит для её выполнения новую группу нитей. Сама породившая нить станет в новой группе нитью-мастером. Если система не поддерживает вложенный параллелизм, данная функция не будет иметь эффекта.

Пример 7 демонстрирует использование вложенных параллельных областей и функции omp_set_nested(). Вызов функции omp_set_nested() перед первой частью разрешает использование вложенных параллельных областей. Для определения номера нити в текущей параллельной секции используются вызовы функции omp_get_thread_num (). Каждая нить внешней параллельной области породит новые нити, каждая из которых напечатает свой номер вместе с номером породившей нити. Далее вызов omp_set_nested() запрещает использование вложенных параллельных областей. Во второй части вложенная параллельная область будет выполняться без порождения новых нитей, что и видно по получаемой выдаче.

#include <stdio.h>

#include <omp.h>

int main(int argc, char *argv[])

{

int n;

omp_set_nested(l) ;

#pragma omp parallel private(n)

{

n=omp_get_thread_num();

#pragma omp parallel

{

printf("Часть 1, нить %d - %d\n", n, omp_get_thread_num());

}

}

omp_set_nested(0);

#pragma omp parallel private(n)

{

n=omp_get_thread_num();

#pragma omp parallel

{

printf("Часть 2, нить %d - %d\n", n, omp_get_thread_num());

}

}

}

Пример 7a. Вложенные параллельные области на языке Си.

program example7b include "omp_lib.h" integer n

call omp_set_nested(.TRUE.) !$omp parallel private(n)

n=omp_get_thread_num() !$omp parallel

print *, "Часть 1, нить ", n, " - ", & omp_get_thread_num()

!$omp end parallel !$omp end parallel

call omp_set_nested(.FALSE.) !$omp parallel private(n)

n=omp_get_thread_num() !$omp parallel

print *, "Часть 2, нить ", n, " - ", & omp_get_thread_num()

!$omp end parallel !$omp end parallel end

Пример 7b. Вложенные параллельные области на языке Фортран.

Узнать значение переменной omp_nested можно при помощи функции omp_get_nested().

Си:

int omp_get_nested (void) ;

Фортран:

logical function omp_get_nested()

Функция omp_in_parallel() возвращает 1 (.true, для языка Фортран), если она была вызвана из активной параллельной области программы.

Си:

int omp_in_parallel(void);

Фортран:

logical function omp_in_parallel()

Пример 8 иллюстрирует применение функции omp_in_parallel (). Функция mode демонстрирует изменение функциональности в зависимости от того, вызвана она из последовательной или из параллельной области. В последовательной области будет напечатано "Последовательная область", а в параллельной -- "Параллельная область".

Содержание документа

1. Введение. Основные идеи, причина возникновения, модель программирования. Для чего создан новый интерфейс? Кто разрабатывает? Что входит в стандарт? Сравнение с MPI и другими средствами. POSIX threads и основные понятия, связанные с нитями. Механизм работы - директивы (спецкомментарии), инкрементальное распараллеливание. Пример - параллельное вычисление числа Пи.

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

2. Основные конструкции (директивы). PARALLEL - порождение нитей. DO/SECTIONS - распределение работы; распределение итераций в циклах. Средства синхронизации.

3. Классы переменных (PRIVATE,SHARED,REDUCTION, etc.)

4. Run-time-поддержка. Процедуры, переменные среды,.

5. Привязки к C/C++.

6. Поддержка производителями и разработчиками. Реализации. Компиляторы и препроцессоры. Приложения. Будущее развитие, место среди средств параллельного программирования. Конференции.

Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model). В стандарт OpenMP входят спецификации набора директив компилятора, процедур и переменных среды.

Примерами систем с общей памятью, масштабируемых до большого числа процессоров, могут служить суперкомпьютеры Cray Origin2000 (до 128 процессоров), HP 9000 V-class (до 32 процессоров в одном узле, а в конфигурации из 4 узлов - до 128 процессоров), Sun Starfire (до 64 процессоров).

Разработкой стандарта занимается организация OpenMP ARB (ARchitecture Board), в которую вошли представители крупнейших компаний - разработчиков SMP-архитектур и программного обеспечения. Спецификации для языков Fortran и C/C++ появились соответственно в октябре 1997 года и октябре 1998 года. Открыт список рассылки для публичного обсуждения OpenMP (omp@openmp.org).

Основной источник информации - сервер www.openmp.org. На сервере доступны спецификации, статьи, учебные материалы, ссылки.

До появления OpenMP не было подходящего стандарта для эффективного программирования на SMP-системах.

Наиболее гибким, переносимым и общепринятым интерфейсом параллельного программирования является MPI (интерфейс передачи сообщений). Однако модель передачи сообщений 1) недостаточно эффективна на SMP-системах; 2) относительно сложна в освоении, так как требует мышления в "невычислительных" терминах.

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

OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (или аналогичными библиотеками нитей).

Многие поставщики SMP-архитектур (Sun,HP,SGI) в своих компиляторах поддерживают спецдирективы для распараллеливания циклов. Однако эти наборы директив, как правило, 1) весьма ограничены; 2) несовместимы между собой; в результате чего разработчикам приходится распараллеливать приложение отдельно для каждой платформы. OpenMP является во многом обобщением и расширением упомянутых наборов директив.

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

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

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

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

Согласно терминологии POSIX threads, любой UNIX-процесс состоит несколько нитей управления, которые имеют общее адресное пространство, но разные потоки команд и раздельные стэки. В простейшем случае, процесс состоит из одной нити. Нити иногда называют также потоками, легковесными процессами, LWP (light-weight processes).

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

Простой пример: вычисление числа "Пи". В последовательную программу вставлены две строчки, и она распараллелена!

program compute_pi

parameter (n = 1000)

integer i

double precision w,x,sum,pi,f,a

f(a) = 4.d0/(1.d0+a*a)

w = 1.0d0/n

sum = 0.0d0;

!$OMP PARALLEL DO PRIVATE(x), SHARED(w)

!$OMP& REDUCTION(+:sum)

do i=1,n

x = w*(i-0.5d0)

sum = sum + f(x)

enddo

pi = w*sum

print *,'pi = ',pi

stop

end

Классы переменных

В OpenMP переменные в параллельных областях программы разделяются на два основных класса:

* SHARED (общие; под именем A все нити видят одну переменную) и * PRIVATE (приватные; под именем A каждая нить видит свою переменную).

Отдельные правила определяют поведение переменных при входе и выходе из параллельной области или параллельного цикла: REDUCTION, FIRSTPRIVATE, LASTPRIVATE, COPYIN.

SHARED

Применяется к переменным, которые необходимо сделать общими.

PRIVATE

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

THREADPRIVATE

Применяется к COMMON-блокам, которые необходимо сделать приватными. Директива должна применяться после каждой декларации COMMON-блока.

FIRSTPRIVATE

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

LASTPRIVATE

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

REDUCTION(+:A)

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

COPYIN

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

Runtime-процедуры и переменные среды

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

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

* во время исполнения контролировать и запрашивать различные параметры, определяющие поведение приложения (такие как число нитей и процессоров, возможность вложенного параллелизма); процедуры назначения параметров имеют приоритет над соотвествующими переменными среды.

* использовать синхронизацию на базе замков (locks).

Переменные среды

OMP_SCHEDULE

Определяет способ распределения итераций в цикле, если в директиве DO использована клауза SCHEDULE(RUNTIME).

OMP_NUM_THREADS

Определяет число нитей для исполнения параллельных областей приложения.

OMP_DYNAMIC

Разрешает или запрещает динамическое изменение числа нитей.

OMP_NESTED

Разрешает или запрещает вложенный параллелизм.

Процедуры для контроля/запроса параметров среды исполнения

OMP_SET_NUM_THREADS

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

OMP_GET_MAX_THREADS

Возвращает максимальное число нитей.

OMP_GET_NUM_THREADS

Возвращает фактическое число нитей в параллельной области программы.

OMP_GET_NUM_PROCS

Возвращает число процессоров, доступных приложению.

OMP_IN_PARALLEL

Возвращает .TRUE., если вызвана из параллельной области программы.

OMP_SET_DYNAMIC / OMP_GET_DYNAMIC

Устанавливает/запрашивает состояние флага, разрешающего динамически изменять число нитей.

OMP_GET_NESTED / OMP_SET_NESTED

Устанавливает/запрашивает состояние флага, разрешающего вложенный параллелизм.

Процедуры для синхронизации на базе замков

В качестве замков используются общие переменные типа INTEGER (размер должен быть достаточным для хранения адреса). Данные переменные должны использоваться только как параметры примитивов синхронизации.

OMP_INIT_LOCK(var) / OMP_DESTROY_LOCK(var)

Инициализирует замок, связанный с переменной var.

OMP_SET_LOCK

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

OMP_UNSET_LOCK

Освобождает замок, если он был захвачен вызвавшей нитью.

OMP_TEST_LOCK

Пробует захватить указанный замок. Если это невозможно, возвращает .FALSE.

Спецификация OpenMP для языков C/C++

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

Необходимо лишь отметить следующие моменты:

1) Вместо спецкомментариев используются директивы компилятора "#pragma omp".

2) Компилятор с поддержкой OpenMP определяет макрос "_OPENMP", который может использоваться для условной компиляции отдельных блоков, характерных для параллельной версии программы.

3) Распараллеливание применяется к for-циклам, для этого используется директива "#pragma omp for". В параллельных циклах запрещается использовать оператор break.

4) Статические (static) переменные, определенные в параллельной области программы, являются общими (shared).

5) Память, выделенная с помощью malloc(), является общей (однако указатель на нее может быть как общим, так и приватным).

6) Типы и функции OpenMP определены во включаемом файле <omp.h>.

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

Пример распараллеливания for-цикла в C

#pragma omp parallel for private(i)

#pragma omp shared(x, y, n) reduction(+: a, b)

for (i=0; i<n; i++)

{

a = a + x[i];

b = b + y[i];

}

Поддержка произвлдителями и разработчиками. Развитие стандарта.

Реализации OpenMP

1)Silicon Graphics. Поддержка OpenMP для Fortran реализована в компиляторах Fortran 77/90 семейства MIPSpro для платформы IRIX начиная с версии 7.2.1. В версии 7.3 появится поддержка OpenMP для C/C++.

2)Compaq/DEC. DIGITAL Fortran поддерживает распараллеливание в стандарте OpenMP для Фортрана.

3)Kuck & Associates (KAI). Guide - полная реализация OpenMP как для Фортрана, так и для C/C++. Подробнее: http://www.kai.com/parallel/kappro/guide/.

4)Portland Group (PGI). Пакет PGI Workstation 3.0 поддерживает OpenMP для Fortran и C/C++ на платформах Windows NT, Linux, Solaris (x86).

Справочная информация

Документы для загрузки

1. OpenMP: A Proposed Industry Stadard API for Shared Memory Programming. Октябрь 1997. (Postcript, 100K)

2. OpenMP Fortran API. Октябрь 1997. (PDF, 127K)

3. OpenMP C/C++ API. Октябрь 1998. (PDF, 201K)

Ссылки

*OpenMP FAQ

*OpenMP tutorial, мультимедийный учебник/справочник по OpenMP, подготовленный в университете Бостона.

MPI (Message Passing Interface)

MPI: The Message Passing Interface

Новости MPI

* 15 сентября 2000 г. Реализация MPICH: выпущена версия 1.2.1. Исправлены несколько ошибок версии 1.2.0.

* 24 марта 2000 г. Реализация LAM/MPI: выпущены версии 6.3.2 и 6.4-a3. LAM 6.4 поддерживает спецификацию IMPI.

Стандарт MPI

* Стандарт MPI-1.1. включает следующие основные группы функций:

o Обмены типа точка-точка

o Коллективные обмены

o Контексты, группы и коммуникаторы

o Топологии процессов

Стандарт MPI-2.0. Данный документ содержит уточнения, привязки к языку C++ и расширения стандарта MPI 1.1, введенные в версиях 1.2 и 2.0.

Стандарт MPI-2: Extensions to the Message-Passing Interface включает следующие основные группы функций:

o Динамическое порождение процессов и управление процессами

o Односторонние коммуникации

o Параллельный Ввод/Вывод

Краткая история MPI

* 1992 г. Началась работа над стандартом эффективной и переносимой библиотеки передачи сообщений (Oak Ridge National Laboratory, Rice University). * 29/30 апреля 1992. Workshop on Standards for Message Passing in a Distributed Memory Environment (Williamsburg, Virginia). Обсуждены необходимые основные черты стандарта MPI, учреждена рабочая группа по стандартизации.

* Ноябрь 1992 г. Появился рабочий вариант стандарта MPI1, вызвавший большую дискуссию.

* Февраль 1992 г. Опубликован пересмотренный вариант MPI1 (Dongarra, Hempel, Hey and Walker). Создана организация MPI Forum для дальнейшего развития стандарта. Для обсуждения стандарта и отдельных его глав были созданы несколько открытых списков рассылки. Собрания MPI Forum назначались каждые 6 недель.

* Ноябрь 1993 г. Рабочий вариант стандарта представлен на конференции Supercomputing'93.

* 5 мая 1994 г. Окончательный вариант стандарта MPI 1.0.

* 12 Июня 1995 г. Новая версия стандарта - MPI 1.1. Исправлены некоторые ошибки оригинального стандарта и внесены разъяснения.

* 18 Июля 1997 г. Опубликован стандарт MPI-2: Extensions to the Message-Passing Interface.

Реализации MPI

Бесплатные реализации MPI

* MPICH. Переносимая реализация (работает почти на всех UNIX-системах и Windows NT), разработанная в Argonne National Laboratory. Поддерживаются кластеры на базе SMP-узлов. Поддерживается стандарт MPI 1.2 и некоторые элементы стандарта MPI 2.0.

o Загрузить копию MPICH c исходными текстами.

o Cправочные страницы (manual pages) из MPICH 1.1 (HTML)

o Руководство пользователя по MPICH (HTML)

o Руководство по установке MPICH (HTML)

* LAM. Реализация MPI и среда разработки MPI-программ для гетерогенных кластеров из UNIX-машин, разработана в Ohio Supercomputer Center, теперь эта реализация перешла в ведение Laboratory for Scientific Computing (университет Notre-Damme). Последняя версия - 6.1.

* BIP-MPI - реализация MPI для кластеров на базе ОС Linux и коммутатора Myrinet, в составе пакета BIP Messages. Основана на MPICH.

* CHIMP/MPI, одна из первых реализаций MPI; разработана в EPCC. Поддерживаемые платформы: SunOS, Solaris, AIX, IRIX, транспьютеры Meiko. Последняя версия - 2.1.1c (от 13 Ноября 1995 г.)

* MPI-FM, реализация MPI на базе протокола Fast Messages (адаптированная версия MPICH). Входит в состав пакета HPVM (High Performance Virtual Machines). HPVM работает на Intel-платформах c ОС Linux и Windows NT. Распространяются только двоичные файлы для этих платформ. Поддерживаются сетевые среды Myrinet (основная) и TCP/IP.

* WMPI - реализация MPI для платформ Win32 (Microsoft Windows 95/98/NT), разработанная и поддерживаемая Jose Meireles Marinho (Университет Coimbra, Португалия). Базируется на на реализации P4 для Win32 (интерфейс к P4 также входит в поставку). Последняя версия - WMPI 1.3; поддерживается стандарт MPI 1.1).

* TOMPI (Threads-Only MPI) - реализация MPI через множественные потоки (POSIX/Solaris threads) для работы на одном компьютере (или однопроцессорном или с SMP-архитектурой).

* LA-MPI - реализация MPI 1.2 в Лос-аламосской лаборатории для больших кластеров. Поддерживается устойчивость к сбоям. Находится в состоянии разработки.

Смотрите также раздел MPI в нашем FTP-архиве. Доступны для загрузки копии последних версий MPICH и WMPI.

Коммерческие реализации MPI

* MPI/PRO for Windows NT. Реализация, разработанная компанией MPI Software Technology. Работает на кластерах рабочих станций и серверов Windows NT (платформы Intel и Alpha). Поддерживается стандарт MPI 1.2.

* PaTENT MPI - реализация MPI компании Genias Sotfware для кластеров на базе Windows NT. PowerMPI - реализация MPI для транспьютерных систем Parsytec.

Справочная информация

Документы для загрузки

1. OpenMP: A Proposed Industry Stadard API for Shared Memory Programming. Октябрь 1997. (Postcript, 100K)

2. OpenMP Fortran API. Октябрь 1997. (PDF, 127K)

3. OpenMP C/C++ API. Октябрь 1998. (PDF, 201K)

Ссылки

* OpenMP FAQ

* OpenMP tutorial, мультимедийный учебник/справочник по OpenMP, подготовленный в университете Бостона.

MPI. Терминология и обозначения

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

Атрибуты сообщения - номер процесса-отправителя, номер процесса-получателя и идентификатор сообщения. Для них заведена структура MPI_Status, содержащая три поля: MPI_Source (номер процесса отправителя), MPI_Tag (идентификатор сообщения), MPI_Error (код ошибки); могут быть и добавочные поля.Идентификатор сообщения (msgtag) - атрибут сообщения, являющийся целым неотрицательным числом, лежащим в диапазоне от 0 до 32767.Процессы объединяются в группы, могут быть вложенные группы. Внутри группы все процессы перенумерованы. С каждой группой ассоциирован свой коммуникатор. Поэтому при осуществлении пересылки необходимо указать идентификатор группы, внутри которой производится эта пересылка. Все процессы содержатся в группе с предопределенным идентификатором MPI_COMM_WORLD.При описании процедур MPI будем пользоваться словом OUT для обозначения "выходных" параметров, т.е. таких параметров, через которые процедура возвращает результаты.

Общие процедуры MPI

int MPI_Init( int* argc, char*** argv)

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

int MPI_Finalize( void )

MPI_Finalize - завершение параллельной части приложения. Все последующие обращения к любым MPI-процедурам, в том числе к MPI_Init, запрещены. К моменту вызова MPI_Finalize некоторым процессом все действия, требующие его участия в обмене сообщениями, должны быть завершены.Сложный тип аргументов MPI_Init предусмотрен для того, чтобы передавать всем процессам аргументы main:

int main(int argc, char** argv)

{

MPI_Init(&argc, &argv);

...

MPI_Finalize();

}

int MPI_Comm_size( MPI_Comm comm, int* size)

Определение общего числа параллельных процессов в группе comm.

* comm - идентификатор группы

* OUT size - размер группы

int MPI_Comm_rank( MPI_Comm comm, int* rank)

Определение номера процесса в группе comm. Значение, возвращаемое по адресу &rank, лежит в диапазоне от 0 до size_of_group-1.

* comm - идентификатор группы

* OUT rank - номер вызывающего процесса в группе comm

double MPI_Wtime(void)

Функция возвращает астрономическое время в секундах (вещественное число), прошедшее с некоторого момента в прошлом. Гарантируется, что этот момент не будет изменен за время существования процесса.

Прием/передача сообщений между отдельными процессами