Е. Ю. Алексеева Южно-Уральский государственный Университет Механико - математический факультет Кафедра прикладной математики

Механико - математический факультет Южно-Уральского государственного Университета

Содержание курса Введение Архитектура высокопроизводительных систем Особенности параллельных вычислений Технология OpenMP Интерфейс передачи сообщений MPI Моделирование физических задач средствами OpenMP и MPI Механико - математический факультет Южно-Уральского государственного Университета

Структура курса лекции практические занятия Е. Ю. Алексеева самостоятельные задания ЗАЧЕТ Механико - математический факультет Южно-Уральского государственного Университета

Области применения суперкомпьютеров Научно-исследовательские институты Университеты Геофизика Биология Метеорология Финансовая область Энергетика Наукоемкие отрасли промышленности Медицина Генетика Геологоразведка Контроль за окружающей средой Механико - математический факультет Южно-Уральского государственного Университета

Пример проблемы решаемой с помощью параллельного программирования Car Crash Simulation: Поверхность машины моделируется как считанное количество треугольных элементов. Моделируется позиция каждого элемента во времени с учетом сил действующих на него и его свойств. Каждый элемент взаимодействует только с соседними элементами Механико - математический факультет Южно-Уральского государственного Университета

Сетка конечных элементов Механико - математический факультет Южно-Уральского государственного Университета

Архитектура ЭВМ Архитектура компьютера Организация компьютера Схема компьютера Механико - математический факультет Южно-Уральского государственного Университета

Архитектура фон Неймана Программа хранится в компьютере Программа во время выполнения и необходимые для её работы данные находятся в оперативной памяти Имеется арифметико-логическое устройство, выполняющее арифметические и логические операции с данными Имеется устройство управления, которое интерпретирует команды, выбираемые из памяти, и выполняет их Устройства ввода и вывода используются для ввода программ и данных и для вывода результатов расчетов. Работают под управлением УУ Механико - математический факультет Южно-Уральского государственного Университета

Архитектура фон Неймана II Механико - математический факультет Южно-Уральского государственного Университета ПАМЯТЬ УСТРОЙСТВО УПРАВЛЕНИЯ АРИФМЕТИКО- ЛОГИЧЕСКОЕ УСТРОЙСТВО ВВОДВЫВОД

Классификация Флинта Механико - математический факультет Южно-Уральского государственного Университета

SISD-компьютеры

SIMD-компьютеры Механико - математический факультет Южно-Уральского государственного Университета

MISD-компьютеры Механико - математический факультет Южно-Уральского государственного Университета

MIMD-компьютеры Механико - математический факультет Южно-Уральского государственного Университета

Компоненты компьютера Центральный процессор и оперативная память ядро системы Внешняя память и устройства ввода/вывода «периферия» Коммуникации между компонентами системы осуществляется посредством шин Механико - математический факультет Южно-Уральского государственного Университета

Схема компьютера

Технологии параллельного программирования Механико - математический факультет Южно-Уральского государственного Университета Все, что начинается хорошо, кончается плохо. Все, что начинается плохо, кончается еще хуже. Из законов Мерфи

Особенности программирования параллельных вычислений Модель программирования Алгоритм Информационный граф Вход Выход (n, s) (v, d) Механико - математический факультет Южно-Уральского государственного Университета

Примеры алгоритмов Механико - математический факультет Южно-Уральского государственного Университета Вход Выход Вход Выход Последовательный Параллельный

Основные черты последовательной модели Применение стандартных языков программирования Хорошая переносимость программ Невысокая производительность Механико - математический факультет Южно-Уральского государственного Университета

Основные черты параллельной модели Высокая производительность программ Применение специальных приёмов программирования Более высокая трудоёмкость программирования Проблемы с переносимостью программ Механико - математический факультет Южно-Уральского государственного Университета

Фундаментальные требования к параллельным программам Параллелизм Локальность Масштабируемость Детерминизм Механико - математический факультет Южно-Уральского государственного Университета

Параллелизм Данных Задач Механико - математический факультет Южно-Уральского государственного Университета

Параллелизм данных Основные особенности подхода: Обработкой данных управляет одна программа Пространство имен является глобальным Слабая синхронизация вычислений на параллельных процессорах Параллельные операции над элементами массива выполняются одновременно на всех доступных процессорах Механико - математический факультет Южно-Уральского государственного Университета

Параллелизм задач Повышенная трудоёмкость разработки и отладки программы Программист отвечает за равномерную и сбалансированную загрузку процессоров Минимизация обмена данными между задачами Возникновение конфликтов Механико - математический факультет Южно-Уральского государственного Университета

Модель задача/канал Механико - математический факультет Южно-Уральского государственного Университета задача асинхронная передача синхронная передача

Параллелизм задач Большая гибкостьБольшая свобода Механико - математический факультет Южно-Уральского государственного Университета Максимальное быстродействие

Масштабируемость Независимость результата выполнения параллельной программы от числа процессоров. Механико - математический факультет Южно-Уральского государственного Университета

Детерминизм Механико - математический факультет Южно-Уральского государственного Университета

