Параллельное программирование. Модели и приемы

Серия «Библиотека профессионала»

И. Е. Федотов

Параллельное 
программирование 

Модели и приемы

СОЛОН-Пресс 

Москва  
2018
2020

УДК 681.3
ББК 32.97
      Ф 34

Федотов И. Е.
Параллельное программирование. Модели и приемы. — М.: СОЛОН-Пресс, 
2018. — 390 с. (Серия «Библиотека профессионала»)

ISBN 978-5-91359-222-4

Книга посвящена рассмотрению некоторых высокоуровневых моделей параллельного и распределенного программирования. В порядке усложнения описываются несколько моделей внутренней организации параллельных программ: ярусно-параллельная форма программы, сети конечных автоматов, сети Петри, модель актеров, а также 
модель квантовых вычислений. Приводятся примеры программной реализации на C++ с 
использованием различных средств распараллеливания (OpenMP, MPI, POSIX Threads, 
Windows API). В каждом случае рассматриваются вопросы контекстно-независимой 
реализации конструкций описываемой модели без привязки к конкретным задачам, а 
также приведены примеры решения с использованием такой реализации некоторых 
конкретных задач. Некоторые из описанных моделей (к примеру, модель актеров), в настоящий момент приобретают все большую популярность вследствие распространения 
основанных на ее использовании языков и библиотек.
Книга ориентирована на подготовленного читателя в области программирования. 
Будет полезна программистам, желающим освоить высокоуровневые подходы к организации параллельных и распределенных программ, студентам старших курсов, аспирантам и преподавателям технических ВУЗов, преподающим параллельное программирование.

Сайт журнала «Ремонт & Сервис»: www.remserv.ru 
Сайт издательства «СОЛОН-Пресс»: www.solon-press.ru

ISBN 978-5-91359-222-4 
© «СОЛОН-Пресс», 2018
 
© Федотов И. Е., 2018

КНИГА — ПОЧТОЙ

Книги издательства «СОЛОН-Пресс» можно заказать наложенным платежом (оплата при 
получении) по фиксированной цене. Заказ можно оформить одним из трех способов:
1. Послать открытку или письмо по адресу: 123001, Москва, а/я 82.
2. Оформить заказ на сайте www.solon-press.ru в разделе «Книга — почтой».
3. Заказать книгу по тел. (495) 617-39-64, (495) 617-39-65.
При оформлении заказа следует правильно и полностью указать адрес, по которому должны быть высланы книги, а также фамилию, имя и отчество получателя. Желательно указать 
дополнительно свой телефон и адрес электронной почты.
Через Интернет вы можете в любое время получить свежий каталог издательства «СОЛОНПресс», считав его с адреса http://www.solon-press.ru/katalog.
Интернет-магазин размещен на сайте www.solon-press.ru.

По вопросам приобретения книг обращаться: 
ООО «СОЛОН-Пресс» 
Тел: (495) 617-39-64, (495) 617-39-65, 
E-mail: kniga@solon-press.ru, www.solon-press.ru

2020

2020

2020

Оглавление

Предисловие
6
О проблеме параллельного программирования . . . . . . . . . . . . . . . . . . . . .
6
О целях издания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
О содержании
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
Об используемой терминологии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Некоторые вопросы стиля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

1. Программные интерфейсы
22
1.1. Интерфейс OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
1.1.1.
Беглый взгляд «под капот» OpenMP . . . . . . . . . . . . . . . . . . . .
23
1.1.2.
Основные конструкции параллельного выполнения
. . . . . . . . . . .
29
1.1.3.
Некоторые вспомогательные директивы . . . . . . . . . . . . . . . . . .
34
1.1.4.
Разделение данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
1.1.5.
Runtime-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
1.1.6.
Вычисление определенного интеграла
. . . . . . . . . . . . . . . . . . .
44
1.2. Интерфейс передачи сообщений MPI . . . . . . . . . . . . . . . . . . . . . . . .
47
1.2.1.
Снова ряд Лейбница
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
1.2.2.
Краткое описание предоставляемых функций . . . . . . . . . . . . . . .
55
1.2.3.
Распределение вычислений в однородной среде . . . . . . . . . . . . . .
65
1.2.4.
Некоторые вопросы распределения в неоднородной среде . . . . . . . .
72
1.2.5.
Умножение матрицы на вектор . . . . . . . . . . . . . . . . . . . . . . .
75
1.2.6.
Перемножение матриц
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
83

