Учебное пособие содержит материал для работы в области параллельного программирования. Дается краткая характеристика принципов построения параллельных вычислительных систем, рассматриваются математические модели параллельных алгоритмов и программ для анализа эффективности параллельных вычислений, приводятся примеры конкретных параллельных методов для решения типовых задач вычислительной математики. Пособие подготовлено по заданию Инновационной образовательной программы Нижегородского госуниверситета им. Н.И. Лобачевского в рамках Национального проекта \"Образование\". Для студентов, аспирантов и специалистов, изучающих и практически использующих параллельные компьютерные системы для решения вычислительно трудоемких задач.

Введение......17Лекция 1. Принципы построения параллельных вычислительных систем......231.1. Пути достижения параллелизма......231.2. Примеры параллельных вычислительных систем......251.3. Классификация вычислительных систем......361.4. Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах......411.5. Характеристика системных платформ для построения кластеров......451.6. Краткий обзор лекции......461.7. Обзор литературы......471.8. Контрольные вопросы......471.9. Задачи и упражнения......48Лекция 2. Моделирование и анализ параллельных вычислений......492.1. Модель вычислений в виде графа «операции — операнды»......492.2. Описание схемы параллельного выполнения алгоритма......512.3. Определение времени выполнения параллельного алгоритма......522.4. Показатели эффективности параллельного алгоритма......552.5. Учебный пример. Вычисление частных сумм последовательности числовых значений......572.6. Оценка максимально достижимого параллелизма......632.7. Анализ масштабируемости параллельных вычислений......662.8. Краткий обзор лекции......672.9. Обзор литературы......692.10. Контрольные вопросы......692.11. Задачи и упражнения......70Лекция 3. Оценка коммуникационной трудоемкости параллельных алгоритмов......713.1. Общая характеристика механизмов передачи данных......713.2. Анализ трудоемкости основных операций передачи данных......733.3. Методы логического представления топологии коммуникационной среды......833.4. Оценка трудоемкости операций передачи данных для кластерных систем......853.5. Краткий обзор лекции......893.6. Обзор литературы......903.7. Контрольные вопросы......903.8. Задачи и упражнения......91Лекция 4. Принципы разработки параллельных методов......924.1. Моделирование параллельных программ......944.2. Этапы разработки параллельных алгоритмов......964.3. Параллельное решение гравитационной задачи N тел......1044.4. Краткий обзор лекции......1074.5. Обзор литературы......1084.6. Контрольные вопросы......1084.7. Задачи и упражнения......108Лекция 5. Параллельное программирование на основе MPI......1105.1. MPI: основные понятия и определения......1125.2. Введение в разработку параллельных программ с использованием MPI......1155.3. Операции передачи данных между двумя процессами......1335.4. Коллективные операции передачи данных......1385.5. Производные типы данных в MPI......1445.6. Управление группами процессов и коммуникаторами......1565.7. Виртуальные топологии......1615.8. Дополнительные сведения о MPI......1675.9. Краткий обзор лекции......1715.10. Обзор литературы......1735.11. Контрольные вопросы......1735.12. Задачи и упражнения......174Лекция 6. Параллельные методы умножения матрицы на вектор......1766.1. Принципы распараллеливания......1776.2. Постановка задачи......1796.3. Последовательный алгоритм......1796.4. Разделение данных......1806.5. Умножение матрицы на вектор при разделении данных по строкам......1806.6. Умножение матрицы на вектор при разделении данных по столбцам......1916.7. Умножение матрицы на вектор при блочном разделении данных......1956.8. Краткий обзор лекции......2016.9. Обзор литературы......2026.10. Контрольные вопросы......2036.11. Задачи и упражнения......204Лекция 7. Параллельные методы матричного умножения......2057.1. Постановка задачи......2057.2. Последовательный алгоритм......2067.3. Умножение матриц при ленточной схеме разделения данных......2077.4. Алгоритм Фокса умножения матриц при блочном разделении данных......2147.5. Алгоритм Кэннона умножения матриц при блочном разделении данных......2287.6. Краткий обзор лекции......2327.7. Обзор литературы......2347.8. Контрольные вопросы......2347.9. Задачи и упражнения......235Лекция 8. Параллельные методы решения систем линейных уравнений......2368.1. Постановка задачи......2368.2. Алгоритм Гаусса......2378.3. Метод сопряженных градиентов......2528.4. Краткий обзор лекции......2588.5. Обзор литературы......2608.6. Контрольные вопросы......2608.7. Задачи и упражнения......261Лекция 9. Параллельные методы сортировки......2629.1. Принципы распараллеливания......2639.2. Масштабирование параллельных вычислений......2649.3. Пузырьковая сортировка......2659.4. Сортировка Шелла......2739.5. Быстрая сортировка......2789.6. Краткий обзор лекции......2959.7. Обзор литературы......2969.8. Контрольные вопросы......2979.9. Задачи и упражнения......297Лекция 10. Параллельные методы на графах......29910.1. Задача поиска всех кратчайших путей......30110.2. Задача нахождения минимального охватывающего дерева......31010.3. Задача оптимального разделения графов......31710.4. Краткий обзор лекции......32610.5. Обзор литературы......32710.6. Контрольные вопросы......32810.7. Задачи и упражнения......328Лекция 11. Параллельные методы решения дифференциальных уравнений в частных производных......32911.1. Последовательные методы решения задачи Дирихле......33011.2. Организация параллельных вычислений для систем с общей памятью......33311.3. Организация параллельных вычислений для систем с распределенной памятью......35311.4. Краткий обзор лекции......36711.5. Обзор литературы......36911.6. Контрольные вопросы......36911.7. Задачи и упражнения......370Лекция 12. Программная система ПараЛаб для изучения и исследования методов параллельных вычислений......37112.1. Введение......37112.2. Общая характеристика системы......37212.3. Формирование модели вычислительной системы......37512.4. Постановка вычислительной задачи и выбор параллельного метода решения......38112.5. Определение графических форм наблюдения за процессом параллельных вычислений......39912.6. Накопление и анализ результатов экспериментов......40612.7. Выполнение вычислительных экспериментов......40812.8. Использование результатов экспериментов......41512.9. Краткий обзор лекции......41612.10. Обзор литературы......417Список литературы......418Основная литература......418Дополнительная литература......418Учебно-методические пособия......422Информационные ресурсы сети Интернет......423

Гергель В.П.
Гергель Виктор Павлович - доктор технических наук, профессор, декан факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского. Автор нового научного направления в области математических моделей, методов и программных средств информационного обеспечения процессов поиска рациональных вариантов. Имеет значительный опыт профессиональной деятельности в области разработки сложного программного обеспечения для поддержки процессов выбора решений. Активно занимается учебной и научной работой в области высокопроизводительных параллельных вычислений. Автор более 120 научных работ.