u_course
.pdfФедеральное агенство по образованию Сибирский федеральный университет
Карепова Е.Д., Кузьмин Д.А., Легалов А.И., Редькин А.В., Удалова Ю.В., Федоров Г.А.
СРЕДСТВА РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ
Учебное пособие
Красноярск 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.Параллельные компьютеры с общей (разделяемой) памятью. Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. В данное направление входят многие современные мно-