Основы параллельного программирования с использованием MPI Лекция 1

Содержание

Слайд 2

План лекции

2008

Обзор курса
Модели программирования последовательная и
параллельная
Программные инструменты

План лекции 2008 Обзор курса Модели программирования последовательная и параллельная Программные инструменты
параллельного
программирования
Литература и другие источники информации

Слайд 3

Обзор курса

2008

Аннотация
Курс «Основы параллельного программирования с использованием MPI» посвящен основам разработки параллельных

Обзор курса 2008 Аннотация Курс «Основы параллельного программирования с использованием MPI» посвящен
программ с использованием интерфейса обмена сообщениями (MPI ‑ Message Passing Interface). В курсе рассматриваются основные понятия и концепции модели передачи сообщений, «архитектура» MPI. Обсуждаются способы организации обменов разного типа: двухточечных, коллективных, блокирующих и неблокирующих, и т. д. Рассматриваются вспомогательные средства, такие как пользовательские типы, виртуальные топологии, другие вопросы. В курсе сочетаются теоретические и практические занятия. Приводятся примеры, предусмотрено выполнение лабораторных работ и домашних заданий, а также тестирование.

Слайд 4

Обзор курса

2008

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

Обзор курса 2008 Темы курса: краткий обзор моделей параллельного программирования и программных
этих моделей;
архитектура MPI, привязки к языкам программирования C/C++ и
Fortran;
структура MPI-программы, настройка среды, компиляция и
выполнение MPI-программ;
двухточечные обмены, блокирующие и неблокирующие,
буферизованные, двух- и односторонние, и т. д.;
коллективные обмены – широковещательная рассылка,
распределение и сбор данных, операции редукции, синхронизация и
т. д.;
работа с группами процессов, интра- и интеркоммуникаторы;
пользовательские типы данных;
виртуальные топологии.

Слайд 5

О лекторе

2008

Немнюгин Сергей Андреевич

Кандидат физико-математических наук, доцент кафедры вычислительной физики Санкт-Петербургского

О лекторе 2008 Немнюгин Сергей Андреевич Кандидат физико-математических наук, доцент кафедры вычислительной
государственного университета. Научные интересы связаны с использованием методов статистического моделирования для решения задач квантовой физики, моделированием процессов распространения заряженных частиц и жесткого электромагнитного излучения в веществе, математическим моделированием в экономике, а также применением методов высокопроизводительных и распределенных вычислений для решения задач вычислительной физики. Активно занимается педагогической деятельностью в области вычислительной физики и высокопроизводительных вычислений.
Электронная почта:
[email protected]

Слайд 6

Лекция 1

2008

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

Лекция 1 2008 Аннотация В первой лекции обсуждаются последовательная и параллельная модели
парадигмы параллельного программирования и их программные реализации (POSIX Threads, Microsoft Windows API, OpenMP, MPI, PVM и т. д.).

Слайд 7

Последовательная и параллельная модели программирования

2008

Последовательная и параллельная модели программирования 2008

Слайд 8

Идея Флинна

2008

Идея Флинна 2008

Слайд 9

SISD-архитектура

SIMD-архитектура

MIMD-архитектура

SISD-архитектура SIMD-архитектура MIMD-архитектура

Слайд 10

Что происходит с данными внутри программы

Что происходит с данными внутри программы

Слайд 11

Последовательная программа

Последовательная программа

Слайд 12

Параллельная программа

Параллельная программа

Слайд 13

Общий случай

Последовательный+распараллеливаемый компоненты

Общий случай Последовательный+распараллеливаемый компоненты

Слайд 14

Последовательная модель программирования

Последовательную модель программирования характеризуют:
невысокая производительность;
применение стандартных языков программирования;

Последовательная модель программирования Последовательную модель программирования характеризуют: невысокая производительность; применение стандартных языков программирования; хорошая переносимость.
хорошая переносимость.

Слайд 15

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

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

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

Слайд 16

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

Повышенная трудоёмкость параллельного программирования связана с тем, что программист должен

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

Слайд 17

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

Две парадигмы параллельного программирования
параллелизм данных;
параллелизм задач.

Параллельная модель программирования Две парадигмы параллельного программирования параллелизм данных; параллелизм задач.