2. Ярусно-параллельная форма программы
91
2.1. Цель и механизм построения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
2.2. Варианты реализации механизма . . . . . . . . . . . . . . . . . . . . . . . . . .
95
2.2.1.
Поярусное выполнение комплекса работ . . . . . . . . . . . . . . . . . .
95
2.2.2.
Учет индивидуальных зависимостей работ
. . . . . . . . . . . . . . . .
98
2.3. Симуляция выполнения логических схем . . . . . . . . . . . . . . . . . . . . . . 103

3. Сети конечных автоматов
111
3.1. Программирование конечных автоматов . . . . . . . . . . . . . . . . . . . . . . 111
3.2. Параллелизм сетей конечных автоматов . . . . . . . . . . . . . . . . . . . . . . 115
3.3. Пример программной реализации . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.3.1.
Реализация с использованием OpenMP . . . . . . . . . . . . . . . . . . . 118
3.3.2.
Простая реализация с использованием MPI . . . . . . . . . . . . . . . . 123
3.3.3.
Реализация с поддержкой вложенных сетей . . . . . . . . . . . . . . . . 125
3.4. Примеры сетей автоматов
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.1.
Параллельный сумматор . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

3

ОГЛАВЛЕНИЕ

3.4.2.
Прямоугольный бильярд . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

4. Сети Петри
147
4.1. Краткое введение в теорию сетей Петри . . . . . . . . . . . . . . . . . . . . . . 147
4.1.1.
Знакомство с сетями Петри
. . . . . . . . . . . . . . . . . . . . . . . . . 147
4.1.2.
Строго иерархические сети . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.1.3.
Параллельные вычисления и синхронизация
. . . . . . . . . . . . . . . 152
4.1.4.
Задача об обедающих философах . . . . . . . . . . . . . . . . . . . . . . 155
4.1.5.
Задача чтения-записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.2. Программная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.2.1.
Функционирование строго иерархических сетей . . . . . . . . . . . . . . 163
4.2.2.
Выполнение параллельных процессов
. . . . . . . . . . . . . . . . . . . 168
4.3. Некоторые примеры использования . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.3.1.
Реализация игры в жанре «квест»
. . . . . . . . . . . . . . . . . . . . . 179
4.3.2.
Обработка потоков данных
. . . . . . . . . . . . . . . . . . . . . . . . . 188
4.3.3.
Реализация задачи об обедающих философах . . . . . . . . . . . . . . . 192

5. Модель актеров
197
5.1. Описание модели актеров
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.1.1.
Первоначальное описание модели . . . . . . . . . . . . . . . . . . . . . . 197
5.1.2.
Язык SAL для описания поведения актеров . . . . . . . . . . . . . . . . 201
5.1.3.
Некоторые существующие модификации модели . . . . . . . . . . . . . 205
5.2. Различные варианты реализации . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.2.1.
Простая одноуровневая реализация . . . . . . . . . . . . . . . . . . . . . 208
5.2.2.
Многопроцессный вариант . . . . . . . . . . . . . . . . . . . . . . . . . . 219
5.2.3.
Низкоуровневая многопоточная реализация . . . . . . . . . . . . . . . . 230
5.2.4.
Поддержка вложенных подсистем актеров . . . . . . . . . . . . . . . . . 239
5.3. Примеры решения некоторых задач
. . . . . . . . . . . . . . . . . . . . . . . . 247
5.3.1.
Вычисление факториала . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.3.2.
Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.3.3.
Задача чтения-записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
5.3.4.
Вычисление количества максимальных значений . . . . . . . . . . . . . 268
5.3.5.
Поиск выхода из лабиринта . . . . . . . . . . . . . . . . . . . . . . . . . 272

6. Квантовые вычисления
280
6.1. Описание вычислительной модели
. . . . . . . . . . . . . . . . . . . . . . . . . 280
6.1.1.
Классические обратимые вычисления
. . . . . . . . . . . . . . . . . . . 281
6.1.2.
Квантовый бит и принцип суперпозиции . . . . . . . . . . . . . . . . . . 285
6.1.3.
Системы кубитов и квантовая запутанность . . . . . . . . . . . . . . . . 289
6.1.4.
Унитарные преобразования и квантовые схемы . . . . . . . . . . . . . . 291
6.1.5.
Измерение результата вычислений . . . . . . . . . . . . . . . . . . . . . 294
6.1.6.
Параллелизм в квантовых вычислениях . . . . . . . . . . . . . . . . . . 296
6.2. Симулятор квантового компьютера . . . . . . . . . . . . . . . . . . . . . . . . . 298
6.2.1.
Виртуальный квантовый вычислитель . . . . . . . . . . . . . . . . . . . 298
6.2.2.
Реализация базовых вентилей . . . . . . . . . . . . . . . . . . . . . . . . 302
6.3. Алгоритм Дойча . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
6.4. Aлгоритм Гровера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
6.4.1.
Общее описание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
6.4.2.
Схема обращения знака
. . . . . . . . . . . . . . . . . . . . . . . . . . . 309
6.4.3.
Обращение относительно среднего
. . . . . . . . . . . . . . . . . . . . . 310

