Параллельные вычислительные системы

Министерство науки и высшего образования Российской Федерации
Сибирский федеральный университет

ПАРАЛЛЕЛЬНЫЕ  
ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

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

Красноярск 
СФУ 
2019

УДК 004.272(07)
ББК 32.971.35-02я73
П180

Р е ц е н з е н т ы: 
М. Н. Фаворская, доктор технических наук, профессор, зав. кафедрой информатики и вычислительной техники ФГБОУ ВО «Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева»;
В. А. Хабаров, кандидат технических наук, ведущий инженер-конструктор отдела систем управления АО «НПП Радиосвязь»

П180 
 
Параллельные вычислительные системы : учеб. пособие / Н. Ю. Сиротинина, О. В. Непомнящий, К. В. Коршун, 
В. С. Васильев. – Красноярск : Сиб. федер. ун-т, 2019. – 178 c.
ISBN 978-5-7638-4180-0

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

Электронный вариант издания см.: 
УДК 004.272(07)

http://catalog.sfu-kras.ru 
ББК 32.971.35-02я73

ISBN 978-5-7638-4180-0 
© Сибирский федеральный
университет, 2019

ОГЛАВЛЕНИЕ

Введение .......................................................................................................6

1. Понятие параллелизма. Архитектуры параллельных  
вычислительных систем...........................................................................9
1.1. Классификация Флинна для параллельных  
вычислительных систем .................................................................... 17
1.2. Производительность вычислительных систем................................ 25
1.3. Суперкомпьютеры .............................................................................. 26
Контрольные вопросы и задания ............................................................. 30

2. Общие вопросы организации вычислительных процессов  
и программирования параллельных вычислительных систем .... 32
2.1. Общие проблемы разработки прикладного параллельного  
программного обеспечения ............................................................... 32
2.1.1. Психологическая проблема .................................................... 32
2.1.2. Проблема верификации и отладки ППО ............................... 33
2.1.3. Проблемы наращиваемости и переносимости ..................... 36
2.2. Закон Амдала ...................................................................................... 37
2.3. Параллелизм по данным и функциональный параллелизм ........... 40
2.4. Подходы к созданию параллельного прикладного  
программного обеспечения ............................................................... 41
2.4.1. Автоматическое распараллеливание ..................................... 41
2.4.2. Явное описание параллелизма ............................................... 42
2.4.3. Сочетание автоматического распараллеливания  
и явного описания параллелизма .......................................... 44
Контрольные вопросы и задания ............................................................. 45

3. Мультипроцессорные вычислительные системы:  
организация и программирование ...................................................... 47
3.1. Представление программы в OpenMP ............................................. 47
3.2. Функции OpenMP  .............................................................................. 49
3.2.1. Переменные окружения OpenMP и функции  
работы с ними ......................................................................... 50
3.2.2. Функции работы с переменными времени ........................... 55
3.3. Директивы OpenMP ........................................................................... 56
3.3.1. Создание параллельной секции – директива parallel ........... 57

Оглавление

3.3.2. Реализация функционального параллелизма  
в OpenMP – директива parallel sections ................................. 59
3.4. Параллельное исполнение цикла – директива for........................... 60
3.4.1. Статическое планирование исполнения цикла..................... 65
3.4.2. Динамическое планирование исполнения цикла ................. 66
3.4.3. Управляемое планирование исполнения цикла.................... 68
3.4.4. Планирование исполнения цикла  
во время работы программы .................................................. 70
3.5. Разделяемые и локальные переменные OpenMP ............................ 71
3.6. Работа с разделяемыми ресурсами в OpenMP ................................. 76
3.6.1. Организация критической секции – директива critical ........ 79
3.6.2. Организация взаимного исключения при выполнении  
элементарной операции – директива atomic ........................ 80
3.6.3. Однократное выполнение блока кода – директива single .... 81
3.6.4. Выполнение блока кода  
мастер-процессом – директива master .................................. 81
3.7. Неявная и явная синхронизация потоков  
в OpenMP – директива barrier ............................................................ 82
3.8. Рекомендации: когда следует использовать OpenMP ..................... 83
Контрольные вопросы и задания ............................................................. 84

4. Кластерные системы и системы с массовым  
параллелизмом: организация и программирование ........................ 86
4.1. Общие сведения о стандарте MPI .................................................... 86
4.2. Основные функции библиотеки MPI ............................................... 89
4.2.1. Инициализация и завершение параллельной части  
приложения .............................................................................. 89
4.2.2. Определение общего числа параллельных процессов  
и номера процесса в группе ................................................... 90
4.2.3. Работа с таймером ................................................................... 91
4.3. Функции передачи и приема сообщений между процессами ........ 91
4.3.1. Блокирующие функции обмена точка-точка ........................ 92
4.3.2. Буферизованная передача ..................................................... 100
4.3.3. Неблокирующие (асинхронные) функции обмена MPI .... 102
4.4. Коллективные функции ................................................................... 105
4.4.1. Точки синхронизации (барьеры) .......................................... 106
4.4.2. Функции коллективного обмена данными ......................... 108
4.4.3. Коллективные операции свертки (редукции) ..................... 116

