Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

u_course

.pdf
Скачиваний:
39
Добавлен:
04.06.2015
Размер:
1.87 Mб
Скачать

Федеральное агенство по образованию Сибирский федеральный университет

Карепова Е.Д., Кузьмин Д.А., Легалов А.И., Редькин А.В., Удалова Ю.В., Федоров Г.А.

СРЕДСТВА РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

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

Красноярск 2007

2

УДК 681.3.06

ББК

Рецензенты:

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

Предназначено для магистрантов группы 230100.68 «Информатика и вычислительная техника», обучающихся по направлению 230100.68.02 «Высокопроизводительные вычислительные системы», а также может быть полезно для инженеров и магистров, работающих в области высокопроизводительных параллельных вычислений.

3

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ..........................................................................................................

5

ГЛАВА 1. ОСОБЕННОСТИ ПАРАЛЛЕЛЬНОГО

 

ПРОГРАММИРОВАНИЯ..............................................................................

8

Основные классы современных параллельных компьютеров ...................

8

Разработка параллельных приложений ......................................................

14

Программные средства.................................................................................

18

Парадигмы параллельных приложений......................................................

21

Контрольные вопросы..................................................................................

35

ГЛАВА 2. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРИЛОЖЕНИЙ ДЛЯ

 

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С ОБЩЕЙ ПАМЯТЬЮ......................

36

Анатомия потока...........................................................................................

36

Синхронизация потоков. Оператор ожидания...........................................

40

Взаимное исключение. Задача критической секции.................................

42

Барьерная синхронизация ............................................................................

46

Семафоры.......................................................................................................

52

Мониторы.......................................................................................................

57

Контрольные вопросы..................................................................................

61

ГЛАВА 3. УПРАВЛЕНИЕ ПОТОКАМИ С ИСПОЛЬЗОВАНИЕМ

 

БИБЛИОТЕКИ PTHREAD...........................................................................

63

Создание и основы управления потоками в библиотеке Pthread.............

63

Синхронизация потоков с помощью семафоров .......................................

71

Блокировки.....................................................................................................

88

Барьеры...........................................................................................................

93

Контрольные вопросы..................................................................................

96

ГЛАВА 4. УПРАВЛЕНИЕ ПОТОКАМИ С ПОМОЩЬЮ

 

ФУНКЦИЙ WINAPI .....................................................................................

98

Объекты ядра.................................................................................................

98

Процессы......................................................................................................

104

Потоки..........................................................................................................

112

Синхронизация потоков в пользовательском режиме ............................

117

Синхронизация потоков с помощью объектов ядра................................

124

Контрольные вопросы................................................................................

141

4

ГЛАВА 5. ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ OPENMP ..............

143

Директивы pragma.......................................................................................

144

Функции OpenMP и переменные среды...................................................

152

Контрольные вопросы................................................................................

162

ГЛАВА 6. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ПРИЛОЖЕНИЙ ДЛЯ

 

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С РАСПРЕДЕЛЕННОЙ

 

ПАМЯТЬЮ..................................................................................................

164

Примитивы передачи сообщений..............................................................

164

Технология распараллеливания для массивно-параллельных

 

архитектур и основы MPI...........................................................................

170

Контрольные вопросы................................................................................

188

ГЛАВА 7. ОСНОВНЫЕ ФУНКЦИИ СТАНДАРТА MPI...........................

189

Понятие группы, области связи, коммуникатора....................................

189

Обрамляющие и информационные функции...........................................

192

Парные функции приема / передачи сообщений.....................................

193

Функции коллективного взаимодействия процессов..............................

201

Контрольные вопросы................................................................................

208

СПИСОК ЛИТЕРАТУРЫ...............................................................................

210

ВВЕДЕНИЕ

Сегодня параллельное программирование применяется не только для научных вычислений, но и в повседневных областях человеческой деятельности. Это обуславливается массовым переходом производителей микропроцессоров на многоядерные архитектуры. Любой современный персональный компьютер является параллельной вычислительной системой (ПВС) и состоит из двух или более одновременно работающих процессоров. Вполне естественно, что многоядерные процессоры стали широко использоваться и при создании новых высокопроизводительных вычислительных систем, состоящих из десятков тысяч процессорных узлов.

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

применять опыт, накопленный в течение многолетней эксплуатации вычислительных машин с традиционной архитектурой;

разрабатывать последовательные программы, не зависящие от особенностей параллельной вычислительной системы;

использовать продукты, накопленные за многие годы создания программного обеспечения;

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

Однако в далнейшем выяснилось, что такой подход обладает следующими недостатками:

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

