НОУ ИНТУИТ | Повышение квалификации | Введение в методы параллельного программирования

Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней

Темы: Программирование, Параллельное программирование, Суперкомпьютерные технологии

Учебное пособие содержит материал, для работы в области параллельного программирования.

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

Цель: Для студентов, аспирантов и специалистов, изучающих и практически использующих параллельные компьютерные системы для решения вычислительно трудоемких задач.

Вам нравится? Нравится 1 студенту

| Поделиться |

Поддержать

Занятие	Заголовок <<	Дата изучения
	Экзамен экстерном	-
Лекция 1	Введение В лекции дается общая информация о курсе. Вводится понятие параллельных вычислений и разъясняется их необходимость. Рассказывается о сдерживающих факторах развития этой отрасли, а также предоставляется характеристика необходимых знаний и умений для работы в области вычислений Оглавление Введение Введение Содержание Параллельные вычисления Понятие параллельных вычислений Необходимость параллельных вычислений Сдерживающие факторы Характеристика необходимых знаний и умений Содержание курса Структура учебного плана Литература Заключение Вопросы для обсуждения Следующая тема Авторский коллектив О проекте	-
Лекция 2	Принципы построения параллельных вычислительных систем Лекция посвящена рассмотрению принципов построения параллельных вычислительных систем (ПВС). Дана краткая характеристика способов достижения параллелизма, приведены примеры ПВС. Приводится классификация параллельных вычислительных систем, рассматриваются типовые топологии сетей передачи данных в ПВС. Оглавление Пути достижения параллелизма Примеры параллельных вычислительных систем Суперкомпьютеры Программа ASCI Система BlueGene МВС-1000 МВС-15000 Кластеры Кластер Beowulf Кластер AC3 Velocity Cluster Кластер NCSA NT Supercluster Кластер Thunder Высокопроизводительный вычислительный кластер ННГУ Классификация вычислительных систем Систематика Флинта Детализация систематики Флинта Мультипроцессоры Мультикомпьютеры Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах Топология сети передачи данных Примеры топологий сети передачи данных Топология сети вычислительных кластеров Характеристики топологии сети Характеристика системных платформ для построения кластеров Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 1 18 минут	6 заданий	-
Лекция 3	Моделирование и анализ параллельных вычислений В лекции описывается модель вычислений в виде графа "операции – операнды". Приводятся основные показатели качества параллельных методов — ускорение (speedup), эффективность (efficiency), стоимость (cost) и масштабируемость (scalability) вычислений. Введенные понятия демонстрируются на примере учебной задачи нахождения частных сумм последовательности числовых значений Оглавление Модель вычислений в виде графа "операции – операнды" Описание схемы параллельного выполнения алгоритма Определение времени выполнения параллельного алгоритма Показатели эффективности параллельного алгоритма Учебный пример. Вычисление частных сумм последовательности числовых значений Задача нахождения частных сумм Последовательный алгоритм суммирования Каскадная схема суммирования Модифицированная каскадная схема Вычисление всех частных сумм Оценка максимально достижимого параллелизма Анализ масштабируемости параллельных вычислений Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 2 18 минут	6 заданий	-
Лекция 4	Оценка коммуникационной трудоемкости параллельных алгоритмов Лекция посвящена вопросам анализа информационных потоков, возникающих при выполнении параллельных алгоритмов. Дается общая характеристика механизмов передачи данных, проводится анализ трудоемкости основных операций обмена информацией, рассматриваются методы логического представления структуры многопроцессорных вычислительных систем. Оглавление Общая характеристика механизмов передачи данных Алгоритмы маршрутизации Методы передачи данных Анализ трудоемкости основных операций передачи данных Анализ трудоемкости основных операций передачи данных Передача данных между двумя процессорами сети Передача данных от одного процессора всем остальным процессорам сети Передача данных от всех процессоров всем процессорам сети Обобщенная передача данных от одного процессора всем остальным процессорам сети Обобщенная передача данных от всех процессоров всем процессорам сети Циклический сдвиг Методы логического представления топологии коммуникационной среды Методы логического представления топологии коммуникационной среды Представление кольцевой топологии в виде гиперкуба Отображение топологии решетки на гиперкуб Оценка трудоемкости операций передачи данных для кластерных систем Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 3 21 минута	7 заданий	-
Лекция 5	Параллельное программирование на основе MPI В лекции рассматривается стандарт для программирования в системах с распределенной памятью MPI. Дается обзор истории возникновения и развития стандарта, а также перечисляются его основные возможности. Приводятся примеры программ, использующих рассматриваемый стандарт. Оглавление MPI: основные понятия и определения Понятие параллельной программы Операции передачи данных Понятие коммуникаторов Типы данных Виртуальные топологии Введение в разработку параллельных программ с использованием MPI Основы MPI Инициализация и завершение MPI-программ Определение количества и ранга процессов Передача сообщений Прием сообщений Первая параллельная программа с использованием MPI Определение времени выполнение MPI-программы Начальное знакомство с коллективными операциями передачи данных Передача данных от одного процесса всем процессам программы Передача данных от всех процессов одному процессу. Операция редукции Синхронизация вычислений Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Лекция 6	Операции передачи данных между процессами и производные типы данных в MPI В лекции продолжается рассматриваться параллельное программирование на основе MPI. Рассказывается об операциях передачи данных между процессами и производных типах данных в MPI. Оглавление Операции передачи данных между двумя процессами Режимы передачи данных Организация неблокирующих обменов данными между процессами Одновременное выполнение передачи и приема Коллективные операции передачи данных Обобщенная передача данных от одного процесса всем процессам Обобщенная передача данных от всех процессов одному процессу Общая передача данных от всех процессов всем процессам Дополнительные операции редукции данных Производные типы данных в MPI Понятие производного типа данных Способы конструирования производных типов данных Непрерывный способ конструирования Векторный способ конструирования Индексный способ конструирования Структурный способ конструирования Объявление производных типов и их удаление Формирование сообщений при помощи упаковки и распаковки данных	-
Лекция 7	Управление группами, виртуальные топологии в MPI Лекция посвящена управлению группами процессов и коммуникаторами, виртуальным топологиям и дополнительным возможностям MPI. Оглавление Управление группами процессов и коммуникаторами Управление группами Управление коммуникаторами Виртуальные топологии Декартовы топологии (решетки) Топологии графа Дополнительные сведения о MPI Разработка параллельных программ с использованием MPI на алгоритмическом языке Fortran Общая характеристика среды выполнения MPI-программ Дополнительные возможности стандарта MPI-2и Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 4 36 минут	12 заданий	-
Лекция 8	Принципы разработки параллельных методов В лекции рассматриваются базовые принципы разработки параллельных алгоритмов. Описываются основные понятия, подробно разбираются все этапы создания и анализа параллельных алгоритмов. Приводится пример применения обсуждаемых методов. Оглавление Моделирование параллельных программ Этапы разработки параллельных алгоритмов Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование набора подзадач Распределение подзадач между процессорами Параллельное решение гравитационной задачи N тел Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислени Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 5 18 минут	6 заданий	-
Лекция 9	Параллельные методы умножения матрицы на вектор В лекции рассматривается задача умножения матрицы на вектор. Приводится постановка задачи и последовательный алгоритм ее решения. Описываются методы разделения матрицы между процессорами вычислительной системы, которые необходимы для параллельной реализации матричных операций. Далее излагаются три возможных подхода к параллельной реализации алгоритма умножения матрицы на вектор. Оглавление Принципы распараллеливания Постановка задачи Последовательный алгоритм Разделение данных Умножение матрицы на вектор при разделении данных по строкам Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Программная реализация Результаты вычислительных экспериментов Умножение матрицы на вектор при разделении данных по столбцам Определение подзадач и выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Результаты вычислительных экспериментов Умножение матрицы на вектор при блочном разделении данных Определение подзадач Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Результаты вычислительных экспериментов Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 6 18 минут	6 заданий	-
Лекция 10	Параллельные методы матричного умножения В лекции рассматривается одна из основных задач матричных вычислений— умножение матриц. Приводится постановка задачи и дается последовательный алгоритм ее решения. Далее описываются возможные подходы к параллельной реализации алгоритма и подробно рассматриваются наиболее широко известные алгоритмы: алгоритм, основанный на ленточной схеме разделения данных, алгоритм Фокса (Fox) и алгоритм Кэннона (Cannon). Оглавление Постановка задачи Последовательный алгоритм Умножение матриц при ленточной схеме разделения данных Определение подзадач Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Результаты вычислительных экспериментов Алгоритм Фокса умножения матриц при блочном разделении данных Определение подзадач Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Программная реализация Результаты вычислительных экспериментов Алгоритм Кэннона умножения матриц при блочном разделении данных Определение подзадач Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Результаты вычислительных экспериментов Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 7 18 минут	6 заданий	-
Лекция 11	Параллельные методы решения систем линейных уравнений В лекции рассматривается задача решения систем линейных уравнений. Приводятся необходимые определения и постановка задачи. Описывается последовательный и параллельный варианты одного из прямых методов решения линейных систем общего вида – метода Гаусса. Далее дается описание последовательного и параллельного алгоритмов, реализующих итерационный метод сопряженных градиентов. Оглавление Постановка задачи Алгоритм Гаусса Последовательный алгоритм Прямой ход алгоритма Гаусса Обратный ход алгоритма Гаусса Определение подзадач Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Программная реализация Результаты вычислительных экспериментов Метод сопряженных градиентов Последовательный алгоритм Организация параллельных вычислений Анализ эффективности Результаты вычислительных экспериментов Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 8 18 минут	6 заданий	-
Лекция 12	Параллельные методы сортировки В лекции рассматриваются различные алгоритмы сортировки данных. Излагаются как общие принципы, применяемые при распараллеливании, так и конкретные алгоритмы. Теоретически оценивается эффективность рассматриваемых алгоритмов. Приводятся и анализируются результаты вычислительных экспериментов. Оглавление Принципы распараллеливания Пузырьковая сортировка Последовательный алгоритм Алгоритм чет-нечетной перестановки Определение подзадач и выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности Сортировка Шелла Последовательный алгоритм Организация параллельных вычислений Анализ эффективности Быстрая сортировка Последовательный алгоритм Параллельный алгоритм быстрой сортировки Анализ эффективности Результаты вычислительных экспериментов Обобщенный алгоритм быстрой сортировки Программная реализация Результаты вычислительных экспериментов Сортировка с использованием регулярного набора образцов Организация параллельных вычислений Анализ эффективности Результаты вычислительных экспериментов Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 9 24 минуты	8 заданий	-
Лекция 13	Параллельные методы обработки графов В лекции рассматриваются различные типовые задачи, возникающие при обработке графов. Приводятся алгоритмы, применяемые для решения этих задач, и обсуждаются пути их распараллеливания. Дается теоретическая оценка эффективности рассматриваемых алгоритмов. Анализируются результаты вычислительных экспериментов. Оглавление Задача поиска всех кратчайших путей Последовательный алгоритм Флойда Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислений Результаты вычислительных экспериментов Задача нахождения минимального охватывающего дерева Последовательный алгоритм Прима Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислений Результаты вычислительных экспериментов Задача оптимального разделения графов Постановка задачи оптимального разделения графов Метод рекурсивного деления пополам Покоординатное разбиение Рекурсивный инерционный метод деления пополам Деление сети с использованием кривых Пеано Комбинаторные методы Деление с учетом связности Алгоритм Кернигана – Лина Сравнение алгоритмов разбиения графов Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 10 27 минут	9 заданий	-
Лекция 14	Параллельные методы решения дифференциальных уравнений в частных производных В лекции рассматриваются вопросы организации параллельных вычислений для решения задач, в которых при математическом моделировании используются дифференциальные уравнения в частных производных. Для численного решения подобных задач обычно применяется метод конечных разностей (метод сеток), обладающий высокой вычислительной трудоемкостью. В лекции последовательно разбираются возможные способы распараллеливания сеточных методов на многопроцессорных вычислительных системах с общей и распределенной памятью. При этом большое внимание уделяется проблемам, возникающим при организации параллельных вычислений, анализу причин появления таких проблем и нахождению путей их преодоления. Для наглядной демонстрации излагаемого материала в качестве учебного примера рассматривается проблема численного решения задачи Дирихле для уравнения Пуассона. Оглавление Последовательные методы решения задачи Дирихле Организация параллельных вычислений для систем с общей памятью Использование OpenMP для организации параллелизма Проблема синхронизации параллельных вычислений Возможность неоднозначности вычислений в параллельных программах Проблема взаимоблокировки Исключение неоднозначности вычислений Волновые схемы параллельных вычислений Балансировка вычислительной нагрузки процессоров Организация параллельных вычислений для систем с распределенной памятью Общие принципы распределения данных Обмен информацией между процессорами Коллективные операции обмена информацией Организация волны вычислений Блочная схема разделения данных Оценка трудоемкости операций передачи данных Краткий обзор лекции Контрольные вопросы Задачи и упражнения Обзор литературы	-
Тест 11 18 минут	6 заданий	-
Лекция 15	Параллельные методы многоэкстремальной оптимизации В лекции рассматриваются задачи минимизации функции, дается обзор методов их решения и программная реализация. Оглавление Задачи минимизации некоторой функции Постановка задачи Обзор методов Индексная схема учета ограничений Последовательный алгоритм Редукция размерности Множественные отображения Принцип распараллеливания Параллельный алгоритм Программная реализация Краткий обзор лекции Контрольные вопросы Обзор литературы	-
Лекция 16	Программная система ПараЛаб для изучения и исследования методов параллельных вычислений В лекции описывается программная система Параллельная Лаборатория (сокращенное наименование – ПараЛаб), которая предназначена для учебного применения студентами и преподавателями вузов в целях исследования и изучения параллельных алгоритмов решения сложных вычислительных задач в рамках лабораторного практикума по различным учебным курсам в области параллельного программирования. Оглавление Введение Общая характеристика системы Формирование модели вычислительной системы Выбор топологии сети Задание количества процессоров Задание характеристик сети Постановка вычислительной задачи и выбор параллельного метода решения Применяемые параллельные алгоритмы Выбор задачи Определение параметров задачи Определение метода решения Редактор графов Определение графических форм наблюдения за процессом параллельных вычислений Область "Выполнение эксперимента" Область "Текущее состояние массива" Область "Результат умножения матрицы на вектор" Область "Результат умножения матриц" Область "Результат решения системы уравнений" Область "Результат обработки графа" Выбор процессора Накопление и анализ результатов экспериментов Просмотр результатов Выполнение вычислительных экспериментов Последовательное выполнение экспериментов Выполнение нескольких экспериментов Выполнение серии экспериментов Использование результатов экспериментов Запоминание результатов Краткий обзор лекции Обзор литературы	-
Тест 12 18 минут	6 заданий	-
5 часов	Экзамен	-

Авторизоваться

Введение в методы параллельного программирования

План занятий