Оглавление

4.5. Функции для работы с группами процессов  
и коммуникаторами .......................................................................... 119
4.6. Функции для работы со структурами данных ............................... 120
4.7. Функции формирования топологии процессов ............................. 121
4.8. Рекомендации: когда следует использовать MPI? ......................... 122
Контрольные вопросы и задания ........................................................... 123

Практические работы  ......................................................................... 125
Тематические практические работы к разделу OpenMP ..................... 126
Тематические практические работы к разделу MPI ............................ 131
Сквозной мини-проект ........................................................................... 141
Пример выполнения работы .................................................................. 160

Заключение ............................................................................................. 171
Список литературы .............................................................................. 172

ВВЕДЕНИЕ

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

Введение

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

Введение

данных, базовое представление об архитектуре и организации вычислительной машины.
Материал курса далее будет востребован в дисциплинах «Микропроцессорные системы», «Программируемые логические интегральные 
схемы», может оказаться полезным при выполнении выпускной квалификационной работы и при дальнейшем обучении в магистратуре. 
Пособие может использоваться в качестве основной и дополнительной 
литературы для таких дисциплин, как «Параллельное программирование», «Современные вычислительные системы», «Гибридные вычислительные системы» и пр. 

1. ПОНЯТИЕ ПАРАЛЛЕЛИЗМА. АРХИТЕКТУРЫ 
ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Практически в любом учебнике или научной статье, посвященной 
вычислительной технике, можно встретить слова «интенсивно развивающаяся область», «постоянное совершенствование вычислительной 
техники» и подобные. Как правило, основной характеристикой вычислительной техники, свидетельствующей о ее развитии, считается производительность современных вычислительных систем. Схожий смысл 
имеют понятия: быстродействие, вычислительная мощность и пр.
Производительность ЭВМ – характеристика, описывающая скорость выполнения вычислений [1].
Если рассмотреть динамику роста производительности электронных вычислительных машин, можно отметить следующую закономерность: скорость выполнения арифметических операций возрастает приблизительно в 10 раз за каждые 5 лет [2]. За счет чего это происходит? 
Первый вариант ответа, который напрашивается сам собой: за 
счет повышения быстродействия элементной базы.
Действительно, в первом поколении вычислительных машин в качестве коммутирующих элементов использовались электронные лампы 
с временем задержки на вентиле порядка 1 мкс. В начале 60-х г. ХХ в. 
в машинах второго поколения они были заменены на дискретные германиевые транзисторы с временем задержки порядка 0.3 мкс. В середине 60-х г. были внедрены биполярные интегральные схемы с малым 
уровнем интеграции с временем задержки около 10 нс на вентиль. К середине 70-х г. время задержки снизилось до 1 нс на вентиль за счет 
совершенствования технологии производства и использования новых 
полупроводниковых материалов. Таким образом, за период с 1950 по 
1975 г. быстродействие элементов, измеряемое как величина, обратная 
времени задержки вентиля, увеличилась приблизительно в 103 раз. В то 
же время прирост производительности ЭВМ в целом составил 105 раз, 
т. е. на два порядка больше. Объяснить этот разрыв между ростом производительности отдельных компонентов и ростом производительности 
вычислительной системы в целом можно только совершенствованием 
способов организации вычислительных систем.

Параллельные вычислительные системы

Далее, в середине 70-х г. ХХ в. появились электронные компоненты, реализованные с применением технологий метал – окисел – проводник (МОП) и комплиментарной МОП (кМОП). Быстродействие этих 
компонентов почти на порядок ниже, чем у ранее используемых компонентов на базе биполярных транзисторов, но при этом их геометрические размеры существенно меньше. Это позволило разместить на одном 
кристалле интегральной схемы большее число компонентов, а значит, 
воплотить более сложные и ресурсоемкие решения по организации ВС. 
В настоящее время продолжается развитие элементной базы 
кМОП в основном в направлении уменьшения размера компонентов. 
В связи с этим часто упоминается закон Гордона Мура – эмпирическое 
наблюдение, сделанное в 1965 г. и уточненное 10 лет спустя, согласно 
которому каждые 2 года количество транзисторов на кристалле интегральной схемы удваивается. В результате повышается быстродействие 
компонентов за счет сокращения времени переходных процессов, а увеличение плотности размещения позволяет уменьшить время распространения электрических сигналов между отдельными компонентами 
интегральной схемы. Это развитие можно охарактеризовать таким параметром, как норма технологического процесса – разрешающая способность литографического оборудования, используемого при производстве интегральных микросхем. На рис. 1 приведен график изменения 
нормы технологического процесса за последние 10 лет. На нем видно, 
что темп развития по этому пути сокращается. Это связано не только 
со сложностями технологии производства, но и с фундаментальными 
физическими ограничениями. Процессы, происходящие в полупроводниках, носят статистический характер. Число атомов, которые формируют полупроводниковый переход, должно составлять несколько сотен. 
Современные технологии вплотную приблизились к этому рубежу, и, 
судя по всему, недалек тот день, когда дальнейшее продвижение в этом 
направлении станет невозможным.
В настоящее время активно ведется работа по поиску новых вариантов элементной базы, отличной от полупроводниковой [2]. Это 
оптические и квантовые схемы, компоненты на основе биотехнологии, 
элементы с использованием явлений сверхпроводимости и т. д. Определенные успехи в этом направлении имеются, однако делать прогнозы пока сложно. И даже если альтернатива будет найдена, переход на 