в реальной ситуации учесть особенности различных параллельных систем оказалось гораздо труднее, чем это изначально предполагалось.

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

Средства разработки параллельных программм

6

очередь ведет к появлению новых проблем, среди которых можно отметить, что:

программист сам должен формировать все параллельные фрагменты

иследить за корректной синхронизацией процессов;

использование в языках такого типа "ручного" управления памятью может привести к конфликтам между процессами в борьбе за общий ресурс (программисту самому приходится тщательно следить за распределением памяти или явно соблюдать принцип единственного присваивания);

разработанные программы оказываются жестко привязанными к конкретной архитектуре или к семейству архитектур (дальнейшая смена поколений вычислительных систем или появление новых, более эффективных архитектур ведут к полной потере разработанного ПО и необходимости его переработки, что не раз случалось на различных этапах исторического развития);

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

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

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

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

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

Средства разработки параллельных программм

7

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

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

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

Вчетвертой главе рассматривается многопоточное программирование для операционной системы Windows с использовнием WinAPI. Это позволяет сравнить методы, применяемые в различных операционных системах для решения аналогичных задач.

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

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

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

ГЛАВА1. ОСОБЕННОСТИПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ

ОСНОВНЫЕКЛАССЫСОВРЕМЕННЫХПАРАЛЛЕЛЬНЫХКОМПЬЮТЕРОВ

Современные суперкомпьютеры поражают воображение. Например,

компьютер BlueGene/L (eServer Blue Gene Solution, рис. 1.1–1.2) от IBM Ли-

верморской национальной (радиационной) лаборатории Лоренса (США) занимает первое место в 28-мом (вышедшем в ноябре 2006 года) списке самых мощных компьютеров мира. Он объединяет 65536 двухпроцессорных узлов (всего 131072 процессора) с общей оперативной памятью в 32 TB (терабайта) и пиковой производительностью1 367 TFlops (3.67e+15 Flops). На тесте LINPACK BlueGene/L показал производительность2 280.6 TFlops. Узлы сконфигурированы в 32 X 32 X 64 трехмерный тор: каждый узел непосредственно

Рис. 1.1. Архитектура суперкомпьютера BlueGene/L

1Пиковая производительность (Rpeak). При определении пиковой производительности предполагается, что все устройства компьютера работают в максимально производительном режиме. Пиковая производительность измеряется одним из следующих способов: 1) число команд, в единицу времени – MIPS (Million Instructions Per Seconds) (недостаток – команды процессора, они разные для разных машин); 2) число операций (сложения) для чисел с плавающей точкой в единицу времени – Flops (Floating Points Operations Per Seconds).

2Производительность на тесте LINPACK (Rmax): производительность замеряется на решение СЛАУ с плотной матрицей с выбором главного элемента по строке.

Средства разработки параллельных программм

9

Рис. 1.2. Монтаж суперкомпьютера BlueGene/L

связан с шестью соседними узлами. Древовидная структура поддерживает быстрые (несколько микросекунд) операции свертки данных (ссумирование всех элементов массива, нахождение максимального и т.д.) на всех 131072 процессорах. Обмен с дисковой системой происходит со скоростью 1024 гигабит в секунду.

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

Можно привести пример несколько иного характера. По сообщению

Electronic Frontier Foundation (1996 г.), Джон Гилмор (John Gilmore) и Поль Кочер (Paul Kocher) смогли взломать 56-битный код, используемый банками и некоторыми военными организациями США, с помощью собранной в домашних условиях параллельной вычислительной системы.

Раскрытый алгоритм шифрования, известный как DES (Data Encryption Standard), использует 56-битные ключи. Работа по расшифровке была проде-

Средства разработки параллельных программм

10

СуперЭВМ

PVP (векторноконвейрные)

MPP

 

SMP

(распределенная

 

(общая

память)

 

память)

 

 

 

NUMA

Кластеры ccNUMA

Рис. 1.3. Классификация суперЭВМ

лана за 56 часов на компьютере, состоящем более чем из 1000 процессоров: 27 плат по 64 процессора в каждой. Каждая плата была подсоединена к обычному компьютеру, который управлял всем процессом. После проверки 17.902.806.669.197.312 ключей компьютер определил, что зашифрованным предложением было: «'It' + CHAR(39) + 's time for those 128-, 192-, and 256-bit keys'».

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

цессоров с оперативной памятью (рис. 1.3).

1.Векторно-конвейерные компьютеры. Конвейерные функциональ-

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

Векторно-конвейерная архитектура процессора (PVP, Pipe Vector Processor) может использоваться как в компьютерах с одним процессором, так и

вмногопроцессорной системе.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]