Основы многопоточного и параллельного программирования [Евгения Дмитриевна Карепова] (pdf) читать онлайн

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

СИБИРСКИЙ ФЩЕРАЛЬНЫИ УНИВЕРСИТЕТ
SIBERIflfl FEDERAL UfllVERSITY

m

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

ш
•о
CD
о
со
ш

О
О

>
>

Е. Д. Карепова

ОСНОВЫ много поточи о го
И ПАРАЛЛЕЛЬНОГО
ПРОГРАММИРОВАНИЯ

О
оо
ia сг
ia
m
ia
сг О
—I
I
О О

Z1

о

=2
°I


О

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

й о
•о
О

УМО

S

ИНСТИТУТ МАТЕМАТИКИ
I Ж

#• I Л Л Л Я 1~" I 1 Т Д Я I

I |

А

М

I Л

1 А Л П 1 1

Jk^PI Л 1 X 1 л

ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА
ФУНДАМЕНТАЛЬНАЯ И Н Ф О Р М А Т И К А ^
/ . И
И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

я/

и

Оглавление

Министерство образования и науки Российской Федерации
Сибирский федеральный университет
Федеральное государственное бюджетное учреждение науки
«Институт вычислительного моделирования
Сибирского отделения Российской академии наук»
Сибирский научно-образовательный центр
суперкомпьютерных технологий

Е. Д. Карепова

ОСНОВЫ МНОГОПОТОЧНОГО
И ПАРАЛЛЕЛЬНОГО
ПРОГРАММИРОВАНИЯ
Допущено УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших
учебных заведений, обучающихся по направлениям ВПО
010400 «Прикладная математика и информатика» и 010300
«Фундаментальная информатика и информационные технологии», 23 марта 2015 г.

Красноярск
СФУ
2016
1

Оглавление

УДК 004.272(07)
ББК 32.973я73
К225

Карепова, Е. Д.
К225
Основы многопоточного и параллельного программирования :
учеб. пособие / Е. Д. Карепова. – Красноярск : Сиб. федер. ун-т, 2016. –
356 с.
ISBN 978-5-7638-3385-0
Рассматриваются современные подходы к разработке программного обеспечения для высокопроизводительных параллельных вычислительных систем.
Приводятся общие сведения об архитектурах современных суперкомпьютеров
и методах их программирования. Описываются особенности ряда популярных
средств разработки многопоточных и параллельных программ и их использования для эффективного решения научных и прикладных задач.
Предназначено для студентов, аспирантов, инженеров и исследователей,
работающих в области прикладной математики, вычислительной физики и высокопроизводительных параллельных вычислений.
Работа выполнена при частичной поддержке Российского научного фонда
(проект № 14-11-00147)

Электронный вариант издания см.:
http://catalog.sfu-kras.ru
ISBN 978-5-7638-3385-0

2

УДК 004.272(07)
ББК 32.973я73
© Сибирский федеральный
университет, 2016

Оглавление

ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ.................................................................................................. 5
ВВЕДЕНИЕ .......................................................................................................... 8
Г л а в а 1. ОБЗОР ОБЛАСТИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ..... 10
1.1. Основные архитектурные особенности построения
параллельной вычислительной среды ............................... 10
1.2. Основные классы современных
параллельных компьютеров .............................................. 17
1.3. Разработка параллельных приложений ............................. 25
1.4. Программные средства ........................................................ 29
1.5. Парадигмы параллельных приложений ............................ 34
Контрольные вопросы и задания .............................................. 51
Задачи ........................................................................................... 52
Г л а в а 2. ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ
ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
С ОБЩЕЙ ПАМЯТЬЮ ............................................................ 54
2.1. Анатомия потока .................................................................. 54
2.2. Синхронизация потоков. Оператор ожидания .................. 58
2.3. Взаимное исключение. Задача критической секции ........ 60
2.4. Сигнализирующие события. Барьерная
синхронизация ...................................................................... 65
2.5. Семафоры.............................................................................. 73
2.6. Мониторы ............................................................................. 85
Контрольные вопросы и задания .............................................. 91
Задачи ........................................................................................... 93
Г л а в а 3. УПРАВЛЕНИЕ ПОТОКАМИ
С ПОМОЩЬЮ ФУНКЦИЙ WinAPI ..................................... 95
3.1. Объекты ядра ........................................................................ 95
3.2. Процессы............................................................................. 101
3.3. Потоки ................................................................................. 108
3.4. Синхронизация потоков в пользовательском режиме ... 113
3.5. Синхронизация потоков с помощью объектов ядра ...... 120
3.6. Проблемы условной синхронизации ............................... 128
3.7. Проецируемые в память файлы ........................................ 138
3.8. Совместный доступ процессов
к данным через механизм проецирования ...................... 144
Контрольные вопросы и задания ............................................ 146
Задачи ......................................................................................... 147
3

Оглавление

Г л а в а 4. ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ OpenMP ............ 153
4.1. Программная модель OpenMP.......................................... 153
4.2. Модель памяти OpenMP .................................................... 156
4.3. Среда выполнения OpenMP-программы ......................... 158
4.4. Директива omp parallel ..................................................... 164
4.5. Распределение работы в параллельной области
по нитям .............................................................................. 171
4.6. Директивы синхронизации ............................................... 191
4.7. Переменные среды и функции времени выполнения .... 204
4.8. Спецификации стандарта OpenMP v. 4.0 ........................ 210
4.9. Оптимизация программ OpenMP ..................................... 212
4.10. Ограничения OpenMP...................................................... 213
Контрольные вопросы и задания ............................................ 215
Задачи ......................................................................................... 215
Г л а в а 5. СОГЛАСОВАННОЕ
ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ ...................... 221
5.1. Проблемы программирования
для вычислительных систем
с распределенной памятью ............................................... 221
5.2. Оценка эффективности параллельных алгоритмов ....... 225
5.3. Реализация базовых алгоритмов
вычислительной математики ............................................ 248
5.4. Проблемы выбора эффективной
параллельной реализации ................................................. 272
Контрольные вопросы и задания ............................................ 289
Г л а в а 6. ОСНОВЫ ТЕХНОЛОГИИ
ПРОГРАММИРОВАНИЯ MPI ............................................... 291
6.1. Архитектурная парадигма MPI ........................................ 291
6.2. Обрамляющие и информационные функции MPI.......... 293
6.3. MPI и крупноблочное распараллеливание ...................... 294
6.4. Организация вычислений .................................................. 300
6.5. Организация взаимодействий процессов ........................ 311
6.6. Повышение эффективности MPI-программ .................... 335
Контрольные вопросы и задания ............................................ 338
Задачи ......................................................................................... 340
БИБЛИОГРАФИЧЕСКИЙ СПИСОК .......................................................... 347

4

Предисловие

ПРЕДИСЛОВИЕ
Предлагаемое учебное пособие содержит материал для
базового курса «Параллельное программирование», который охватывает
широкий круг вопросов, связанных с высокопроизводительными вычислениями, а также отражает содержание нескольких спецкурсов, которые на
протяжении ряда лет читаются автором в Институте математики и фундаментальной информатики Сибирского федерального университета и аспирантуре Института вычислительного моделирования СО РАН.
Пособие можно разделить на три части: общие аспекты параллельного
программирования; программирование для параллельных вычислительных
систем (ПВС) с общей памятью; программирование для систем с распределенной памятью. В каждой части сначала обсуждаются проблемы, порождаемые архитектурой соответствующей вычислительной системы (ВС),
теоретические основы решения этих проблем, затем подробно рассматривается языковая реализация всех базовых механизмов. Как теоретический, так
и практический материал проиллюстрирован большим количеством примеров, многие из которых давно уже стали классикой параллельного программирования.
В первой главе рассматриваются основные особенности параллельного программирования. Приводится краткая классификация основных
видов архитектур ПВС, и подчеркивается необходимость использования
разнообразных методов написания параллельных программ в зависимости
от типа архитектуры. Здесь же дан краткий перечень существующих программных средств, методов написания параллельных программ, а также
факторов, определяющих те или иные приемы распараллеливания.
Во второй главе более подробно описываются особенности разработки программ для ПВС с общей памятью. Дается определение потока,
рассматриваются основные состояния, в которых может находиться поток.
Приводятся сведения о создании параллельных потоков и методах решения проблем, порождаемых необходимостью их синхронизации (взаимного исключения, барьерной синхронизации, условного ожидания), вводятся
основные синхропримитивы, используемые при многопоточном программировании. Подробно рассмотрено использование семафоров и мониторов.
Обсуждаются способы решения классических задач многопоточного программирования (задачи о критической секции, кольцевом буфере, философах, читателях и писателях).

5

Предисловие

