ОГЛАВЛЕНИЕ

Предисловие 6
О проблеме параллельного программирования . . . . . . . . . . . . . . . . . . . . . 6
О целях издания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
О содержании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Об используемой терминологии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Некоторые вопросы стиля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1. Программные интерфейсы 21
1.1. Интерфейс OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.1.1. Беглый взгляд «под капот» OpenMP . . . . . . . . . . . . . . . . . . . . 22
1.1.2. Основные конструкции параллельного выполнения . . . . . . . . . . . 28
1.1.3. Некоторые вспомогательные директивы . . . . . . . . . . . . . . . . . . 33
1.1.4. Разделение данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.1.5. Runtime-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.1.6. Вычисление определенного интеграла . . . . . . . . . . . . . . . . . . . 43
1.2. Интерфейс передачи сообщений MPI . . . . . . . . . . . . . . . . . . . . . . . . 46
1.2.1. Снова ряд Лейбница . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.2.2. Краткое описание предоставляемых функций . . . . . . . . . . . . . . . 55
1.2.3. Распределение вычислений в однородной среде . . . . . . . . . . . . . . 65
1.2.4. Некоторые вопросы распределения в неоднородной среде . . . . . . . . 71
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.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. Задача чтения-записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.2. Программная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.2.1. Функционирование строго иерархических сетей . . . . . . . . . . . . . . 163
4.2.2. Выполнение параллельных процессов . . . . . . . . . . . . . . . . . . . 169
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. Некоторые существующие модификации модели . . . . . . . . . . . . . 206
5.2. Различные варианты реализации . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.2.1. Простая одноуровневая реализация . . . . . . . . . . . . . . . . . . . . . 208
5.2.2. Многопроцессный вариант . . . . . . . . . . . . . . . . . . . . . . . . . . 219
5.2.3. Низкоуровневая многопоточная реализация . . . . . . . . . . . . . . . . 231
5.2.4. Поддержка вложенных подсистем актеров . . . . . . . . . . . . . . . . . 240
5.3. Примеры решения некоторых задач . . . . . . . . . . . . . . . . . . . . . . . . 248
5.3.1. Вычисление факториала . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.3.2. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.3.3. Задача чтения-записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
5.3.4. Вычисление количества максимальных значений . . . . . . . . . . . . . 269
5.3.5. Поиск выхода из лабиринта . . . . . . . . . . . . . . . . . . . . . . . . . 273
6. Квантовые вычисления 281
6.1. Описание вычислительной модели . . . . . . . . . . . . . . . . . . . . . . . . . 281
6.1.1. Классические обратимые вычисления . . . . . . . . . . . . . . . . . . . 282
6.1.2. Квантовый бит и принцип суперпозиции . . . . . . . . . . . . . . . . . . 286
6.1.3. Системы кубитов и квантовая запутанность . . . . . . . . . . . . . . . . 290
6.1.4. Унитарные преобразования и квантовые схемы . . . . . . . . . . . . . . 292
6.1.5. Измерение результата вычислений . . . . . . . . . . . . . . . . . . . . . 295
6.1.6. Параллелизм в квантовых вычислениях . . . . . . . . . . . . . . . . . . 298
6.2. Симулятор квантового компьютера . . . . . . . . . . . . . . . . . . . . . . . . . 299
6.2.1. Виртуальный квантовый вычислитель . . . . . . . . . . . . . . . . . . . 300
6.2.2. Реализация базовых вентилей . . . . . . . . . . . . . . . . . . . . . . . . 303
6.3. Алгоритм Дойча . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
6.4. Полная реализация алгоритма Шора . . . . . . . . . . . . . . . . . . . . . . . . 309
6.4.1. Общая схема и описание . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
6.4.2. Модульное возведение в степень . . . . . . . . . . . . . . . . . . . . . . . 314
6.4.3. Квантовое преобразование Фурье . . . . . . . . . . . . . . . . . . . . . . 332
6.4.4. Извлечение порядка из результата измерения . . . . . . . . . . . . . . . 333
А. Шаблоны классов матрицы и вектора 336
Б. Классы для выполнения комплексов работ 340
В. Классы для выполнения сетей конечных автоматов 344
Г. Классы для выполнения сетей Петри 352
Д. Классы для выполнения систем актеров 360
Е. Классы для симуляции квантовых вычислений 372
Литература 380