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

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

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

Описание

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

Настоящее пособие является попыткой восполнить указанную нишу. В нем описывается несколько теоретических подходов к организации параллельных вычислений. Для каждого подхода приведены примеры реализации с использованием различных средств распараллеливания. С этой целью в первой главе на простых примерах кратко описываются две популярных сегодня технологии распараллеливания последовательных программ - OpenMP и MPI. В остальных главах в порядке усложнения моделей излагаются рассматриваемые подходы : ярусно-параллельная форма программы, сети конечных автоматов, сети Петри. Описанными подходами не исчерпываются существующие модели и парадигмы параллельного программирования, однако они создают начальную базу для дальнейшего изучения моделей параллельных вычислений.

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

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

Оглавление

• Введение 3
  • О целях издания 3
  • О проблеме параллельного программирования 5
  • Об используемой терминологии 8
• Глава 1. Интерфейсы и технологии параллельного программирования 10
  • 1.1 Интерфейс OpenMP 10
    • 1.1.1 Первая программа - ряд Лейбница 11
    • 1.1.2 Основные конструкции параллельного выполнения 17
    • 1.1.3 Некоторые вспомогательные директивы 22
    • 1.1.4 Разделение данных 24
    • 1.1.5 Runtime-функции 26
    • 1.1.6 Вычисление определенного интеграла 30
  • 1.2 Интерфейс передачи сообщений MPI 32
    • 1.2.1 Краткое описание предоставляемых функций 33
    • 1.2.2 Снова ряд Лейбница 36
    • 1.2.3 Неравномерное распределение вычислений 38
    • 1.2.4 Умножение матрицы на вектор 45
    • 1.2.5 Перемножение матриц 51
• Глава 2. Ярусно-параллельная форма программы 60
  • 2.1 Цель и механизм построения ЯПФ 60
  • 2.2 Реализация выполнения комплекса работ при использовании фиксированного количества параллельных ресурсов 65
  • 2.3 Случай неравномерной длительности работ 69
• Глава 3. Сети конечных автоматов 75
  • 3.1 Программирование конечных автоматов 75
  • 3.2 Параллелизм сетей конечных автоматов 80
  • 3.3 Пример программной реализации 83
    • 3.3.1 Реализация с использованием OpenMP 86
    • 3.3.2 Простая реализация с использованием MPI 92
    • 3.3.3 Реализация с поддержкой вложенных сетей 95
  • 3.4 Бильярдные шары 103
  • 3.5 Сумматор 112
• Глава 4. Сети Петри 121
  • 4.1 Краткое введение в теорию сетей Петри 121
    • 4.1.1 Знакомство с сетями Петри 121
    • 4.1.2 Строго иерархические сети 125
    • 4.1.3 Параллельные вычисления и синхронизация 127
    • 4.1.4 Задача об обедающих философах 130
  • 4.2 Пример реализации механизма сетей Петри 133
    • 4.2.1 Функционирование строго иерархических сетей 134
    • 4.2.2 Выполнение параллельных процессов 145
• Заключение 157
• Приложение 1. Шаблоны классов матрицы и вектора 159
• Приложение 2. Классы построения и выполнения комплекса работ 163
• Приложение 3. Классы построения и выполнения сетей конечных автоматов 167
• Приложение 4. Классы построения и выполнения сетей Петри 174
• Библиографический список 182
• Оглавление 186

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

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