Закон Амдала Механико - математический факультет Южно-Уральского государственного Университета - один процессор - N процессоров - коэффициент ускорения выполнения программы

Закон Амдала II коэффициент ускорения выполнения программы S - доля последовательной части P - доля параллельной части N - число независимых ветвей/процессоров Механико - математический факультет Южно-Уральского государственного Университета

Две парадигмы параллельного программирования Равномерная загрузка процессоров Эффективная организация обмена информацией между задачами Механико - математический факультет Южно-Уральского государственного Университета

Базовый набор операций Операции управления данными Операции над массивами в целом, а также их фрагментами Условные операции Операции приведения Операции сдвига Операции сканирования Операции, связанные с пересылкой данных Механико - математический факультет Южно-Уральского государственного Университета

Управление данными Механико - математический факультет Южно-Уральского государственного Университета

Операции над массивами Механико - математический факультет Южно-Уральского государственного Университета

Условные операции Механико - математический факультет Южно-Уральского государственного Университета

Операции приведения Механико - математический факультет Южно-Уральского государственного Университета

Операции сдвига Механико - математический факультет Южно-Уральского государственного Университета

Операции сканирования Механико - математический факультет Южно-Уральского государственного Университета

Операции пересылки данных Механико - математический факультет Южно-Уральского государственного Университета

Разработка параллельного алгоритма Механико - математический факультет Южно-Уральского государственного Университета проблема декомпозиция коммуникации укрупнение планирование вычислений подзадачи процессоры

Декомпозиция (сегментирование) Метод декомпозиции данных Метод функциональной декомпозиции Механико - математический факультет Южно-Уральского государственного Университета

Рекомендации по декомпозиции Количество подзадач должно на порядок превосходить количество процессоров Следует избегать лишних вычислений и пересылок данных Подзадачи должны быть примерно одного размера С увеличением объема задачи количество подзадач увеличивалось Механико - математический факультет Южно-Уральского государственного Университета

Зернистость Механико - математический факультет Южно-Уральского государственного Университета мелкозернистаясреднеблочныйкрупноблочный < 20 ~ 500 независимые программы Через разделяемые переменныеЧерез сообщения

Независимость частей программы Независимость по данным Независимость по управлению Независимость по ресурсам Механико - математический факультет Южно-Уральского государственного Университета do k = 1, m if (a[k] < c) then a[k] = 1 endif enddo do k = 1, m if (a[k-1] < c) then a[k] = 1 endif enddo

Проектирование коммуникаций Локальные Глобальные Структурированные Неструктурированные Статические Динамические Синхронные Асинхронные Механико - математический факультет Южно-Уральского государственного Университета

Рекомендации по проектированию коммуникаций Количество коммуникаций у подзадач должно быть примерно одинаковым Желательно использовать локальные коммуникации Коммуникации должны быть, по возможности, параллельными Механико - математический факультет Южно-Уральского государственного Университета

Тупиковые ситуации Механико - математический факультет Южно-Уральского государственного Университета

Реализация обмена сообщениями MPI (Message Passing Interface) PVM (Parallel Virtual Machine) RPC (Remote Procedure Control) CORBA (Common Object Request Broker Architecture) DCOM (Distributed Component Object Model) Механико - математический факультет Южно-Уральского государственного Университета

Укрупнение Механико - математический факультет Южно-Уральского государственного Университета

Укрупнение Снижение затрат на коммуникации При необходимом дублировании вычислений или данных не должно быть потерь в производительности или масштабируемости Результирующие задачи должны иметь примерно одинаковую трудоёмкость Сохранение масштабируемости Сохранение возможности параллельного выполнения Снижение стоимости и трудоёмкости разработки Механико - математический факультет Южно-Уральского государственного Университета

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

Характеристики быстродействия Факторы влияющие на производительность Технология выполнения аппаратной части Архитектура вычислительной системы Методы управления ресурсами Эффективность параллельного алгоритма Особенности структуры данных Эффективность языка программирования Квалификация программиста Эффективность транслятора Механико - математический факультет Южно-Уральского государственного Университета

Последовательность действий Разработка алгоритма Предварительный анализ быстродействия программы Оценка трудоёмкости и целесообразности разработки параллельной программы Кодирование Механико - математический факультет Южно-Уральского государственного Университета

Список литературы: Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. -СПб.: Петербург, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -СПб: BHV, А.С.Антонов "Параллельное программирование с использованием технологии MPI", издательстве Московского университета 2004 А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003, 208 с Калиткин Н.Н. Численные методы. - М.: Наука, с В. Д. Корнеев Параллельное программирование в MPI, издательство "Регулярная и хаотическая динамика" 2003 г., стр. Грегори Р. Эндрюс Основы многопоточного, параллельного и распределенного программирования, издательство "Вильямс" 2003 г стр. Богачев К.Ю. Основы параллельного программирования издательство "Бином. Лаборатория знаний" 2003 г стр. Воеводин В.В. Параллельные структуры алгоритмов и программ. - М.: ОВМ АН СССР, с. Механико - математический факультет Южно-Уральского государственного Университета