Answers (1)


Оглавление
TOC \o "1-3" \h \z \u 1.Основные архитектуры параллельных компьютеров PAGEREF _Toc345841538 \h 22.Классификация архитектур вычислительных систем. (Классификация Флинна) PAGEREF _Toc345841539 \h 33.Модели параллельного программирования. Основные свойства параллельных алгоритмов PAGEREF _Toc345841540 \h 34.Модель задача-канал. Основные свойства модели "задача/канал" PAGEREF _Toc345841541 \h 35.Модель передачи сообщений PAGEREF _Toc345841542 \h 36.Модель параллелизма данных PAGEREF _Toc345841543 \h 37.Модель разделяемой памяти PAGEREF _Toc345841544 \h 38.Понятие о детерминизме программы PAGEREF _Toc345841545 \h 39.Модульность. Виды композиции модулей и/или программ PAGEREF _Toc345841546 \h 310. Пример параллельного алгоритма: конечные разности. PAGEREF _Toc345841547 \h 311. Основные этапы разработки параллельной программы. PAGEREF _Toc345841548 \h 312. Декомпозиция. Цели. Виды декомпозиции. Итоги этапа декомпозиции. PAGEREF _Toc345841549 \h 313.Коммуникация. Виды коммуникаций: локальные, глобальные,динамические, асинхронные. Распределенные коммуникации ивычисления. Итоги. PAGEREF _Toc345841550 \h 314. Интеграция. Цели интеграции. Укрупнение детализации. Репликация вычислений. Итоги. PAGEREF _Toc345841551 \h 315. Отображение. Цели отображения. Основные стратегии. Итоги. PAGEREF _Toc345841569 \h 316. Анализ эффективности параллельных алгоритмов. Система показателей оценки характеристик параллельной программы. Асимптотический анализ. PAGEREF _Toc345841582 \h 317. Анализ эффективности параллельных алгоритмов. Модель производительности. Снижение сложности модели. PAGEREF _Toc345841588 \h 322. Краткая характеристика библиотеки MPI PAGEREF _Toc345841594 \h 323. Базовые функции MPI (минимальный набор) PAGEREF _Toc345841598 \h 324. Библиотека MPI. Организация приема/передачи данных между отдельными процессами PAGEREF _Toc345841599 \h 325. Библиотека MPI. Коллективные функции PAGEREF _Toc345841603 \h 326. Библиотека MPI. Глобальные вычислительные операции над распределенными данными PAGEREF _Toc345841605 \h 327. Библиотека MPI. Обеспечение модульности. Коммуникаторы, группы и области связи PAGEREF _Toc345841606 \h 328. Библиотека MPI. Проблемы использования различных типов данных. Пользовательские типы данных PAGEREF _Toc345841610 \h 329. Библиотека MPI. Производные типы данных и передача упакованных данных PAGEREF _Toc345841613 \h 330.Технология OpenMP. Стратегия подхода. PAGEREF _Toc345841618 \h 331.Директивы OpenMP. Формат записи директив. PAGEREF _Toc345841619 \h 332.Директивы OpenMP. Области видимости директив. Типы директив. PAGEREF _Toc345841620 \h 333.Директивы OpenMP. Определение параллельной области. PAGEREF _Toc345841621 \h 334.Директивы OpenMP. Распределение вычислений по потокам. PAGEREF _Toc345841622 \h 335.Директивы OpenMP. Синхронизация. PAGEREF _Toc345841623 \h 336.Директивы OpenMP. Управление областью видимости данных. PAGEREF _Toc345841624 \h 337. Библиотека функций OpenMP. Функции контроля параметров среды исполнения. PAGEREF _Toc345841625 \h 338. Библиотека функций OpenMP. Функции синхронизации. PAGEREF _Toc345841626 \h 339. Технология OpenMP. Переменные среды исполнения. PAGEREF _Toc345841627 \h 3
Основные архитектуры параллельных компьютеровПараллелизм – направление развития вычислительной техники, целью которого является повышение ее производительности.
Пути достижения параллелизма:
независимость функционирования отдельных устройств компьютеров;
избыточность элементов вычислительной системы (использование специализированных устройств и дублирование);
конвейерная реализация обрабатывающих устройств.
Сдерживающие факторы развития:
высокая стоимость параллельных вычислительных систем (суперкомпьютеров);
необходимость обобщения последовательных программ;
потери производительности при организации параллелизма (гипотеза Минского);
постоянное совершенствование последовательных компьютеров;
последовательность большинства вычислительных алгоритмов (закон Амдала);
зависимость эффективности параллелизма от учета архитектуры параллельных систем.
Основные архитектуры
1. Симметричные мультипроцессорные системы SMP-системы.

Архитектура: cистема состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора (HP 9000). Аппаратно поддерживается когерентность кэшей.
Масштабируемость: наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число – не более 32 в реальных системах. Для построения масштабируемых систем на базе SMP используются кластерные или NUMA-архитектуры.
Операционная система: вся система работает под управлением единой ОС (обычно UNIX-подобной). ОС автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling), но иногда возможна и явная привязка.
Модель программирования: программирование в модели общей памяти. (POSIX threads, OpenMP). Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания.
2. Укрупненно-распараллеленные системы (МРР-системы)

Архитектура: система состоит из однородных вычислительных узлов, включающих: один или несколько центральных процессоров локальную память (прямой доступ к памяти других узлов невозможен) коммуникационный процессор или сетевой адаптер иногда - жесткие диски (как в SP) и/или другие устройства В/В. К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.)
Масштабируемость: общее число процессоров в реальных системах достигает нескольких тысяч (ASCI Red, Blue Mountain).
Операционная система: существуют два основных варианта: полноценная ОС работает только на управляющей машине (front-end), на каждом узле работает сильно урезанный вариант ОС, обеспечивающие только работу расположенной в нем ветви параллельного приложения. Пример: Cray T3E. На каждом узле работает полноценная UNIX-подобная ОС (вариант, близкий к кластерному подходу). Пример: IBM RS/6000 SP + ОС AIX, устанавливаемая отдельно на каждом узле.
Модель программирования: программирование в рамках модели передачи сообщений (MPI, PVM, BSPlib).
3. Системы с неоднородным доступом к памяти (NUMA)

Архитектура: система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом, доступ к локальной памяти в несколько раз быстрее, чем к удаленной.
Масштабируемость: масштабируемость NUMA-систем ограничивается объемом адресного пространства возможностями аппаратуры поддержки когерентности кэшей возможностями операционной системы по управлению большим числом процессоров. На настоящий момент, максимальное число процессоров в NUMA-системах составляет 256.
Операционная система: обычно вся система работает под управлением единой ОС, как в SMP. Но возможны также варианты динамического "подразделения" системы, когда отдельные "разделы" системы работают под управлением разных ОС (например, Windows и UNIX в NUMA-Q 2000).
Модель программирования: аналогична SMP.
4. Параллельные векторные системы PVP-системы
Архитектура: основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).
Модель программирования: эффективное программирование подразумевает векторизацию циклов (для достижения разумной производительности одного процессора) и их распараллеливание (для одновременной загрузки нескольких процессоров одним приложением).
5. Кластерные системы
Архитектура: набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта укрупненно-распараллеленного компьютера. Для связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. Гетерогенные (неоднородные) кластеры.
Операционная система: используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые - Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки.
Модель программирования: программирование, как правило, в рамках модели передачи сообщений (чаще всего MPI). Дешевизна подобных систем оборачивается большими накладными расходами на взаимодействие параллельных процессов между собой, что сильно сужает потенциальный класс решаемых задач.

Классификация архитектур вычислительных систем. (Классификация Флинна)  Single Instruction(Одиночный поток команд) Multiple Instruction(Множество потоков команд )
Single Data (Одиночный поток данных) SISDSingle Instruction, Single Data
обычные последовательные компьютеры MISDне существует
Multiple Data(Множество потоков данных) SIMDSingle Instruction, Multiple Data
большинство векторных компьютеров MIMDMultiple Instruction, Multiple Data
параллельные многопроцессорные вычислительные системы
Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD,MISD,SIMD,MIMD.
SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.
SIMD (single instruction stream / multiple data stream) – одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными – элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.
MISD (multiple instruction stream / single data stream) – множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. Будем считать, что пока данный класс пуст.
MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.
Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике того или иного компьютера. Если говорится, что компьютер принадлежит классу SIMD или MIMD, то сразу становится понятным базовый принцип его работы, и в некоторых случаях этого бывает достаточно. Однако видны и явные недостатки. В частности, некоторые заслуживающие внимания архитектуры, например dataflow и векторно-конвейерные машины, четко не вписываются в данную классификацию. Другой недостаток – это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попадают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования.
Модели параллельного программирования. Основные свойства параллельных алгоритмовМодели параллельного программирования:
Модель «задача/канал»;
Модель передачи
сообщений;
Модель разделяемой общей памяти;
Модели, использующие параллелизм данных (в следующих вопросах каждая из моделей описана подробнее).
Основные свойства модели параллельного программирования:
Параллелизм (concurrency) – способность выполнять несколько действий (операций, задач) одновременно.
Масштабируемость (scalability) – потенциальные возможности увеличения производительности при увеличении числа процессоров.
Локальность (locality) – предпочтительность использования локальной памяти по сравнению с обращением к удаленной памяти.
Модульность (modularity) – возможность декомпозиции сложных программ на простые компоненты.

