Параллельные вычислительные системы
Параллельные Вычислительные Системы: Обзор и Практическое Руководство
В современном мире вычислительная техника развивается стремительно, и ключевым фактором этого прогресса является повышение производительности вычислительных систем. Это достигается, в первую очередь, за счет развития архитектур в направлении параллелизма. Данное учебное пособие, предназначенное для бакалавров направления "Информатика и вычислительная техника", представляет собой всесторонний обзор параллельных вычислительных систем, их архитектур, принципов организации и программирования.
Архитектуры Параллельных Вычислительных Систем
Книга начинается с введения в понятие параллелизма и классификации параллельных вычислительных систем (ПВС). Рассматривается классификация Флинна, основанная на потоках команд и данных, выделяющая четыре основных класса: SISD, SIMD, MISD и MIMD. Особое внимание уделяется классу MIMD, который является наиболее распространенным в современных системах. Далее следует детальное рассмотрение архитектур с общей и распределенной памятью, включая мультипроцессоры (UMA, NUMA) и мультикомпьютеры (кластеры, MPP). Обсуждаются преимущества и недостатки каждой архитектуры, а также их масштабируемость.
Общие Вопросы Организации и Программирования
Второй раздел посвящен общим вопросам организации вычислительных процессов и программирования ПВС. Рассматриваются основные проблемы, возникающие при разработке параллельного программного обеспечения (ППО), такие как психологические аспекты, проблемы верификации и отладки, а также вопросы масштабируемости и переносимости. Подробно анализируется закон Амдала, определяющий теоретический предел ускорения при распараллеливании. Обсуждаются различные подходы к созданию ППО, включая автоматическое распараллеливание, явное описание параллелизма и комбинированный подход.
Мультипроцессорные Системы и OpenMP
Третий раздел посвящен мультипроцессорным вычислительным системам и их программированию с использованием OpenMP. Рассматривается модель "fork-join", лежащая в основе OpenMP, и основные директивы, процедуры и переменные окружения, необходимые для разработки параллельных программ. Подробно описываются директивы #pragma omp parallel, #pragma omp for, #pragma omp sections и другие, а также клаузы, управляющие планированием и синхронизацией потоков.
Кластерные Системы и MPI
Четвертый раздел посвящен кластерным системам и системам с массовым параллелизмом, которые являются мощными инструментами для решения научных и прикладных задач. Рассматривается стандарт MPI (Message Passing Interface) как де-факто стандарт для программирования параллельных систем этого класса. Описываются основные функции MPI для инициализации и завершения процессов, передачи и приема сообщений, коллективных операций, работы с группами и коммуникаторами, а также формирования топологии процессов.
Практические Работы
В заключение пособие включает практические работы, направленные на закрепление полученных знаний. Представлены тематические практические работы по OpenMP и MPI, а также сквозной мини-проект, позволяющий применить полученные знания для решения прикладной задачи в комплексе. Это позволяет студентам освоить инструменты и приемы программирования параллельных вычислительных систем на практике.
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ Учебное пособие ИНСТИТУТ КОСМИЧЕСКИХ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Министерство науки и высшего образования Российской Федерации Сибирский федеральный университет ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ Учебное пособие Красноярск СФУ 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 раз, т. е. на два порядка больше. Объяснить этот разрыв между ростом производительности отдельных компонентов и ростом производительности вычислительной системы в целом можно только совершенствованием способов организации вычислительных систем.