Слайд 18

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

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

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

Слайд 19

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

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

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

Слайд 20

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

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

Параллельная модель программирования Параллелизм задач Параллелизм данных характеризуется тем, что: вычислительная задача
относительно самостоятельных подзадач. Каждая подзадача выполняется на своем процессоре (ориентация на архитектуру MIMD);
для каждой подзадачи пишется своя собственная программа на обычном языке программирования (чаще всего это Fortran или С);
подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.

Слайд 21

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

Параллелизм задач
Достоинства подхода:
большая гибкость и большая свобода, предоставляемая программисту в

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

Слайд 22

Разработка параллельной программы/алгоритма

Разработка параллельной программы/алгоритма

Слайд 24

Разработка параллельной программы/алгоритма

Декомпозиция
На этом этапе выполняются анализ, оценка возможности распараллеливания. Задача и

Разработка параллельной программы/алгоритма Декомпозиция На этом этапе выполняются анализ, оценка возможности распараллеливания.
связанные с ней данные разделяются на более мелкие части  подзадачи и фрагменты структур данных. Особенности архитектуры конкретной вычислительной системы на данном этапе могут не учитываться.
Требования
количество подзадач после декомпозиции должно быть достаточно
большим;
следует избегать лишних вычислений и пересылок данных;
подзадачи должны быть примерно одинакового размера.

Слайд 25

Разработка параллельной программы/алгоритма

Декомпозиция
Независимость
независимость по данным - данные, обрабатываемые одной частью

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

Слайд 26

Разработка параллельной программы/алгоритма

Проектирование коммуникаций
Типы коммуникаций:
локальные - каждая подзадача связана с небольшим набором

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

Слайд 27

Разработка параллельной программы/алгоритма

Проектирование коммуникаций
Рекомендации по проектированию коммуникаций:
количество коммуникаций у подзадач должно быть

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

Слайд 28

Разработка параллельной программы/алгоритма

Укрупнение
На этапе укрупнения учитывается архитектура вычислительной системы, при этом часто

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

Слайд 29

Разработка параллельной программы/алгоритма

Организация параллельной программы
Простая схема хозяин/работник (Master/slave)
главная задача отвечает за

Разработка параллельной программы/алгоритма Организация параллельной программы Простая схема хозяин/работник (Master/slave) главная задача
размещение подчиненных задач;
подчиненная задача получает исходные данные для обработки от
главной задачи и возвращает ей результат работы.

Слайд 30

Разработка параллельной программы/алгоритма

Организация параллельной программы
Иерархическая схема хозяин/работник (Master/slave)
Подчиненные задачи разделены на непересекающиеся

Разработка параллельной программы/алгоритма Организация параллельной программы Иерархическая схема хозяин/работник (Master/slave) Подчиненные задачи
подмножества и у каждого из этих подмножеств есть своя главная задача. Главные задачи подмножеств управляются одной "самой главной" задачей.

Слайд 31

Разработка параллельной программы/алгоритма

Разработка параллельной программы/алгоритма

Слайд 32

Многопоточные программы

Поток (нить) представляет собой последовательный поток управления (последовательность команд) в рамках

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

Слайд 33

Многопоточные программы

При разработке многопоточных приложений возникают следующие проблемы:
гонки за данными;
блокировки;

Многопоточные программы При разработке многопоточных приложений возникают следующие проблемы: гонки за данными;
несбалансированность загрузки.
Гонки за данными (data races) - являются следствием зависимостей, когда несколько потоков модифицируют содержимое одной и той же области памяти. Наличие гонок за данными не всегда является очевидным.

Слайд 34

Многопоточные программы

Блокировка возникает, если поток ожидает выполнение условия, которое не может быть

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

Слайд 35

Программные инструменты параллелизма

2008

Программные инструменты параллелизма 2008

Слайд 36

2008
OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей памятью.

2008 OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей
Поддерживает языки C, C++, Fortran.
Официальный сайт OpenMP
http://openmp.org

Open Multi-Processing (OpenMP)

Слайд 37

2008

Корпорация Intel предлагает Intel ® Cluster OpenMP кластерный вариант OpenMP, предназначенный для