ОГЛАВЛЕНИЕ
5

6.4.4.
Полная схема алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
6.5. Полная реализация алгоритма Шора . . . . . . . . . . . . . . . . . . . . . . . . 314
6.5.1.
Общая схема и описание . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
6.5.2.
Модульное возведение в степень . . . . . . . . . . . . . . . . . . . . . . . 320
6.5.3.
Квантовое преобразование Фурье . . . . . . . . . . . . . . . . . . . . . . 337
6.5.4.
Извлечение порядка из результата измерения . . . . . . . . . . . . . . . 338

А. Шаблоны классов матрицы и вектора
341

Б. Классы для выполнения комплексов работ
345

В. Классы для выполнения сетей конечных автоматов
349

Г. Классы для выполнения сетей Петри
357

Д. Классы для выполнения систем актеров
365

Е. Классы для симуляции квантовых вычислений
377

Литература
385

Предисловие

Сравнительно недавно современные компьютеры вплотную приблизились к своему пределу тактовых частот. Производительность процессоров (точнее, их отдельных ядер) перестала нарастать сказочными темпами, и теперь остается возможность обеспечить дальнейшее повышение вычислительных мощностей лишь за счет увеличения их количества:
производительность компьютеров начала расти «вширь», а не «в высоту». В связи с этим
параллельное программирование уже перестало быть узкоспециализированной дисциплиной для высокопроизводительных вычислений и приобрело большую актуальность для широких масс представителей программистского сообщества. Есть немало публикаций, посвященных рассмотрению архитектур параллельных вычислительных систем и теоретическим
вопросам распараллеливания последовательных алгоритмов. Также существует достаточно учебных пособий и статей, посвященных рассмотрению существующих технологий, программных интерфейсов и библиотек. В то же время, довольно давно создано немало моделей, успешно описывающих выполнение параллельных процессов, которые уже являются
основой многих программных технологий и некоторых не слишком популярных инструментов построения параллельных программ. Таким моделям посвящено немало учебного
материала теоретического характера, однако наблюдается некоторый дефицит в области
практического их рассмотрения с доступными примерами программной реализации на основе современных средств. В результате освещения таких моделей лишь с теоретической
точки зрения они, порой, остаются вне практического арсенала программиста, отчего возможность использования их при решении конкретной задачи зачастую даже не рассматривается. Настоящее издание стремится в какой-то степени восполнить указанную нишу и
исправить такое положение.

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

Главная проблема параллельного программирования основана на относительной сложности построения схемы параллельных вычислений в голове программиста. Человек в принципе мыслит последовательно. Здесь, разумеется, имеется в виду процесс построения умозаключений, а не внутренние процессы мозга на физиологическом уровне. Именно поэтому
последовательны большинство существующих сегодня языков программирования. Многие
авторы, работающие в области параллельного программирования, сходятся во мнении, что
развитой дисциплины параллельного программирования на сегодняшний момент нет, и что
индустрия создания параллельных программ движется по тупиковому пути [21, 25, 24, 69].
Большинство сегодняшних параллельных вычислений реализуется в виде параллельнопоследовательных программ. При этом в существующем последовательном алгоритме выделяются независимые друг от друга последовательные ветви, которые могут быть выполнены
параллельно, и с этим учетом пишется параллельно-последовательная программа. Нередко берется уже существующая последовательная программа, которая путем добавления
неких конструкций распараллеливания преобразуется в параллельно-последовательную.

6

О ПРОБЛЕМЕ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ
7

