6.5. О построении параллельных алгоритмов

Loading...

En provenance du cours de National Research Tomsk State University

Введение в параллельное программирование с использованием OpenMP и MPI

37 notes

National Research Tomsk State University

Введение в параллельное программирование с использованием OpenMP и MPI

37 notes

Потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия «классических» – по схеме фон Неймана – ЭВМ привели к появлению многопроцессорных вычислительных систем (МВС) или суперкомпьютеров. Широкое распространение параллельные вычисления приобрели с переходом компьютерной индустрии на массовый выпуск многоядерных процессоров с векторными расширениями. В настоящие время практически все устройства – от карманных гаджетов и до самых мощных суперкомпьютеров – оснащены многоядерными процессорами. И если вы пишите последовательную программу, не применив распределение работы между разными ядрами центрального процессора и не проведя векторизацию, то вы используете только часть вычислительных возможностей центрального процессора. Пройдя этот курс, вы познакомитесь с основными архитектурами МВС, с двумя стандартами (OpenMP и MPI), позволяющими писать параллельные программы для систем с общей и распределенной памятью. На простых примерах будут разобраны основные конструкции и способы распределения работы. Выполнение практических заданий позволит вам приобрести практические навыки создания параллельных программ. Курс будет интересен всем, кто занимается программированием. Для участия в курсе слушателю необходимо иметь базовые знания по программированию с использованием С/С++. Курс состоит из 9 недель. Каждая неделя курса содержит видеолекции, а также проверочные задания. Сертификат получают слушатели, набравшие более 80 % от максимально возможного количества баллов. При этом итоговый результат, представленный как 100 %, складывается из следующих составляющих: тесты 1–5 недели дают 4 %, тесты 6–9 недели дают 5 %, все практические задания дают 10 %, кроме итогового практического задания по OpenMP, которое дает 20 %. Сертификат о прохождении данного курса дает дополнительные баллы при поступлении в магистратуру Национального исследовательского Томского государственного университета. Перечень магистерских программ находится по ссылке: https://pro-online.tsu.ru/edu/student/table.php

À partir de la leçon

Системы с распределённой памятью. Основы MPI

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

6.1. Основные понятия модели передачи сообщений, MPI среди других средств разработки параллельных программ5:16

6.2. Основные понятия и определения, состав MPI. Синтаксис функций MPI4:06

6.3. Первая параллельная программа с использованием MPI5:48

6.4. Ускорение работы параллельной программы7:06

6.5. О построении параллельных алгоритмов5:31

Rencontrer les enseignants

Николай Николаевич Богословский (Nikolay N. Bogoslovskiy)
Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
Кафедра вычислительной математики и компьютерного моделирования ММФ (Department of Calculus Mathematics and Computer Modelling, Mechanics and Mathematics Faculty)
Евгений Александрович Данилкин (Evgeniy A. Danilkin)
Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
Кафедра вычислительной математики и компьютерного моделирования ММФ (Department of Calculus Mathematics and Computer Modelling, Mechanics and Mathematics Faculty)

[МУЗЫКА]

[МУЗЫКА] Здравствуйте,

уважаемые слушатели.

Мы с вами уже познакомились с частью функций библиотеки MPI,

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

организовывать взаимосвязь между этими процессами.

А теперь давайте познакомимся с алгоритмом построения параллельных программ.

Этот алгоритм включает в себя 4 основных этапа: декомпозиция,

планирование коммуникаций, укрупнение и планирование вычислений.

На этапе декомпозиции задача анализируется,

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

Если задача поддается распараллеливанию,

то она делится на более мелкие части фундаментальной подзадачи.

Это, как правило, либо структуры данных более мелкие,

либо более мелкие фрагменты алгоритма.

В качестве примера можно рассматривать алгоритм вычисления

скалярного произведения двух векторов a и b.

Здесь, в качестве фундаментальной подзадачи, можно рассматривать

произведение i-той компоненты вектора a и i-той компоненты вектора b.