2008 Корпорация Intel предлагает Intel ® Cluster OpenMP кластерный вариант OpenMP, предназначенный
программирования для систем с распределенной памятью
Официальный сайт
http://www.intel.com

Open Multi-Processing (OpenMP)

Слайд 38

2008

POSIX Threads - стандарт POSIX реализации потоков (нитей) выполнения, определяющий API для

2008 POSIX Threads - стандарт POSIX реализации потоков (нитей) выполнения, определяющий API
создания и управления ими.
Ссылка
http://www.opengroup.org/onlinepubs/009695399/basedefs/pthread.h.html

POSIX Threads

Слайд 39

2008

В Microsoft Windows имеется возможность разработки многопоточных приложений на C++.
Ссылка
http://msdn.microsoft.com

Windows API

2008 В Microsoft Windows имеется возможность разработки многопоточных приложений на C++. Ссылка http://msdn.microsoft.com Windows API

Слайд 40

2008

PVM (Parallel Virtual Machine) - позволяет объединить разнородный набор компьютеров, связанных сетью,

2008 PVM (Parallel Virtual Machine) - позволяет объединить разнородный набор компьютеров, связанных
в общий вычислительный ресурс, который называют Параллельной Виртуальной Машиной.
Официальный сайт PVM
http://www.csm.ornl.gov/pvm

Parallel Virtual Machine (PVM)

Слайд 41

2008

Message Passing Interface (MPI) - Интерфейс Передачи Сообщений, спецификация разработанная в 1993—1994

2008 Message Passing Interface (MPI) - Интерфейс Передачи Сообщений, спецификация разработанная в
годах группой MPI Forum, в состав которой входили представители академических и промышленных кругов. Она стала первым стандартом систем передачи сообщений.
Официальный сайт MPI
http://www.mpi-forum.org

Message Passing Interface (MPI)

Слайд 42

2008

MPICHameleon (MPICH) является свободно распространяемой реализацией MPI.
Официальный сайт MPICH
http://www-unix.mcs.anl.gov/mpi/mpich1

Message Passing Interface (MPI)

2008 MPICHameleon (MPICH) является свободно распространяемой реализацией MPI. Официальный сайт MPICH http://www-unix.mcs.anl.gov/mpi/mpich1 Message Passing Interface (MPI)

Слайд 43

2008

В этой лекции мы рассмотрели:
особенности последовательной и параллельной моделей
программирования;

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

Заключение

Слайд 44

2008

В чём вы видите ограничения последовательной модели
программирования?
Какие достоинства

2008 В чём вы видите ограничения последовательной модели программирования? Какие достоинства и
и недостатки у подходов, основанных на
параллелизме данных и параллелизме задач?
В чём достоинства и недостатки различных видов
коммуникаций?

Вопросы для обсуждения

Слайд 45

2008

Следуя приведённым в лекции ссылкам, познакомьтесь с
основными особенностями наиболее

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

Темы для самостоятельной работы

Слайд 46

Литература

2008

С.Немнюгин, О.Стесик. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002.

С.Немнюгин,

Литература 2008 С.Немнюгин, О.Стесик. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.:
М.Чаунин, А.Комолкин. Эффективная работа:UNIX. – СПб.: Питер, 2001.

В.П.Гергель. Теория и практика параллельных вычислений. Интернет-университет информационных технологий - ИНТУИТ.ру, БИНОМ. Лаборатория знаний, 2007 г., 424 стр.

Слайд 47

Литература

2008

С.Немнюгин, О.Стесик. Современный Фортран. Самоучитель. – СПб.: БХВ-Петербург, 2004.

В.В.Воеводин, Вл.В. Воеводин Вл.В.

Литература 2008 С.Немнюгин, О.Стесик. Современный Фортран. Самоучитель. – СПб.: БХВ-Петербург, 2004. В.В.Воеводин,
Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.

Портал PARALLEL.RU

Материалы к курсу «Средства программирования для многопроцессорных и многоядерных вычислительных систем». Сайт физического факультета СПбГУ (раздел «Библиотека»):
http://www.phys.spbu.ru

Имя файла: Основы-параллельного-программирования-с-использованием-MPI-Лекция-1.pptx
Количество просмотров: 140
Количество скачиваний: 0