Параллельные машины произвольного доступа (PRAM) — это модель, которая рассматривается для большинства параллельных алгоритмов. Здесь несколько процессоров подключены к одному блоку памяти. Модель PRAM содержит —
-
Набор процессоров аналогичного типа.
-
Все процессоры имеют общий блок памяти. Процессоры могут общаться между собой только через общую память.
-
Блок доступа к памяти (MAU) соединяет процессоры с одной общей памятью.
Набор процессоров аналогичного типа.
Все процессоры имеют общий блок памяти. Процессоры могут общаться между собой только через общую память.
Блок доступа к памяти (MAU) соединяет процессоры с одной общей памятью.
Здесь n числа процессоров могут выполнять независимые операции над n количеством данных в конкретную единицу времени. Это может привести к одновременному доступу к одной и той же ячейке памяти разными процессорами.
Для решения этой проблемы на модель PRAM были наложены следующие ограничения:
-
Эксклюзивная чтение Эксклюзивная запись (EREW). Здесь нет двух процессоров, которые могут одновременно считывать или записывать данные в одну и ту же область памяти.
-
Exclusive Read Concurrent Write (ERCW) — здесь двум процессорам не разрешено читать из одной и той же области памяти одновременно, но разрешено выполнять запись в одну и ту же область памяти одновременно.
-
Одновременная запись с эксклюзивным чтением (CREW) — здесь всем процессорам разрешено выполнять чтение из одной и той же области памяти в одно и то же время, но не разрешено выполнять запись в одну и ту же область памяти в одно и то же время.
-
Одновременное чтение Одновременная запись (CRCW) — всем процессорам разрешено выполнять чтение или запись в одну и ту же ячейку памяти одновременно.
Эксклюзивная чтение Эксклюзивная запись (EREW). Здесь нет двух процессоров, которые могут одновременно считывать или записывать данные в одну и ту же область памяти.
Exclusive Read Concurrent Write (ERCW) — здесь двум процессорам не разрешено читать из одной и той же области памяти одновременно, но разрешено выполнять запись в одну и ту же область памяти одновременно.
Одновременная запись с эксклюзивным чтением (CREW) — здесь всем процессорам разрешено выполнять чтение из одной и той же области памяти в одно и то же время, но не разрешено выполнять запись в одну и ту же область памяти в одно и то же время.
Одновременное чтение Одновременная запись (CRCW) — всем процессорам разрешено выполнять чтение или запись в одну и ту же ячейку памяти одновременно.
Существует много методов для реализации модели PRAM, но наиболее выдающимися являются:
- Модель с общей памятью
- Модель передачи сообщений
- Параллельная модель данных
Модель общей памяти
Общая память делает упор на параллелизм управления, а не на параллелизм данных . В модели с общей памятью несколько процессов выполняются на разных процессорах независимо, но они совместно используют общее пространство памяти. Из-за какой-либо активности процессора, если есть какое-либо изменение в какой-либо области памяти, это видно остальным процессорам.
Поскольку несколько процессоров обращаются к одной и той же ячейке памяти, может случиться так, что в любой конкретный момент времени более одного процессора обращаются к одной и той же ячейке памяти. Предположим, что один читает это местоположение, а другой пишет в этом месте. Это может создать путаницу. Чтобы избежать этого, для обеспечения взаимного исключения реализован некоторый механизм управления, такой как блокировка / семафор .
Программирование общей памяти было реализовано следующим образом:
-
Библиотеки потоков. Библиотека потоков позволяет нескольким элементам управления одновременно работать в одной и той же области памяти. Библиотека потоков предоставляет интерфейс, который поддерживает многопоточность через библиотеку подпрограмм. Содержит подпрограммы для
- Создание и уничтожение потоков
- Планирование выполнения потока
- передача данных и сообщений между потоками
- сохранение и восстановление контекстов потока
Библиотеки потоков. Библиотека потоков позволяет нескольким элементам управления одновременно работать в одной и той же области памяти. Библиотека потоков предоставляет интерфейс, который поддерживает многопоточность через библиотеку подпрограмм. Содержит подпрограммы для
Примеры библиотек потоков: потоки SolarisTM для Solaris, потоки POSIX, реализованные в Linux, потоки Win32, доступные в Windows NT и Windows 2000, и потоки JavaTM как часть стандартного комплекта разработки JavaTM (JDK).
-
Системы с распределенной общей памятью (DSM) — системы DSM создают абстракцию совместно используемой памяти в слабо связанной архитектуре для реализации программирования совместно используемой памяти без аппаратной поддержки. Они реализуют стандартные библиотеки и используют расширенные функции управления памятью на уровне пользователя, имеющиеся в современных операционных системах. Примерами являются система протекторов, Munin, IVY, Shasta, Brazos и Cashmere.
-
Пакеты аннотаций программы — это реализовано на архитектурах, имеющих одинаковые характеристики доступа к памяти. Наиболее ярким примером пакетов аннотаций программ является OpenMP. OpenMP реализует функциональный параллелизм. Основное внимание уделяется распараллеливанию циклов.
Системы с распределенной общей памятью (DSM) — системы DSM создают абстракцию совместно используемой памяти в слабо связанной архитектуре для реализации программирования совместно используемой памяти без аппаратной поддержки. Они реализуют стандартные библиотеки и используют расширенные функции управления памятью на уровне пользователя, имеющиеся в современных операционных системах. Примерами являются система протекторов, Munin, IVY, Shasta, Brazos и Cashmere.
Пакеты аннотаций программы — это реализовано на архитектурах, имеющих одинаковые характеристики доступа к памяти. Наиболее ярким примером пакетов аннотаций программ является OpenMP. OpenMP реализует функциональный параллелизм. Основное внимание уделяется распараллеливанию циклов.
Концепция разделяемой памяти обеспечивает низкоуровневое управление системой разделяемой памяти, но, как правило, она утомительна и ошибочна. Это более применимо для системного программирования, чем прикладное программирование.
Преимущества совместного использования памяти
-
Глобальное адресное пространство дает удобный для пользователя подход к программированию памяти.
-
Благодаря близости памяти к процессору, обмен данными между процессами происходит быстро и равномерно.
-
Нет необходимости четко определять передачу данных между процессами.
-
Затраты на процесс-коммуникацию незначительны.
-
Это очень легко учиться.
Глобальное адресное пространство дает удобный для пользователя подход к программированию памяти.
Благодаря близости памяти к процессору, обмен данными между процессами происходит быстро и равномерно.
Нет необходимости четко определять передачу данных между процессами.
Затраты на процесс-коммуникацию незначительны.
Это очень легко учиться.
Недостатки совместного использования памяти
- Это не портативный.
- Управление локальностью данных очень сложно.
Модель передачи сообщений
Передача сообщений является наиболее часто используемым подходом параллельного программирования в системах с распределенной памятью. Здесь программист должен определить параллелизм. В этой модели все процессоры имеют свой собственный локальный блок памяти и обмениваются данными через сеть связи.
Процессоры используют библиотеки передачи сообщений для связи между собой. Помимо отправляемых данных, сообщение содержит следующие компоненты:
-
Адрес процессора, с которого отправляется сообщение;
-
Начальный адрес ячейки памяти данных в отправляющем процессоре;
-
Тип данных отправляемых данных;
-
Размер данных отправляемых данных;
-
Адрес процессора, на который отправляется сообщение;
-
Начальный адрес ячейки памяти для данных в принимающем процессоре.
Адрес процессора, с которого отправляется сообщение;
Начальный адрес ячейки памяти данных в отправляющем процессоре;
Тип данных отправляемых данных;
Размер данных отправляемых данных;
Адрес процессора, на который отправляется сообщение;
Начальный адрес ячейки памяти для данных в принимающем процессоре.
Процессоры могут общаться друг с другом любым из следующих способов:
- Двухточечная связь
- Коллективное общение
- Интерфейс передачи сообщений
Двухточечная связь
Двухточечная связь — это самая простая форма передачи сообщений. Здесь сообщение может быть отправлено с отправляющего процессора на принимающий процессор с помощью любого из следующих режимов передачи:
-
Синхронный режим — следующее сообщение отправляется только после получения подтверждения того, что его предыдущее сообщение было доставлено, для поддержания последовательности сообщения.
-
Асинхронный режим — для отправки следующего сообщения получение подтверждения доставки предыдущего сообщения не требуется.
Синхронный режим — следующее сообщение отправляется только после получения подтверждения того, что его предыдущее сообщение было доставлено, для поддержания последовательности сообщения.
Асинхронный режим — для отправки следующего сообщения получение подтверждения доставки предыдущего сообщения не требуется.
Коллективное общение
Коллективное общение включает в себя более двух процессоров для передачи сообщений. Следующие режимы позволяют коллективные коммуникации —
-
Барьер — Барьерный режим возможен, если все процессоры, включенные в коммуникацию, запускают определенный блок (известный как барьерный блок ) для передачи сообщений.
-
Вещание — Вещание бывает двух типов —
-
One-to-all — Здесь один процессор с одной операцией отправляет одно и то же сообщение всем другим процессорам.
-
All-to-all — Здесь все процессоры отправляют сообщения всем остальным процессорам.
-
Барьер — Барьерный режим возможен, если все процессоры, включенные в коммуникацию, запускают определенный блок (известный как барьерный блок ) для передачи сообщений.
Вещание — Вещание бывает двух типов —
One-to-all — Здесь один процессор с одной операцией отправляет одно и то же сообщение всем другим процессорам.
All-to-all — Здесь все процессоры отправляют сообщения всем остальным процессорам.
Передаваемые сообщения могут быть трех типов:
-
Персонализированные — уникальные сообщения отправляются всем другим процессорам назначения.
-
Неперсонализированный — все процессоры назначения получают одно и то же сообщение.
-
Сокращение — при сокращенном широковещании один процессор группы собирает все сообщения от всех других процессоров в группе и объединяет их в одно сообщение, к которому могут обращаться все остальные процессоры в группе.
Персонализированные — уникальные сообщения отправляются всем другим процессорам назначения.
Неперсонализированный — все процессоры назначения получают одно и то же сообщение.
Сокращение — при сокращенном широковещании один процессор группы собирает все сообщения от всех других процессоров в группе и объединяет их в одно сообщение, к которому могут обращаться все остальные процессоры в группе.
Преимущества передачи сообщений
- Обеспечивает низкоуровневое управление параллелизмом;
- Это портативный;
- Меньше ошибок;
- Меньше накладных расходов при параллельной синхронизации и распределении данных.
Недостатки передачи сообщений
-
По сравнению с параллельным кодом совместно используемой памяти для кода передачи сообщений обычно требуется больше программных издержек.
По сравнению с параллельным кодом совместно используемой памяти для кода передачи сообщений обычно требуется больше программных издержек.
Библиотеки передачи сообщений
Есть много библиотек для передачи сообщений. Здесь мы обсудим две наиболее часто используемые библиотеки для передачи сообщений —
- Интерфейс передачи сообщений (MPI)
- Параллельная виртуальная машина (PVM)
Интерфейс передачи сообщений (MPI)
Это универсальный стандарт для обеспечения связи между всеми параллельными процессами в системе распределенной памяти. Большинство обычно используемых параллельных вычислительных платформ обеспечивают по крайней мере одну реализацию интерфейса передачи сообщений. Он был реализован как набор предопределенных функций, называемых библиотекой, и может вызываться из таких языков, как C, C ++, Fortran и т. Д. MPI являются быстрыми и переносимыми по сравнению с другими библиотеками передачи сообщений.
Преимущества интерфейса передачи сообщений
-
Работает только на архитектурах с общей памятью или архитектурах с распределенной памятью;
-
Каждый процессор имеет свои локальные переменные;
-
По сравнению с большими компьютерами с общей памятью компьютеры с распределенной памятью дешевле.
Работает только на архитектурах с общей памятью или архитектурах с распределенной памятью;
Каждый процессор имеет свои локальные переменные;
По сравнению с большими компьютерами с общей памятью компьютеры с распределенной памятью дешевле.
Недостатки интерфейса передачи сообщений
- Для параллельного алгоритма требуется больше программных изменений;
- Иногда трудно отладить; а также
- Не работает хорошо в сети связи между узлами.
Параллельная виртуальная машина (PVM)
PVM — это портативная система передачи сообщений, предназначенная для соединения отдельных разнородных хост-машин в единую виртуальную машину. Это единый управляемый ресурс параллельных вычислений. Большие вычислительные проблемы, такие как исследования сверхпроводимости, моделирование молекулярной динамики и матричные алгоритмы, могут быть решены более экономически эффективно с использованием памяти и совокупной мощности многих компьютеров. Он управляет всеми маршрутизацией сообщений, преобразованием данных, планированием задач в сети несовместимых компьютерных архитектур.
Особенности PVM
- Очень прост в установке и настройке;
- Несколько пользователей могут использовать PVM одновременно;
- Один пользователь может выполнять несколько приложений;
- Это небольшой пакет;
- Поддерживает C, C ++, Fortran;
- Для данного запуска программы PVM пользователи могут выбрать группу машин;
- Это модель передачи сообщений,
- Процессные вычисления;
- Поддерживает гетерогенную архитектуру.
Параллельное программирование данных
Основное внимание в модели параллельного программирования данных уделяется одновременному выполнению операций над набором данных. Набор данных организован в некоторую структуру, такую как массив, гиперкуб и т. Д. Процессоры совместно выполняют операции над одной и той же структурой данных. Каждая задача выполняется в отдельном разделе с одинаковой структурой данных.
Это ограничение, так как не все алгоритмы могут быть определены с точки зрения параллелизма данных. Это причина, почему параллелизм данных не является универсальным.
Языки параллельных данных помогают определить декомпозицию и отображение данных на процессоры. Он также включает в себя операторы распределения данных, которые позволяют программисту контролировать данные — например, какие данные будут поступать на какой процессор — чтобы уменьшить объем связи внутри процессоров.