Машины с параллельным произвольным доступом

Parallel Random Access Machines (PRAM)- это модель, которая рассматривается для большинства параллельных алгоритмов. Здесь к одному блоку памяти подключено несколько процессоров. Модель PRAM содержит -

Набор однотипных процессоров.
Все процессоры используют общий блок памяти. Процессоры могут взаимодействовать между собой только через общую память.
Блок доступа к памяти (MAU) соединяет процессоры с единой общей памятью.

Вот, n количество процессоров может выполнять независимые операции на nколичество данных в определенную единицу времени. Это может привести к одновременному доступу к одному и тому же участку памяти разными процессорами.

Чтобы решить эту проблему, в модели PRAM были наложены следующие ограничения:

Exclusive Read Exclusive Write (EREW) - Здесь нет двух процессоров, которым разрешено читать или записывать в одну и ту же ячейку памяти одновременно.
Exclusive Read Concurrent Write (ERCW) - Здесь никаким двум процессорам не разрешено одновременное чтение из одной и той же области памяти, но разрешено одновременную запись в одну и ту же область памяти.
Concurrent Read Exclusive Write (CREW) - Здесь всем процессорам разрешено одновременное чтение из одной и той же области памяти, но не разрешается одновременная запись в одну и ту же область памяти.
Concurrent Read Concurrent Write (CRCW) - Всем процессорам разрешено читать или записывать в одну и ту же ячейку памяти одновременно.

Есть много методов для реализации модели PRAM, но самые известные из них -

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

Модель общей памяти

Общая память подчеркивает control parallelism чем на data parallelism. В модели с общей памятью несколько процессов выполняются на разных процессорах независимо, но используют общее пространство памяти. Из-за какой-либо активности процессора, если есть какие-либо изменения в какой-либо области памяти, они видны остальным процессорам.

Поскольку несколько процессоров обращаются к одному и тому же участку памяти, может случиться так, что в любой конкретный момент времени более одного процессора обращаются к одному и тому же участку памяти. Предположим, что один читает это место, а другой пишет в этом месте. Это может создать путаницу. Чтобы этого избежать, некоторые механизмы контроля, напримерlock / semaphore, реализован для обеспечения взаимного исключения.

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

Thread libraries- Библиотека потоков допускает одновременное выполнение нескольких потоков управления в одной и той же области памяти. Библиотека потоков предоставляет интерфейс, который поддерживает многопоточность через библиотеку подпрограмм. Он содержит подпрограммы для
- Создание и уничтожение потоков
- Планирование выполнения потока
- передача данных и сообщений между потоками
- сохранение и восстановление контекстов потоков

Примеры библиотек потоков включают: потоки SolarisTM для Solaris, потоки POSIX, реализованные в Linux, потоки Win32, доступные в Windows NT и Windows 2000, и потоки JavaTM как часть стандартного комплекта разработки JavaTM (JDK).

Distributed Shared Memory (DSM) Systems- Системы DSM создают абстракцию совместно используемой памяти на слабосвязанной архитектуре для реализации программирования совместно используемой памяти без аппаратной поддержки. Они реализуют стандартные библиотеки и используют расширенные функции управления памятью на уровне пользователя, имеющиеся в современных операционных системах. Примеры включают систему маркировки протектора, Munin, IVY, Shasta, Brazos и Cashmere.
Program Annotation Packages- Это реализовано на архитектурах с одинаковыми характеристиками доступа к памяти. Наиболее ярким примером пакетов аннотаций программ является OpenMP. OpenMP реализует функциональный параллелизм. В основном он фокусируется на распараллеливании циклов.

Концепция общей памяти обеспечивает низкоуровневый контроль над системой общей памяти, но, как правило, утомительна и ошибочна. Он больше подходит для системного программирования, чем для прикладного программирования.

Достоинства программирования с общей памятью

Глобальное адресное пространство обеспечивает удобный подход к программированию памяти.
Благодаря близости памяти к ЦП обмен данными между процессами происходит быстро и единообразно.
Нет необходимости четко указывать обмен данными между процессами.
Накладные расходы на коммуникацию процесса незначительны.
Учиться очень легко.

Недостатки программирования с общей памятью

Он не переносится.
Управлять местонахождением данных очень сложно.

Модель передачи сообщений

Передача сообщений - это наиболее часто используемый подход параллельного программирования в системах с распределенной памятью. Здесь программист должен определить параллелизм. В этой модели все процессоры имеют свой собственный блок локальной памяти и обмениваются данными через сеть связи.

Процессоры используют библиотеки передачи сообщений для связи между собой. Помимо отправляемых данных, сообщение содержит следующие компоненты:

