Теория и практика параллельных вычислений

Введение
Пути достижения параллелизма
Примеры параллельных вычислительных систем
Суперкомпьютеры
Программа ASCI
Система BlueGene
МВС-
МВС-0
Кластеры

Кластер Beowulf
Кластер ACVelocity Cluster
Кластер NCSA NT Supercluster
Кластер Thunder
Высокопроизводительный вычислительный кластер ННГУ
Классификация вычислительных систем
Мультипроцессоры

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

Обзор литературы
Контрольные вопросы
Задачи и упражнения

Моделирование и анализ параллельных вычислений

Модель вычислений в виде графа "операции – операнды"
Описание схемы параллельного выполнения алгоритма
Определение времени выполнения параллельного алгоритма
Определение времени выполнения параллельного алгоритма - 2
Показатели эффективности параллельного алгоритма
Учебный пример Вычисление частных сумм последовательности числовых значений
Последовательный алгоритм суммирования
Каскадная схема суммирования

Модифицированная каскадная схема
Вычисление всех частных сумм
Оценка максимально достижимого параллелизма
Анализ масштабируемости параллельных вычислений
Краткий обзор лекции
Обзор литературы
Контрольные вопросы

Задачи и упражнения

Теория и практика параллельных вычислений

Алгоритмы маршрутизации
Методы передачи данных

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

Циклический сдвиг
Методы логического представления топологии коммуникационной среды
Представление кольцевой топологии в виде гиперкуба
Отображение топологии решетки на гиперкуб
Оценка трудоемкости операций передачи данных для кластерных систем
Краткий обзор лекции
Обзор литературы

Контрольные вопросы
Задачи и упражнения
Принципы разработки параллельных методов
Моделирование параллельных программ
Этапы разработки параллельных алгоритмов
Разделение вычислений на независимые части
Выделение информационных зависимостей

Масштабирование набора подзадач
Распределение подзадач между процессорами
Параллельное решение гравитационной задачи N тел
Разделение вычислений на независимые части
Выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности параллельных вычислений
Краткий обзор лекции
Обзор литературы

Контрольные вопросы
Задачи и упражнения

Теория и практика параллельных вычислений

Параллельное программирование на основе MPI
MPI: основные понятия и определения
Понятие параллельной программы
Операции передачи данных
Понятие коммуникаторов
Типы данных
Виртуальные топологии

Декартовы топологии (решетки)
Топологии графа
Разработка параллельных программ с использованием MPI на алгоритмическом языке Fortran
Общая характеристика среды выполнения MPI-программ
Дополнительные возможности стандарта MPI-2
Краткий обзор лекции

Обзор литературы
Контрольные вопросы
Задачи и упражнения
Основы MPI
Инициализация и завершение MPI-программ
Определение количества и ранга процессов
Передача сообщений
Прием сообщений
Первая параллельная программа с использованием MPI

Определение времени выполнение MPI-программы
Начальное знакомство с коллективными операциями передачи данных
Передача данных от одного процесса всем процессам программы
Передача данных от всех процессов одному процессу Операция редукции
Синхронизация вычислений
Аварийное завершение параллельной программы
Операции передачи данных между двумя процессами
Режимы передачи данных

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

Производные типы данных в MPI
Понятие производного типа данных
Способы конструирования производных типов данных
Непрерывный способ конструирования
Векторный способ конструирования
Индексный способ конструирования
Структурный способ конструирования
Объявление производных типов и их удаление
Формирование сообщений при помощи упаковки и распаковки данных

Формирование сообщений при помощи упаковки и распаковки данных - 2
Управление группами процессов и коммуникаторами
Управление группами
Управление коммуникаторами
Пример 2

Теория и практика параллельных вычислений

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

Постановка задачи
Последовательный алгоритм
Разделение данных
Умножение матрицы на вектор при разделении данных по строкам
Выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности
Программная реализация

Результаты вычислительных экспериментов
Умножение матрицы на вектор при разделении данных по столбцам
Определение подзадач и выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности
Результаты вычислительных экспериментов
Умножение матрицы на вектор при блочном разделении данных

Определение подзадач
Выделение информационных зависимостей
Анализ эффективности
Результаты вычислительных экспериментов
Краткий обзор лекции
Обзор литературы
Контрольные вопросы
Задачи и упражнения

Теория и практика параллельных вычислений

Постановка задачи
Последовательный алгоритм

Умножение матриц при ленточной схеме разделения данных
Определение подзадач
Выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности
Результаты вычислительных экспериментов
Алгоритм Фокса умножения матриц при блочном разделении данных
Определение подзадач

