Основы параллельного программирования

К. Ю. Богачёв
ОСНОВЫ
параллельного
программирования
5-е издание, электронное
Москва
Лаборатория знаний
2024

УДК 004.65
ББК 32.073
Б73
Богачёв К. Ю.
Б73
Основы параллельного программирования : учебное пособие / К. Ю. Богачёв. — 5-е изд., электрон. — М. : Лаборатория знаний, 2024. — 345 с. — Систем. требования: Adobe
Reader XI ; экран 10". — Загл. с титул. экрана. — Текст :
электронный.
ISBN 978-5-93208-802-9
Данная книга представляет собой введение в методы программирования для параллельных ЭВМ.
Основной ее целью является научить читателя самостоятельно
разрабатывать максимально эффективные программы для таких
компьютеров.
Вопросы распараллеливания конкретных алгоритмов рассмотрены на многочисленных примерах программ на языке С. В основу
книги положен курс лекций для студентов механико-математического факультета МГУ им. М. В. Ломоносова.
Для студентов, аспирантов, научных работников, программистов
и всех, кто хочет научиться разрабатывать программы для параллельных ЭВМ.
УДК 004.65
ББК 32.073
Деривативное издание на основе печатного аналога: Основы
параллельного программирования : учебное пособие / К. Ю. Богачёв. — 2-е изд. — М. : БИНОМ. Лаборатория знаний, 2013. — 342 с. :
ил. — ISBN 978-5-9963-1616-8.
В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации
ISBN 978-5-93208-802-9
© Лаборатория знаний, 2015

Оглавление
Предисловие
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Порядок чтения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Глава 1. Для нетерпеливого читателя . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.1. Последовательная программа . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2. Ускорение работы за счет параллелизма . . . . . . . . . . . . .
12
1.3. Параллельная программа, использующая процессы .
13
1.4. Параллельная программа, использующая задачи . . . .
18
1.5. Параллельная программа, использующая MPI
. . . . . .
21
Глава 2. Пути повышения производительности процессоров . . .
24
2.1. CISC- и RISC-процессоры . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.2. Основные черты RISC-архитектуры . . . . . . . . . . . . . . . . .
25
2.3. Конвейеризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.4. Кэш-память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.5. Многопроцессорные архитектуры . . . . . . . . . . . . . . . . . . . .
39
2.5.1. Основные архитектуры . . . . . . . . . . . . . . . . . . . . . .
39
2.5.2. Комбинированные архитектуры
. . . . . . . . . . . . .
40
2.5.3. Обанкротившиеся архитектуры . . . . . . . . . . . . . .
43
2.6. Поддержка многозадачности и многопроцессорности
44
2.7. Использование параллелизма процессора для повышения эффективности программ . . . . . . . . . . . . . . . . . . . . . . .
45
Глава 3. Пути повышения производительности оперативной памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Глава 4. Организация данных во внешней памяти . . . . . . . . . . . . .
64

Оглавление
Глава 5. Основные положения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.1. Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.2. Виды ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.3. Типы взаимодействия процессов . . . . . . . . . . . . . . . . . . . . .
73
5.4. Состояния процесса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
Глава 6. Стандарты на операционные системы UNIX . . . . . . . . . .
79
6.1. Стандарт BSD 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
6.2. Стандарт UNIX System V Release 4 . . . . . . . . . . . . . . . . . .
79
6.3. Стандарт POSIX 1003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
6.4. Стандарт UNIX X/Open . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
Глава 7. Управление процессами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
7.1. Функция fork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
7.2. Функции execl, execv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.3. Функция waitpid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.4. Функция kill
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
7.5. Функция signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
Глава 8. Синхронизация и взаимодействие процессов . . . . . . . . . .
96
8.1. Разделяемая память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
8.1.1. Функция shmget
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
8.1.2. Функция shmat
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
8.1.3. Функция shmctl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
8.2. Семафоры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100
8.2.1. Функция semget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
8.2.2. Функция semop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
8.2.3. Функция semctl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
104
8.2.4. Пример использования семафоров и разделяемой памяти
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
104
8.3. События
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
120
8.4. Очереди сообщений (почтовые ящики)
. . . . . . . . . . . . . .
122
8.4.1. Функция msgget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
124
8.4.2. Функция msgsnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
124
8.4.3. Функция msgrcv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
125
8.4.4. Функция msgctl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
126
8.4.5. Пример использования очередей . . . . . . . . . . . . .
126
8.4.6. Функция pipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
133
8.5. Пример многопроцессной программы, вычисляющей
произведение матрицы на вектор . . . . . . . . . . . . . . . . . . . .
135