Чем сложнее исходная последовательная программа, чем хуже она структурирована, чем
запутаннее зависимости между отдельными ее ветвями, тем сложнее оказывается выполнить ее распараллеливание.
Случаются ситуации, когда существующая последовательная программа реализует
некоторый алгоритм, в котором изначально присутствует логический параллелизм, однако
реализация этого алгоритма в программе обременена сложным взаимодействием участков
кода, которые в идеале могут и должны быть независимыми. В таком случае бывает сложно без существенных изменений программы выделить в ней ветви, выполнение которых
может быть физически распараллелено. Использование моделей параллельного программирования, в том числе рассматриваемых в настоящем издании, обеспечивает основу для
такого описания задач, при котором присущий им логический параллелизм выявляется
изначально и не теряется в дальнейшем.
Существует немало изданий, посвященных интерфейсам и технологиям параллельного
программирования, наподобие рассматриваемых ниже MPI и OpenMP. Однако это лишь
инструменты, а одного прекрасного знания инструмента, как правило, недостаточно для
того, чтобы легко и эффективно реализовать решение конкретной задачи. Помимо знаний
о том, какой инструмент нужно использовать и каковы правила его использования (непосредственные требования спецификации), необходимы знания о том, какие цели должны
быть при этом достигнуты и, самое главное, каким образом инструмент должен помочь
в достижении этих целей (идиоматические конструкции, образцы (patterns) решения типовых задач и т.п.). Именно такую роль в параллельном программировании выполняют
соответствующие вычислительные модели.
Многие авторы публикаций по параллельным вычислениям сходятся в том, что для
описания параллельных программ необходимо уйти от императивных языков программирования [10, 12]. Императивные языки (от лат. imperativus — повелительный) описывают,
какие действия и в каком порядке следует выполнить, чтобы получить результат. Такими
является большинство популярных сегодня языков: C++, Pascal, Java, Perl и т.п. В данном же случае требуется использование декларативных языков (от лат. declaratio — заявление, объявление), т.е. таких, которые описывают, чем является результат, который должен
быть получен, оставив выполнение действий, как и выбор их последовательности, на долю
компилятора или интерпретатора. Примерами декларативных языков являются язык логического программирования Prolog и языки функционального программирования Haskell,
Erlang, Lisp и т.п. Различие между императивным и декларативным программированием в
чем-то напоминает различие между прямым вычислением функции и решением уравнения,
т.е. обращением функции.
С момента становления программирования как дисциплины декларативным языкам
пророчили большое будущее, поскольку они зачастую позволяют легко, наглядно и потому
надежно описать задачу, что само по себе обычно гораздо проще, чем детально описывать процесс ее решения. При этом возникает другая сложность: создание эффективного
компилятора или интерпретатора, который, в общем-то, и принимает в этом случае бремя
принятия решений о выполнении действий, снятое с плеч программиста.
Несмотря на потенциальную мощь, декларативные языки не приобрели широкой популярности. Одна из возможных причин заключается в том, что на момент их появления
мощности машин не хватало для реализации достаточно эффективных компиляторов и интерпретаторов. Вследствие этого программисты были вынуждены пользоваться языками,
которые позволяют «подсказать», а вернее даже «повелеть» машине выполнение конкретных действий, т.е. императивными языками.
Ситуация здесь сродни той, почему в прежние времена было популярно использование
низкоуровневых языков. Оптимизирующие компиляторы языков высокого уровня и вы

ПРЕДИСЛОВИЕ