Модель задача-канал. Основные свойства модели "задача/канал"
Параллельная программа состоит из одной или нескольких задач. Задачи выполняются одновременно. Число задач может изменяться при выполнении программы.
Задача инкапсулирует последовательную программу и локальную память. Кроме того, набор входных (inports) и выходных (outports) портов определяет интерфейс задачи с ее окружением.
Задача может выполнять четыре основных действия в дополнение к чтению/записи локальной памяти:
послать сообщения на outports
получить сообщения из inports
создать новые задачи
завершить выполнение
Операция посылки сообщения является асинхронной: она завершается немедленно. Операция получения сообщения является синхронной: ее выполнение блокирует задачу до прихода сообщения.
Пары входных/выходных портов могут быть связаны очередью сообщений - программным каналом. Каналы могут создаваться и удаляться, ссылки на каналы могут передаваться в сообщениях, что делает соединения динамическими.
Задачи могут быть отображены на имеющиеся процессоры различными способами; используемое отображение не влияет на семантику программы. В частности несколько задач могут быть отображены на единственный процессор.
Абстракция задача обеспечивает механизм локальности (данные, которые находятся в локальной памяти задачи – это «закрытые» данные, все остальные данные – «удаленные»).
Абстракция канал обеспечивает механизм для индикации того, что в одной задаче потребовались данные другой задачи чтобы выполнить некую обработку (зависимость по данным)
Основные свойства модели «задача/канал»:
Эффективность
Независимость отображения
Модульность
Детерминизм

Модель передачи сообщенийНаиболее широко используемая модель параллельного программирования.  Программы этой модели, подобно программам модели процесс/канал, создают множество процессов, с каждым из которых ассоциированы локальные данные. Каждый процесс идентифицируется уникальным именем. Процессы взаимодействуют, посылая и получая сообщения. В этом отношение модель обмен сообщениями является разновидностью модели процесс/канал и отличается только механизмом, используемым при передаче данных. 
Возможно:
динамическое создание задач,
выполнение нескольких задач на одном процессоре,
выполнение различных программ различными задачами.
НО в большинстве систем передачи сообщений:
создается фиксированное число идентичных задач при запуске программы;
не поддерживается динамическое управление задачами во время выполнения программы;
используется модель программирования – SIMD: каждая задача выполняет одну и ту же программу, но функционирует на различных данных.

Модель параллелизма данныхНазвание модели происходит оттого, что она эксплуатирует параллелизм, который заключается в применении одной и той же операции к множеству элементов структур данных.
Используется естественный параллелизм приложения или некой однотипной операции над элементами структуры данных например, «добавляется 2 к всем элементам этой таблицы» или «увеличивается оклад всех служащих со стажем свыше 5 лет»
Программа с параллелизмом данных состоит из последовательности таких операций
Компиляторы, использующие параллелизм данных, часто требуют, чтобы программист явно указал распределение данных по процессорам.

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

Понятие о детерминизме программыДетерминизм – предсказуемое поведение программы в процессе ее исполнения.
Параллельная программа может давать разные результаты при повторных запусках даже без модификации кода и исходных данных. Это является следствием «гонок за данными» - одновременного и асинхронного доступа разных процессов или потоков к общим переменным
Хотя недетерминизм иногда является полезным и его стараются поддерживать, для параллельного программирования желательно выполнение условия детерминизма программы. Детерминированные программы просты для понимания. Например, отследить корректность программы проще по результату одного исполнения, чем по множеству всех возможных

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

10. Пример параллельного алгоритма: конечные разности.Параллельный алгоритм для конечно-разностной задачи. Дан вектор X где N=8. Весь пример разделён на 8 подзадач (далее просто задачи), каждая из которых инкапсулирует только свои данные и взаимодействует с соседями слева и справа через каналы. В структуре каждой задачи есть два входных и выходных порта. (Термин «задача» - обобщающий и используется потому, что это может быть как отдельный узел (процессор), так и просто поток в рамках одного узла).
Дано на каждой задаче. Найти на каждой задаче.


Параллельный алгоритм для данного примера подразумевает создание N задач, по одной на каждую точку в векторе . Начальное условие примера разделено между всеми задачами: в i-ой задаче дано и она отвечает за вычисление значений в течение всех шагов T. Поэтому на каждом шаге t для вычисления очередного значения данная задача должна получить числа и от своих соседей слева (i-1) и справа (i+1) соответственно, как показано на рисунке выше. Для этого каждая задача (кроме 0-ой и (N-1)-ой, потому что для них новые значения по времени вычисляются из граничных условий – курс ЧМ©) делает следующие действия:
Посылает своё текущее значение соседу слева и справа;
Получает значения и от левого и правого соседа;
Использует полученные значения для вычисления по формуле выше.

11. Основные этапы разработки параллельной программы.Этапы процесса проектирования: декомпозиция (partitioning), взаимодействие (communication), интеграция (agglomeration), отображение (mapping)
Основное внимание уделяется: на первых двух этапах – параллелизм, масштабируемость; на третьем, четвертом – локальность, другие проблемы эффективности.
Декомпозиция: вычисление, которое должно быть выполнено, и данные, необходимые для этого вычисления, делятся на малые задачи; практические проблемы (число процессоров компьютера, на котором будет выполняться задача) игнорируются; внимание сосредоточено на обнаружении (выделении) возможностей параллельного выполнения.
Взаимодействие: определяются взаимодействия, требуемые для координации выполнения задачи; определяются соответствующие коммуникационные структуры и алгоритмы.
Интеграция: задача и коммуникационные структуры, определенные на первых двух этапах проекта оцениваются в соответствии с требованиями эффективности и стоимости реализации; при необходимости задачи объединяются в большие задачи, чтобы улучшить быстродействие или уменьшить стоимость разработки.
Отображение: каждая задача назначается на процессор таким образом, чтобы попытаться удовлетворить двум противоречивым целям: максимизации использования процессора и уменьшения издержек связи; отображение может быть определено статически или выполнено динамически с помощью алгоритмов сбалансированной загрузки.
Процесс проектирования:
Действие последовательное
НО, практически, это – существенно параллельный процесс
Одновременно учитывается много аспектов
Возможен, хотя и не желателен, перебор с возвратами (на предыдущие этапы)
Анализ части или всего проекта может потребовать изменений проектных решений, сделанных на предыдущих этапах.

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

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

«разделяй и властвуй». . Полная сумма вычисляется за шагов.
ИТОГИ:
Несбалансированные коммуникационные требования предполагают немасштабируемую конструкцию. Если структура данных, к которой часто обращаются, инкапсулирована в одной задаче, рассмотрите возможности распределения или репликации этой структуры данных.
Каждая задача взаимодействует, преимущественно, с малым числом соседей. Если же она должна взаимодействовать с большим количеством других задач, оцените возможность формулировки такого глобального взаимодействия в терминах локальной коммуникационной структуры, как это было сделано в алгоритме парных взаимодействий.
Операции обмена способны выполняться одновременно. Если нет, то вероятно, что ваш алгоритм не является эффективным и масштабируемым. Попробуйте использовать метод "разделяй и властвуй", чтобы выявить параллелизм.
Возможно одновременное выполнение вычислений, распределённых по разным задачам. Если нет, то весьма вероятно, что ваш алгоритм не является эффективным и масштабируемым, и тогда возможно поможет переупорядочение операции вычисления и обмена или, может быть, желательно переформулировать задачу.