Третья глава посвящена практическому применению потоков для
операционной системы Windows с использованием WinAPI. Дается общее
понятие объекта ядра ОС Windows, процесса и потока. Приводится описание общей структуры создаваемой многопоточной программы. Обсуждаются особенности реализации проблемы взаимного исключения потоков
одного процесса, т. е. потоков, находящихся в общем адресном пространстве
(синхронизация в пользовательском режиме), и общий случай синхронизации потоков, относящихся, может быть, к разным процессам, с помощью
объектов ядра. Рассмотрен один из простых механизмов организации связи
между потоками разных процессов, например, для обмена данными. Автор
благодарит аспиранта Г. А. Федорова за помощь в отборе материала и отладке кода ряда примеров.
Технология OpenMP создания параллельных программ для ВС с общей памятью обсуждается в четвертой главе. В отличие от реализации
многопоточности в языке Си с помощью функций WinAPI, или библиотек
Pthread, или Qt библиотека OpenMP в большей степени рассчитана
на прикладного программиста, позволяя быстро создавать короткие и простые
многопоточные приложения с помощью директив компилятора из последовательного кода. Знание основ технологии OpenMP полезно еще и по той
причине, что ее современные реализации обеспечивают поддержку программирования для комбинированных ПВС, содержащих как общую, так
и распределенную память.
Общие сведения о разработке параллельных программ для систем
с распределенной памятью на основе механизма передачи сообщений
приводятся в пятой главе. Кратко обсуждаются вопросы, связанные с исследованием информационных зависимостей и оценками внутреннего
параллелизма алгоритмов, даются понятия ускорения, эффективности,
масштабируемости. На ряде примеров показаны различные стратегии использования вычислительных ресурсов ПВС, взаимодействующих между
собой через механизм передачи сообщений. Рассмотрены достоинства
и недостатки каждого из подходов. Описаны двухточечные и коллективные взаимодействия процессов, подходы к оценке времени, необходимого
на передачу сообщений в кластерных системах. В конце главы рассмотрены основные задачи вычислительной математики и схемы возможных
параллельных алгоритмов для их решения.
В шестой главе рассмотрены основы программирования для ВС
с распределенной памятью с помощью библиотеки MPI, которая соответствует всем требованиям одноименного стандарта средств организации
передачи сообщений (message passing interface – MPI). Описана архитектурная парадигма MPI, ее связь с крупноблочным распараллеливанием.
Обсуждаются вопросы организации вычислений (использование комму6

Предисловие

никаторов, производных типов, виртуальных топологий) и взаимодействий
процессов (двухточечные и коллективные обмены, операции приведения
и барьерной синхронизации). Отметим, что хотя в тексте и приведены синтаксис и характеристика большинства функций MPI для языка Си, главу не
следует рассматривать как описание стандарта MPI. Все вводимые концепции, понятия и методы проиллюстрированы примерами. Автор благодарит А. В. Малышева за предоставленный материал и полезные обсуждения по теме главы.
Знания и навыки, полученные при изучении курса, позволяют
в дальнейшем перейти к более детальному освоению инструментальных
средств разработки параллельных программ и методов эффективного распараллеливания практических и научных задач.
Базовый курс «Параллельное программирование» читается в Институте математики и фундаментальной информатики Сибирского федерального университета в течение восьми лет. В это же время автором читались
и более узконаправленные спецкурсы и курсы для магистрантов и аспирантов, материалы которых также включены в пособие.
Следует отметить, что при разработке курса и подготовке настоящего
учебного пособия автором использовались, прежде всего, учебные пособия
и монографии [1, 2, 9–14, 25–27, 34, 35, 48], материалы по параллельному
программированию, представленные на порталах [77, 82], а также электронный курс [68] «Многопроцессорные вычислительные системы и параллельное программирование», разработанный под руководством профессора В. П. Гергеля в Нижегородском госуниверситете им. Н. И. Лобачевского.
Автор благодарит за полезные обсуждения члена-корреспондента
РАН В. В. Шайдурова, профессора А. В. Старченко, профессора А. И. Легалова, Д. А. Кузьмина, а также признателен за помощь и участие Андрею Малышеву, Юрию Шанько, Георгию Федорову, Екатерине Дементьевой и Марине Вдовенко.
Работа выполнена при частичной поддержке Российского научного
фонда (проект № 14-11-00147).

7

Введение

ВВЕДЕНИЕ
Сегодня многопоточное и параллельное программирование применяется не только для научных вычислений, но и в повседневных
областях человеческой деятельности. Это обуславливается массовым переходом производителей микропроцессоров на многоядерные архитектуры.
Любой современный персональный компьютер является параллельной вычислительной системой, а многие приложения – суть многопроцессные
(или многопоточные). Многие научные и промышленные предприятия
используют для повседневных нужд высокопроизводительные вычислительные системы, состоящие из десятков тысяч процессорных узлов.
Очевидно, что при разработке параллельных программ необходимо
применять методы, обеспечивающие эффективное использование предоставляемых вычислительных ресурсов. Однако разнообразие архитектур
ПВС привело к тому, что в настоящее время не существует языка, позволяющего создавать программы, легко и эффективно переносимые с одной
архитектуры на другую.
Первоначально виделось, что использование языков последовательного программирования обеспечит универсальный путь для написания
параллельных приложений. Однако быстро выяснилось, что такой подход
обладает рядом недостатков:
● Прямое распараллеливание последовательных программ часто не
обеспечивает достижения приемлемого уровня параллелизма из-за ограничений, обусловленных принципиально последовательными реализациями
алгоритмов и стереотипами последовательного мышления.
● В большинстве языковых средств для реализации параллелизма
необходимо явно формировать все параллельные фрагменты и следить
за корректной синхронизацией процессов.
● Допустимость использования в языках «ручного» управления
памятью может привести к конфликтам между процессами в борьбе за общий ресурс.
● Разработанные программы оказываются жестко привязанными
к конкретной архитектуре или к семейству архитектур (дальнейшая смена
поколений вычислительных систем или появление новых, более эффективных, архитектур ведут к потере разработанного ПО и/или необходимости его переработки, что не раз случалось на различных этапах развития
программирования).
● Существует излишняя детализация ведения вычислений, поскольку
кроме управления, связанного с непосредственным преобразованием дан8

Введение

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

9

Г л а в а 1. Обзор области параллельных вычислений

Глава 1

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

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

1.1. Основные архитектурные особенности
построения параллельной вычислительной среды
Следуя [9], выделим два основных фактора, определяющих бурное
развитие вычислительной техники на пути увеличения производительности вычислительных систем, уменьшения их размеров, а также расширения круга решаемых задач: 1) развитие элементной базы; 2) совершенствование архитектуры.
Сравним характеристики (табл. 1.1) одного из первых компьютеров
мира – EDSAC, появившегося в 1949 году в Кембридже, – и одного процессора современного суперкомпьютера Roadrunner1, инсталлированного
в 2008 году в Лос-Аламосской национальной лаборатории (США).
За 60 лет тактовая частота процессора выросла в тысячи раз, а производительность увеличилась в сотни миллионов. Ясно, что основное увеличение производительности обусловлено не наращиванием мощности процессора, а использованием новых решений в архитектуре компьютеров.
Архитектуру однопроцессорного компьютера принято называть
архитектурой фон Неймана (рис. 1.1). Она была логичным решением2 проблемы создания первой электронной машины с запоминаемой программой
1

Суперкомпьютер Roadrunner создан компанией IBM для Министерства энергетики США и установлен в Лос-Аламосской национальной лаборатории в НьюМексико, США. Roadrunner первым в мире преодолел на тесте Linpack рубеж производительности в 1 PFlop/s.
2
В 1948–1950 гг. в Советском Союзе независимо от Джона фон Неймона под
руководством Сергея Александровича Лебедева была разработана и реализована
МЭСМ (малая электронная счетная машина), основанная на сходных идейных и архитектурных принципах.
10

1.1. Основные архитектурные особенности построения параллельной вычислительной среды

и показала свою жизнеспособность. Основными компонентами для выполнения программ в такой архитектуре являются центральное процессорное
устройство (ЦПУ), кэш- и оперативная память. Процессор выбирает инструкции из памяти, декодирует их и выполняет. Он содержит управляющее
устройство (УУ), арифметико-логическое устройство (АЛУ) и регистры.
УУ вырабатывает сигналы, управляющие действиями АЛУ, системой памяти и внешними устройствами. АЛУ выполняет арифметические и логические инструкции, определяемые набором инструкций процессора. В регистрах хранятся инструкции, данные и состояние машины, в том числе
счетчик команд.
Таблица 1.1
Характеристика

EDSAC (1949)

Тактовая частота
Пиковая производительность1

0,5 МГц
1,0e+2 оп/с

1 процессор
Roadrunner (2008)
3200 MГц
1,28e+10 флопс

Значение
увеличилось
↑ 6,4е+3
↑1,28е+8

Однако архитектура однопроцессорного компьютера начала изменяться и совершенствоваться буквально с первых шагов развития вычислительной техники, что, прежде всего, связано с идеями параллелизма.
Оперативная память
Кэш уровня 3
Кэш уровня 2
Кэш уровня 1
ЦПУ