1. Понятие параллелизма. Архитектуры параллельных вычислительных систем

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

Рис. 1. Динамика изменения нормы технологического процесса

Параллельные вычислительные системы

что позволило снизить непроизводительные временные затраты на обмен информацией (командами, данными) внутри процессора. 
Однако потребности пользователей всегда растут опережающими 
темпами, и следующим шагом, позволившим поднять производительность процессора ценой минимальных дополнительных аппаратных затрат, явилось введение так называемой опережающей выборки. 
Традиционно процесс исполнения команды процессором можно 
было разделить на следующие основные этапы:
• выборка команды;
• дешифрация команды;
• выборка операндов;
• исполнение команды;
• завершение исполнения команды, включающее формирование 
слова состояния, опрос прерываний, формирование адреса следующей 
команды.
Этапы исполнялись последовательно, и каждый этап исполнялся 
своим аппаратным модулем. Таким образом, на каждом этапе исполнения команды работал только один модуль, остальные простаивали. 
Вместе с тем один из принципов фон Неймана, положенный в основу 
архитектуры вычислительных машин, утверждает, что программа хранится в памяти ЭВМ в последовательно расположенных ячейках и естественным порядком исполнения программы является выбор следующей 
команды из следующей ячейки (за исключением команд, нарушающих 
этот порядок – это команды переходов, условного и безусловного, вызова и возврата из подпрограмм и т. д.). 
Опережающая выборка позволяет совместить этапы исполнения 
текущей команды, осуществляемой арифметико-логическим устройством процессора, и выборку следующей команды [3]. Это решение не 
требует добавления новых аппаратных модулей в процессор, а прежде 
всего изменяет порядок работы уже существующих. Такой вариант реорганизации работы процессора можно рассматривать как зачатки конвейера команд. 
Введение опережающей выборки в одном из первых процессоров 
семейства Х86 (Intel 286) позволило поднять его производительность 
среднем на 30 %. Этот результат оказался настолько эффективным, что 
уже в следующем поколении процессоров, 386, был реализован полно

1. Понятие параллелизма. Архитектуры параллельных вычислительных систем

ценный 5-ступенчатый конвейер [4]. Поскольку в конвейерной системе 
на разных этапах обработки находится несколько команд, этот вариант 
организации работы можно рассматривать как одну из форм параллелизма. 
Далее развитие конвейера команд шло в основном по пути увеличения длины конвейера и сокращения времени, требуемого для отдельной фазы исполнения команды. На последних этапах эволюции конвейерных процессоров в процессорных ядрах реализовывались полностью 
или частично несколько конвейеров, в результате чего возникали так 
называемые гипертрейдинговые архитектуры.
Однако конвейер команд представляет собой достаточно сложно управляемую структуру, а разное время исполнения команд разных 
типов, а также неизбежное наличие команд, нарушающих последовательность исполнения программы, привели ко все большей сложности 
управления конвейером. Конвейеризация процессора не видна программисту, управление и оптимизация его работы осуществляется аппаратными средствами. С какого-то момента дальнейшее развитие конвейера 
команд перестало быть эффективным.
Следующим этапом эволюции процессоров стало появление многоядерных процессоров, в котором на одном кристалле располагались 
несколько полноценных процессорных ядер, часто разделяющих общую кэш-память команд и данных [4]. 
Этот вид параллелизма допускает программное управление. Загрузка отдельных ядер процессора может осуществляться как средствами системного программного обеспечения, так и прикладными 
программами, часто позволяющими достичь высокой эффективности 
в использовании вычислительных ресурсов [5].
Если рассматривать дальнейшее развитие вычислительной техники на примере персональных компьютеров, то одним из важных этапов стало выделение задачи обработки графической информации. Эта 
задача имеет ряд специфических особенностей, которые затрудняли ее 
решение средствами процессоров со стандартной архитектурой. Для 
решения этой задачи в состав вычислительных систем стали вводиться 
графические сопроцессоры (GPU). Они содержат большое количество 
специализированных процессорных ядер, которые позволяют выполнять обработку графической информации с высоким параллелизмом [6].