14. Интеграция. Цели интеграции. Укрупнение детализации. Репликация вычислений. Итоги.Это 3 этап процесса разработки параллельной программы.
Задача и коммуникационные структуры, определенные на первых двух этапах проекта оцениваются в соответствии с требованиями эффективности и стоимости реализации.
При необходимости задачи объединяются в большие задачи, чтобы улучшить быстродействие или уменьшить стоимость разработки.
Цели интеграцииУменьшение коммуникационных издержек
Сохранение гибкости
Сокращение стоимости разработки ПО
Критические проблемы этапаЗатраты на коммуникацию
Количество пересылок
Объем пересылаемых данных
Затраты на создание задач
Уменьшение коммуникационных издержекОсновные подходы:
Укрупнение элементов разбиения
Репликация вычислений
Репликация данных
Устранение лишних связей
Укрупнение детализацииУменьшение количества и объема коммуникаций путем объединения отдельных задач в одну
Критерий - отношение поверхности к объему:
Затраты на связь ~ поверхности подобласти
Вычисления ~ объему подобласти
Примеры укрупненияУменьшение размерности декомпозиции
Объединение смежных задач - повышение степени детализации
Объединение поддеревьев в структуре «разделяй и властвуй»
Объединение узлов в дереве
Пример двумерной задачи"поверхность" ~ N; "объем" ~ N2; (N - размер задачи)
Следовательно,
количество взаимодействий, выполняемых для вычислительной единицы (коэффициент обмен данными / вычисления) уменьшается при увеличении размера задачи
Следствие эффектов «поверхность / объем»Декомпозиции с большей размерностью являются обычно наиболее эффективными (при прочих равных условиях), потому что они уменьшают поверхностную область (связь), требуемую для данного объема (вычисление).
Следовательно, более эффективно укрупнять элементы, интегрируя задачи по всем размерностям, нежели уменьшать размерность декомпозиции.

Пример двумерной проблемысетка 88
88=64 задач, 644=256 связей 256 значений данных22=4 задачи, 44=16 связей
164=64 значений данных
Репликация вычислений

Сохранение гибкостиЧисло задач превышает количество доступных процессоров
Оптимальное число задач определяется комбинацией аналитического анализа модели и эмпирических исследований
Степень детализации – параметр этапа компиляции или этапа выполнения
Нет ограничений на число создаваемых задач
Сокращение стоимости разработки ПООтносительные издержки разработки различных стратегий декомпозиции
Распределение данных, используемое другими компонентами большой системы
ИтогиИздержки связи уменьшены? Локализация увеличилась? Если нет, исследуйте алгоритм, чтобы определить, возможно ли этого достигнуть, используя альтернативную стратегию скопления.
Получена ли выгода от репликации вычислений?
Если реплицируются данные, не ухудшает ли это масштабируемость алгоритма?
Получены ли задачи с приблизительно одинаковыми вычислительными и коммуникационными потребностями?
Число задач все еще соотносится с размером задачи?
Если интеграция уменьшила степень параллелизма выполнения задачи, проверьте, осталось ли достаточно параллелизма для используемого и предполагаемого компьютера?
Может ли и далее уменьшить число задач, без появления несбалансированности загрузки, увеличения издержек разработки ПО, или уменьшения масштабируемости?
При и эффективнее тех, которые создают много мелких задач.
Если распараллеливается существующая последовательная программа, определена ли стоимость внесения изменений в последовательный код?
Если эти издержки высоки, надо рассмотреть альтернативные стратегии интеграции, увеличивающие возможности многократного использования кода.
Используйте методы оценки эффективности, чтобы оценить компромиссы стоимости.

15. Отображение. Цели отображения. Основные стратегии. Итоги.Это 4 этап процесса разработки параллельной программы.
Основная цель этапаМинимизация общего времени выполнения параллельной задачи
Сложности достижения цели:
Ограниченность ресурсов может лимитировать число задач, размещаемых на одном процессоре
Проблема отображения является NP-полной задачей
Стратегии достижения целиЗадачи, которые могут выполняться одновременно, размещаются на различных процессорах, расширяя, таким образом, параллелизм.
Задачи, которые часто взаимодействуют, размещаются на одном и том же процессоре, увеличивая, таким образом, локализацию.
Стратегия дляалгоритмов с декомпозицией по данным, которые отличаются фиксированным числом задач одинакового размера и локальными и глобальными коммуникациями, имеющими структурную определённость.
Прямое (простое) отображение является эффективным.
Прямое (простое) отображениеЗадачи отображаются таким способом, чтобы минимизировать межпроцессорное взаимодействие
Возможно укрупнение задач, отображенных на один и тот же процессор, если это еще не было сделано, с тем, чтобы получить P крупно модульных задач, по одной на каждый процессор.

Каждому процессору сопоставляется одинаковый объем вычислений
Минимизируются межпроцессорные взаимодействия
Стратегия дляалгоритмов, основанных на декомпозиции по данным с переменным объемом вычислений у задач и/или неструктурированным характером взаимодействий.
Эффективные стратегии интеграции и отображения могут быть не очевидны для программиста
Алгоритмы сбалансированной загрузкиИспользуют эффективные стратегии укрупнения и отображения, используя эвристические методы.
Необходимо сопоставлять время, требуемое для работы этих алгоритмов, с уменьшением общего времени выполнения.
Вероятностные методы сбалансированной загрузки имеют более низкие накладные расходы, чем, методы, которые опираются на знание структуры приложения.
Стратегия дляприложений, в которых либо число задач, либо объем вычислений или коммуникаций, приходящийся на задачу, изменяется динамически во время выполнения программы.
Динамическая стратегия сбалансированной загрузки
Динамическая стратегия сбалансированной загрузкиАлгоритм сбалансированной загрузки выполняется периодически, переопределяя укрупнение и отображение.
Поскольку во время выполнения программы определение сбалансированности загрузки должно выполняться многократно, в данном случае предпочтительны локальные алгоритмы, которые не требуют глобальных знаний относительно состояния вычислений.
Стратегия дляалгоритмов, основанных на функциональной декомпозиции. Большое количество короткоживущих задач, которые координируют с другими задачами только в начале и в конце своего выполнения.
Алгоритмы диспетчеризации, которые распределяют задачи по процессорам, которые являются неактивными, или в скором времени станут таковыми.
Алгоритмы сбалансированной загрузкиРекурсивные методы биекции (деления пополам)
Локальные алгоритмы
Вероятностные методы
Методы циклического отображения
Алгоритм планировщика задачИспользуется, когда функциональная декомпозиция приводит к задачам со слабыми требованиями к локальности.
Централизованный или распределенный пул задач, в который помещаются новые задачи и откуда они выбираются для распределения по процессорам.
ИтогиРассмотрен ли алгоритм, основанный на динамическом создании и удалении задач?
При использовании централизованной сбалансированной загрузки, не является ли менеджер узким местом?
Затраты связи можно уменьшить, передавая менеджеру указатели на задачи, а не собственно задачи.
При использовании динамических алгоритмов сбалансированной загрузки, оценены ли относительные затраты различных стратегий?
Убедитесь, что учитываются затраты на выполнение алгоритма балансировки.
Вероятностные или циклические схемы отображения просты и нужно всегда их рассматривать, потому что они могут избежать потребности в повторных этапов балансировки.
При использовании вероятностных или циклических методов, имеется ли достаточно большое число задач, чтобы гарантировать корректную сбалансированность?
Как правило, требуется по крайней мере в десять раз больше задач, чем количество процессоров, имеющихся в наличии.

16. Анализ эффективности параллельных алгоритмов. Система показателей оценки характеристик параллельной программы. Асимптотический анализ.Эффективность параллельной программыВремя выполнения
Масштабируемость процесса вычислений
Устройства генерации, хранения данных, передачи по сети, чтения/записи на диск, передачи данных между различными этапами вычислений
Стоимость различных стадий проектирования
Система показателей оценки характеристикВремя выполнения
Эффективность распараллеливания
Требования по памяти
Производительность
Латентность
Скорость ввода/вывода
Переносимость
Масштабируемость
Стоимость разработки
Стоимость реализации
Стоимость верификации
Возможность повторного использования
Аппаратные требования
Стоимость аппаратуры
Стоимость эксплуатации
Экстраполяция по результатам наблюденияПараллельный алгоритм X обеспечил коэффициент ускорения вычислений 10.8 для компьютера с 12 процессорами при размере задачи N=100 .
Хорошо это или плохо?
А на 1000 процессорах?
Для N=10 или N=1000 ?
А если затраты на коммуникацию возрастут в 10 раз?
Асимптотический анализВремя работы алгоритма ~ O(N log N) на O(N) процессорах
Это означает, что существует константа c и минимальный размер задачи N0 такие, что для всех N>N0 временные затраты ≤ c N log N на N процессорах.
Недостатки асимптотического анализаИгнорируются малые значения N и P. T ~ N log NT=10N+N log N (N < 1024)
1000N log N vs. 10N2 (лучше при N<996 )
Нет привязки к конкретному параллельному компьютеру (архитектуре)
Поэтому – использовать осторожно!

17. Анализ эффективности параллельных алгоритмов. Модель производительности. Снижение сложности модели.Модель производительности


Снижение сложности моделиИспользуется идеализированный мультикомпьютер
Масштабный анализ, т.е. определение незначащих составляющих задачи.
Эмпирические исследования для уточнения простой модели vs. усложнение модели
Время вычислений -
Чаще всего зависит от
размера задачи N
характеристик процессоров
параметров оперативной памяти
Время коммуникаций -
Различают два типа коммуникаций:
межпроцессорные (interprocessor)
внутри процессорные (intraprocessor)