АЛУ

Контроллеры
периферийных
устройств

Контроллер

УУ

Периферийные
устройства

Дисковая
память

Рис. 1.1. Принципиальная схема однопроцессорной ЭВМ

Возможные пути достижения параллелизма детально рассматриваются в монографиях [8, 16, 32, 39, 43, 48, 51, 56, 64, 72], в этих же работах
описывается история развития параллельных вычислений и приводятся
примеры конкретных параллельных ЭВМ.
1

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

Г л а в а 1. Обзор области параллельных вычислений

Параллелизм опирается на следующие архитектурные особенности
построения вычислительной среды.
1. Независимость функционирования отдельных устройств ЭВМ –
в настоящее время утверждение справедливо для всех основных компонентов ВС: для устройств ввода-вывода, для обрабатывающих процессоров
и для устройств памяти.
2. Иерархическое устройство памяти – очень важная особенность
архитектуры, влияющая на его производительность (рис. 1.2, табл. 1.2).
Оперативная память
Кэш уровня 3
Кэш уровня 2
Кэш уровня 1
ЦПУ
Рис. 1.2. Иерархия памяти в современном компьютере
Таблица 1.2
Вид памяти
Регистры
Кэш первого уровня
Кэш второго уровня
Кэш третьего уровня
Оперативная память

Размер
Несколько десятков байт
Несколько десятков килобайт
Несколько мегабайт
До нескольких десятков мегабайт
Несколько гигабайт

Скорость доступа
1 такт работы
1–2 такт работы
8–20 тактов работы
30–60 тактов работы
50–100 тактов работы

Самая быстрая память – регистровая, но она небольшая по объему.
Кэш – это также небольшой1 по объему, но скоростной модуль памяти, в который помещаются данные, часто используемые процессором. Использование кэш-памяти заметно ускоряет выполнение программы. Этому
способствует временная локальность программ, означающая, что если
произошло обращение к некоторой области памяти, то, скорее всего,
в ближайшем будущем обращение к этому же участку памяти повторится.
В результате при обращении к некоторой области памяти процессор сначала ищет данные в кэше. Если данные находятся (попадание в кэш), то
они считываются из кэша, иначе (промах) данные считываются из оперативной памяти и в процессор, и в кэш. Для ускорения также используется
свойство пространственной локальности программ: за обращением к не1

Следует отметить, что объем кэш-памяти в современных компьютерах сравним
с объемом оперативной памяти в компьютерах пятилетней давности.
12

1.1. Основные архитектурные особенности построения параллельной вычислительной среды

которой странице памяти обычно следует обращение к соседним страницам.
С учетом этого данные в кэш считываются блоками страниц.
По записи различают сквозной кэш – измененные данные помещаются
в память немедленно – и кэш с обратной записью, в котором обновление
оперативной памяти происходит по более сложным алгоритмам. В последнем случае может наблюдаться временное несоответствие содержимого
кэша и оперативной памяти.
В современных процессорах обычно имеется до трех уровней кэша.
Кэш первого уровня является неотъемлемой частью процессора, расположен с ним на одном кристалле и имеет минимальное время доступа. В современных многоядерных системах этот вид памяти принадлежит непосредственно ядру, а не всему процессору. Кэш второго уровня чаще всего
также находится на кристалле процессора и принадлежит ядру. Кэш
третьего уровня (если он есть), как правило, расположен отдельно, разделяется ядрами (процессорами) и может быть достаточно большим по объему
(несколько мегабайт на ядро).
Уровни кэш-памяти отличаются и организацией. Кэш-память первого
уровня отображается непосредственно и содержит отдельные области
для хранения инструкций и данных. Кэш-память второго и третьего уровней обычно унифицирована, т. е. не делает различий между данными и инструкциями. Поскольку последовательный перебор всех строк кэша в поисках необходимых данных существенно увеличил бы время доступа,
то память этих уровней чаще является множественно-ассоциативной. Для
сокращения времени поиска ячейки оперативной памяти (ОП) жёстко привязываются к строкам кэш-памяти, т. е. в каждой строке могут быть данные из фиксированного набора адресов, при этом каждая ячейка ОП может
быть ассоциирована с несколькими строками кэша.
Кэширование данных существенно увеличивает производительность
современных компьютеров. Однако в многоядерных системах возникают
проблемы согласования данных в кэшах ядер.
3. Параллельная обработка данных чаще всего реализует простую
идею: если некое устройство выполняет одну операцию за единицу времени, то K операций оно выполнит за K единиц, а система из N устройств ту
же работу выполнит за K/N единиц времени. Ярким примером операций,
допускающих параллельную обработку, являются арифметические операции над векторами. В конце прошлого века процессоры, в набор команд
которых входили операции над векторами, были широко распространены
(например, компьютеры семейства Cray). В большинстве современных
микропроцессоров имеются векторные расширения, в видеокартах используется параллельная обработка изображения.

13

Г л а в а 1. Обзор области параллельных вычислений

С идеями параллельной обработки данных тесно связано и простое
дублирование устройств ВС. Получило распространение использование
нескольких однотипных обрабатывающих процессоров, а также многоядерных архитектур. Например, суперкомпьютер Roadrunner построен по
гибридной схеме и содержит 6 120 двухъядерных процессоров AMD
Opteron для вычислений и 12 240 процессоров IBM Cell 8i в специальных
блэйд-модулях TriBlades. Кроме того, еще 442 двухядерных процессора
AMD Opteron задействованы для системных функций. В свою очередь, сам
процессор IBM Cell 8i включает в себя одно универсальное ядро Power
и восемь специальных ядер для операций с плавающей точкой.
Одной из реализаций параллельной обработки данных в архитектуре
ВС можно считать суперскалярность многих современных процессоров
(в том числе x86 начиная с Pentium, MIPS и т. д.). Суперскалярный процессор
может выполнять несколько команд за один такт, причем распараллеливание потока команд происходит динамически на аппаратном уровне.
Развитие идей суперскалярности представлено VLIW-архитектурой
(Very Long Instruction Word) процессоров. В этом случае одна инструкция
процессора содержит набор операций, которые должны выполняться
параллельно различными функциональными устройствами. Распараллеливание кода в таких архитектурах возложено на программиста или компилятор. В первом случае архитрудоемкость процесса предполагает высокий
уровень квалификации, а во втором – требуется перекомпиляция существующих кодов, практически исключается возможность влияния программиста на повышение производительности, падение которой неизбежно при
универсальности, и не исключается проявление возможных ошибок компилятора. VLIW-архитектура реализована в микропроцессрах Крузо
(Transmeta Crusoe), видеопроцессорах AMD, микропроцессорах архитектуры
Intel Itanium и др.
4. Конвейерная реализация обрабатывающих устройств основана на
том, что сложную операцию (даже некоторые команды процессора) можно
разбить на несколько простых этапов1. На каждом этапе функциональное
устройство (ФУ), выполнив свою работу, передает результат следующему,
одновременно принимая от предыдущего новую порцию входных данных.
Организовывая цепочку из таких ФУ, получаем очевидный выигрыш
в скорости обработки за счет совмещения прежде разнесенных во времени
операций.
Предположим, что в операции над некоторым набором операндов
можно выделить K микроопераций, каждая из которых выполняется за одну
1

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

1.1. Основные архитектурные особенности построения параллельной вычислительной среды

единицу времени. Если есть одно неделимое последовательное универсальное устройство, то M наборов операндов оно обработает за K×M единиц. Если каждую микрооперацию выделить в отдельный этап (ступень)
конвейерного устройства, то на K-й единице времени на разной стадии обработки будут находиться первые K наборов операндов. Все M наборов
операндов будут обработаны за K+(M–1) единиц времени – ускорение по
сравнению с последовательным устройством почти в K раз (по числу ступеней конвейера).
Проиллюстририруем преимущество применения конвейера на примере простого пятиуровневого1 конвейера команд в RISC-процессорах
(рис. 1.3).
Instruction 1

Instruction 2

Instruction 3

Instruction 4

Instruction 5

IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB

TICK 1
TICK 2
TICK 3
TICK 4
TICK 5
TICK 6
TICK 7
TICK 8
TICK 9

IF
IF 1
IF 2
IF 3
IF 4
IF 5
BUBBLE
BUBBLE
IF 6
IF 7

ID
N/A
ID 1
ID 2
ID 3
ID 4
ID 5
BUBBLE
BUBBLE
ID 6

EX
N/A
N/A
EX 1
EX 2
EX 3
EX 4
EX 5
BUBBLE
BUBBLE

MEM
N/A
N/A
N/A
MEM 1
MEM 2
MEM 3
MEM 4
MEM 5
BUBBLE

WB
N/A
N/A
N/A
N/A
WB 1
WB 2
WB 3
WB 4
WB 5