числительные системы, на которых они работали, не были достаточно мощными, чтобы
обеспечить производительность и размер программ, сравнимые с программами на языках низкого уровня. Именно это является одной из причин, по которым Д. Кнут избрал
машинно-ориентированный язык для представления алгоритмов в своем известном многотомнике, о чем он и говорит в самом начале первого тома. Когда оптимизаторы кода
достигли приемлемого уровня качества, программирование на языках низкого уровня постепенно утратило популярность в угоду повышению переносимости. Однако переход на
языки высокого уровня не потребовал смены парадигмы, и языки остались императивными. Смена языка в рамках одной парадигмы гораздо проще смены парадигмы, к тому же
для перехода на языки высокого уровня был стимул: повышение переносимости.
Развитие вычислительных мощностей сказалось также и на повышении эффективности использования компиляторов и интерпретаторов декларативных языков. Более того,
в отношении смены парадигмы на декларативную теперь также появился стимул: перенос
реализации механизмов распараллеливания с программистов на компиляторы и интерпретаторы. Такие механизмы являются частью системы, и забота о них не должна лежать
на плечах прикладного программиста. Поэтому можно надеяться, что в скором времени
изменится и отношение к декларативному программированию.
Есть мнение, что вместо освоения новых языков программирования необходимо пополнение конструкциями распараллеливания традиционных последовательных языков (императивных), поскольку первое гораздо дороже обходится с точки зрения переобучения персонала. Подобные аргументы допустимы лишь в рамках корпоративной политики отдельно
взятых производств, в общем же случае они попросту встают на пути прогресса. Нельзя не
признать, однако, что какой-то переходный этап на пути от императивных языков к декларативным неизбежен. Существует и другое мнение, утверждающее, что выбор императивных языков был изначально неверным, поскольку вынуждает задавать в программе больше
деталей, чем необходимо для представления алгоритма, тем самым усложняя процесс описания решаемой задачи программистом компьютеру. Задание четкой последовательности
действий в ситуации, когда она не важна, — одна из таких «ненужных» подробностей, присущая императивным языкам.
Многие могут возразить: зачем использовать декларативные языки, если машина все
равно выполняет императивный поток инструкций? С тем же успехом можно спросить,
зачем вообще использовать языки высокого уровня, если можно программировать сразу
в машинных инструкциях. Машина «мыслит» совершенно не так, как человек, и здесь
не возникает разногласий. Человеку нелегко дается описывать задачу в терминах машины. Высокоуровневое же программирование призвано быть как раз промежуточным слоем,
обеспечивающим преобразование описания задачи, представленного в терминах человека
(на формальном, но все же приближенном к представлению человека языке), в описание
той же задачи, представленное в терминах машины. Чем проще, естественнее и точнее высокоуровневый язык позволяет человеку описать свою задачу, тем лучше он соответствует
своему назначению. В этом отношении декларативные языки, определенно, во многих областях опережают императивные.
Многие существующие уже давно языки декларативного программирования, несмотря на свою мощь, не обеспечивают полноценной базовой платформы для удобного описания программы с возможностью неявной передачи присущей ей внутренней параллельной
структуры. Причина, вероятно, в том, что спецификации этих языков создавались тогда,
когда вопрос параллельного программирования не стоял так остро, как сегодня, и, видимо,
поэтому в них зачастую содержатся ограничения, также сводящие вычисления к последовательным. К примеру, наличие в языке Lisp операции присваивания вносит необходимость
задания четкого порядка для вычисления последовательности выражений (к примеру, ар

О ЦЕЛЯХ ИЗДАНИЯ
9

гументов функции), что лишает интерпретатор права распараллелить этот процесс, даже
если программисту этот порядок не важен [10].
Выходит, для полноценного удобного описания параллельных программ, так или иначе, требуется более современный язык. Возможно, им станет один из уже существующих
языков, попыток создания которых, в том числе весьма удачных, на сегодняшний момент
известно немало. Среди них, к примеру, мультипарадигменный язык Oz. Как и в случае
многих других языков, нельзя сказать, что параллельное программирование является первостепенной его задачей, однако удобство и эффективность, с которыми оно выполняется, является естественным следствием выразительности соответствующих декларативных
языковых конструкций. Параллельное выполнение в Oz основано на легковесных потоках
управления (green threads) и элементах модели потоков данных (dataflow), близкой к рассматриваемому ниже ярусно-параллельному представлению программы. Функциональный
язык Erlang изначально создавался с целью построения распределенных систем, в связи с
чем предоставляет не менее удобные конструкции для создания параллельных программ,
а также высокую степень эффективности их выполнения. Модель существования и взаимодействия параллельно выполняющихся процессов в Erlang близка к модели актеров,
которая также будет рассмотрена ниже. Многие языки, такие как, к примеру, Alice, используют понятие фьючеров (future, будущее значение), которые напоминают переменные
и представляют собой результат выполнения каких-либо еще не завершенных операций,
выполняемых обычно параллельно. Наконец, существуют языки, которые сами по себе не
предоставляют явно конструкций для распараллеливания, однако мощь и выразительность
их синтаксиса позволяет создание для этих целей специальных библиотек, удобство и прозрачность использования которых оказывается сравнима с использованием языковых конструкций. Таким является мультипарадигменный язык Scala, компилируемый в байт-код
для виртуальной машины Java.
Эти и другие подобные языки, несмотря не свои достоинства, пока не обрели достаточно широкой популярности, и можно лишь надеяться, что они обретут ее в будущем. В
противном случае можно надеяться, что появятся и обретут широкую популярность другие
высокоуровневые языки для описания параллельных программ. Пока же мы будем отталкиваться от факта их отсутствия, в связи с чем будем рассматривать популярные модели
параллельных вычислений с примерами на основе популярного императивного языка.
Следует понимать, что под прозвучавшим утверждением об отсутствии популярных
языков параллельного программирования подразумевалось отсутствие таких языков, которые не ориентированы на какую-либо узкоспециализированную область применения и которые используются для реализации параллельных вычислений повсеместно. Стоит отметить,
что популярность средства программирования очень важна в сегодняшних условиях, когда
большинство программистов вынуждены быть «совместимыми» друг с другом. Временные
затраты на освоение многочисленных, хоть и прогрессивных, но зачастую мало распространенных технологий, как правило, не оправдывают себя, вследствие чего большинство
программистов вынуждены консервативно пользоваться решениями на основе, порой, не
самых удачных, но устоявшихся средств.

О целях издания

Представленное в книге описание моделей параллельного программирования, помимо
очевидных академических целей, стремится проиллюстрировать следующие два взаимосвязанных момента.
Во-первых, ставится задача показать проблему современного параллельного программирования, заключающуюся, прежде всего, в том, что наиболее популярные сегодня средства