Idle Time
22. Краткая характеристика библиотеки MPIОсновные характеристикиMPI - Message Passing Interface, интерфейс передачи сообщений
Языки программирования:
– FORTRAN;
– C;
Более 120 функций;
SPMD-модель параллельного программирования;
Наличие групп процессов (безопасность сообщений), топологий процессов;
Структурирование передаваемого сообщения, типизация, гетерогенность;
Режимы: normal (blocking and non-blocking), synchronous, ready (to allow access to fast protocols), buffered;
Большое разнообразие коллективных операций.
Чего нет в MPI: Функции управления процессами, работа с удаленной памятью, разделяемая общая память, active messages, threads.
MPI (message passing interface) - библиотека функций, предназначенная для поддержки работы параллельных процессов в терминах передачи сообщений.
MPI предоставляет программисту единый механизм взаимодействия процессов внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные или многопроцессорные, с общей или локальной памятью), взаимного расположения ветвей (на одном процессоре или на разных) и API операционной системы.
Минимально в состав MPI входят: библиотека программирования (заголовочные и библиотечные файлы для языков С, С++ и FORTRAN) и загрузчик приложений. Дополнительно включаются: профилирующий вариант библиотеки (используется на стадии тестирования параллельного приложения), загрузчик с графическим и сетевым интерфейсом для X-Window и проч.
MPI может работать также на базе любого из трех способов соединений:
через общую память;
через скоростную внутримашинную сеть многопроцессорных вычислительных систем;
через сеть, как правило, работающую по протоколу TCP/IP.
Соглашения о терминахПараллельное приложение состоит из нескольких процессов (ветвей, потоков, задач), выполняющихся одновременно. Разные процессы могут выполняться как на разных процессорах, так и на одном и том же – для программы это роли не играет, поскольку в обоих случаях механизм обмена данными одинаков. С каждым потоком связывается номер процесса - целое неотрицательное число, являющееся уникальным атрибутом процесса.
Процессы обмениваются друг с другом данными в виде сообщений. Атрибутами сообщения являются номер процесса-отправителя, номер процесса-получателя и идентификатор сообщения. Для них заведена структура MPI_Status, содержащая три поля: MPI_Source (номер процесса отправителя), MPI_Tag (идентификатор сообщения), MPI_Error (код ошибки). Могут быть и дополнительные поля.
Идентификатор сообщения (msgtag) - атрибут сообщения, являющийся целым неотрицательным числом, лежащим в диапазоне от 0 до 32767. Идентификаторы позволяют программе и библиотеке связи отличать сообщения друг от друга.
Для совместного проведения тех или иных расчетов процессы внутри приложения объединяются в группы. Группы могут быть вложенными. Внутри группы все процессы пронумерованы. Каждый процесс может узнать у библиотеки связи свой номер внутри группы и в зависимости от номера выполнить соответствующую часть расчетов. С каждой группой ассоциирован свой коммуникатор. Поэтому при осуществлении пересылки необходимо указать идентификатор группы, внутри которой производится эта пересылка. Все процессы содержатся в группе с предопределенным идентификатором MPI_COMM_WORLD.
Термин "процесс" используется также в Unix, и здесь нет путаницы: в MPI процесс запускается и работает как обычный процесс Unix, связанный через MPI с остальными процессами, входящими в приложение. В остальном процессы следует считать изолированными друг от друга: у них разные области кода, стека и данных.
Принятая в MPI нотация записиРегистр букв: важен в С, не играет роли в FORTRAN.
Все идентификаторы начинаются с префикса MPI_. Не рекомендуется заводить пользовательские идентификаторы, начинающиеся с этой приставки, а также с приставок MPID_, MPIR_ и PMPI_, которые используются в служебных целях.
Если идентификатор сконструирован из нескольких слов, слова в нем, как правило, разделяются подчерками: MPI_Get_count, MPI_Comm_rank. Иногда разделитель не используется: MPI_Sendrecv, MPI_Alltoall.
Порядок слов в составном идентификаторе выбирается по принципу "от общего к частному": сначала префикс MPI_, потом название категории (Type, Comm, Group, Attr, Errhandler и т.д.), потом название операции (MPI_Errhandler_create, MPI_Errhandler_set, ...). Наиболее часто употребляемые функции выпадают из этой схемы: они имеют короткие и стереотипные названия, например MPI_Barrier, или MPI_Unpack.
Имена констант (и неизменяемых пользователем переменных) записываются полностью заглавными буквами: MPI_COMM_WORLD, MPI_FLOAT. В именах функций первая за префиксом буква - заглавная, остальные маленькие: MPI_Send, MPI_Comm_size.
Определение всех именованных констант, прототипов функций и определение типов выполняется в языке Си подключением файла mpi.h, а в Фортране – mpif.h.
23. Базовые функции MPI (минимальный набор)Существует несколько функций, которые используются в любом, даже самом коротком приложении MPI. Занимаются они не столько собственно передачей данных, сколько ее обеспечением.
MPI_Init - инициализация параллельной части приложения. Реальная инициализация для каждого приложения выполняется не более одного раза, а если MPI уже был инициализирован, то никакие действия не выполняются и происходит немедленный возврат из подпрограммы. Все оставшиеся MPI-процедуры могут быть вызваны только после вызова MPI_Init.
int MPI_Init( int* argc, char*** argv) - функции передаются адреса аргументов, стандартно получаемых программой от операционной системы и хранящих параметры командной строки. В конец командной строки программы MPI-загрузчик mpirun добавляет ряд информационных параметров, которые требуются MPI_Init. Возвращает: в случае успешного выполнения - MPI_SUCCESS, иначе - код ошибки (То же самое возвращают и все остальные функции, рассматриваемые в данном пособии).
MPI_Finalize - завершение параллельной части приложения. Все последующие обращения к любым MPI-процедурам, в том числе к MPI_Init, запрещены. К моменту вызова MPI_Finalize некоторым процессом все действия, требующие его участия в обмене сообщениями, должны быть завершены: int MPI_Finalize(void).
MPI_Abort – аварийное закрытие библиотеки. Вызывается, если пользовательская программа завершается по причине ошибок времени выполнения, связанных с MPI.
void MPI_Abort(MPI_Comm comm, int error) - Вызов MPI_Abort из любой задачи принудительно завершает работу всех задач, подсоединенных к области связи comm. Если указан описатель MPI_COMM_WORLD, будет завершено все приложение (все его задачи) целиком, что, по-видимому, и является наиболее правильным решением. Используйте код ошибки MPI_ERR_OTHER, если не знаете, как охарактеризовать ошибку в классификации MPI.
int MPI_Comm_size(MPI_Comm comm, int* size) - Определение общего числа параллельных процессов в группе comm. Параметры: comm - идентификатор группы; size - размер группы (выходной параметр).
int MPI_Comm_rank( MPI_comm comm, int* rank) - Определение номера процесса в группе comm. Значение, возвращаемое по адресу &rank, лежит в диапазоне от 0 до size_of_group-1. Параметры: comm – идентификатор группы; rank – номер вызывающего процесса в группе comm (выходной параметр).
double MPI_Wtime(void) - Функция возвращает астрономическое время в секундах (вещественное число), прошедшее с некоторого момента в прошлом. Гарантируется, что этот момент не будет изменен за время существования процесса.
24. Библиотека MPI. Организация приема/передачи данных между отдельными процессамиСамый простой тип связи между задачами: одна ветвь вызывает функцию передачи данных, а другая - функцию приема. Проще всего это осуществляется функциями приема/передачи сообщений с блокировкой.
Функции приема/передачи сообщений с блокировкойint MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int msgtag,MPI_Comm comm):
buf - адрес начала буфера посылки сообщения;
count - число передаваемых элементов в сообщении;
datatype - тип передаваемых элементов;
dest - номер процесса-получателя;
msgtag - идентификатор сообщения;
comm - идентификатор группы.
Блокирующая посылка сообщения с идентификатором msgtag, состоящего из count элементов типа datatype, процессу с номером dest. Все элементы сообщения расположены подряд в буфере buf. Значение count может быть нулем, задается не в байтах, а в количестве ячеек. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа. Разрешается передавать сообщение самому себе.
Блокировка гарантирует корректность повторного использования всех параметров после возврата из подпрограммы. Следует специально отметить, что возврат из подпрограммы MPI_Send не означает ни того, что сообщение уже передано процессу dest, ни того, что сообщение покинуло процессорный элемент, на котором выполняется процесс, выполнивший MPI_Send.
int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_comm comm, MPI_Status *status);
buf - адрес начала буфера приема сообщения (выходной параметр);
count - максимальное число элементов в принимаемом сообщении;
datatype - тип элементов принимаемого сообщения;
source - номер процесса-отправителя;
msgtag - идентификатор принимаемого сообщения;
comm - идентификатор группы;
status - параметры принятого сообщения (выходной параметр).
Основные функции приема/передачи сообщений без блокировкиint MPI_ISend(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request).
Параметры: полностью аналогично MPI_Send, request - идентификатор асинхронной передачи (выходной параметр).
Передача сообщения, аналогичная MPI_Send, однако возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf. Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки.
Окончание процесса передачи (т.е. того момента, когда можно переиспользовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.
Сообщение, отправленное любой из процедур MPI_Send и MPI_ISend, может быть принято любой из процедур MPI_Recv и MPI_IRecv.
int MPI_IRecv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_comm comm, MPI_Request *request).
Параметры: полностью аналогично MPI_Recv, request - идентификатор асинхронного приема сообщения (выходной).
Прием сообщения, аналогичный MPI_Recv, однако возврат из подпрограммы происходит сразу после инициализации процесса приема без ожидания получения сообщения в буфере buf. Окончание процесса приема можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.
Совмещенные прием/передача сообщенийНекоторые конструкции с приемо-передачей применяются очень часто. Ситуация настолько распространенная, что в MPI специально введены функции, осуществляющие одновременно посылку одних данных и прием других.
int MPI_Sendrecv( void *sbuf, int scount, MPI_Datatype stype, int dest, int stag, void *rbuf, int rcount, MPI_Datatype rtype, int source, MPI_DAtatype rtag, MPI_Comm comm, MPI_Status *status).
Параметры:
sbuf - адрес начала буфера посылки сообщения
scount - число передаваемых элементов в сообщении
stype - тип передаваемых элементов
dest - номер процесса-получателя
stag - идентификатор посылаемого сообщения
rbuf - адрес начала буфера приема сообщения (выходной параметр)
rcount - число принимаемых элементов сообщения
rtype - тип принимаемых элементов
source - номер процесса-отправителя
rtag - идентификатор принимаемого сообщения
comm - идентификатор группы
status - параметры принятого сообщения (выходной параметр)
Данная операция объединяет в едином запросе посылку и прием сообщений. Принимающий и отправляющий процессы могут являться одним и тем же процессом. Сообщение, отправленное операцией MPI_Sendrecv, может быть принято обычным образом, и точно также операция MPI_Sendrecv может принять сообщение, отправленное обычной операцией MPI_Send. Буфера приема и посылки обязательно должны быть различными.
25. Библиотека MPI. Коллективные функцииПод термином "коллективные" в MPI подразумеваются три группы функций:
функции коллективного обмена данными;
точки синхронизации, или барьеры;
функции поддержки распределенных операций.
Коллективная функция одним из аргументов получает описатель области связи (коммуникатор). Вызов коллективной функции является корректным, только если произведен из всех процессов-абонентов соответствующей области связи, и именно с этим коммуникатором в качестве аргумента. В этом и заключается коллективность: либо функция вызывается всем коллективом процессов, либо никем.
Функция синхронизации процессов: int MPI_Barrier (MPI_Comm comm), comm - идентификатор группы. Блокирует работу процессов, вызвавших данную процедуру, до тех пор, пока все оставшиеся процессы группы comm также не выполнят эту процедуру. Гарантирует, что к выполнению следующей за MPI_Barrier инструкции каждая задача приступит одновременно с остальными.
Это единственная в MPI функция, вызовами которой гарантированно синхронизируется во времени выполнение различных процессов.
Функции коллективного обмена даннымиШироковещательная рассылка данных:
int MPI_Bcast( void *buffer, int count, MPI_Datatype datatype, int source, MPI_Comm comm);
buffer - адрес начала буфера посылки сообщения (выходной параметр);
count - число передаваемых элементов в сообщении;
datatype - тип передаваемых элементов;
root - номер рассылающего процесса;
comm - идентификатор группы.
Выполняется рассылка сообщения от процесса root всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buffer процесса root будет скопировано в локальный буфер процесса. Значения параметров count, datatype и root должны быть одинаковыми у всех процессов.
Функции сбора блоков данных от всех процессов группы:
int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm).
sendbuf - адрес начала буфера посылки;
sendcount - число элементов в посылаемом сообщении;
sendtype - тип элементов отсылаемого сообщения;
recvbuf - адрес начала буфера сборки данных (выходной параметр);
recvcount - число элементов в принимаемом сообщении;
recvtype - тип элементов принимаемого сообщения;
root - номер процесса, на котором происходит сборка данных;
comm - идентификатор группы;
ierror - код ошибки (выходной параметр).
Данная функция ("совок") выполняет сборку данных со всех процессов в буфере recvbuf процесса root. Каждый процесс, включая root, посылает содержимое своего буфера sendbuf процессу root. Собирающий процесс сохраняет данные в буфере recvbuf, располагая их в порядке возрастания номеров процессов. Параметр recvbuf имеет значение только на собирающем процессе и на остальных игнорируется, значения параметров sendcount, datatype и root должны быть одинаковыми у всех процессов. Векторный вариант функции сбора данных – MPI_Gatherv – позволяет задавать разное количество отправляемых данных в разных задачах-отправителях. Соответственно, на приемной стороне задается массив позиций в приемном буфере, по которым следует размещать поступающие данные, и максимальные длины порций данных от всех задач. Оба массива содержат позиции/длины не в байтах, а в количестве ячеек типа recvcount.
int MPI_Allgather(void* sendbuf, intsendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm);
int MPI_Gatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void*rbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm).
Функция MPI_Allgather аналогична MPI_Gather, но прием осуществляется не в одной задаче, а во всех: каждая имеет специфическое содержимое в передающем буфере, и все получают одинаковое содержимое в буфере приемном. Как и в MPI_Gather, приемный буфер последовательно заполняется данными изо всех передающих. Вариант с неодинаковым количеством данных называется MPI_Allgatherv.
Функции распределения блоков данных по всем процессам группы:
int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm).
Функция MPI_Scatter ("разбрызгиватель") выполняет обратную "совку" операцию - части передающего буфера из задачи root распределяются по приемным буферам всех задач.
int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm).
Векторный вариант – MPI_Scatterv, рассылает части различной длины в приемные буфера разного размера.
Совмещенные коллективные операции:
int MPI_Alltoall(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm).
MPI_Alltoall : каждый процесс нарезает передающий буфер на куски и рассылает куски остальным процессам; каждый процесс получает куски от всех остальных и поочередно размещает их приемном буфере. Это "совок" и "разбрызгиватель" в одном флаконе. Векторный вариант называется MPI_Alltoallv.
26. Библиотека MPI. Глобальные вычислительные операции над распределенными даннымиИдея проста: в каждой задаче имеется массив. Над нулевыми ячейками всех массивов производится некоторая операция (сложение/произведение/поиск минимума/максимума и т.д.), над первыми ячейками производится такая же операция и т.д. Четыре функции предназначены для вызова этих операций и отличаются способом размещения результата в задачах.
int MPI_Allreduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm).
sendbuf - адрес начала буфера для аргументов;
recvbuf - адрес начала буфера для результата (выходной параметр);
count - число аргументов у каждого процесса;
datatype — тип аргументов;
op - идентификатор глобальной операции;
comm - идентификатор группы.
Выполнение count глобальных операций op с возвратом count результатов во всех процессах в буфере recvbuf. Операция выполняется независимо над соответствующими аргументами всех процессов. Значения параметров count и datatype у всех процессов должны быть одинаковыми. Из соображений эффективности реализации предполагается, что операция op обладает свойствами ассоциативности и коммутативности.
int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm).
root - процесс-получатель результата.
Функция аналогична предыдущей, но результат будет записан в буфер recvbuf только у процесса root.
int MPI_Reduce_scatter(void* sendbuf, void* recvbuf, int *recvcounts, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm).
MPI_Reduce_scatter : каждая задача получает не весь массив-результат, а его часть. Длины этих частей находятся в массиве-третьем параметре функции. Размер исходных массивов во всех задачах одинаков, и равен сумме длин результирующих массивов.
int MPI_Scan(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm).
MPI_Scan : аналогична функции MPI_Allreduce в том отношении, что каждая задача получает результирующий массив. Главное отличие: здесь содержимое массива- результата в задаче i является результатом выполнение операции над массивами из задач с номерами от 0 до i включительно.
27. Библиотека MPI. Обеспечение модульности. Коммуникаторы, группы и области связиДва взаимосвязанных механизма:функции для работы с группами процессов как упорядоченными множествами;
функции для работы с коммуникаторами, для создания новых коммуникаторов, как описателей новых областей связи.
Основные понятия (группа):Группа – упорядоченное множество процессов;
Каждый процесс идентифицируется переменной целого типа (непрерывный ряд, начинающийся с 0);
Специальный тип данных MPI_Group;
Набор функций для работы с переменными и константами типа MPI_Group;
Две предопределенные группы:
MPI_GROUP_EMPTY
MPI_GROUP_NULL
Нет группы, соответствующей коммуникатору MPI_COMM_WORLD;
Созданная группа не может быть модифицирована (расширена или усечена);
Можно только создать новую группу;
Основные понятия (коммуникатор):Коммуникатор – скрытый объект с некоторым набором атрибутов, правилами его создания, использования и уничтожения;
Коммуникатор описывает некоторую область связи;
Два предопределенных коммуникатора:
– MPI_COMM_WORLD
– MPI_COMM_SELF
Одной и той же области связи может соответствовать несколько коммуникаторов, но они не являются тождественными и не могут участвовать во взаимном обмене сообщениями.
Если данные посылаются через один коммуникатор, процесс-получатель может получить их только через тот же самый коммуникатор.
Область связи (communication domain) – это нечто абстрактное. В распоряжении программиста нет типа данных, описывающего непосредственно области связи, как нет и функций по управлению ими. Области связи автоматически создаются и уничтожаются вместе с коммуникаторами. Абонентами одной области связи являются все задачи либо одной, либо двух групп.
Типичное использование:
MPI_Comm_group: Получаем описатель глобальной группы, содержащей все процессы из MPI_COMM_WORLD;
MPI_Group_incl: Формируем новую группу как подмножество глобальной группы;
MPI_Comm_create: Создаем новый коммуникатор для новой группы;
MPI_Comm_rank: Получаем новый номер rank процесса в новом коммуникаторе;
Выполняем передачу данных;
MPI_Comm_free и MPI_Group_free: Освобождаем описатели нового коммуникатора и новой группы;
Определение числа процессов в группе: MPI_Group_size(MPI_Group group, int *size),
Определение номера процесса в группе: MPI_Group_rank(MPI_Group group, int *rank).
Установка соответствия между номерами процессов в двух группах: MPI_Group_translate_ranks(MPI_Group group1, int n, int *ranks1, MPI_Group group2, int *ranks2).
ranks1 – массив номеров процессов из 1-й группы; ranks2 – номера тех же процессов во 2-ой группе.
28. Библиотека MPI. Проблемы использования различных типов данных. Пользовательские типы данныхСтандартные функции пересылки данных прекрасно обходятся без подобной информации – им требуется знать только размер в байтах. Вместо одного такого аргумента функции MPI получают два: количество элементов некоторого типа, и символический описатель указанного типа. Причин тому несколько:
1. MPI позволяет описывать пользовательские типы данных, которые располагаются в памяти не непрерывно, а с разрывами, или наоборот, с перехлестом. Переменная такого типа характеризуется не только размером, и эти характеристики MPI хранит в описателе типа.
2. Приложение MPI может работать на гетерогенном вычислительном комплексе (коллективе ЭВМ с разной архитектурой). Одни и те же типы данных на разных машинах могут иметь разное представление, например: на плавающую арифметику существует 3 разных стандарта (IEEE, IBM, Cray); тип char в терминальных приложениях Windows представлен альтернативной кодировкой ГОСТ, а в Unix - кодировкой KOI-8r; в многобайтовых числах на процессорах фирмы intel младший байт занимает младший адрес, на всех остальных – наоборот. Если приложение работает в гетерогенной сети, через сеть задачи обмениваются данными в формате XDR (eXternal Data Representation), принятом в Internet. Перед отправкой и после приема данных задача конвертирует их в/из XDR, при этом MPI должен знать количество передаваемых байт и тип содержимого.
3. Обязательным требованием к MPI была поддержка языка FORTRAN в силу его инерционной популярности. В этом языке тип CHARACTER требует особого обращения, поскольку переменная такого типа содержит не собственно текст, а адрес текста и его длину. Ошибка в указании типа приведет: при отправке – к копированию служебных данных вместо текста, при приеме – к записи текста на место служебных данных.
4. Такие часто используемые в С типы данных, как структуры, могут содержать в себе некоторое пустое пространство, чтобы все поля в переменной такого типа размещались по адресам, кратным некоторому четному числу (часто 2, 4 или 8) – это ускоряет обращение к ним. Причины тому чисто аппаратные. Выравнивание данных настраивается ключами компилятора. Разные задачи одного и того же приложения, выполняющиеся на одной и той же машине (даже на одном и том же процессоре), могут быть построены с разным выравниванием, и типы с одинаковым текстовым описанием будут иметь разное двоичное представление.
Пользовательские типы данных:Производный тип строится из предопределенных типов MPI и ранее определенных производных типов с помощью специальных функций-конструкторов MPI_Type_contiguous, MPI_Type_vector, MPI_Type_hvector, MPI_Type_indexed, MPI_Type_hindexed, MPI_Type_struct;
регистрируются вызовом функции MPI_Type_commit;
ненужные типы уничтожаются функцией MPI_Type_free;
Предопределенные типы MPI считаются зарегистрированными.
Характеристики типов:Протяженность типа – сколько байт переменная данного типа занимает в памяти (адрес последней ячейки данных - адрес первой ячейки данных + длина последней ячейки данных);
int MPI_Type_extent(MPI_Datatype datatype, MPI_Aint *extent);
размер типа определяет количество реально передаваемых байт в коммуникационных операциях;
Эта величина равна сумме длин всех базовых элементов определяемого типа опрашивается подпрограммой
int MPI_Type_size(MPI_Datatype datatype, int *size);
int MPI_Type_commit(MPI_Datatype *datatype);
int MPI_Type_free(MPI_Datatype *datatype);
Функция MPI_Type_free устанавливает описатель типа в состояние MPI_DATATYPE_NULL.
29. Библиотека MPI. Производные типы данных и передача упакованных данныхМеханизмы эффективной пересылки данные разных типов:создание производных типов для использования в коммуникационных операциях вместо предопределенных типов MPI;
пересылка упакованных данных (процесс-отправитель упаковывает пересылаемые данные перед их отправкой, а процесс-получатель распаковывает их после получения);
Производные типы данных:Производный тип строится из предопределенных типов MPI и ранее определенных производных типов с помощью специальных функций-конструкторов MPI_Type_contiguous, MPI_Type_vector, MPI_Type_hvector, MPI_Type_indexed, MPI_Type_hindexed, MPI_Type_struct;
регистрируются вызовом функции MPI_Type_commit;
ненужные типы уничтожаются функцией MPI_Type_free;
Предопределенные типы MPI считаются зарегистрированными.
Характеристики типов:Протяженность типа – сколько байт переменная данного типа занимает в памяти (адрес последней ячейки данных - адрес первой ячейки данных + длина последней ячейки данных);
int MPI_Type_extent(MPI_Datatype datatype, MPI_Aint *extent);
размер типа определяет количество реально передаваемых байт в коммуникационных операциях;
Эта величина равна сумме длин всех базовых элементов определяемого типа опрашивается подпрограммой
int MPI_Type_size(MPI_Datatype datatype, int *size);
int MPI_Type_commit(MPI_Datatype *datatype);
int MPI_Type_free(MPI_Datatype *datatype);
Функция MPI_Type_free устанавливает описатель типа в состояние MPI_DATATYPE_NULL.
Передача упакованных данных:int MPI_Pack(void* inbuf, int incount, MPI_Datatype datatype, void *outbuf, int outsize, int *position, MPI_Comm comm);
int MPI_Pack_size(int incount, MPI_Datatype datatype, MPI_Comm comm, int *size);
int MPI_Unpack(void* inbuf, int insize, int *position, void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm).
/* Упаковка данных */
if (myrank == 0) {position = 0;
MPI_Pack(&x, 1, MPI_DOUBLE, buff, 100, &position, MPI_COMM_WORLD);
MPI_Pack(&y, 1, MPI_DOUBLE, buff, 100, &position, MPI_COMM_WORLD);
MPI_Pack(a, 2, MPI_INT, buff, 100, &position, MPI_COMM_WORLD);
}
/* Рассылка упакованного сообщения */
MPI_Bcast(buff, position, MPI_PACKED, 0, MPI_COMM_WORLD);
/* Распаковка сообщения во всех процессах */
if (myrank != 0) {position = 0;
MPI_Unpack(buff, 100, &position, &x, 1, MPI_DOUBLE, MPI_COMM_WORLD);
MPI_Unpack(buff, 100, &position, &y, 1, MPI_DOUBLE, MPI_COMM_WORLD);
MPI_Unpack(buff, 100, &position, a, 2, MPI_INT, MPI_COMM_WORLD);}
Технология OpenMP. Стратегия подхода.OpenMP - это интерфейс прикладного программирования для создания многопоточных приложений, предназначенных в основном для параллельных вычислительных систем с общей памятью. Разработчики стандарта ARB (Architecture Board).
Основания для достижения эффекта – разделяемые для параллельных процессов данные располагаются в общей памяти, и для организации взаимодействия не требуется операций передачи сообщений.
Интерфейс OpenMP служит основой для формирования новой технологии параллельного программирования для систем с общей памятью (shared-memory programming).
Положительные стороны:
Поэтапное (инкрементальное) распараллеливание
Можно распараллеливать программы поэтапно, не меняя их структуру
Единственность разрабатываемого кода
Нет необходимости поддерживать последовательный и параллельный вариант программы, т.к. директивы игнорируются обычным компилятором
Эффективность
Учет и использование возможностей систем с общей памятью
Стандартизованность (переносимость), поддержка в наиболее
распространенных языках (C, Fortran) и платформах (Windows, Unix)
Принцип организации параллелизма:
Использование потоков (общее адресное пространство)
Пульсирующий («вилочный», fork-join) параллелизм
При выполнении обычного кода (вне параллельных областей) программа выполняется одним потоком (master thread)
При выполнении директивы #parallel происходит создание «команды» (team) потоков для параллельного выполнения вычислений
После выхода из области действия директивы #parallel происходит синхронизация, все потоки, кроме master, уничтожаются
Продолжается последовательное выполнение кода (до следующей директивы #parallel)
Структура:
Набор директив компилятора
Библиотека функций
Набор переменных окружения

Директивы OpenMP. Формат записи директив.Формат: # pragma omp имя_директивы [clause,…]
Пример: # pragma omp parallel default (shared) \
private (beta, pi)
Общий вид основных директив OpenMP на языке C/C++
# pragma omp parallel \
private (var1, var2, …) \
shared (var1, var2, …) \
firstprivate (var1, var2, …) \
lastprivate (var1, var2, …) \
copyin (var1, var2, …) \
reduction (operator: var1, var 2, …) \
if (expression) \
default (shared | none) \
{
[ Структурный блок программы]
В рассматриваемом фрагменте предложение OpenMP shared используется для описания общих переменных. Общие переменные позволяют организовать обмен данными между параллельными процессами в OpenMP. Предложение private используется для описания внутренних (локальных) переменных для каждого параллельного процесса. Предложение firstprivate применяется для описания внутренних переменных параллельных процессов, однако данные в эти переменные импортируются из главного потока.
Предложение reduction позволяет собрать вместе в главном потоке результаты вычислений частичных сумм, разностей и т. п. из параллельных потоков. Предложение if является условным оператором в параллельном блоке. И, наконец, предложение default определяет по умолчанию тип всех переменных в последующем параллельном структурном блоке программы. Символ \ - продолжение директивы на другой строке.
Структурный блок – последовательность инструкций с одной точкой входа в начале блока и с одной точкой выхода в конце блока.

Директивы OpenMP. Области видимости директив. Типы директив.Параллельное выполнение программы будет осуществляться не только для программного блока, непосредственно следующего за директивой parallel, но и для всех функций, вызываемых из этого блока (см. рис.). Для обозначения этих динамически-возникающих параллельно выполняемых участков программного кода в OpenMP используется понятие параллельных областей ( parallel region ).
Ряд директив OpenMP допускает использование как непосредственно в блоках директивы, так и в параллельных областях. Такие директивы носят наименование отделяемых директив ( orphaned directives ).
Параллельный фрагмент ( parallel construct ) - блок программы, управляемый директивой parallel ; именно параллельные фрагменты, совместно с параллельными областями, представляют параллельно-выполняемую часть программы;
Параллельная область ( parallel region ) - параллельно выполняемые участки программного кода, динамически-возникающие в результате вызова функций из параллельных фрагментов – см.рис.
Параллельная секция ( parallel section ) - часть параллельного фрагмента, выделяемая для параллельного выполнения при помощи директивы section.
Типы директив:
Определение параллельной области
Разделение работы
Синхронизация

Директивы OpenMP. Определение параллельной области.Директива parallel одна из основных. Правила, определяющие действия директивы:
Когда программа достигает директиву parallel, создается набор ( team ) из N потоков; исходный поток программы является основным потоком этого набора ( master thread ) и имеет номер 0.
Программный код блока, следующий за директивой, дублируется или может быть разделен при помощи директив между потоками для параллельного выполнения.
В конце программного блока директивы обеспечивается синхронизация потоков - выполняется ожидание окончания вычислений всех потоков; далее все потоки завершаются - дальнейшие вычисления продолжает выполнять только основной поток (в зависимости от среды реализации OpenMP потоки могут не завершаться, а приостанавливаться до начала следующего параллельного фрагмента - такой подход позволяет снизить затраты на создание и удаление потоков).
#pragma omp parallel [clause ...] newline
structured_block
clause
if (scalar_expression)private (list)
shared (list)
default (shared | none)
firstprivate (list)
reduction (operator: list)
copyin (list)
num_threads (scalar_expression)
Семантика parallel
Количество потоков (по убыванию старшинства)
omp_set_num_threads()
OMP_NUM_THREADS
Параметр реализации
Динамические потоки
По умолчанию количество потоков одинаковое – для активизации динамического режима функция omp_set_dynamic() или переменная OMP_DYNAMIC
Вложенность параллельных областей (во многих реализациях не обеспечивается)
по умолчанию во вложенной области создается один поток
управление – функция omp_set_nested() или переменная OMP_NESTED
Параметры (clause) – если условия в if не выполняются, то процессы не создаются.

Директивы OpenMP. Распределение вычислений по потокам.Существует 3 директивы для распределения вычислений в параллельной области:
DO/for – распараллеливание циклов
section – распараллеливание раздельных фрагментов кода (функциональное распараллеливание)
single – директива для указания последовательного выполнения кода
!Начало выполнения директив по умолчанию не синхронизируется, завершение директив по умолчанию является синхронным.
Директива DO/for распределение итераций цикла между потоками; параллельная область уже должна быть активна, иначе игнорируется.
# pragma omp for [clause ...] newline
for_loop
clause
schedule (type[,chunk])ordered
private (list)
firstprivate (list)
lastprivate (list)
shared (list)
reduction (operator: list)
nowait
Директива DO/for – распределение итераций регулируется параметром schedule.
static – итерации делятся на блоки по chunk итераций и статистически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно.
dynamic – распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1)
guided – размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1)
runtime – правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен)
Директива section – распределение вычислений для раздельных фрагментов кода
фрагменты выделяются при помощи директивы section
каждый фрагмент выполняется однократно
разные фрагменты выполняются разными потоками
завершение директивы по умолчанию синхронизируется
директивы section должны использоваться только в статическом контексте
# pragma omp section [clause ...] newline
{
# pragma omp section newline
structured_block
}
clause
firstprivate (list)
lastprivate (list)
reduction (operator: list)
nowait

