Федотов И.Е.
Модели параллельного программирования

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

Книга ориентирована на подготовленного читателя в области программирования. Будет полезна программистам, желающим освоить высокоуровневые подходы к организации параллельных и распределенных программ, студентам старших курсов, аспирантам и преподавателям технических ВУЗов, преподающим параллельное программирование.

Описание

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

В книге приводятся исходные тексты примеров на языке C++ с использованием библиотеки шаблонов STL, в связи с чем необходимо предварительное знакомство читателя с ними. В примерах реализации описанных подходов иллюстрируется использование технологий OpenMP и MPI, а также низкоуровневых программных интерфейсов Win32 API и POSIX Threads (pthreads). Последние используются в случаях, когда средства высокоуровневых интерфейсов оказываются недостаточно гибкими.

Для компиляции приведенных примеров программ могут быть использованы компиляторы MS Visual C++ версии от 8.0 (2005) или GNU C++. Для компиляции в среде MS Windows программ, использующих функции интерфейса POSIX Threads, возможно использование библиотеки Pthreads-w32 или эмулятора Cygwin.

Оглавление

• Предисловие
  • О проблеме параллельного программирования
  • О целях издания
  • О содержании
  • Об используемой терминологии
  • Некоторые вопросы стиля
• Глава 1. Программные интерфейсы
  • 1.1 Интерфейс OpenMP
    • 1.1.1. Беглый взгляд под капот OpenMP
    • 1.1.2. Основные конструкции параллельного выполнения
    • 1.1.3. Некоторые вспомогательные директивы
    • 1.1.4. Разделение данных
    • 1.1.5. Runtime-функции
    • 1.1.6. Вычисление определенного интеграла
  • 1.2. Интерфейс передачи сообщений MPI
    • 1.2.1. Снова ряд Лейбница
    • 1.2.2. Краткое описание предоставляемых функций
    • 1.2.3. Распределение вычислений в однородной среде
    • 1.2.4. Некоторые вопросы распределения в неоднородной среде
    • 1.2.5. Умножение матрицы на вектор
    • 1.2.6. Перемножение матриц
• Глава 2. Ярусно-параллельная форма программы
  • 2.1. Цель и механизм построения
  • 2.2. Варианты реализации механизма
    • 2.2.1. Поярусное выполнение комплекса работ
    • 2.2.2. Учет индивидуальных зависимостей работ
  • 2.3. Симуляция выполнения логических схем
• Глава 3. Сети конечных автоматов
  • 3.1. Программирование конечных автоматов
  • 3.2. Параллелизм сетей конечных автоматов
  • 3.3. Пример программной реализации
    • 3.3.1. Реализация с использованием OpenMP
    • 3.3.2. Простая реализация с использованием MPI
    • 3.3.3. Реализация с поддержкой вложенных сетей
  • 3.4. Примеры сетей автоматов
    • 3.4.1. Параллельный сумматор
    • 3.4.2. Прямоугольный бильярд
• Глава 4. Сети Петри
  • 4.1. Краткое введение в теорию сетей Петри
    • 4.1.1. Знакомство с сетями Петри
    • 4.1.2. Строго иерархические сети
    • 4.1.3. Параллельные вычисления и синхронизация
    • 4.1.4. Задача об обедающих философах
    • 4.1.5. Задача чтения-записи
  • 4.2. Программная реализация
    • 4.2.1. Функционирование строго иерархических сетей
    • 4.2.2. Выполнение параллельных процессов
  • 4.3. Некоторые примеры использования
    • 4.3.1. Реализация игры в жанре квест
    • 4.3.2. Обработка потоков данных
    • 4.3.3. Реализация задачи об обедающих философах
• Глава 5. Модель актеров
  • 5.1. Описание модели актеров
    • 5.1.1. Первоначальное описание модели
    • 5.1.2. Язык SAL для описания поведения актеров
    • 5.1.3. Некоторые существующие модификации модели
  • 5.2. Различные варианты реализации
    • 5.2.1. Простая одноуровневая реализация
    • 5.2.2. Многопроцессный вариант
    • 5.2.3. Низкоуровневая многопоточная реализация
    • 5.2.4. Поддержка вложенных подсистем актеров
  • 5.3. Примеры решения некоторых задач
    • 5.3.1. Вычисление факториала
    • 5.3.2. Числа Фибоначчи
    • 5.3.3. Задача чтения-записи
    • 5.3.4. Вычисление количества максимальных значений
    • 5.3.5. Поиск выхода из лабиринта
• Глава 6. Квантовые вычисления
  • 6.1. Описание вычислительной модели
    • 6.1.1. Классические обратимые вычисления
    • 6.1.2. Квантовый бит и принцип суперпозиции
    • 6.1.3. Системы кубитов и квантовая запутанность
    • 6.1.4. Унитарные преобразования и квантовые схемы
    • 6.1.5. Измерение результата вычислений
    • 6.1.6. Параллелизм в квантовых вычислениях
  • 6.2. Симулятор квантового компьютера
    • 6.2.1. Виртуальный квантовый вычислитель
    • 6.2.2. Реализация базовых вентилей
  • 6.3. Алгоритм Дойча
  • 6.4. Полная реализация алгоритма Шора
    • 6.4.1. Общая схема и описание
    • 6.4.2. Модульное возведение в степень
    • 6.4.3. Квантовое преобразование Фурье
    • 6.4.4. Извлечение порядка из результата измерения
• Приложение А. Шаблоны классов матрицы и вектора
• Приложение Б. Классы для выполнения комплексов работ
• Приложение В. Классы для выполнения сетей конечных автоматов
• Приложение Г. Классы для выполнения сетей Петри
• Приложение Д. Классы для выполнения систем актеров
• Приложение Е. Классы для симуляции квантовых вычислений
• Литература

Ссылки для загрузки

Прочие ссылки