Рис. 1.3. Исполнение 5 команд в RISC-процессорах: последовательное (вверху)
и с помощью конвейера команд (внизу). Показано продвижение по конвейеру «пузыря»

В этом случае принято, что выполнение типичной инструкции разделено на пять этапов (ступеней конвейера):
IF (Instruction Fetch) – по текущей позиции счетчика команд выбор
очередной команды из памяти и размещение ее в регистре команд, увеличение счетчика команд;
ID (Instruction Decoding) – декодирование команды, определение ее
типа и типов операндов, при необходимости параллельная загрузка операндов из регистрового файла в регистры;
EX (Execute) – выполнение операции над cоответсвующими регистрами (для команд типа Register-Register ALU instruction и Regis1

Количество этапов, на которые разбивается выполнение процессорной команды, сильно варьируется; например, в разных моделях процессоров х86 конвейер команд
имеет от 2 ступеней для i8088 до нескольких десятков у Pentium.
15

Г л а в а 1. Обзор области параллельных вычислений

ter_Immediate ALU instruction) или вычисление эффективного адреса для
команд загрузки или записи (Load / Store instructions);
MEM (Memory access) – непосредственная работа с памятью для команд загрузки / записи;
WB (Write Back cycle) – запись результата команды в регистровый
файл (из памяти в случае операции загрузки или непосредственно из ALU).
Если считать, что выполнение каждой ступени конвейера занимает
один такт, то конвейерное выполнение пяти команд займет всего 9 тактов
(рис. 1.3), а их последовательное выполнение заняло бы 25 тактов. Отметим, что для успешного функционирования конвейера необходимо,
чтобы данные для первой операции поступали непрерывно: иначе неизбежно возникновение «пузырей» (bubble), снижающих эффективность
процесса.
Конечно, конвейерную обработку можно заменить обычным
параллелизмом, для чего надо продублировать универсальное устройство
по числу ступеней конвейера. Каждое такое устройство должно: 1) быть
универсальным, т. е. уметь делать операции всех ступеней конвейера;
2) сделать все операции за то же время, которое работает конвейер. Это
многократно увеличивает объем, энергопотребление и стоимость оборудования.
5. Использование специализированных устройств широко распространено в современных ВС. Например, блэйд-модули уже упоминавшегося
суперкомпьютера Roadrunner содержат процессоры IBM Cell 8i, включающие в себя наряду с универсальным ядром Power восемь специальных ядер
для операций с плавающей точкой.
Современные видеокарты содержат графические процессоры (GPU),
которые по сложности не уступают центральному процессору компьютера,
но имеют архитектуру, максимально нацеленную на увеличение скорости
расчета текстур и сложных графических объектов. В настоящее время GPU –
это массивно-параллельное программируемое вычислительное устройство
с высоким быстродействием, большим объемом собственной оперативной
памяти. GPU может использоваться как сопроцессор, пригодный для решения широкого круга задач, мало связанных с графикой. В связи с этим
появился термин GPGPU (General Purpose Graphics Processor Unit) – графические процессоры общего назначения.
Более того, наряду с видеокартами получают распространение «ускорители физики» – выделенный специализированный процессор, предназначенный для обработки динамичного видеоизображения, связанного
с динамикой жидкости, твёрдых и мягких тел, обнаружением столкновений, симуляцией волос, меха и ткани, разломов объектов.

16

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

1.2. Основные классы
современных параллельных компьютеров
Современные суперкомпьютеры поражают воображение. В первом
параграфе мы уже упоминали характеристики высокопроизводительной
вычислительной системы Roadrunner, занимавшей первое место в 32-м
списке1 (вышедшем в ноябре 2008 года) самых мощных компьютеров мира.
Другим популярным решением является семейство суперкомпьютеров BlueGene. Например, суперкомпьютер BlueGene/L (eServer Blue Gene
Solution, рис. 1.4–1.6) от IBM Ливерморской национальной (радиационной)
лаборатории Лоренса (США) в течение двух лет (2006–2007) занимал первую строчку2 в top500. Суперкомпьютер объединяет 106 496 двухпроцессорных узла (всего 212 992 процессора) с общей оперативной памятью в 53 TB
(терабайта) и пиковой производительностью 596,4 TFlops (5,964e+14 Flops).
На тесте LINPACK3 BlueGene/L показал производительность 478,2 TFlops.
Узлы BlueGene/L сконфигурированы в 32×32×64-трехмерный тор: каждый
узел непосредственно связан с шестью соседними узлами. Древовидная
структура поддерживает быстрые (несколько микросекунд) операции
свертки данных (суммирование всех элементов массива, нахождение максимального и т.д.) на всех 212 992 процессорах. Обмен с дисковой системой происходит со скоростью 1 024 гигабит в секунду.
Ясно, что создание и обслуживание таких вычислительных монстров –
это не простое любопытство небольших коллективов ученых-энтузиастов,
а отвечающая современным экономическим запросам технология.
Автомобилестроение, нефте- и газодобыча, фармакология, прогноз
погоды и моделирование изменения климата, сейсморазведка, проектирование электронных устройств, синтез новых материалов, крупнейшие
мировые системы бронирования – вот неполный список областей челове1

На сайте top500.org можно найти выпускаемый два раза в год (в июне и ноябре)
рейтинг суперкомпьютеров. Рейтинг строится на основе сравнений пиковой производительности и производительности, показанной по тесту LINPACK. Последний раз Roadrunner упомянут в 40-й редакции списка от ноября 2012 года на 22-м месте.
2
Развитие высокопроизводительной техники стремительно. Последнйй раз BlueGine/L упоминался в 36-й редакции списка top500 от ноября 2010 года на 12-м месте.
Однако архитектурное решение BlueGine оказалось очень удачным, а суперкомпьютеры подобной архитектуры регулярно занимают высокие строчки в top500.
3
Тест решает случайно заданную систему линейных уравнений с плотной матрицей методом LU-разложения, используя 64-битную арифметику с плавающей точкой,
что позволяет судить о реальной производительности вычислительной системы. Существует много публикаций, критикующих такой подход к оценке реальной производительности суперкомпьютеров, но общепринятой альтернативы тесту до сих пор не
предложено.
17

Г л а в а 1. Обзор области параллельных вычислений

ческой деятельности, в которых использование суперкомпьютеров действительно необходимо.
Разделяемая кэш-память третьего уровня (L3)
Корректный досКэш-память
Кэш-память
туп в кэш-память
второго уровня
второго
уровня
(snoop)
(L2 prefetch buffer)
(L2 prefetch buffer)
Кэш-память
первого уровня
L1-I
L1-D
(команды)
(данные)
Процессор
(PowerPC)
Специализированный
процесcор для
операций
с плавающей точкой
(Double Hummer FPU)

Порт для коммуникаций «точка –
точка»
(Torus
interconnect)

Кэш-память
первого уровня
L1-I
L1-D
(команды)
(данные)
Процессор
(PowerPC)
Специализированный
процессор для
операций
с плавающей точкой
(Double Hummer FPU)

Порт для
коллективных
операций
обмена
(Collective
interconnect)

Порт глобальной барьерной
синхронизации
(Global barrier
interrupt)

Рис. 1.4. Устройство одного узла в архитектуре BlueGene/L

Самой известной схемой классификации компьютерных архитектур
является таксономия Флинна [60–61], предложенная еще в 1966 году. В ее
основу положены способы взаимодействия компьютера с потоками команд и данных. Согласно Флинну имеется два класса параллельных архитектур, которые впоследствии были дополнены еще одной (систолические
массивы), в эту же классификацию включена архитектура обычного однопроцессорного компьютера. Таким образом, в настоящее время говорят
о следующей таксономии Флинна.
1. SISD (Single Instraction Stream – Single Data Stream) – это обычные
последовательные компьютеры, когда в каждый момент времени выполняется только одна операция над одним элементом данных. Возможно включение в состав ВС нескольких процессоров, но каждый работает со своим
набором данных, относящихся к своей независимой программе.
18

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