Директива single – определение фрагмента кода, который должен быть выполнен только одним потоком; все остальные потоки ожидают завершения выполнения фрагмента (если не указан параметр nowait)
# pragma omp single [clause ...] newline
structured_block
clause
private (list)
firstprivate (list)
nowait

Директивы OpenMP. Синхронизация.master –определяет фрагмент кода , который должен быть выполнен только основным потоком; все остальные потоки пропускают данный фрагмент (завершение директивы по умолчанию не синхронизируется)
#pragma omp master newline
structured_block
critical – определяет фрагмент кода, который должен выполняться только одним потоком в каждый текущий момент времени (критическая секция)  При попытке входа в критическую секцию, которая уже исполняется одним из потоков используется, все другие потоки приостанавливаются ( блокируются ). Как только критическая секция освобождается, один из приостановленных потоков (если они имеются) активизируется для выполнения критической секции.
#pragma omp critical [name] newline
structured_block
Как можно заметить, критические секции могут быть именованными - можно рекомендовать активное использование данной возможности для разделения критических секций, т.к. это позволит уменьшить число блокировок процессов.
barrier – определяет точку синхронизации, которую должны достигнуть все процессы для продолжения вычислений (директива должна быть вложена в блок)
#pragma omp barrier newline
atomic – определяет переменную, доступ к которой (чтение/запись) должен быть выполнен как неделимая операция
#pragma omp atomic
statement_exrpession
Возможный формат записи выражения: x binop = expr, x++,++x,x--,--x
x должна быть скалярной переменной
expr не должна ссылаться на x
binop должна быть перегруженной операцией вида +,-,*,/,&,^,|,>>,<<
flush – определяет точку синхронизации, в которой системой должно быть обеспечено единое для всех процессов состояние памяти (т.е. если потоком какое-либо значение извлекалось из памяти для модификации, измененное значение обязательно должно быть записано в общую память)
#pragma omp flush (list) newline
Если указан список list, то восстанавливаются только указанные переменные.
Директива flush неявным образом присутствует в директивах barrier, critical, ordered, parallel, for, section, single
ordered – указывает фрагмент кода параллельного цикла, который должен выполняться точно в таком же порядке, как и при последовательном выполнении.
#pragma omp ordered newline
structured_block
В каждый момент в блоке ordered может находиться только один поток.
На одной итерации цикла может быть только одна директива ordered и эта директива может выполниться только однократно.
Цикл, в котором есть директива ordered, должен иметь параметр ordered
threadprivate – используется для создания поточных копий для глобальных переменных программы; созданные копии не видимы между потоками, но существуют все время выполнения программы
#pragma omp threadprivate (list)
Директивы OpenMP. Управление областью видимости данных.Общие (разделяемые между потоками, shared) переменные – static переменные с областью видимости в пределах файла.
Локальные (private) данные потоков – переменные циклы.
Управление областью видимости обеспечивается при помощи параметров (clauses) директив private, firstprivate, lastprivate, shared, default, reduction, copyin, которые определяют, какие соотношения существуют между переменными последовательных и параллельных фрагментов выполняемой программы.
shared – определяет список переменных, которые будут общими для всех потоков
параллельной области; правильность использования таких переменных должна обеспечиваться программистом.
shared (list)
private – определяет список переменных, которые будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным.
private(list)
firstprivate – позволяет создать локальные переменные потоков, которые перед использованием инициализируются значениями исходных переменных.
firstprivate (list)
lastprivate - позволяет создать локальные переменные потоков, значения которых запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию)
lastprivate (list)
copyin - позволяет выполнить инициализацию переменных директивы threadprivate
copyin (list)
default – устанавливает область видимости переменных по умолчанию
default (shared|none)
reduction – определяет список переменных, для которых выполняется операция редукции; перед выполнением параллельной области для каждого потока создаются копии этих переменных, потоки формируют значения в своих локальных переменных и при завершении параллельной области над всеми локальными значениями выполняются необходимые операции редукции, результаты которых запоминаются в исходных (глобальных) переменных
reduction (operator: list)
Возможный формат записи выражения: x = x op expr; x = expr op x; x binop = exrp; x++,++x,x--,--x
x должна быть скалярной переменной
expr не должна ссылаться на x
op (operator) должна быть перегруженной операцией вида +,-,*,/,&,^,|,&&,||
binop должна быть перегруженной операцией вида +,-,*,/,&,^,|