Масштабирование и распределение подзадач по процессорам
Программная реализация
Программная реализация - 4
Результаты вычислительных экспериментов
Алгоритм Кэннона умножения матриц при блочном разделении данных

Определение подзадач
Выделение информационных зависимостей
Анализ эффективности
Результаты вычислительных экспериментов
Краткий обзор лекции
Обзор литературы
Контрольные вопросы
Задачи и упражнения
Пример 1

Теория и практика параллельных вычислений

Решение систем линейных уравнений
Постановка задачи
Алгоритм Гаусса
Последовательный алгоритм
Прямой ход алгоритма Гаусса
Обратный ход алгоритма Гаусса

Определение подзадач
Выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности
Программная реализация
Результаты вычислительных экспериментов
Метод сопряженных градиентов

Последовательный алгоритм
Организация параллельных вычислений
Анализ эффективности
Результаты вычислительных экспериментов
Краткий обзор лекции
Обзор литературы
Контрольные вопросы
Задачи и упражнения
Пример 1

Теория и практика параллельных вычислений

Параллельные методы сортировки
Принципы распараллеливания
Масштабирование параллельных вычислений
Последовательный алгоритм
Алгоритм чет-нечетной перестановки
Определение подзадач и выделение информационных зависимостей

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

Организация параллельных вычислений
Обобщенный алгоритм быстрой сортировки
Программная реализация
Краткий обзор лекции

Обзор литературы
Контрольные вопросы
Задачи и упражнения
Пример 1

Теория и практика параллельных вычислений

Параллельные методы на графах
Задача поиска всех кратчайших путей
Последовательный алгоритм Флойда

Разделение вычислений на независимые части
Выделение информационных зависимостей
Масштабирование и распределение подзадач по процессорам
Анализ эффективности параллельных вычислений
Программная реализация
Результаты вычислительных экспериментов
Задача нахождения минимального охватывающего дерева
Последовательный алгоритм Прима

Выделение информационных зависимостей
Задача оптимального разделения графов
Постановка задачи оптимального разделения графов
Метод рекурсивного деления пополам
Геометрические методы
Покоординатное разбиение
Рекурсивный инерционный метод деления пополам

Деление сети с использованием кривых Пеано
Комбинаторные методы
Деление с учетом связности
Алгоритм Кернигана – Лина
Сравнение алгоритмов разбиения графов
Краткий обзор лекции
Обзор литературы
Контрольные вопросы
Задачи и упражнения
Пример 1

Теория и практика параллельных вычислений

Параллельные методы решения дифференциальных уравнений в частных производных
Последовательные методы решения задачи Дирихле
Организация параллельных вычислений для систем с общей памятью
Использование OpenMP для организации параллелизма
Проблема синхронизации параллельных вычислений

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

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

Оценка трудоемкости операций передачи данных
Краткий обзор лекции
Обзор литературы
Контрольные вопросы
Задачи и упражнения
Пример 5

Теория и практика параллельных вычислений

Введение
Общая характеристика системы
Накопление и анализ результатов экспериментов
Просмотр результатов
Выполнение вычислительных экспериментов
Последовательное выполнение экспериментов
Выполнение экспериментов по шагам

Выполнение нескольких экспериментов
Выполнение серии экспериментов
Выполнение реальных вычислительных экспериментов
Запоминание результатов
Краткий обзор лекции
Обзор литературы
Формирование модели вычислительной системы
Выбор топологии сети

Задание количества процессоров
Задание характеристик сети
Постановка вычислительной задачи и выбор параллельного метода решения
Сортировка данных
Пузырьковая сортировка
Сортировка Шелла
Быстрая сортировка
Умножение матрицы на вектор

Умножение матрицы на вектор при разделении данных по столбцам
Умножение матрицы на вектор при блочном разделении данных
Матричное умножение
Ленточный алгоритм
Блочные алгоритмы Фокса и Кэннона
Решение систем линейных уравнений
Алгоритм Гаусса
Обработка графов

Алгоритм Прима поиска минимального охватывающего дерева
Алгоритм Дейкстры поиска кратчайших путей
Определение графических форм наблюдения за процессом параллельных вычислений
Область "Выполнение эксперимента"
Область "Текущее состояние массива"
Область "Результат умножения матрицы на вектор"
Область "Результат умножения матриц"
Область "Результат решения системы уравнений"
Область "Результат обработки графа"

Выбор процессора

Ремонт и восстановление жестких дисков см. раздел
Безопасность жизнедеятельности см. раздел

---

---