Учебное пособие содержит материал для работы в области параллельного программирования. Дается краткая характеристика принципов построения параллельных вычислительных систем, рассматриваются математические модели параллельных алгоритмов и программ для анализа эффективности параллельных вычислений, приводятся примеры конкретных параллельных методов для решения типовых задач вычислительной математики.
Пособие подготовлено по заданию Инновационной образовательной программы Нижегородского госуниверситета им. Н.И. Лобачевского в рамках Национального проекта «Образование».
Для студентов, аспирантов и специалистов, изучающих и практически использующих параллельные компьютерные системы для решения вычислительно трудоемких задач.
Учебное пособие содержит материал для работы в области параллельного программирования. Дается краткая характеристика принципов построения параллельных вычислительных систем, рассматриваются математические модели параллельных алгоритмов и программ для анализа эффективности параллельных вычислений, приводятся примеры конкретных параллельных методов для решения типовых задач вычислительной математики.
Пособие подготовлено по заданию Инновационной образовательной программы Нижегородского госуниверситета им. Н.И. Лобачевского в рамках Национального проекта «Образование».
Для студентов, аспирантов и специалистов, изучающих и практически использующих параллельные компьютерные системы для решения вычислительно трудоемких задач.
В.П. Гергель, р.Г. Стронгин Основы параллельных вычислений для многопроцессорных вычислительных систем
Издание 2-е, дополненное
Издательство Нижегородского госуниверситета Нижний Новгород 2003
В учебном пособии излагается учебный материал, достаточный для успешного начала работ в области параллельного программирования. Для этого в пособии дается краткая характеристика принципов построения параллельных вычислительных систем, рассматриваются математические модели параллельных алгоритмов и программ для анализа эффективности параллельных вычислений, приводятся примеры конкретных параллельных методов для решения типовых задач вычислительной математики.
По сравнению с первым изданием в пособии значительно расширены материалы по кластерным вычислительным системам, анализу трудоемкости коммуникационных операций, параллельным методам решения типовых задач вычислительной математики. В пособие включены результаты вычислительных экспериментов на кластере Нижегородского университета.
Учебное пособие предназначено для широкого круга студентов, аспирантов и специалистов, желающих изучить и практически использовать параллельные компьютерные системы для решения вычислительно трудоемких задач.
Роман Григорьевич Стронгин – ректор Нижегородского государственного Университета им. Н.И.Лобачевского (http://www.unn.ru). На данный момент он также возглавляет кафедру математического обеспечения ЭВМ факультета ВМК. Р.Г. Стронгин является заслуженным учёным Российской Федерации, членом редакционной коллегии журнала «Global Optimization» (1991-1998) и международного теоретического журнала «Математика» (1998-
). Р.Г. Стронгин – главный редактор серии публикаций Нижегородского Университета по математическому моделированию и оптимальному управлению, постоянный член Российской Академии Естественных Наук. Его исследовательские интересы в настоящий момент – теория и практика принятия решений. Р.Г. Стронгин – автор новых параллельных методов для решения задач глобальной оптимизации. Им опубликованы три монографии и более 270 статей в журналах «Global Optimization», «Parallel Computing», «Optimization», «Stochastics and Stochastics Reports», «Pattern Recognition and Image Analysis», «Engineering Cybernetics», «Lecture Notes in Economics and Mathematical Systems», «Журнал вычислительной математики и математической физики», «Кибернетика» и др.
Виктор Павлович Гергель – профессор кафедры математического обеспечения ЭВМ факультета ВМК (http://www.software.unn.ac.ru/mo_evm) в Нижегородского государственного Университета им. Н.И.Лобачевского. Он возглавляет Центр компьютерного моделирования и Отделение дополнительного компьютерного обучения. Его исследовательские интересы в настоящий момент – теория и применение параллельный вычислений и разработка методов и программных систем принятия решений. В.П. Гергель – автор новых параллельных методов для решения задач глобальной оптимизации. Им опубликованы три книги и более 120 статей в журналах «Global Optimization», «Optimization», «European Journal of Operation Research», «Pattern Recognition and Image Analysis», «Engineering Cybernetics», «Журнал вычислительной математики и математической физики» и др.
Учебная рабочая программа по общему курсу «Многопроцессорные вычислительные системы и параллельное программирование»
Общий курс Теория и практика параллельных вычислений
1 Нижегородский Государственный Университет им. Н.И. Лобачевского Общий курс Теория и практика параллельных вычислений Лекция 16 Методы разработки параллельных программ для многопроцессорных систем с общей памятью (стандарт OpenMP) 2 Гергель В.П.
2 Содержание Директивы OpenMP Синхронизация Директивы master, critical, barrier, atomic, flush, ordered, threadprivate Управление областью видимости данных Параметры директив shared, private, firstprivate, lastprivate, copyin, default, reduction Совместимость директив и их параметров Библиотека функций OpenMP Функции для контроля/запроса параметров среды исполнения Функции синхронизации Переменные среды Реализации OpenMP 16.2
3 Директивы OpenMP Синхронизация Директива master определяет фрагмент кода, который должен быть выполнен только основным потоком; все остальные потоки пропускают данный фрагмент кода (завершение директивы по умолчанию не синхронизируется) #pragma omp master newline structured_block 16.3
4 Директивы OpenMP Синхронизация Директива critical определяет фрагмент кода, который должен выполняться только одним потоком в каждый текущий момент времени (критическая секция) основным потоком; все остальные потоки пропускают данный фрагмент кода (завершение директивы по умолчанию не синхронизируется) #pragma omp critical [ name ] newline structured_block 16.4
5 Директивы OpenMP Синхронизация Директива critical (пример) #include main() < int x; x = 0; #pragma omp parallel shared(x) < #pragma omp critical x = x + 1; >/* end of parallel section */ > 16.5
6 Директивы OpenMP Синхронизация Директива barrier определяет точку синхронизации, которую должны достигнуть все процессы для продолжения вычислений (директива должны быть вложена в блок) #pragma omp barrier newline 16.6
9 Директивы OpenMP Синхронизация Директива ordered указывает фрагмент кода параллельного цикла, который должен выполняться точно в таком же порядке, как и при последовательном выполнении #pragma omp ordered newline structured_block В каждый момент времени в блоке ordered может находиться только один поток На одной итерации цикла может быть только одна директива ordered и эта директива может выполниться только однократно Цикл, в котором имеется директива ordered, должен иметь параметр ordered 16.9
10 Директивы OpenMP Синхронизация Директива threadprivate используется для создания поточных копий для глобальных переменных программы; созданные копии не видимы между потоками, но существуют во все время выполнения программы #pragma omp threadprivate (list) 16.10
12 Директивы OpenMP Управление областью видимости данных Параметр shared определяет список переменных, которые будут общими для всех потоков параллельной области; правильность использования таких переменных должна обеспечиваться программистом shared (list) Параметр private определяет список переменных, которые будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным private (list) 16.12
13 Директивы OpenMP Управление областью видимости данных Параметр firstprivate позволяет создать локальные переменные потоков, которые перед использованием инициализируются значениями исходных переменных firstprivate (list) Параметр lastprivate позволяет создать локальные переменные потоков, значения которых запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию) lastprivate (list) 16.13
14 Директивы OpenMP Управление областью видимости данных Параметр copyin позволяет выполнить инициализацию переменных директивы threadprivate copyin (list) Параметр default устанавливает область видимости переменных по умолчанию default (shared none) 16.14
15 Директивы OpenMP Управление областью видимости данных Параметр reduction определяет список переменных, для которых выполняется операция редукции; перед выполнением параллельной области для каждого потока создаются копии этих переменных, потоки формируют значения в своих локальных переменных и при завершении параллельной области на всеми локальными значениями выполняются необходимые операции редукции, результаты которых запоминаются в исходных (глобальных) переменных reduction (operator: list) 16.15
19 Библиотека функций OpenMP Функции для контроля/запроса параметров среды исполнения void omp_set_num_threads(int num_threads) Позволяет назначить максимальное число потоков для использования в следующей параллельной области (если это число разрешено менять динамически). Вызывается из последовательной области программы. int omp_get_max_threads(void) Возвращает максимальное число потоков. int omp_get_num_threads(void) Возвращает фактическое число потоков в параллельной области программы
20 Библиотека функций OpenMP Функции для контроля/запроса параметров среды исполнения Функции для контроля/запроса параметров среды исполнения int omp_get_thread_num(void) Возвращает номер потока. int omp_get_num_procs(void) Возвращает число процессоров, доступных приложению. int omp_in_parallel(void) Возвращает.TRUE., если вызвана из параллельной области программы. void omp_set_dynamic(int dynamic) int omp_get_dynamic(void) Устанавливает/запрашивает состояние флага, разрешающего динамически изменять число потоков. void omp_get_nested(int nested) int omp_set_nested(void) Устанавливает/запрашивает состояние флага, разрешающего вложенный параллелизм
21 Библиотека функций OpenMP Функции синхронизации В качестве замков используются общие переменные типа omp_lock_t или omp_nestlock_t. Данные переменные должны использоваться только как параметры примитивов синхронизации. void omp_init_lock(omp_lock_t *lock)void omp_nest_init_lock(omp_nest_lock_t *lock) Инициализирует замок, связанный с переменной lock.void omp_destroy_lock(omp_lock_t *lock) void omp_destroy_nest lock(omp_nest_lock_t *lock) Удаляет замок, связанный с переменной lock
22 Библиотека функций OpenMP Функции синхронизации void omp_set_lock(omp_lock_t *lock) void omp_set_nest lock(omp_nest_lock_t *lock) Заставляет вызвавший поток дождаться освобождения замка, а затем захватывает его. void omp_unset_lock(omp_lock_t *lock) void omp_unset_nest lock(omp_nest_lock_t *lock) Освобождает замок, если он был захвачен потоком ранее. void omp_test_lock(omp_lock_t *lock) void omp_test_nest lock(omp_nest_lock_t *lock) Пробует захватить указанный замок. Если это невозможно, возвращает.false
23 Переменные среды OMP_SCHEDULE Определяет способ распределения итераций в цикле, если в директиве DO использована клауза SCHEDULE(RUNTIME). OMP_NUM_THREADS Определяет число нитей для исполнения параллельных областей приложения. OMP_DYNAMIC Разрешает или запрещает динамическое изменение числа нитей. OMP_NESTED Разрешает или запрещает вложенный параллелизм. Компилятор с поддержкой OpenMP определяет макрос «_OPENMP», который может использоваться для условной компиляции отдельных блоков, характерных для параллельной версии программы 16.23
26 Сравнение технологий MPI и OpenMP для систем с общей памятью Ускорение матричного умножения при использовании параллельных вычислений Ускорение вычислений Ускорение Размер задачи OpenMP MPI 16.26
27 Сравнение технологий MPI и OpenMP для систем с общей памятью Сравнение времени выполнения последовательного варианта программы для задачи матричного умножения с вариантами OpenMP и MPI для 4- процессорного сервера Порядок Время T посл OpenMP MPI матрицы: (последовательный (N) алгоритм) Время T пар Ускорение S Время T Ускорение S
28 Сравнение технологий MPI и OpenMP для систем с общей памятью Ускорение матричного умножения при использовании параллельных вычислений 2.5 Ускорение вычислений 2 Ускорение Размер задачи MPI OpenMP 16.28
29 Комбинированная (MPI+OpenMP) технология программирования для систем с общей памятью Сравнение времени выполнения MPI и MPI+OpenMP вариантов программы для двух 2-процессорных серверов Порядок Время T пар (сек) матрицы: (N) MPI MPI+OpenMP Ускорение S
30 Комбинированная (MPI+OpenMP) технология программирования для систем с общей памятью Ускорение матричного умножения при использовании смешанного MPI+OpenMP варианта параллельной программы Ускорение MPI+OpenMP/MPI Ускорение Размер задачи 16.30
31 Реализации OpenMP 1) Silicon Graphics. Fortran 77/90 (IRIX), планируется поддержка OpenMP для C/C++. 2) Compaq/DEC. DIGITAL Fortran 3) Kuck & Associates (KAI). Fortran, C/C++ (Unix, Windows) 4) Portland Group (PGI). Fortran и C/C++ для Windows NT, Linux, Solaris (x86). 5) OdinMP. OpenMP-препроцессор для языка С, генерация программы в стандарте POSIX threads. 6) Sun. Планируется поддержка OpenMP 7) Pacific-Sierra Research предлагает распараллеливающие препроцессоры VAST/Parallel для Fortran ис, которые обеспечивают автоматическое распознавание параллелизма в программах и выполнение необходимой трансформации программ путем добавления соответствующих директив OpenMP. 8) Intel. Fortran, C/C++ (Unix, Параллельные Windows) вычисления 16.31
33 Вопросы для обсуждения Методы синхронизации обработки данных в OpenMP Программирование с использованием библиотеки функций OpenMP 16.33
34 Задания для самостоятельной работы Разработка параллельных методов для задач линейной алгебры при использовании интерфейса OpenMP 16.34
35 Заключение Методы синхронизации обработки данных Библиотека функций OpenMP Переменные среды окружения 16.35
Презентация была опубликована 8 лет назад пользователемМарфа Рахимова
Похожие презентации
Презентация на тему: » Гергель В.П. Общий курс Теория и практика параллельных вычислений Лекция 9 Методы разработки параллельных программ при использования интерфейса передачи.» — Транскрипт:
1 Гергель В.П. Общий курс Теория и практика параллельных вычислений Лекция 9 Методы разработки параллельных программ при использования интерфейса передачи сообщений MPI – 3 Нижегородский Государственный Университет им. Н.И. Лобачевского
2 Параллельные Гергель В.П. ННГУ, Н.Новгород, Содержание Использование виртуальных топологий Применение топологии в виде решетки Пример: Решение задачи Пуассона Вопросы для обсуждения Задания для самостоятельной работы Заключение Следующая тема
3 Параллельные Гергель В.П. ННГУ, Н.Новгород, Использование виртуальных топологий Использование топологий позволяет снизить сложность разработки параллельных программ (применение «естественных» для параллельного алгоритма структуры коммуникационных связей) В MPI имеется широко используемая в практике вычислений предопределенная топология в виде прямоугольной решетки (cartesian or grid topology) В состав MPI входит набор функций для создания новой (пользовательской) топологии в виде определенной графовой структуры
8 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Задача Пуассона определяется уравнениями 2 u = f(x,y) внутри области u(x,y) = g(x,y) на границе области Для простоты обсуждения в качестве области задания функции используется единичный квадрат. Для численного решения применим широко используемый для таких задач метод конечных разностей. Для этого определим равномерную квадратную сетку (n+2)*(n+2), состоящую из точек (x i,y j ) x i = ih, i=0. n+1, y j = jh, j=0. n+1, h = 1/(n+1). Обозначим оцениваемую при подобном дискретном представлении аппроксимацию функции u(x,y) в точках (x i,y j ) через u i,j.
9 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Используя пятиточечный шаблон для аппроксимации значений вторых производных, можно получить разностную форму задачи Пуассона Полученные уравнения можно переписать в виде системы для решения которой может быть применен метод Якоби с итеративной формулой
10 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона…
11 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Serial Finite Difference Algorithm */ #const N 100 void main() < int i, j, k; double u[N+2][N+2], unew[N+2][N+2]; for ( k=0; k
12 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* основная итерация для пересчета значений в узлах сетки */ #define N 100 void sweep() < int i, j; double u[N+2][N+2], unew[N+2][N+2]]; for ( j=1; j
13 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Разделение области для параллельных расчетов – горизонтальные полосы
14 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* итерация метода Якоби для одной горизонтальной полосы */ #define M N/NPROC /* NPROC – общее к-во процессов */ int i, j; double u[M][N+2], unew[M][N+2]]; for ( j=1; j
15 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона…
16 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Схема обмена граничными значениями
18 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Основная итерация параллельн ог о метода Якоби */ void sweep1d( double a[][N+2], double f[][N+2], int nx, int m, double b[][N+2] ) < int i, j; double h = 1.0/(nx+1); for ( j=1; j
21 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Получение рангов текущего процесса и рангов соседей */ MPI_Comm_rank( comm1d, &myid ); MPI_Cart_shift(comm1d, 0, 1, &rank1, &rank2); /* Определение размера полосы области */ m = GetStripSize(ny, numprocs, myid); /* Подготовка данных */ InitData( a, b, f, nx, m );
22 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Выполнение вычислений */ MPI_Barrier(MPI_COMM_WORLD); t1 = MPI_Wtime(); for ( it=0; it
23 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… > if (myid==0) printf(«Точность не достигнута\n»); > t2 = MPI_Wtime(); if (myid==0) < printf("Выполнено %d итераций, Время выполнения %lf сек.\n", 2*it,t2-t1); >MPI_Finalize(); >
24 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Коммуникационные операции, используемые в методе Якоби
26 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* итерация метода Якоби при блочном разбиении области */ void sweep2d(double a[][N+2], double f[][N+2], int n, int mx, int my, double b[][N+2]) < int i, j; double h = 1.0 / (n+1); for ( i=1; i
28 Параллельные Гергель В.П. ННГУ, Н.Новгород, Вопросы для обсуждения Полезность использования логической топологии типа решетки Анализ эффективности параллельных вычислений для решения задачи Пуассона
29 Параллельные Гергель В.П. ННГУ, Н.Новгород, Задания для самостоятельной работы Разработки параллельной программы для решения задачи Пуассона при блочном разбиении области вычислений Методы создания новых логических топологий в MPI
30 Параллельные Гергель В.П. ННГУ, Н.Новгород, Заключение Методы создания логической топологии типа решетки Пример параллельного решения сложной вычислительной задачи
31 Параллельные Гергель В.П. ННГУ, Н.Новгород, Следующая тема Модели функционирования параллельных программ