Оглавление
5
Глава 9. Управление задачами (threads) . . . . . . . . . . . . . . . . . . . . . . .
156
9.1. Функция pthread_create . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
156
9.2. Функция pthread_join
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
157
9.3. Функция sched_yield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
157
Глава 10. Синхронизация и взаимодействие задач . . . . . . . . . . . . .
158
10.1. Объекты синхронизации типа mutex . . . . . . . . . . . . . . . . .
158
10.1.1. Функция pthread_mutex_init . . . . . . . . . . . . . . . .
161
10.1.2. Функция pthread_mutex_lock . . . . . . . . . . . . . . .
162
10.1.3. Функция pthread_mutex_trylock . . . . . . . . . . . .
162
10.1.4. Функция pthread_mutex_unlock . . . . . . . . . . . . .
162
10.1.5. Функция pthread_mutex_destroy . . . . . . . . . . . .
163
10.1.6. Пример использования mutex . . . . . . . . . . . . . . . .
163
10.2. Пример multithread-программы, вычисляющей определенный интеграл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
168
10.3. Объекты синхронизации типа condvar . . . . . . . . . . . . . . .
168
10.3.1. Функция pthread_cond_init . . . . . . . . . . . . . . . . .
170
10.3.2. Функция pthread_cond_signal . . . . . . . . . . . . . . .
171
10.3.3. Функция pthread_cond_broadcast . . . . . . . . . . .
171
10.3.4. Функция pthread_cond_wait . . . . . . . . . . . . . . . . .
172
10.3.5. Функция pthread_cond_destroy . . . . . . . . . . . . . .
172
10.3.6. Пример использования condvar . . . . . . . . . . . . . .
172
10.4. Пример multithread-программы, вычисляющей произведение матрицы на вектор . . . . . . . . . . . . . . . . . . . . . . . . . .
178
10.5. Влияние дисциплины доступа к памяти на эффективность параллельной программы . . . . . . . . . . . . . . . . . . . . . .
192
10.6. Пример
multithread-программы,
решающей
задачу
Дирихле для уравнения Пуассона
. . . . . . . . . . . . . . . . . . .
202
Глава 11. Интерфейс MPI (Message Passing Interface) . . . . . . . . .
232
11.1. Общее устройство MPI-программы . . . . . . . . . . . . . . . . . .
232
11.2. Сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
234
11.3. Коммуникаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
237
11.4. Попарный обмен сообщениями . . . . . . . . . . . . . . . . . . . . . . .
238
11.5. Операции ввода–вывода в MPI-программах
. . . . . . . . .
240
11.6. Пример простейшей MPI-программы . . . . . . . . . . . . . . . .
242
11.7. Дополнительные функции для попарного обмена сообщениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
243
11.8. Коллективный обмен сообщениями . . . . . . . . . . . . . . . . . .
250

Оглавление
11.9. Пример MPI-программы, вычисляющей определенный
интеграл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
256
11.10. Работа с временем
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
259
11.11. Пример MPI-программы, вычисляющей произведение
матрицы на вектор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261
11.12. Дополнительные функции коллективного обмена сообщениями для работы с массивами . . . . . . . . . . . . . . . . .
273
11.13. Пересылка структур данных . . . . . . . . . . . . . . . . . . . . . . . . .
277
11.13.1. Пересылка локализованных разнородных данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
277
11.13.2. Пересылка распределенных однородных данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
288
11.14. Ограничение коллективного обмена на подмножество
процессов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
290
11.15. Пример MPI-программы, решающей задачу Дирихле
для уравнения Пуассона . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
292
Источники дополнительной информации
. . . . . . . . . . . . . . . . . . . . . .
323
Программа курса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
325
Список задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
329
Указатель русских терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
334
Указатель английских терминов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
336
Список иллюстраций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
339
Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
340
Список примеров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
341

Предисловие
Параллельные ЭВМ, возникшие преимущественно для высокопроизводительных научных вычислений, получают все более
широкое распространение: их можно встретить в небольших
научных подразделениях и офисах. Этому способствуют как
непрерывное падение цен на них, так и постоянное усложнение
решаемых задач. Можно без преувеличения сказать, что параллельные компьютеры сейчас используются или планируются к
использованию всеми, кто работает на передовых рубежах науки и техники:
• научными работниками, применяющими ЭВМ для решения
реальных задач физики, химии, биологии, медицины и других наук, поскольку упрощенные модельные задачи уже рассчитаны на «обычных» ЭВМ, а переход к реальным задачам
сопряжен с качественным ростом объема вычислений;
• программистами, разрабатывающими системы управления
базами данных (СУБД), разнообразные Internet-серверы запросов (WWW, FTP, DNS и др.) и совместного использования данных (NFS, SMB и др.), автоматизированные системы управления производством (АСУП) и технологическими
процессами (АСУТП), поскольку требуется обеспечить обслуживание максимального количества запросов в единицу
времени, а сложность самого запроса постоянно растет.
В настоящий момент практически все крупные разрабатываемые программные проекты как научной, так и коммерческой

