Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 620342.02.99
Данная книга представляет собой введение в методы программирования для параллельных ЭВМ. Основной ее целью является научить читателя самостоятельно разрабатывать максимально эффективные программы для таких компьютеров. Вопросы распараллеливания конкретных алгоритмов рассмотрены на многочисленных примерах программ на языке С. В основу книги положен курс лекций для студентов механико-математического факультета МГУ им. М. В. Ломоносова. Для студентов, аспирантов, научных работников, программистов и всех, кто хочет научиться разрабатывать программы для параллельных ЭВМ.
Богачев, К. Ю. Богачёв, К. Ю. Основы параллельного программирования : учебное пособие / К. Ю. Богачёв. -- 4-е изд. - Москва : Лаборатория знаний, 2020. - 345 с. - ISBN 978-5-00101-758-5. - Текст : электронный. - URL: https://znanium.com/catalog/product/1094361 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Москва

2020

4-е издание, электронное

Лаборатория знаний

ОСНОВЫ
параллельного
программирования

К. Ю. Богачёв

УДК 004.65
ББК 32.073
Б73

Богачёв К. Ю.
Б73
Основы параллельного программирования : учебное пособие / К. Ю. Богачёв. — 4-е изд., электрон. — М. : Лаборатория знаний, 2020. — 345 с. — Систем. требования: Adobe
Reader XI ; экран 10".— Загл. с титул. экрана. — Текст :
электронный.
ISBN 978-5-00101-758-5
Данная книга представляет собой введение в методы программирования для параллельных ЭВМ.
Основной ее целью является научить читателя самостоятельно
разрабатывать максимально эффективные программы для таких
компьютеров.
Вопросы распараллеливания конкретных алгоритмов рассмотрены на многочисленных примерах программ на языке С. В основу
книги положен курс лекций для студентов механико-математического факультета МГУ им. М. В. Ломоносова.
Для студентов, аспирантов, научных работников, программистов
и всех, кто хочет научиться разрабатывать программы для параллельных ЭВМ.
УДК 004.65
ББК 32.073

Деривативное издание на основе печатного аналога: Основы
параллельного программирования : учебное пособие / К. Ю. Богачёв. — 2-е изд. — М. : БИНОМ. Лаборатория знаний, 2013. — 342 с. :
ил. — ISBN 978-5-9963-1616-8.

В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации

ISBN 978-5-00101-758-5
c○ Лаборатория знаний, 2015

2

Оглавление

Предисловие
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
a
f(x) dx ≈ h
f(a)/2 +

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

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

#include "integral.h"

1.1. Последовательная программа
11

/* Интегрируемая функция */
double f (double x)
{
return x;
}

/* Вычислить интеграл по отрезку [a, b] с числом точек
разбиения n методом трапеций. */
double integrate (double a, double b, int n)
{
double res;
/* результат */
double h;
/* шаг интегрирования */
int i;

h = (b - a) / n;
res = 0.5 * (f (a) + f (b)) * h;
for (i = 1; i < n; i++)
res += f (a + i * h) * h;
return res;
}

Соответствующий заголовочный файл integral.h:

double integrate (double a, double b, int n);

Файл sequential.c с текстом последовательной программы:

#include <stdio.h>
#include "integral.h"

/* Все параметры для простоты задаются константами */
static double a = 0.;
/* левый конец интервала */
static double b = 1.;
/* правый конец интервала */
static int n = 100000000; /* число точек разбиения */

int main ()
{

Глава 1. Для нетерпеливого читателя

double total = 0.;
/* результат: интеграл */

/* Вычислить интеграл */
total = integrate (a, b, n);

printf ("Integral from %lf to %lf = %.18lf\n",
a, b, total);

return 0;
}

Компиляция этих файлов:

cc sequential.c integral.c -o sequential

и запуск

./sequential

1.2. Ускорение работы за счет параллелизма

Для ускорения работы программы на вычислительной установке с p процессорами мы воспользуемся аддитивностью интеграла:
b
a
f(x) dx =

p−1
i=0

bi
ai

f(x) dx,

где ai = a + i ∗ l, bi = ai + l, l = (b − a)/p. Использовав для
приближенного определения каждого из слагаемых
bi
ai f(x) dx
этой суммы составную формулу трапеций, взяв n/p в качестве
n, и поручив эти вычисления своему процессору, мы получим
p-кратное ускорение работы программы. Ниже мы рассмотрим
три способа запуска p заданий для исполнения на отдельных
процессорах:

1. создание новых процессов (раздел 1.3, с. 13),
2. создание новых задач (threads) (раздел 1.4, с. 18),
3. Message Passing Interface (MPI) (раздел 1.5, с. 21).

1.3. Параллельная программа, использующая процессы
13

Первые два подхода удобно использовать в системах с общей
памятью (см. раздел 2.5.1, с. 39). Последний подход применим
и в системах с распределенной памятью.

1.3. Параллельная программа, использующая процессы

Рассмотрим пример параллельной программы вычисления определенного интеграла, использующей процессы. Описание ее работы приведено в разделе 8.4.6, с. 133, где рассматривается
функция pipe; о функции fork см. раздел 7.1, с. 81. Файл
process.c с текстом программы:

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <stdlib.h>
#include "integral.h"

/* Все параметры для простоты задаются константами */
static double a = 0.;
/* левый конец интервала */
static double b = 1.;
/* правый конец интервала */
static int n = 100000000; /* число точек разбиения */

/* Канал вывода из главного процесса в порожденные.
from_root[0] - для чтения (в порожденных процессах),
from_root[1] - для записи (в главном процессе). */
static int from_root[2];

/* Канал вывода из порожденных процессов в главный.
to_root[0] - для чтения (в порожденных процессах),
to_root[1] - для записи (в главном процессе). */
static int to_root[2];

/* Функция, работающая в процессе с номером my_rank,
при общем числе процессов p. */
void process_function (int my_rank, int p)

Глава 1. Для нетерпеливого читателя

{
char byte;
/* длина отрезка интегрирования для текущего процесса*/
double len = (b - a) / p;
/* число точек разбиения для текущего процесса */
int local_n = n / p;
/* левый конец интервала для текущего процесса */
double local_a = a + my_rank * len;
/* правый конец интервала для текущего процесса */
double local_b = local_a + len;
/* значение интеграла в текущем процессе */
double integral;

/* Вычислить интеграл в каждом из процессов */
integral = integrate (local_a, local_b, local_n);

/* Ждать сообщения от главного процесса */
if (read (from_root[0], &byte, 1) != 1)
{
/* Ошибка чтения */
fprintf (stderr,
"Error reading in process %d, pid = %d\n",
my_rank, getpid ());
return;
}

/* Передать результат главному процессу */
if (write (to_root[1], &integral, sizeof (double))
!= sizeof (double))
{
/* Ошибка записи */
fprintf (stderr,
"Error writing in process %d, pid = %d\n",
my_rank, getpid ());
return;