ПРЕДИСЛОВИЕ

программирования приспособлены к описанию методов решения стоящей задачи в соответствии с образом мышления программиста, а именно в последовательной форме. Отсюда вытекает сложность наглядного для человека представления с использованием таких средств
параллельных алгоритмов и программ. В связи с этим встает ребром вопрос необходимости
использования для параллельного программирования принципиально иных средств, не являющихся модификациями или надстройками существующих популярных языков. Одним
из возможных направлений является декларативное программирование, что косвенно и демонстрируется примерами в книге, поскольку большинство приведенных программ, хоть и
реализованы на императивном языке, основаны на декларативном представлении задачи.
Во-вторых, делается попытка проиллюстрировать следующий факт, вытекающий из
рассмотрения тех же обстоятельств с обратной стороны. Несмотря на указанные сложности, императивные языки, все же, могут без серьезных препятствий быть использованы
для прозрачной (неявной) реализации параллельных алгоритмов. При этом может быть
реализована некая абстрактная машина, принимающая на входе набор декларативно описывающих алгоритм данных, которая инкапсулирует внутри себя механизмы параллельного
выполнения. Программный интерфейс такой машины принципиально не зависит от средств
распараллеливания, с помощью которых она реализована и которые в общем случае могут
быть разными. Такой подход позволит не уходить от имеющейся на сегодняшний момент
ситуации преобладания императивных языков и, тем самым, в какой-то степени упростит
и сгладит освоение параллельного программирования.
Оба этих момента взаимно дополняют друг друга. Учитывая отсутствие на сегодняшний
момент развитых и одновременно обладающих широкой популярностью средств декларативного параллельного программирования, в практических целях может быть рассмотрен
подход с использованием механизма обработки декларативных данных, реализованного на
императивном языке. Однако в целом такие меры являются вынужденными и требуют
дополнительных затрат, вследствие чего в будущем требуется появление новых либо популяризация существующих более мощных средств разработки, изначально ориентированных
на параллельное программирование и не являющихся видоизменением каких-либо средств
последовательного программирования.
Разумеется, ни одна из представленных в настоящем издании моделей не является панацеей и не дает возможности простого описания для любой задачи, вопреки убеждениям
некоторых их приверженцев. Одни задачи наиболее удобно описываются одной моделью
вычислений, другие — другой, а третьи наиболее просто и наглядно описываются простым
циклом на императивном языке. Тем не менее, понимание рассмотренных моделей и парадигм в комплексе может существенно упростить разработку параллельных программ с той
точки зрения, что даст возможность программисту смотреть шире и сгладит отсутствие
у него «параллельного мышления». Готовые примеры программ «со стороны», наподобие
приведенных здесь, практически никогда не оказываются подходящими во всех отношениях, однако это лишь добавляет стимула для более глубокого самостоятельного изучения
соответствующей темы.

О содержании

Факт наличия параллелизма среды выполнения порождает необходимость распараллеливания ресурсоемких вычислений, однако сама по себе эта необходимость в общем случае
не привязана к конкретной реализации параллельной среды. В связи с этим в книге не
приводится классификация параллельных вычислительных систем и не делается акцента
на конкретную категорию системы. Для ознакомления с классификацией можно обратиться
к другой литературе [1, 4, 9, 15].

О СОДЕРЖАНИИ
11