Адрес процессора, с которого отправляется сообщение;
Начальный адрес ячейки памяти данных в процессоре-отправителе;
Тип данных отправляемых данных;
Размер отправляемых данных;
Адрес процессора, которому отправляется сообщение;
Начальный адрес ячейки памяти для данных в принимающем процессоре.

Процессоры могут связываться друг с другом любым из следующих способов:

Двухточечная связь
Коллективное общение
Интерфейс передачи сообщений

Двухточечная связь

Связь точка-точка - это простейшая форма передачи сообщений. Здесь сообщение может быть отправлено от отправляющего процессора к принимающему процессору в любом из следующих режимов передачи:

Synchronous mode - Следующее сообщение отправляется только после получения подтверждения, что его предыдущее сообщение было доставлено, чтобы поддерживать последовательность сообщения.
Asynchronous mode - Для отправки следующего сообщения получение подтверждения доставки предыдущего сообщения не требуется.

Коллективное общение

Коллективное общение включает более двух процессоров для передачи сообщений. Следующие режимы позволяют коллективное общение -

Barrier - Барьерный режим возможен, если все процессоры, участвующие в обмене данными, работают с определенным блоком (известным как barrier block) для передачи сообщений.
Broadcast - Вещание бывает двух видов -
- One-to-all - Здесь один процессор с одной операцией отправляет одно и то же сообщение всем другим процессорам.
- All-to-all - Здесь все процессоры отправляют сообщение всем другим процессорам.

Транслируемые сообщения могут быть трех типов:

Personalized - Уникальные сообщения отправляются всем остальным процессорам назначения.
Non-personalized - Все процессоры назначения получают одно и то же сообщение.
Reduction - При сокращенной трансляции один процессор группы собирает все сообщения от всех других процессоров в группе и объединяет их в одно сообщение, к которому все остальные процессоры в группе могут получить доступ.

Достоинства передачи сообщений

Обеспечивает низкоуровневый контроль параллелизма;
Это портативный;
Меньше ошибок;
Меньше накладных расходов при параллельной синхронизации и распределении данных.

Недостатки передачи сообщений

По сравнению с параллельным кодом с общей памятью, код передачи сообщений обычно требует больших затрат на программное обеспечение.

Библиотеки передачи сообщений

Есть много библиотек для передачи сообщений. Здесь мы обсудим две из наиболее часто используемых библиотек передачи сообщений:

Интерфейс передачи сообщений (MPI)
Параллельная виртуальная машина (PVM)

Интерфейс передачи сообщений (MPI)

Это универсальный стандарт для обеспечения связи между всеми параллельными процессами в системе с распределенной памятью. Большинство обычно используемых платформ параллельных вычислений предоставляют по крайней мере одну реализацию интерфейса передачи сообщений. Он был реализован в виде набора предопределенных функций, называемыхlibrary и могут вызываться из таких языков, как C, C ++, Fortran и т. д. MPI быстрые и переносимые по сравнению с другими библиотеками передачи сообщений.

Merits of Message Passing Interface

Работает только на архитектурах с общей памятью или архитектурах с распределенной памятью;
У каждого процессора есть свои локальные переменные;
По сравнению с большими компьютерами с общей памятью, компьютеры с распределенной памятью менее дороги.

Demerits of Message Passing Interface

Для параллельного алгоритма требуется больше изменений в программировании;
Иногда сложно отлаживать; и
Плохо работает в сети связи между узлами.

Параллельная виртуальная машина (PVM)

PVM - это портативная система передачи сообщений, предназначенная для соединения отдельных разнородных хост-машин в единую виртуальную машину. Это единый управляемый параллельный вычислительный ресурс. Большие вычислительные задачи, такие как исследования сверхпроводимости, моделирование молекулярной динамики и матричные алгоритмы, могут быть решены более экономически эффективно за счет использования памяти и совокупной мощности многих компьютеров. Он управляет всей маршрутизацией сообщений, преобразованием данных, планированием задач в сети несовместимых компьютерных архитектур.

Features of PVM

Очень проста в установке и настройке;
PVM могут использовать несколько пользователей одновременно;
Один пользователь может выполнять несколько приложений;
Это небольшой пакет;
Поддерживает C, C ++, Fortran;
Для данного запуска программы PVM пользователи могут выбрать группу машин;
Это модель передачи сообщений,
Расчет на основе процессов;
Поддерживает гетерогенную архитектуру.

Параллельное программирование данных

Основное внимание в модели параллельного программирования данных уделяется одновременному выполнению операций с набором данных. Набор данных организован в некоторую структуру, такую как массив, гиперкуб и т. Д. Процессоры совместно выполняют операции с одной и той же структурой данных. Каждая задача выполняется на разных разделах одной и той же структуры данных.

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

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