37. Библиотека функций OpenMP. Функции контроля параметров среды исполнения.Для задания переменных окружения можно воспользоваться командами операционной системы Linux или директивами OpenMP. Однако в OpenMP существует еще одна возможность задания переменных окружения: с помощью функций библиотеки runtime OpenMP. Обращение к этим функциям осуществляется непосредственно в программе и ничем не отличается от вызова обычных функций. Однако следует иметь в виду, что подобная возможность существует не во всех реализациях OpenMP.
В программах, написанных на C/C++ с использованием OpenMP, существуют следующие возможности задания переменных окружения с помощью средств библиотеки реального времени runtime OpenMP.
С помощью вызова функции
(void) omp_set_num_threads(int num_threads)
можно задать число потоков в области параллельных вычислений, т. е. определить значение переменной окружения OMP_NUM_THREADS. При завершении работы эта функция не возвращает в программу никаких значений.
Функция
int omp_get_num_threads()
напротив, возвращает в программу целочисленное значение, равное количеству параллельных потоков в текущий момент времени.
Следующая функция
int omp_get_max_threads()
возвращает в программу целочисленное значение, равное максимальному количеству параллельных потоков, которое может быть возвращено функцией omp_get_num_threads.
Для определения номера параллельного потока в текущий момент временипрограммы можно воспользоваться функцией
int_omp_get_thread_num()
Она возвращает целочисленное значение в диапазоне от 0 до OMP_NUM_THREADS-1.
Определить количество процессоров, доступных программе в текущей точке, можно с помощью функции
int omp_get_num_procs()
Следующая функция позволяет идентифицировать, в какой области программы (параллельной или последовательной) в текущий момент времени проводятся вычисления
(int/logical) omp_in_parallel()
Она возвращает значение TRUE или 1 в точке параллельной области программы и FALSE или 0 в точке последовательной области программы.
Задать или отменить динамический режим работы программы можно, воспользовавшись функцией
(void) omp_set_dynamic( TRUE | FALSE )
Для задания динамического режима следует использовать параметр TRUE, а для его отмены - параметр FALSE. При этом в списке переменных окружения определяется или удаляется переменная окружения
OMP_DYNAMIC или задается ее значение, соответственно равное TRUE или FALSE.
Следующая функция позволяет идентифицировать, какой режим работы параллельной части программы (динамический или статический) осуществляется в текущий момент времени при вызове функции
(int/logical) omp_get_dynamic()
Эта функция возвращает значение TRUE или 1, если режим динамический,и FALSE или 0 в случае статического режима.
Задать или отменить вложенный режим параллельной обработки процессов в параллельной области программы можно с помощью функции
(void) omp_set_nested( TRUE | FALSE )
Она устанавливает или отменяет вложенный режим параллельной обработки. При этом в списке переменных окружения определяется или удаляется переменная окружения OMP_NESTED либо задается ее значение, соответственно равное TRUE или FALSE.
Следующая функция позволяет идентифицировать, установлен или нет вложенный режим параллельной обработки в момент вызова функции
(int/logical) omp_get_nested()
Эта функция возвращает значение TRUE или 1 для вложенного режима параллельной обработки и значение FALSE или 0 при отсутствии такового.