В общем случае количество фундаментальных подзадач должно быть хотя бы на порядок

больше планируемого числа используемых процессов.

При этом все фундаментальные подзадачи, по возможности,

должны быть примерно одинакового размера.

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

фундаментальных подзадач, а их количество.

Тогда мы сможем использовать большее количество процессов при

распараллеливании.

Важно, что на этом этапе не учитывается архитектура многопроцессорной

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

а анализируется только сам алгоритм.

Декомпозиции бывают двух видов: функциональная декомпозиция и декомпозиция

по данным.

Рассмотрим пример функциональной декомпозиции.

Пусть у нас есть два вектора a и b, и нам нужно вычислить их сумму,

разность и скалярное произведение.

Нулевому процессу мы дадим вычисление их суммы, первому процессу дадим вычисление

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

Таким образом, каждый процесс будет занят решением своей задачи.

Это у нас есть функциональная декомпозиция.

Например, декомпозиция по данным — это наша задача с вычислением скалярного

произведения.

Продолжим.

Следующий этап построения параллельной программы — это планирование коммуникаций.

Здесь мы должны установить взаимосвязь между нашими фундаментальными подзадачами.

И здесь преимущество имеют те алгоритмы, когда у нас у каждой подзадачи количество

связей с другими подзадачами не очень велико.

Желательно добиться,

чтобы выполнялись следующие требования на связи между фундаментальными подзадачами.

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

другими фундаментальными подзадачами.

А во-вторых, объем передаваемых данных тоже должен быть примерно одинаков для

каждой фундаментальной подзадачи.

На этом этапе также не учитывается архитектура многопроцессорной

вычислительной системы, а анализируются только свойства самого алгоритма.

Нужно отметить,

что упомянутые выше требования возникают из простых рассуждений.

При распараллеливании мы всю вычислительную работу делим на имеющееся

количество процессов.

Допустим, их у нас p.

Тогда мы ожидаем, что наша программа будет работать в p раз быстрее.

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

что между подзадачами нам нужно осуществлять обмены,

и вот эти обмены мы должны подчинять упомянутым выше требованиям.

Тогда у нас обмены будут требовать минимального количества времени.

Для нашего примера со скалярным произведением все подзадачи

связаны между собой линейно.

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

полученные в рамках фундаментальных подзадач.

Следующий этап — это укрупнение.

На этом этапе мы объединяем наши фундаментальные подзадачи в более крупные

блоки.

И здесь мы следуем одному простому правилу: мы стараемся самые

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

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

На этом этапе мы уже учитываем архитектуру многопроцессорной вычислительной системы,

а именно, количество укрупненных подзадач у нас должно совпадать с количеством

имеющихся процессоров или вычислительных ядер.

Для задачи вычисления скалярного произведение укрупнение происходит по

следующей схеме, где n — это длина вектора,

а p — это количество укрупненных подзадач.

На этапе планирования вычислений осуществляется распределение укрупненных

подзадач по процессорам.

И есть две основные схемы распределения подзадач: это «хозяин–работник» и

«децентрализованная» схема.

В стратегии «хозяин–работник» главный процесс распределяет вычислительную работу

или укрупненные подзадачи по процессам.

Также главный процесс ответственен за сбор результатов решения.

В «децентрализованной» схеме главный или управляющий процесс отсутствует,

а все вычисления происходят по некоторой схеме.

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

Таким образом, мы рассмотрели алгоритм построения параллельной программы.

На практике, когда вы будете разрабатывать параллельный алгоритм,

вы должны взять свою задачу и пройти все эти этапы.

При прохождении этапов выделить фундаментальные подзадачи, посмотреть,

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

параллельной программы именно для вашего алгоритма.

На этом мы заканчиваем с темой введения в MPI.

В рамках следующей темы мы будем более детально знакомиться с функциями

библиотеки MPI и выяснять все особенности их использования.

Спасибо за внимание и до следующей встречи.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play