Также в настоящем издании не рассматриваются специализированные языки параллельного программирования, такие как, например, occam, или языки с естественной поддержкой параллельного программирования, наподобие Erlang или Oz. Здесь, напротив, делается
попытка познакомить читателя с существующими подходами и методами параллельного
программирования на основе уже известных ему конструкций. В частности, с использованием известного языка. Для нашего изложения оказался наиболее удобен язык C++, хотя
вообще выбор языка непринципиален.
Наконец, поскольку эта книга также не предназначена для первоначального ознакомления с основами программирования, она не содержит обзора используемого в примерах
языка. Для понимания изложенного материала необходимо хорошее владение языком, и
именно по этим причинам выбран достаточно популярный язык программирования. По тем
же причинам нигде в тексте не объясняются правила и принципы работы со стандартными
контейнерами библиотеки STL, хотя они широко используются в примерах программ.
Реализация как такового механизма распараллеливания для большинства программ
приводится с использованием нескольких различных программных интерфейсов. При этом
делается попытка максимально сохранить программный интерфейс, предоставляемый клиентскому коду, чтобы избежать изменений в последнем при переходе от одного способа
реализации параллелизма к другому. Такой подход выбран с целью показать, что процесс
написания параллельных программ, хоть и привязан во многом к удобству предоставляемых инструментов, все же упирается не в выбор конкретного инструмента и степень владения им, а в правильный выбор представления параллельной программы, наиболее полно
соответствующий стоящей задаче.
Поскольку полностью уйти от вопросов реализации нельзя, в главе 1 приводится краткий обзор двух популярных интерфейсов параллельного программирования с примерами
программ. Однако за более подробным описанием этих и других программных интерфейсов следует обращаться к спецификациям [72, 75] и специально посвященным им изданиям
[2, 3, 4, 46].
В остальных главах рассматриваются несколько моделей параллельного программирования, существующих сегодня и, порой, выдвигаемых их приверженцами в качестве универсальной основы для построения параллельных программ. Рассматриваемые модели являются по существу разными, и в то же время во многом напоминают друг друга, что дает
возможность неформально говорить о некоторых обобщениях и усовершенствованиях одной модели для формирования другой. Возможные подходы к построению параллельных
программ не ограничиваются рассмотренными вариантами. К примеру, в силу довольно
специфичных областей применения здесь не рассмотрены модель PRAM (Parallel Random
Access Machine), нейронные сети, клеточные автоматы и т.п.
Глава 2 посвящена рассмотрению ярусно-параллельной формы программы, базовому
представлению в виде направленного ациклического графа, в котором выявляются наборы информационно независимых друг от друга операций. Модель предполагает, что все
рассматриваемые операции выполняются единожды, поэтому граф не может содержать
циклических зависимостей, поскольку ни одна операция не должна зависеть сама от себя.
Также вследствие однократного выполнения операций отсутствует необходимость хранения
ими промежуточного состояния.
В главе 3 рассматриваются сети конечных автоматов. Все автоматы сети работают синхронно по тактам, при этом предполагается, что тактов в общем случае много. Как следствие, в таких сетях появляется возможность циклических зависимостей автоматов, поскольку выходные данные автомата могут прямо или косвенно вернуться на вход ему же.
В этих условиях оказывается довольно уместным наличие у автомата внутреннего состояния, т.к. это существенно повышает удобство моделирования ими объектов реального мира.

ПРЕДИСЛОВИЕ

Таким образом, сети конечных автоматов в некотором роде обобщают модель, рассматриваемую в главе 2, являясь, по сути, расширением ярусно-параллельной формы высотой в
один ярус наличием обратных связей и хранением промежуточного состояния элементов.
Сеть Петри, описанию которых посвящена глава 4, в свою очередь, можно считать
некоторым обобщением конечного автомата, который может находиться одновременно в
нескольких состояниях и в общем случае перестает быть конечным.
Модель актеров, рассматриваемая в главе 5, обобщает уже сети конечных автоматов,
снимая некоторые их ограничения, такие как необходимость глобальной синхронизации и
четкий порядок поступления данных, и тем самым добавляя новые возможности.
Глава 6 имеет принципиально иной характер. Она посвящена квантовым вычислениям — альтернативной модели вычислений, которая, в отличие от классической, изначально
базируется на наличии естественного параллелизма. К сожалению, пока эта модель полезна
лишь на бумаге. Практическую выгоду от ее использования на текущий момент получить
затруднительно вследствие отсутствия соответствующей аппаратуры. Однако сама по себе
эта вычислительная модель обладает некоторой завораживающей красотой, и знакомство
с ней, безусловно, будет полезно для заинтересованного читателя.
При рассмотрении каждой модели общие механизмы построения ее базовых конструкций и параллельного выполнения независимых ветвей отделяются от специфики решаемых
задач. В результате в рамках всех описанных моделей рассматриваемые задачи представляются декларативно: сетевым графиком работ, диаграммой состояний автомата, схемой
автоматной сети, схемой сети Петри, схемой взаимодействия актеров и набором описаний
их поведения. Параллельное выполнение декларативно описанной программы зависит от
внутренней реализации конкретного механизма обработки декларативных данных, а не возлагается на плечи прикладного программиста, использующего этот механизм.
Реализация соответствующего механизма может быть как последовательной, так и параллельной с использованием различных подходов к организации физического параллелизма. В нашем случае строится универсальный (контекстно-независимый) набор классов,
реализующих конструкции рассматриваемой модели, который может быть использован для
решения широкого круга задач, и в том числе используется в приведенных примерах. Решение конкретных задач сводится к использованию этих классов в коде, описывающем
задачу в терминах выбранной модели. Осуществление же распараллеливания выполнения
отдельных ветвей инкапсулируется внутри этих классов, что позволяет упростить написание клиентского кода и тем самым повысить его надежность. Для каждой рассматриваемой
модели такой набор контекстно-независимых классов вынесен в приложение. Примеры их
использования, а также варианты изменений с целью смены механизма распараллеливания,
обсуждаются в тексте главы, посвященной соответствующей модели.

