Параллельное программирование: Учебное пособие

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

В.И. Калашников

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

Учебное пособие

Утверждено

редакционно-издательским

советом университета,

протокол № 2 от 2.06.2004

Харьков НТУ “ХПИ” 2004

ББК 32.973-018

К17

УДК 004.42

Рецензенты:

Е.П. Путятин, д-р техн. наук, проф.,

Харьковский национальный университет радиоэлектроники;

В.И. Носков, канд. техн. наук, чл.-корр. ТАУ,

главный конструктор, ГП Електротяжмаш.

Калашников  В.И. Параллельное программирование:  Учебн. пособие – Харьков: НТУ “ХПИ”, 2004. – 320 с. – Русск. яз.

ISBN ____________

Даются основные понятия параллельных систем, вычислений и алгоритмов для выполнения громоздких задач. Рассмотрены показатели и методы построения параллельных форм алгоритмов, способы размещения на процессорах совместно выполняемых взаимодействующих процессов, методы защиты общих данных… Описываются расширения языка программирования С++, предназначенные для программирования параллельных задач. Детально рассматривается применение подпрограмм обмена данными между параллельными процессами в среде программирования MPI. Приводятся сведения по постановке и запуску параллельных программ в Windows 2000 с помощью пакета NT-MPICH.

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

Даються основні поняття рівнобіжних систем, обчислень і алгоритмів для вирішування громіздких задач. Розглянуто показники і методи побудови паралельних форм алгоритмів, способи розміщення на процесорах спільно виконуваних процесів, що взаємодіють, методи захисту загальних даних... Описуються розширення мови програмування С++, призначені для програмування паралельних задач. Детально розглядається застосування підпрограм обміну даними між паралельними процесами у середовищі програмування MPІ. Наводяться відомості за постановки запуску паралельних програм у Wіndows 2000 за допомогою пакета NT-MPІCH.

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

Ил. 68.  Табл. 7.  Библиогр. 17 назв.

ББК 32.973-018

ISBN ____________                                                       © В.И. Калашников, 2004

Содержание........................................................... 3

    Предисловие...................................................................................................... 7

1  Суть проблемы и основные понятия.................................................... 9

1.1  Главные этапы распараллеливания задач............................................ 10

1.2  Cведения о вычислительных процессах............................................... 11

1.3  Распределенная обработка данных....................................................... 12

1.4  Движущее начало параллельных процессов...................................... 15

1.5  Механизмы связи параллельных процессов....................................... 16

1.6  Ускорение при параллельных вычислениях....................................... 17

1.7  Зерна параллельных алгоритмов........................................................... 18

1.8  Формальная модель ускорения алгоритмов........................................ 20

2  Параллельные структуры алгоритмов............................................... 25

2.1  Параметры параллельного алгоритма.................................................. 25

2.2  Два подхода к распараллеливанию....................................................... 27

2.2.1  Распараллеливание регулярных выражений............................... 27

2.2.2  Алгоритмы сдваивания..................................................................... 32

2.2.3  Распараллеливание рекуррентных выражений........................... 37

2.2.4  Преобразование общих рекуррентных выражений................... 41

2.2.5  Распараллеливание циклов.............................................................. 49

2.2.6  Формальный подход к распараллеливанию циклов.................. 54

2.3  Формальные методы распараллеливания............................................ 57

2.3.1  Графовая модель параллельных процессов................................ 57

2.3.2  Описание графов информационной зависимости...................... 58

2.3.3  Свойства матрицы смежности орграфа........................................ 63

2.3.4  Лексикографическое упорядочение вершин по ярусам........... 65

2.3.5  Учет времени протекания вершинных процессов...................... 69

2.3.6  Поиск границ допустимых перемещений процессов................ 71

2.3.7  Оптимизация размещения процессов в алгоритме.................... 76

2.4  Организация взаимного обмена данными............................................ 82

2.4.1  Управление параллельными процессами.................................... 84

2.4.2  Синхронизация и неделимость операторов обмена.................. 88

2.4.3  Способы защиты и ограждения критических секций................ 89

2.4.4  Ограниченные ресурсы и критические секции........................... 98