МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«МОСКОВСКИЙ АВТОМОБИЛЬНО-ДОРОЖНЫЙ
ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ (МАДИ)»
Кафедра «Автоматизированные системы управления»
А.В. В
ОЛОСОВА
ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ
Учебное пособие
МОСКВА
МАДИ
2020
УДК 004.9
ББК 32.81
В 683
Волосова, А.В.
В683
Параллельные методы и алгоритмы [Электронный ресурс]: учебное пособие/ А.В.
Волосова. ‒ М.: МАДИ, Электронные текстовые и графические данные (5,35 Мбайт). 2020.
– 176 с. Учебное электронное издание комбинированного распространения: 1 CD-диск. –
Систем. требования: РС 486 DX-33; Microsoft Windows XP; 2-скоростной дисковод CD-
ROM; Adobe Reader 6.0. Официальный сайт Московского
Автомобильно-дорожного
государственного технического университета (МАДИ). Режим доступа: http://www.
http://
lib.madi.ru //— Загл. с титул. экрана.
В учебном пособии рассматриваются вопросы эффективного решения больших
задач на компьютерах с параллельной архитектурой: архитектуры параллельных
вычислительных систем, численные методы решения задач,
технологии параллельного
программирования, проблемы современных параллельных вычислений
Учебное пособие может быть рекомендовано студентам по направлениям
подготовки
09.03.01
«Информатика
и
вычислительная
техника»,
09.03.02
«Информационные системы и технологии», 38.03.01
«Экономика» и др.
УДК
004.9 ББК
32.81
Рецензенты:
д-р техн. наук, проф., заведующий кафедрой "АСУ" МАДИ Максимычев О.И.
д-р. техн. наук, проф., Министерство по делам Северного Кавказа Голубятников И.В.
3
Введение ......................................................................................................................................... 6
Глава 1. Введение в параллельные вычисления ......................................................................... 7
1.1.
Параллелизм на уровне задач (многопоточность):
................................................................. 8
1.2.
Параллелизм на уровне данных
................................................................................................ 8
1.3.
Параллелизм на
уровне алгоритмов
......................................................................................... 9
1.4.
Параллелизм на уровне инструкций (команд)
......................................................................... 9
Глава 2.
Отображение параллельных структур алгоритмов и программ на архитектуру
компьютера 15
2.1.
Определение проблемных точек процесса реализации программы
.................................... 15
2.2.
Состав, принцип работы, временные характеристики (АЛУ)
.............................................. 18
Глава 3. Способы повышение производительности компьютера .......................................... 27
3.1. Способы параллельной
обработки данных
................................................................................. 27
3.1.1. Параллельная обработка
............................................................................................................ 28
3.1.2. Конвейерная обработка
.............................................................................................................. 29
Глава 4. Способы повышения эффективности работы программ ...................................... 34
4.1.
Разработка спецпроцессоров
................................................................................................... 34
4. 2.
Улучшение архитектуры многопроцессорных
конфигураций
............................................ 35
4.3.
Способы организации коммуникационных систем в суперкомпьютерах
.......................... 37
4.4. Компьютеры с неоднородным доступом к памяти компьютеры с архитектурой NUMA (Non
Uniform Memory Access)
...................................................................................................................... 39
4.5.
Программное обеспечение параллельных компьютеров
...................................................... 40
Глава 5. Архитектура параллельных вычислительных систем ........................................... 43
5.1.
Классификация архитектур вычислительных систем
........................................................... 43
5.2.
Векторно-конвейерные компьютеры (архитектура векторно-конвейерных
супер-ЭВМ
CRAY C90)
............................................................................................................................................ 53
5.3. Параллельные компьютеры с общей памятью (HP Superdom)
................................................ 58
(Cray T3D/T3E)
..................................................................................................................................... 59
Глава 6. Большие задачи и параллельные вычисления ........................................................... 65
6.1.
Решение больших задач
........................................................................................................... 65
6.2.
Граф алгоритма и параллельные вычисления
....................................................................... 66
6.3. Концепция неограниченного параллелизма
............................................................................... 67
6.4.
Внутренний параллелизм
........................................................................................................ 70
Глава 7. Параллельные алгоритмы ............................................................................................ 71
4
7.1. Классификация алгоритмов по типу параллелизма
................................................................... 73
7.2.
Общая схема разработки параллельных алгоритмов
............................................................ 73
7.3.
Простые параллельные операции
........................................................................................... 76
Глава 8.
Базовые методы построения параллельных алгоритмов:
метод сдваивания,
геометрический параллелизм ..................................................................................................... 78
8.1.
Базовые методы построения параллельных алгоритмов
...................................................... 78
8.2. Построение параллельного алгоритма методом сдваивания
.................................................... 79
8.3.
Метод геометрического параллелизма
................................................................................... 83