38. Библиотека функций OpenMP. Функции синхронизации.Функции блокировки играют очень важную роль при написании параллельных программ. Для последовательных программ необходимость функций блокировки обусловлена в основном многопользовательскимрежимом, когда на одном процессоре одновременно могут выполняться несколько заданий различных пользователей. В такой ситуации очень важно обеспечить корректный доступ к данным и их корректную модификацию со стороны различных задач или пользователей. В параллельном программировании даже одно задание порождает несколько параллельных процессов, каждый из которых может оперировать с одними и теми же данными. Для обеспечения корректности доступа к данным и их корректной модификации в OpenMP существуют специальные функции блокировки, обеспечивающие решение задач корректности доступа, записи и обновления данных.
Сначала рассмотрим функции блокировки в OpenMP в программах, написанных на языке C/C++.
Функция
void omp_init_lock ( omp_lock_t *lock )
предназначена для инициализации блокировки объекта с указателем lock.
Она не возвращает никаких значений.
Следующая функция
void omp_destroy_lock ( omp_lock_t *lock )
гарантирует, что объект с указателем lock в данный момент неинициализирован.
С помощью функции
void omp_set_lock ( omp_lock_t *lock )
можно организовать блокировку выполнения потока до тех пор, пока объект открыт для операций чтения-записи. После завершения операций чтения-записи объект блокируется и продолжается выполнение потока. Для открытия заблокированного объекта с указателем lock можно воспользоваться функцией
void omp_unset_lock ( omp_lock_t *lock )
Функция
int omp_test_lock ( omp_lock_t *lock )
позволяет попытаться заблокировать объект, не прерывая выполнения потока. Она возвращает значение TRUE или 1, если попытка завершилась успешно. В противном случае возвращается значение FALSE или 0. Напомним, что при обращении к функциям блокировки в заголовке текста программы должно содержаться включение описания этих функций:
39. Технология OpenMP. Переменные среды исполнения.OpenMP включает следующие переменные среды. Эти переменные среды считываются при запуске программы.
OMP_SCHEDULE
Распределение порций итераций по потокам (или процессорам) определяется значением переменной окружения OMP_SCHEDULE. Значение этой переменной проверяется перед каждым распределением итераций по потокам во время работы программы.
OMP_NUM_THREADS
Определяет число нитей для исполнения параллельных областей приложения.
Количество потоков в параллельной программе определяется либо значением переменной окружения OMP_NUM_THREADS, либо специальными функциями, вызываемыми внутри самой программы.
OMP_DYNAMIC
Разрешает или запрещает динамическое изменение числа нитей. В динамическом режиме (OMP_DYNAMIC = TRUE) [так по умолчанию] количество потоков определяется самой операционной системой в соответствии со значением переменной окружения OMP_NUM_THREADS. В процессе выполнения параллельной программы при переходе от одной области распараллеливания к другой эта переменная может изменять свое значение;
OMP_NESTED
Разрешает или запрещает вложенный параллелизм.
Параллельные структурные блоки могут быть вложенными, но компилятор иногда по ряду причин может выполнять их и последовательно в рамках одного потока. Вложенный режим выполнения параллельных структурных блоков определяется заданием переменной окружения OMP_NESTED=[FALSE|TRUE] (по умолчанию задается FALSE) в операционной системе Linux.

Приложенные файлы

  • docx 24016940
    Размер файла: 509 kB Загрузок: 0

Добавить комментарий