Об используемой терминологии

Оговорим некоторые используемые в дальнейшем термины, трактование которых в существующей литературе зачастую различается. К примеру, в одних источниках термин
«процессор» используется для указания отдельного последовательного вычислительного
устройства (CPU), в других — для указания отдельного узла вычислительной сети. Здесь
термин «процессор» будет использоваться в качестве описания отдельного последовательного вычислительного элемента системы с общей памятью, независимо от того, является
ли он на самом деле отдельным процессором многопроцессорного сервера, ядром многоядерного процессора или элементом вычислительной системы с организацией доступа к
общей памяти через коммутатор. Условимся также называть «узлом» отдельный элемент
вычислительной системы с распределенной памятью. Это может быть элемент системы с

ОБ ИСПОЛЬЗУЕМОЙ ТЕРМИНОЛОГИИ
13

массовым параллелизмом или же просто отдельная машина, работающая в составе вычислительного кластера.

Также следует оговорить некоторые стилистические расхождения в терминах, хотя они
не столь принципиальны. Так сложилось, что отдельные параллельные ветви выполняющегося процесса (threads) многие называют потоками (а также тредами, потоками команд,
потоками управления, но чаще просто потоками). Есть авторы, которые настойчиво используют термин «нить», поскольку именно «нить» соответствует английскому слову «thread»,
в то время как «поток» соответствует слову «stream» (а также в некоторых областях слову
«flow» — «flow-based programming»), и во избежание путаницы в русскоязычной терминологии следует разделять эти понятия. Безусловно, они правы. Однако здесь приходится
учитывать, что на текущий момент для обозначения этого понятия гораздо более широко
распространен термин «поток», и с целью общения на едином языке большинству программистов приходится мириться с некорректностью терминологии. В силу того, что этот
момент не имеет принципиального значения для дальнейшего изложения, мы будем использовать термин «поток», поскольку по исторически сложившимся причинам этот термин
оказывается более привычным для большинства программистов.

Заодно коснемся перевода слова «handle», на предмет которого терминология также
не устоялась. Зачастую в литературе хэндлы называют дескрипторами (или еще проще —
описателями). Эта терминология некорректна, по той простой причине, что хэндл — не дескриптор. В UNIX-системах, откуда происходит этот термин, понятие файлового дескриптора отождествляется с индексом (номером) соответствующей структуры в таблице файловых
дескрипторов процесса, записи в которой, действительно, «описывают» открытые файлы.
Записи этой таблицы недоступны программе, однако она может определенным образом ориентироваться на значения индексов при построении своей внутренней логики. Хэндлы же
не только ничего не описывают, но и не являются индексом, который может быть как-либо
интерпретирован программой. Хэндл является неким «черным ящиком» (opaque type, «темный тип», «мутный тип»), значение которого может быть использовано только в качестве
ссылки на объект при обращении к другим функциям системы. Таким образом, хэндл не дает никакой информации и лишь, как и диктует нам дословный перевод, является «ручкой»,
посредством которой можно так или иначе манипулировать соответствующим объектом. В
связи с этим самым удачным, пожалуй, переводом этого слова является именно «манипулятор», однако этот термин не снискал популярности среди программистов, в связи с чем
нами будет использован наиболее простой и популярный вариант — «хэндл».

Некоторые разногласия возникают в контексте именования модели актеров. Термин «актер» использован в ней ее авторами, на первый взгляд, не в том смысле, который вкладывается в него в русском (да и не только) языке, а лишь в смысле сущности, которая выполняет
действия (actions). По этой причине нередко в русскоязычных материалах вместо него используют термин «актор». Вопрос, какой из двух терминов корректнее, весьма спорный. С
одной стороны, можно согласиться с тем, что в том виде, в каком в каком модель актеров
приобрела популярность, благодаря языку Erlang, объект-актер ничем не напоминает людей, играющих роли в театре, а потому, возможно, следует обозначать его иным термином.
С другой стороны, как мы увидим далее, модель актеров изначально описывается авторами в ином виде. Действия актером выполняются не по его чистой инициативе, а в виде
реакции на внешние воздействия, что плохо увязывается с активно-инициативной природой
«актора». В то же время, актер — это не просто процесс, периодически принимающий сообщения некоторых типов, а сущность, имеющая поведение и изменяющая его в зависимости
от обстоятельств. Т.е. раз от разу выполняющая роли, что гораздо больше соответствует
термину «актер». Становится ясно, что авторы модели использовали этот термин не случайно, а то несоответствие, которое сейчас имеется в его русскоязычном переводе, навеяно