Рис. 1.5. Архитектура суперкомпьютера BlueGene/L
(https://asc.llnl.gov/computing_resources/bluegenel/configuration.html)

Рис. 1.6. Монтаж суперкомпьютера BlueGene/L
(https://asc.llnl.gov/computing_resources/bluegenel/images/cables.jpg)
19

Г л а в а 1. Обзор области параллельных вычислений

2. SIMD (Single Instraction Stream – Multiple Data Stream) состоят из
одного командного процессора (управляющего модуля, контроллера) и нескольких модулей обработки данных (процессорных элементов, ПЭ).
Управляющий модуль принимает, анализирует и выполняет команды. Если
в команде встречаются данные, то контроллер рассылает команду на все
ПЭ, и команда выполняется над данными каждого процессорного элемента. Яркими представителями этого класса являются векторные компьютеры, а также матричные процессоры. Часто такие архитектуры специализированы под решение конкретных задач, допускающих матричное представление, например, задач обработки изображений.
3. MISD (Multiple Instraction Stream – Single Data Stream). Систолический массив процессоров, в котором процессоры находятся в узлах регулярной решетки. Роль ребер играют межпроцессорные соединения, все ПЭ
управляются общим тактовым генератором. В каждом цикле любой ПЭ
получает данные от своих соседей, выполняет одну команду и передает
результат соседям.
4. MIMD (Multiple Instraction Stream – Multiple Data Stream). Этот
класс наиболее богат примерами успешных реализаций. Это кластеры рабочих станций, симметричные параллельные ВС и пр.
Классификация Флинна не дает исчерпывающего описания разнообразных MIMD-архитектур. Например, системы с разделяемой памятью относятся как к MIMD-, так и SIMD-архитектуре. Поэтому рассматриваются
и другие способы классификации параллельных компьютеров, например,
Хокни, Фенга, Хендлера, Шнайдера, Скилликорна [9].
Самой простой классификацией суперкомпьютеров является деление
их по способу взаимодействия процессоров с оперативной памятью
(рис. 1.7).
1. Векторно-конвейерные компьютеры. Конвейерные функциональные устройства и набор векторных команд – это две особенности
таких ВС. В отличие от традиционного подхода векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры.
Векторно-конвейерная архитектура процессора (PVP, Pipe Vector
Processor) может использоваться как в компьютерах с одним процессором,
так и в многопроцессорной системе.
2. Параллельные компьютеры с общей (разделяемой) памятью.
Вся оперативная память таких компьютеров разделяется несколькими
одинаковыми процессорами. В данное направление входят многие современные многопроцессорные и многоядерные SMP-компьютеры (Single Memory
Processor) или, например, отдельные узлы компьютеров HP Exemplar
и Sun StarFire.
20

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

В мультипроцессоре с общей (разделяемой) памятью (SMP) процессоры и оперативная память связаны с помощью соединительной сети (рис. 1.8).
Процессоры совместно используют память, но каждый из них имеет собственный кэш.
Высокопроизводительная ВС
PVP
(векторно-конвейрные)
MPP
(распределенная память)

SMP
(общая память)

Кластеры,
SMP-узловые кластеры

NUMA
ccNUMA

UMA

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

Оперативная
память

Оперативная
память
Связующая сеть

Кэш

Кэш

ЦПУ

ЦПУ

Рис. 1.8. Структура мультипроцессора
с разделяемой памятью

Если число процессоров относительно невелико (от двух до тридцати),
то связующая сеть может быть реализована в виде шины памяти или матричного коммутатора. Поскольку время доступа каждого из процессоров
клюбому участку памяти одинаково, то такой мультипроцессор называется
однородным (UMA, uniform memory access).
В мультипроцессорах с разделяемой памятью, включающих десятки
и сотни процессоров, память организована иерархически. Связующая сеть
имеет вид древообразного набора переключателей и областей памяти
(межкластерные шины, Butterfly и пр.). Поскольку одна часть памяти ближе
к определенному процессору, другая дальше от него, то возникает неоднородность времени доступа, зато снижается нагрузка на каждую шину или
21

Г л а в а 1. Обзор области параллельных вычислений

коммутатор. Такая архитектура называется неоднородной (NUMA, non uniform memory access).
В SMP-компьютерах каждый процессор имеет собственную кэшпамять (кэш), что порождает проблему согласованности кэша. Если два
процессора обращаются к одной области памяти примерно одновременно
и один из них записывает данные, то кэш-память этих процессоров будет
содержать разные данные. Необходимо либо обновить кэш, либо признать
его содержимое недействительным. Протоколы согласования реализуются
аппаратно. NUMA-архитектура, обеспечивающая аппаратную поддержку
согласованности кэш-памяти, называется ccNUMA – cash caherent non uniform memory access.
В SMP-архитектурах также возникает проблема согласованности
оперативной памяти, решение которой опирается на одну из следующих
моделей. Последовательная согласованность гарантирует, что обновление
памяти происходит в некоторой последовательности, причем каждому
процессору «видна» одна и та же последовательность. Это самая сильная
модель. Согласованность процессоров обеспечивает упорядоченность записи в память, выполняемой каждым процессором, но порядок записей,
инициированных разными процессорами, для других процессоров может
выглядеть по-разному. Самая слабая модель – согласованное освобождение, при которой оперативная память обновляется в указанных программистом точках синхронизации.
В последнее время быстрыми темпами развиваются многоядерные
архитектуры, подразумевающие наличие не только общей оперативной
памяти, но и общего кэша второго или третьего уровня.
3. Массивно-параллельные компьютеры с распределенной памятью. Компьютеры этого класса обычно состоят из серийных микропроцессоров (каждый со своей локальной памятью), соединенных посредством
коммуникационной среды.
Достоинства такой архитектуры очевидны – легкая масштабируемость, возможность простого расчета оптимальной конфигурации и т. п.
Однако межпроцессорное взаимодействие в компьютерах этого класса
идет намного медленнее, чем происходит локальная обработка данных самими процессорами.
В мультипроцессорах с распределенной памятью (MPP, Massively
Parallel Processor) каждый процессор имеет свою оперативную память.
В такой архитектуре процессоры взаимодействуют через соединительную
сеть (рис. 1.9), принимая и передавая сообщения, и, следовательно, отсутствуют проблемы согласованности кэша и памяти. Соединительная сеть
может быть организована в гиперкуб или матричную структуру и является
высокоскоростным путем связи между процессорами.
22

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

Наибольшее распространение в рамках MPP-архитектуры получили
высокопроизводительные кластерные системы – все лидеры top500 являются представителями именно такой технологии.
Связующая сеть
Оперативная
память

Оперативная
память

Кэш

Кэш

ЦПУ

ЦПУ

Рис. 1.9. Структура ЭВМ с распределенной памятью

Современный высокопроизводительный кластер обычно строится
следующим образом. Процессорные элементы (вычислительные узлы) состоят из одного или нескольких, чаще всего многоядерных, процессоров
с общей памятью. Узлы между собой соединены специальной коммуникационной сетью с малой латентностью и высокой пропускной способностью. Это может быть коммутируемая последовательная шина или кольцо,
одно- или многомерные торы и пр. (наиболее распространены технологии
InfiniBand, SCI, Mirenet, Gigabit Ethernet). Часто сеть строится на основе
специальных микросхем, включающих модуль прямого доступа к памяти,
процессор передачи данных и управления, высокоскоростной маршрутизатор, создающий несколько высокоскоростных соединений с соседями. Для
связи с управляющим узлом (или узлами), управления и мониторинга системы вычислительные узлы объединяются вспомогательной сетью, которая может быть более медленной и дешевой. Узлы могут быть снабжены
собственной дисковой памятью, возможно, с высокоскоростными подсистемами ввода-вывода, при этом дополнительно к системе добавляются
серверы доступа и файловый сервер с дисковыми массивами.
В настоящее время получили распространение термины, связанные
с префиксом «блейд» (блейд-модули в суперкомпьютерах, блейд-сервера,
блейд-системы и пр.). Термин «блейд» происходит от английского «лезвие»
и прямо связан с семантикой – это не новая технология, а просто способ
компактной организации суперкомпьютера1 или стойки серверов. Достига1

Принята специальная единица измерения высоты оборудования, размещаемого
в стойке (шкафу): 1U (unit) равен 4,445 см, или 1,75 дюйма. В стандартной 19-дюймовой
стойке можно разместить максимально 42 сервера, что может предполагать до 140 кабелей. Блейд-технология позволяет в настоящее время довести количество плат в стойке до 100 и уменьшить количество кабелей до трех.
23

Г л а в а 1. Обзор области параллельных вычислений

ется экономия пространства в основном путем исключения из самой платы
различных вспомогательных (не относящихся непосредственно к вычислениям) устройств: питание, охлаждение, сетевые подключения, подключения жёстких дисков, межсерверные соединенения и управление выносятся
за пределы платы и обслуживают стойку серверов.
4. Гибридные архитектуры. Наиболее общая комбинация – машина
с поддержкой распределенной разделяемой памяти, т. е. распределенной
реализации абстракции разделяемой памяти.
В конце параграфа кратко обсудим высокопроизводительные технологии, представленные в мире, которые к архитектуре суперкомпьютера
отнести нельзя. Одним из представителей систем с распределенной памятью является кластер рабочих станций, объединенных коммуникационной
сетью, желательно, но вовсе не обязательно, высокоскоросной. Такие кластеры обычно рассматривают как относительно дешевую альтернативу
крайне дорогим суперкомпьютерам. Проект Beowolf1 предполагал технологию построения кластера из широко распространённого аппаратного
обеспечения, работающего под управлением свободно распространяемой
операционной системы.
Глобализация кластерной технологии приводит к понятию метакомпьютинга. Интернет очень напоминает кластерную архитектуру: множество
узлов с собственными процессорами, оперативной и внешней памятью,
устройствами ввода-вывода, соединенные друг с другом коммутационным
оборудованием и линиями передачи данных. Энтузиастами метакомпьютинга решаются задачи по поиску все новых простых чисел, повышению
точности значения числа , обнаружению сигналов внеземных цивилизаций и даже поиску формулы лекарства от СПИДа.
В настоящее время в научном сообществе распространена технология грид2 – согласованная, открытая и стандартизованная компьютерная
среда, которая обеспечивает гибкое, безопасное, скоординированное разделение вычислительных ресурсов и ресурсов хранения информации
в рамках некоторой сети. В рамках грид-проектов предполагается объединять и распределять вычислительные ресурсы не энтузиастов-одиночек,
а суперкомпьютерных центров. Получив закрытый ключ и сертификат для
вхождения в грид-инфраструктуру, пользователь может запускать со своего рабочего компьютера трудоемкую задачу, не имея представления
о том, в каких вычислительных центрах она решается и где хранятся полу1

Название происходит от одиного из Linux-кластеров в научно-космическом
центре NASA. Начало проекта – 1994 год.
2
Идеи грид-системы были собраны и объединены Иэном Фостером, Карлом
Кессельманом и Стивом Тики. В настоящее время Карл Кессельман является директором
Центра грид-технологий Института информатики Университета Южной Калифорнии.
24

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

ченные данные. Грид-системы гарантируют безопасность и защиту информации. Ярким примером является научно-техническая программа
«СКИФ-ГРИД», выполняемая совместно Россией и Белоруссией. Цель
программы – «освоение и адаптация передовых наукоемких технологий на
перспективных суперкомпьютерных платформах, оптимизация суперкомпьютерных конфигураций семейства “СКИФ”, ориентированных на построение на их основе Грид-компьютерных сетей…»1.
Технология облачных вычислений – это еще один современный подход
к обеспечению сетевого доступа по требованию к общему пулу конфигурируемых вычислительных ресурсов. В отличие от грид-технологий, связанных, прежде всего, с научными интересами, облачные сервисы обслуживают широкий круг потребителей вычислительных услуг от коммерческих
или государственных организаций до индивидуальных пользователей.

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

Многопоточные:
ОС, многие многооконные приложения и пр.

Распределенные:
файл-сервер, СУБД,
Web и пр.
Параллельные:
научные, графика и
обработка изображений,
задачи оптимизации и пр.

Рис. 1.10. Классы приложений

1. Многопоточные приложения. Термин многопоточный обычно
означает, что программа содержит больше процессов/потоков2, чем суще1

URL: http://skif-grid.botik.ru/.
Мы оставим за рамками обсуждения различия между терминами «процесс»
и «поток». Здесь и далее в этой главе эти термины считаются взаимозаменяемыми. Затем под процессом понимается выполняемая в системе программа, решающая некоторую задачу, владеющая и/или претендующая на некоторые ресурсы системы. Ресурсы
процессу могут выделяться как в безраздельное пользование (например, адресное пространство), так и разделяться с другими процессами (например, процессор). Поток –
2

25

Г л а в а 1. Обзор области параллельных вычислений

ствует процессоров для их выполнения. В результате некоторые процессы
приложения выполняются по очереди.
Примерами многопоточных программ являются операционные системы (ОС), системы разделения времени, системы реального времени,
многие оконные приложения. Эти системы разрабатываются многопоточными, поскольку составляющие их задачи могут планироваться и выполняться независимо. Например, в MS Word один поток отвечает за проверку
орфографии, другой – за пересчет ссылок и полей, третий – за ввод данных
и т. д.
Основной проблемой реализации таких программ является борьба за
разделяемые ресурсы, например, процессор, память, устройства вводавывода и другие.
2. Распределенные системы. В таких системах компоненты программ выполняются на разных вычислительных машинах, связанных
сетью, возможно, работающих под разными ОС. Основным способом
взаимодействия процессов в распределенных системах является обмен
сообщениями. Спецификой процессов является их относительная независимость и возможность обслуживания одним процессом различных клиентов. Подобное обслуживание обычно происходит по поступающим
запросам.
Примерами распределенных систем могут служить файловые серверы
в сети, СУБД, веб-серверы в сети Интернет, отказоустойчивые системы,
которые продолжают работать независимо от сбоев в компонентах.
Распределенные системы необходимы для организации доступа
к территориально удаленным данным, интеграции и управления данными,
распределенными по своей сути, повышения надежности. Как правило,
такие системы основаны на технологии клиент-сервер, а их компоненты
сами являются многопоточными программами.
Основной проблемой реализации распределенных программ является
обмен информацией о состоянии разделяемого ресурса.
3. Параллельные (согласованные) вычисления. Цель таких приложений – совместно и быстро решить данную задачу, причем допустимы
как многопоточный, так и распределенный подходы.
Примерами согласованных параллельных вычислений являются различные научные вычисления (например, численные модели математической физики), графика и обработка изображений (включая создание спецэффектов в кино), крупные комбинаторные и оптимизационные задачи,
интеллектуальный анализ данных.
это «облегченный» процесс, т. е. потоки имеют собственные счетчики команд, стеки
выполнения, но работают в общем адресном пространстве.
26

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

Параллельные программы требуют больших вычислительных мощностей. Обычно число процессов в параллельных программах равно числу
процессоров (ядер).
В таксономии Флинна уже прослеживается два основных подхода
к построению параллельных приложений.
1. Параллелизм по данным основан на выполнении процессами
(потоками) одних и тех же действий над собственной частью данных.
В этом случае программист задает опции векторной или параллельной оптимизации, директивы параллельной компиляции, а собственно векторизацию или распараллеливание выполняет транслятор. Существуют также
специализированные языки параллельных вычислений. Параллелизм по
данным реализует SIMD-технологию. Для такого подхода характерно, что
обработкой данных управляет одна программа, но процессы слабо синхронизированы (каждый процесс выполняет один код, но нет гарантии, что
в заданный момент времени все процессы выполняют одну и ту же инструкцию).
2. Параллелизм по задачам предусматривает разбиение вычислительной задачи на несколько самостоятельных подзадач. Компьютер при
этом представляет MIMD-машину. Для каждой подзадачи, как правило,
пишется своя программа. Подзадачи в ходе работы обмениваются данными, а также согласуют свою работу. При программировании контролируется распределение данных между процессами/потоками и вычислительной
нагрузки между процессорами, что повышает трудоемкость разработки
и отладки программы.
Как правило, выбор метода распараллеливания основан на свойствах
самой задачи или выбранного алгоритма ее решения. Так, для сеточных
вычислений характерен параллелизм по данным, однако можно выбрать
такой алгоритм решения (например, метод прогонки для решения СЛАУ
с трехдиагональной матрицей), который испортит весь параллелизм исходной задачи. Задача обработки изображения может обладать внутренним
параллелизмом по задачам, а каждая задача – параллелизмом по данным.
Процесс проектирования параллельных приложений обязательно
включает следующие три составляющие: декомпозиция – связь – синхронизация (ДСС).
Декомпозиция – это процесс разбиения прикладной задачи на части.
Иногда декомпозиция естественным образом следует из природы самой
задачи, иногда она определяется разработчиком.
Можно проводить разбиение на основе логики действий (например,
сортировка, поиск, ввод-вывод, вычисление), на основе логики ресурсов
(например, работа с файлом, принтером, базой данных), на основе логики
данных (например, обработка массива по строкам, столбцам или блокам).
27

Г л а в а 1. Обзор области параллельных вычислений

Чем меньше размер подзадач, полученных на этом этапе, и чем
больше их количество, тем более гибким получается параллельный алгоритм и тем легче обеспечить равномерную загрузку процессоров. При необходимости всегда можно провести обратную операцию – укрупнение.
Параллелизм можно организовать на уровне команд (рис. 1.11). Этот
вид параллелизма обычно обеспечивается компилятором, ОС и внутренней
архитектурой процессора. Обсуждение этих вопросов выходит за рамки
нашего пособия.
E = (A + B) / (C * D)
E1 = A + B

E2 = C * D

Параллельное выполнение
Синхронизация

E = E1 / E2
Рис. 1.11. Синхронизация на уровне команд

Следующий уровень параллелизма в итеративных программах –
цикл. Не всякий цикл можно выполнять параллельно [9]. Решение об этом
принимает, как правило, программист, например, с помощью директив
компиляции.
Дальнейшее использование параллелизма проводится на уровне подпрограмм (функций). Решение подзадач можно оформить отдельными
функциями, выполнение которых распределяется по потокам. При наличии
нескольких процессоров выполнение ряда потоков может протекать параллельно. Этот уровень требует тщательного проектирования синхронизации
и взаимодействия, которые, в свою очередь, во многом определяются
архитектурой вычислительной системы.
Как параллелизм этого же уровня можно представить и некоторую
разновидность асинхронного выполнения SIMD-программ, при котором
один и тот же код программы запускается на разных вычислительных узлах
среды с распределенной памятью, поддерживающей обмен сообщениями.
В данном учебном пособии в основном обсуждается создание приложений, поддерживающих параллелизм уровня циклов и подпрограмм.
Дальнейшее укрупнение уровня параллелизма – объекты и приложения – характерно для распределенных приложений, которые в нашем
уебном пособии не рассматриваются.
Планирование связей, или коммуникаций, между частями приложения – следующий этап проектирования. Методы связывания, как правило,
определяются архитектурой вычислительной системы (разделяемые переменные, каналы, передача сообщений и т. д.), а их конкретная программ28

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

ная реализация диктуется выбранным инструментом программирования –
языком или библиотекой.
Поскольку множество потоков программы работают в рамках одной
задачи, то их функционирование необходимо координировать, поэтому
важным моментом проектирования является синхронизация. Следует предусмотреть, какие задачи могут выполняться параллельно, а какие –
последовательно и в каком порядке; если некоторые части программы закончили работу раньше, то следует ли им заняться выполнением других
заданий. Необходимо учесть и то, как разные подзадачи «узнают», что
решение достигнуто.
При некорректной организации связей и синхронизации обычно
появляются следующие проблемы.
«Гонка данных» возникает из-за того, что несколько процессов одновременно пытаются обновить и использовать общие данные. Проблема
наиболее очевидна, если данные одновременно перезаписываются. Однако
«гонка данных» часто возникает и в случае, когда один процесс неоднократно использует данные, обновляемые другим процессом. При отсутствии согласованности задача-потребитель может использовать устаревшие
данные (при опережающем чтении) или утерять данные (производитель
может при записи затереть еще не использованные данные).
Некорректное планирование последовательности выполнения задач
приводит и к другой проблеме – «живой блокировке», при которой задача
может никогда не получить возможность выполниться. Также эту проблему иногда называют «ситуацией бесконечной отсрочки».
«Мертвая (взаимная) блокировка» – еще одна ловушка, связанная
с ожиданием. В простейшем случае взаимная блокировка возникает, если
«задача 1» ждет данных (сигнала) от «задачи 2», которая, в свою очередь,
ожидает данных (сигнала) от «задачи 1». В общем случае ситуация может
оказаться еще более запутанной.
Все эти проблемы должны быть выявлены и разрешены на стадии
проектирования параллельного приложения.

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

Г л а в а 1. Обзор области параллельных вычислений

Ниже дан краткий обзор языков параллельного программирования,
библиотек и систем разработки параллельных программ [16, 28, 43–44,
48, 64].
Библиотека PTHREAD разработана в 90-х годах прошлого века под
эгидой организации POSIX (Portable Operating System Interface – интерфейс
переносимой ОС). Она определяет стандартный набор функций языка Си
для многопоточного программирования. В распоряжении программиста
оказывается большой набор функций создания и управления потоками
и набором их атрибутов, а также различные методы синхронизации потоков (блокировки, мьютексы, семафоры, барьеры).
Язык программирования Java объединяет возможности интерпретируемых, объектно ориентируемых и параллельных языков, добавляя
несколько новых. Он поддерживает как многопоточное, так и распределенное программирование.
Одним из наиболее популярных средств программирования многопроцессорных компьютеров с общей памятью в настоящее время является
технология OpenMP. При ее использовании за основу берется последовательная программа. Для создания ее параллельной версии применяется набор директив, процедур и переменных окружения. Технология OpenMP
представляет программу как цепочку параллельных и последовательных
областей, используя схему FORK/JOINT для поддержки параллелизма. Все
порожденные нити исполняют один и тот же код параллельной области.
Переменные программы разделяются на общие (SHARED) и локальные
(PRIVATE). Стандарт OpenMP разработан для языков Fortran, Си, C++.
Реализация стандарта доступна как для UNIX-платформ, так и в среде
Windows.
Язык программирования CSP (Communicating Sequential Processes –
взаимодействующие последовательные процессы) впервые был описан
в 1978 году Тони Хоаром. Его первое описание содержало идеи синхронной передачи сообщений и защищенного взаимодействия. Язык CSP повлиял на разработку таких языков программирования, как Occam и Ada.
Его последняя версия стала формальным языком для моделирования
и анализа поведения параллельных систем.
Язык программирования Occam начал разрабатываться в середине
1980-х годов для транспьютеров, являясь, по сути, их машинным языком.
Язык содержит очень малое число механизмов, что и определило его
название (от выражения «бритва Оккама»). Базовыми элементами языка
являются декларации и три примитивных процесса (присваивание, ввод
и вывод), которые объединяются в обычные процессы с помощью трех
типов конструкторов (последовательный, параллельный и защищенного
взаимодействия).
30

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

Система программирования Linda разработана в середине 1980-х годов
в Йельском университете США. В рамках системы параллельная программа – это множество параллельных процессов, каждый из которых работает
как последовательная программа. Все процессы имеют доступ к общей
памяти, единицей которой является кортеж – упорядоченная последовательность значений. Процессы в системе Linda никогда не взаимодействуют
друг с другом явно, их общение идет всегда опосредованно, через пространство кортежей, которое можно считать виртуальной ассоциативной памятью.
По замыслу создателей Linda, для того чтобы любой последовательный
язык стал средством параллельного программирования, достаточно добавить в него только четыре функции: извлечь/прочитать элемент из пространства кортежей, поместить элемент в пространство кортежей, вычисляя его последовательно или параллельно. Несколько языков программирования, включая Си и FORTRAN, были дополнены примитивами Linda.
При использовании библиотеки MPI (Message Passing Interface – интерфейс передачи сообщений) процессы распределенной программы записываются на таком последовательном языке, как Си или FORTRAN. Их
взаимодействие или синхронизация задаются с помощью вызова процедур
библиотеки. Каждый процессор выполняет копию одной и той же программы, использующей функции MPI. Каждый экземпляр программы может определить собственный идентификатор и, следовательно, выполнять
действия, отличные от других.
Система разработки и выполнения параллельных программ PVM
(Parallel Virtual Machine – параллельная виртуальная машина) разработана
в США в 90-х годах прошлого века. Она позволяет объединить разнородный
набор компьютеров, связанных сетью в общий вычислительный ресурс.
Единицей параллелизма в PVM является задача, состояние которой изменяется (вычисления, обмен данными и пр.). Выполнение PVM-программы
порождает несколько процессов, которые взаимодействуют посредством
обмена сообщениями. Система поддерживает языки Си, FORTAN, Perl, Java
и даже математический пакет Matlab.
HPF (High Performance FORTRAN – высокопроизводительный
FORTRAN) – это язык, параллельный по данным. Он является расширением языка FORTRAN-90 для разработки параллельных программ. Основные
компоненты HPF – параллельное по данным присваивание массивов, директивы компилятора для управления распределением данных и операторы
записи и синхронизации параллельных циклов.
Система разработки и выполнения параллельных программ DVM
разработана в ИПМ им. М. В. Келдыша РАН как расширение языков Си
и FORTRAN. Последовательная программа, написанная на одном из этих
языков, дополняется директивами, оформленными как параметры макроса,
31

Г л а в а 1. Обзор области параллельных вычислений

который в последовательной программе расширяется в пустую строку, что
позволяет поддерживать одну программу для последовательной и параллельной версий. DVM-система реализует параллелизм по данным для компьютеров с распределенной, общей памятью, а также гибридной архитектуры, при которой каждый узел распределенной вычислительной системы
является многоядерным (многопроцессорным), расширенным графическими процессорами. Директивы DVM-системы управляют распределением
данных, вычислений и удаленным доступом к данным. Среда дополнена
инструментами запуска, отладки и анализа производительности.
Языки, параллельные по данным (C*, ZPL, NESL), поддерживают
стиль программирования, в котором все процессы выполняют один и тот
же код на разных частях данных. Они значительно упрощают обработку
массивов и матриц. Несмотря на явное взаимодействие процессов, в таких
языках синхронизация часто поддерживается неявно, после каждого оператора. Большинство языков, параллельных по данным, создавалось под
определенную архитектуру ВС (например, C* тесно связан с архитектурой
CM-1, первой SIMD Connection Machine).
Объектно ориентированные системы, как правило, поддерживают
многопоточность. Например, библиотека C Qt позволяет осуществлять
управление потоками добавлением объектов класса QThread.
Особо следует отметить объектно ориентированные языки, например
C#, Distributed Java, поддерживающие CORBA (Common Object Request
Broker Architecture) – стандарт для определения отношений, взаимодействий и связей между распределенными объектами.
В языках упреждающих вычислений параллелизм реализован с помощью параллельного выполнения вычислений еще до того, как их результат потребуется для продолжения выполнения программы. Таковым,
например, является Multilisp – параллельная версия известного декларативного языка Lisp.
Еще одним неимперативным языком для параллельного программирования является разработка компании Ericsson – функциональный язык
Erlang. Изначально сотрудники лаборатории Ericsson Computer Science
Laboratory реализовали возможности параллелизма логического языка
Prolog. Перестав быть диалектом Prolog’а в 1990 году, разработка получила
название1 и собственный синтаксис. В настоящее время язык Erlang,
построенный на идеологии передачи сообщений, считается языком многопоточного и распределенного программирования высокой надежности.
1

По фамилии датского математика Агнера Крарупа Эрланга (Agner Krarup
Erlang, 1878–1929), широко известного своими исследованиями в сфере телекоммуникаций. В честь А. Эрланга названа также мера телекоммуникационного трафика в телефонии.
32

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

Центральным понятием Erlang является процесс, который реализован
средствами языка и не требует соответствующего функционала ОС.
В Erlang процессы очень легковесны, сравнимы с вызовом функций в императивных языках, поэтому работающие программы без труда могут запускать их тысячами и даже миллионами1. Язык содержит три основные
примитивные операции: создание процесса, отправка сообщения и получение процессом сообщения из собственного почтового ящика. Являясь
функциональным языком, Erlang не содержит операции присваивания, что
позволяет избавиться от необходимости применения сложных механизмов
синхронизации процессов в многопоточном программировании (семафоров, мьютексов, событий).
Использование графических процессоров привело к созданию многочисленных графических API (OpenGL, Direct3D) для обработки данных
на GPU, которые, по сути, имеют массово-параллельную архитектуру.
Программа обработки изображения пишется на двух языках – на традиционном, например С++, и на языке для шейдеров2. Шейдеры являются, в некотором смысле параллельными программами, но поскольку параллельная
обработка точек не требует взаимодействия нитей, то API не предоставляет никакого механизма синхронизации и коллективных операций.
В настоящее время получила распространение предложенная компанией Nvidia технология CUDA (Compute Unified Device Architecture), которая вышла за рамки GAPI и предназначается для программирования
массивно-параллельных вычислительных устройств (GPU компании
Nvidia, начиная с серии GeForce8, семейства Tesla и пр.). Основная идея
технологии заключается в том, что GPU является массивно-параллельным
«сопроцессором» к CPU, обладающим собственной памятью. Последовательная часть программы, написанной на CUDA, выполняется на CPU,
а параллельная – на GPU в виде набора одновременно выполняющихся нитей.
Нити GPU обладают крайне небольшой стоимостью создания, управления
и уничтожения (контекст нити минимален, все регистры распределены заранее). Реализация синхронизации нитей является некоторым компромиссом между необходимостью взаимодействия нитей и стоимостью такого
взаимодействия. Взаимодействовать могут только нити одного блока сетки
нитей путем либо разделения памяти, либо барьерной синхронизацией.
Параллельность «приобрели» не только языки программирования, но
и системы инженерного анализа, предназначенные для 2D- и 3D-моделиро1

Существуют эксперименты, демонстрирующие сотни тысяч созданных
и уничтоженных процессов в секунду (http://www.lshift.net/blog/2006/09/10/erlangprocesses-vs-java-threads).
2
Шейдер – подпрограмма создания эффектов подсветки поверхности объекта,
построения теней, текстур и прочих графических спецэффектов.
33

Г л а в а 1. Обзор области параллельных вычислений

вания сложных (в том числе турбулентных) течений жидкости и газа, деформаций твердых тел, многофазных явлений. Как правило, такие системы
включают все этапы численного моделирования: построение и адаптацию
сеток, визуализацию постановки дифференциальной задачи и обработку
результатов, выбор параметров численных методов. Например, популярный пакет конечноэлементного решения стационарных и нестационарных
пространственных задач механики деформируемого твёрдого тела и механики конструкций ANSYS выпускается с возможностью автоматического
распараллеливания расчетов. Другой пакет компании ANSYS (поглотившей
конкурента) – ANSYS FLUENT – предназначен для моделирования сложных течений жидкостей и газов с широким диапазоном свойств. Интересна
также российская разработка – программный комплекс по вычислительной
гидродинамике FlowVision.
Приведенный краткий обзор языков, библиотек и систем параллельного программирования далеко не полон. С одной стороны, это дает основание надеяться, что для решения любой задачи найдется эффективный
языковый инструментарий, а с другой стороны, свидетельствует об отсутствии единственного оптимального решения.
Параллельное программирование – это та область программирования, которая еще долго будет искусством, а не ремеслом.

1.5. Парадигмы параллельных приложений
Существует ряд схем взаимодействия самостоятельных частей параллельного приложения. Кратко опишем основные.
Итеративный параллелизм используется для реализации параллелизма в итеративной программе (чаще всего в циклах). Такой параллелизм
характерен для распараллеливания по данным в согласованных параллельных вычислениях.
Рекурсивный параллелизм используется в программах с одной или
несколькими рекурсивными процедурами, вызов которых независим. Каждый рекурсивный вызов порождает один или несколько новых процессов,
которые независимо работают над решением задачи. В рамках такой парадигмы часто реализуются технологии «разделяй и властвуй» или «перебор
с возвращением».
Итеративный и рекурсивный параллелизм основан на приемах,
известных в последовательном программировании. Следующие схемы
взаимодействия характерны именно для параллельных программ.
«Производители и потребители» – модель взаимодействия неравноправных процессов по поводу общих данных. Одни процессы «производят»
34

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

данные, другие – их «потребляют». Часто такие процессы организуются
в конвейер, через который проходит информация. Каждый процесс конвейера потребляет выход своего предшественника и производит входные данные для своего последователя. Другой распространенный способ организации потоков – древовидная структура, на ней основан, в частности,
принцип дихотомии.
«Клиенты и серверы» – наиболее распространенная модель взаимодействия процессов в распределенных системах. Клиентский процесс запрашивает (возможно, неоднократно) данные у сервера и ожидает ответа,
затем использует полученные данные по своему усмотрению. Серверный
процесс ожидает запроса от клиента, далее в соответствии с поступившим
запросом обрабатывает данные и возвращает запросившему их процессуклиенту. Таким образом, в отличие от предыдущего случая, между клиентом
и сервером необходимо установить двустороннюю связь. Сервер может
быть реализован как одиночный процесс, обслуживающий одновременно
несколько клиентских процессов. Сервер может быть многопоточной программой, каждый поток которой обслуживает своего клиента. Если клиент
и сервер выполняются на одном компьютере, то они представляют собой
параллельное программное обобщение процедур: сервер исполняет роль
процедуры, а клиент ее вызывает. Однако если коды клиента и сервера
разнесены в пространстве, то для синхронизации используются специальные технологии, такие как удаленный вызов процедур или рандеву.
«Управляющий и рабочие» – модель организации вычислений, при
которой существует поток, координирующий работу всех остальных потоков. Как правило, управляющий поток распределяет данные, собирает
и анализирует результаты. Эта парадигма часто применяется в задачах
оптимизации и статистической обработки информации, при обработке изображений и других научных вычислениях с итеративными алгоритмами.
«Взаимодействующие равные» – модель, в которой исключен не занимающийся непосредственными вычислениями управляющий поток.
Распределение работ в таком приложении либо фиксировано заранее, либо
динамически определяется во время выполнения. Одним из распространенных способов динамического распределения работ при создании программ для ВС с общей памятью является портфель задач. Портфель задач,
как правило, реализуется с помощью разделяемой переменной, доступ
к которой в один момент времени имеет только один процесс. Если же память ВС распределенная, то такая схема распределения работ превращается в
схему «управляющий – рабочий», поскольку портфель задач оформляется
отдельным процессом. Основными примерами в этой области являются
научные вычисления с итеративными алгоритмами и системы, требующие
децентрализованного принятия решений.
35

Г л а в а 1. Обзор области параллельных вычислений

Нотация для определения параллельных вычислений
Множество чтения операции – это множество переменных, которые
в ходе операции читаются, но не изменяются. Множество записи операции – это множество переменных, которые в ходе операции изменяются
(и, возможно, читаются).
Две операции называются независимыми, если их множества записи
не пересекаются.
Две операции могут выполняться параллельно, если они независимы,
т. е. процессы всегда могут безопасно читать переменные, которые не изменяются. Однако двум процессам небезопасно выполнять запись в общую
переменную или одному процессу читать переменную, которую изменяет
другой процесс.
Для иллюстрации обсуждаемых здесь и далее алгоритмов введем
общую нотацию, подобную рассмотренной в [48]. Особенности ее конкретных реализаций с помощью функций WinAPI, технологии OpenMP
и библиотеки MPI описаны в соответствующих главах.
Для определения параллельного выполнения нескольких различных
потоков команд примем следующую нотацию (оператор par – от «parallel»):
par
{ … ;}
\\
{ … ;}
endpar

// группа операторов 1
// разделитель различных ветвей оператора
// группа операторов 2

Для независимого выполнения тела цикла для каждого значения
счетчика оператор par будем записывать в следующем виде:
par for (i=0;i