Предисловие
направленности либо уже содержат поддержку параллельной
работы на компьютерах разных типов, либо эта поддержка запланирована на ближайшее время (причем промедление здесь
часто вызывает поражение проекта в конкурентной борьбе).
Настоящая книга представляет собой введение в методы программирования параллельных ЭВМ. Основной ее целью является научить читателя самостоятельно разрабатывать максимально эффективные программы для таких компьютеров. Вопросы
распараллеливания конкретных алгоритмов рассматриваются
на многочисленных примерах. В качестве языка программирования использован язык C, как наиболее распространенный (и,
заметим, единственный (не считая своего расширения C++), на
котором можно реализовать все приведенные примеры). Программы, посвященные использованию параллелизма процесса и
MPI, могут быть легко переписаны на языке FORTRAN-77. Для
иллюстрации подпрограмма умножения двух матриц, дающая
почти 14-кратное ускорение на одном процессоре, приведена на
двух языках: C и FORTRAN-77.
Изложение начинается с изучения параллелизма в работе
процессора, оперативной памяти и методов его использования.
Затем приводится описание архитектур параллельных ЭВМ и
базовых понятий межпроцессного взаимодействия. Для систем с
общей памятью подробно рассматриваются два метода программирования: с использованием процессов и использованием задач
(threads). Для систем с распределенной памятью рассматривается ставший фактическим стандартом интерфейс MPI. Для
указанных систем приведены описания основных функций и
примеры их применения. В описаниях намеренно выброшены
редко используемые детали, чтобы не пугать читателя большим
объемом информации (чем страдают большинство руководств
пользователя).
Книга используется в качестве учебного пособия в основном
курсе «Практикум на ЭВМ» на механико-математическом факультете МГУ им. М. В. Ломоносова по инициативе и при поддержке академика РАН Н. С. Бахвалова.

Порядок чтения
9
Порядок чтения
Книгу можно разделить на 5 достаточно независимых частей:
1. В главах 2, 3, 4 описан параллелизм в работе процессора
и оперативной памяти, а также разнообразные приемы, используемые для повышения эффективности их работы. Эту
информацию можно использовать для достижения значительного ускорения работы программы даже на однопроцессорном компьютере.
2. В главах 5 и 6 изложены основные понятия, используемые
при рассмотрении параллельных программ, а также стандарты на операционные системы UNIX, установленные на
подавляющем большинстве параллельных ЭВМ.
3. В главах 7 и 8 описаны основные функции для управления процессами и осуществления межпроцессного взаимодействия. Эти функции можно использовать для запуска
многих совместно работающих процессов в системах с общей
памятью, а также для разработки параллельного приложения для систем, не поддерживающих задачи (threads).
4. В главах 9 и 10 описаны основные функции для управления
задачами (threads) и осуществления межзадачного взаимодействия. Эти функции можно использовать для разработки
параллельного приложения в системах с общей памятью.
5. В главе 11 описаны основные функции Message Passing
Interface (MPI). Эти функции можно использовать для разработки параллельного приложения в системах как с общей,
так и с распределенной памятью.
Части расположены в рекомендуемом порядке чтения. Последние три независимы друг от друга и могут изучаться в произвольной последовательности. Главу 1, адресованную нетерпеливому читателю, при систематическом изучении рекомендуется разбирать по мере ознакомления с материалом основных
частей книги.
Книгой можно воспользоваться и в качестве учебника. Для
этого в конце приведены программа курса и список типовых
экзаменационных задач. Эти материалы будут полезны и для
самостоятельной подготовки.

Для нетерпеливого
читателя
Для нетерпеливого читателя, желающего как можно быстрее
научиться писать параллельные приложения, сразу же приведем пример превращения последовательной программы в параллельную. Для простоты рассмотрим задачу вычисления определенного интеграла от заданной функции и будем считать, что
все входные параметры (концы отрезка интегрирования и количество точек, в которых вычисляется функция) заданы константами. Все использованные функции будут описаны в последующих главах.
1.1. Последовательная программа
Для вычисления приближения к определенному интегралу от
функции f по отрезку [a, b] используем составную формулу трапеций:
b

n−1

j=1
f(a + jh) + f(b)/2

,
a
f(x) dx ≈h

f(a)/2 +
где h = (b −a)/n, а параметр n задает точность вычислений.
Вначале — файл integral.c с текстом последовательной
программы, вычисляющей определенный интеграл этим способом:
#include "integral.h"