Для систем с распределенной памятью рассматривается ставший фактическим стандартом интерфейс MPI. <...> 133, где рассматривается функция pipe; о функции fork см. раздел 7.1, с. <...> Параллельная программа, использующая процессы /* Ошибка записи */ fprintf (stderr, "Error writing in root process\n"); return 100; } /* Считываем результат */ if (read (to_root[0], &integral, sizeof (double)) != sizeof (double)) { /* Ошибка чтения */ fprintf (stderr, "Error reading in root process\n"); return 101; } total += integral; } /* Закрываем каналы */ close (from_root[1]); close (to_root[0]); printf ("Integral from %lf to %lf = %. <...> Файл thread.c с текстом программы: #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include "integral.h" /* Все параметры для простоты задаются константами */ static double a = 0.; /* левый конец интервала */ static double b = 1.; /* правый конец интервала */ static int n = 100000000; /* число точек разбиения */ /* Результат: интеграл */ static double total = 0. <...> ; /* Объект типа mutex для синхронизации доступа к total */ static pthread_mutex_t total_mutex = PTHREAD_MUTEX_INITIALIZER; /* Общее количество процессов */ static int p; /* Функция, работающая в задаче с номером my_rank */ void * process_function (void *pa) { 1.4. <...> Параллельная программа, использующая задачи 19 /* номер текущей задачи */ int my_rank = (int) pa; /* длина отрезка интегрирования для текущего процесса*/ 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); /* "захватить" mutex для работы с total */ pthread_mutex_lock (&total_mutex); /* сложить все ответы */ total += integral; /* "освободить" mutex */ pthread_mutex_unlock (&total_mutex); return 0; } int main (int argc, char * argv[]) { /* массив идентификаторов созданных задач */ pthread_t * threads; int i; if (argc ! <...> Для нетерпеливого читателя /* Функция, работающая в процессе с номером my_rank, при общем <...>
Основы_параллельного_программирования.pdf
К. Ю. Богачёв
ОСНОВЫ
параллельного
программирования
4-е издание, электронное
Москва
2020
Лаборатория знаний
Стр.2
ББКУДК 004.65
32.073
Б73
Богачёв К. Ю.
Б73 Основы параллельного программирования : учебное пособие
/ К. Ю. Богачёв. — 4-е изд., электрон. — М. : Лаборатория
знаний, 2020. — 345 с. — Систем. требования: Adobe
Reader XI ; экран 10".— Загл. с титул. экрана. — Текст :
электронный.
ISBN 978-5-00101-758-5
Данная книга представляет собой введение в методы программирования
для параллельных ЭВМ.
Основной ее целью является научить читателя самостоятельно
разрабатывать максимально эффективные программы для таких
компьютеров.
Вопросы распараллеливания конкретных алгоритмов рассмотрены
на многочисленных примерах программ на языке С. В основу
книги положен курс лекций для студентов механико-математического
факультета МГУ им. М. В. Ломоносова.
Для студентов, аспирантов, научных работников, программистов
и всех, кто хочет научиться разрабатывать программы для параллельных
ЭВМ.
32.073
ББКУДК 004.65
Деривативное издание на основе печатного аналога: Основы
параллельного программирования : учебное пособие / К. Ю. Богачёв.
— 2-е изд. —М. : БИНОМ. Лаборатория знаний, 2013. — 342 с. :
ил. —ISBN 978-5-9963-1616-8.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-00101-758-5
○c Лаборатория знаний, 2015
Стр.3
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Порядок чтения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 1. Для нетерпеливого читателя . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1. Последовательная программа . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Ускорение работы за счет параллелизма . . . . . . . . . . . . .
1.3. Параллельная программа, использующая процессы .
1.4. Параллельная программа, использующая задачи . . . .
1.5. Параллельная программа, использующая MPI . . . . . .
Глава 2. Пути повышения производительности процессоров . . .
2.1. CISC- и RISC-процессоры . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Основные черты RISC-архитектуры . . . . . . . . . . . . . . . . .
2.3. Конвейеризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4. Кэш-память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5. Многопроцессорные архитектуры . . . . . . . . . . . . . . . . . . . .
2.5.1. Основные архитектуры . . . . . . . . . . . . . . . . . . . . . .
2.5.2. Комбинированные архитектуры . . . . . . . . . . . . .
2.5.3. Обанкротившиеся архитектуры . . . . . . . . . . . . . .
2.6. Поддержка многозадачности и многопроцессорности
2.7. Использование параллелизма процессора для повышения
эффективности программ . . . . . . . . . . . . . . . . . . . . . . .
Глава 3. Пути повышения производительности оперативной памяти
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 4. Организация данных во внешней памяти . . . . . . . . . . . . .
7
9
10
10
12
13
18
21
24
24
25
26
34
39
39
40
43
44
45
61
64
Стр.4
4
Оглавление
Глава 5. Основные положения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Виды ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Типы взаимодействия процессов . . . . . . . . . . . . . . . . . . . . .
5.4. Состояния процесса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 6. Стандарты на операционные системы UNIX . . . . . . . . . .
6.1. Стандарт BSD 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Стандарт UNIX System V Release 4 . . . . . . . . . . . . . . . . . .
6.3. Стандарт POSIX 1003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4. Стандарт UNIX X/Open . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 7. Управление процессами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1. Функция fork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2. Функции execl, execv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3. Функция waitpid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4. Функция kill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5. Функция signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 8. Синхронизация и взаимодействие процессов . . . . . . . . . .
8.1. Разделяемая память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.1. Функция shmget . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.2. Функция shmat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.3. Функция shmctl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
66
72
73
77
79
79
79
80
80
81
81
84
84
87
88
96
97
98
99
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
Оглавление
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
Стр.6
6
Оглавление
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
Стр.7