Параллельная ОЗУ

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

В информатике параллельная машина с произвольным доступом ( параллельное ОЗУ или PRAM ) — это абстрактная машина с общей памятью . Как следует из названия, PRAM представляет собой аналогию параллельных вычислений машине с произвольным доступом (RAM) (не путать с оперативной памятью ). ^[1] Точно так же, как ОЗУ используется разработчиками последовательных алгоритмов для моделирования производительности алгоритмов (например, временной сложности), PRAM используется разработчиками параллельных алгоритмов для моделирования производительности параллельных алгоритмов (например, временной сложности, когда обычно также указывается предполагаемое количество процессоров). Подобно тому, как модель RAM игнорирует практические вопросы, такие как время доступа к кэш-памяти по сравнению с основной памятью, модель PRAM игнорирует такие проблемы, как синхронизация и связь , но обеспечивает любое (зависящее от размера задачи) количество процессоров. Например, стоимость алгоритма оценивается с использованием двух параметров O(время) и O(время × номер_процессора).

Конфликты чтения/записи

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

1. Эксклюзивное чтение и эксклюзивная запись (EREW) — каждая ячейка памяти может быть прочитана или записана только одним процессором одновременно.
2. Одновременное чтение и эксклюзивная запись (CREW) — несколько процессоров могут читать ячейку памяти, но только один может записывать одновременно.
3. Эксклюзивное чтение с одновременной записью (ERCW) — обычно никогда не рассматривается, поскольку в большинстве случаев не увеличивает мощность ^[2]
4. Одновременное чтение и одновременная запись (CRCW) — чтение и запись могут выполняться несколькими процессорами. CRCW PRAM иногда называют параллельной машиной произвольного доступа . ^[3]

Здесь E и C означают «эксклюзивный» и «параллельный» соответственно. Чтение не вызывает расхождений, в то время как параллельная запись далее определяется как:

Общий — все процессоры записывают одно и то же значение; иначе незаконно

Произвольный — только одна произвольная попытка успешна, остальные удаляются.

Приоритет — ранг процессора указывает, кто имеет право писать.

Другой вид операции сокращения массива, такой как СУММ, логическое И или МАКС.

При рассмотрении разработки алгоритмов для PRAM делается несколько упрощающих предположений. Они есть:

1. Ограничений на количество процессоров в машине нет.
2. Любая ячейка памяти одинаково доступна из любого процессора.
3. Ограничений на объем общей памяти в системе нет.
4. Конфликт за ресурсы отсутствует.
5. Программы, написанные на этих машинах, обычно относятся к типу SIMD .

Подобные алгоритмы полезны для понимания использования параллелизма, разделения исходной проблемы на схожие подзадачи и их параллельного решения. Введение формальной модели P-RAM в диссертации Уилли 1979 года ^[4] имело целью количественную оценку анализа параллельных алгоритмов способом, аналогичным машине Тьюринга . Анализ был сосредоточен на модели программирования MIMD с использованием модели CREW, но показал, что многие варианты, включая реализацию модели CRCW и реализацию на машине SIMD, были возможны только с постоянными накладными расходами.

Выполнение

Алгоритмы PRAM не могут быть распараллелены с помощью комбинации ЦП и динамической оперативной памяти (DRAM), поскольку DRAM не обеспечивает одновременный доступ к одному банку (даже к разным адресам в банке); но они могут быть реализованы аппаратно или выполнять чтение/запись во внутренние блоки статической оперативной памяти (SRAM) программируемой вентильной матрицы (FPGA), это можно сделать с использованием алгоритма CRCW.

Однако проверка практической значимости алгоритмов PRAM (или RAM) зависит от того, обеспечивает ли их модель стоимости эффективную абстракцию какого-либо компьютера; структура этого компьютера может сильно отличаться от абстрактной модели. Знание слоев программного и аппаратного обеспечения, которые необходимо вставить, выходит за рамки этой статьи. Но такие статьи, как Vishkin (2011), демонстрируют, как абстракция, подобная PRAM, может поддерживаться парадигмой явной многопоточности (XMT), а такие статьи, как Caragea & Vishkin (2011), демонстрируют, что алгоритм PRAM для задачи максимального потока может обеспечить значительное ускорение по сравнению с самой быстрой последовательной программой для той же задачи. В статье Ганим, Вишкин и Баруа (2018) показано, что алгоритмы PRAM сами по себе могут достичь конкурентоспособной производительности даже без каких-либо дополнительных усилий по преобразованию их в многопоточные программы на XMT.

Пример кода

Это пример кода SystemVerilog , который находит максимальное значение в массиве всего за 2 такта. Он сравнивает все комбинации элементов массива на первом такте и объединяет результат на втором такте. Он использует память CRCW; m[i] <= 1и maxNo <= data[i]пишутся одновременно. Параллелизм не вызывает конфликтов, поскольку алгоритм гарантирует, что одно и то же значение записывается в одну и ту же память. Этот код можно запустить на оборудовании FPGA .

модуль FindMax #( параметр int len ​​= 8 ) ( входной бит тактовой частоты , сбросN , входной бит [ 7 : 0 ] данных [ len ], выходной бит [ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARE , MERGE , DONE } State ; Государство государство ; бит м [ лен ]; интервал я , j ; Always_ff @( posege clock , negedge resetN ) begin if ( ! resetN ) begin for ( i = 0 ; i < len ; i ++ ) m [ i ] <= 0 ; состояние <= СРАВНИТЬ ; конец еще начало регистр ( состояние ) СРАВНЕНИЕ: начало для ( я = 0 ; я < длина ; я ++ ) начало для ( j = 0 ; j < длина ; j ++ ) начало если ( данные [ я ] < данные [ j ]) м [ я ] <= 1 ; конец конечного состояния <= MERGE ; end MERGE: начать for ( i = 0 ; i < len ; i ++ ) начать if ( m [ i ] == 0 ) maxNo <= data                                                                                                                [ я ]; конечное состояние <= ГОТОВО ; конец конца корпуса конец конца модуля        

Смотрите также

• Анализ алгоритмов PRAM
• Таксономия Флинна
• Алгоритмы без блокировки и без ожидания
• Машина произвольного доступа
• Модель параллельного программирования
• ХМТС
• Параллельная внешняя память (модель)

Рекомендации

1. Фортуна, Стивен; Уилли, Джеймс (1 мая 1978 г.). «Параллелизм в машинах с произвольным доступом». Материалы десятого ежегодного симпозиума ACM по теории вычислений . СТОК '78. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 114–118. дои : 10.1145/800133.804339. hdl : 1813/7454 . ISBN 978-1-4503-7437-8.
2. Маккензи, Филип Д.; Рамачандран, Виджая (6 апреля 1998 г.). «ERCW PRAM и оптическая связь». Теоретическая информатика . 196 (1): 153–180. дои : 10.1016/S0304-3975(97)00199-0. ISSN  0304-3975.
3. Нил Иммерман, Выразимость и параллельная сложность . SIAM Journal on Computing, том. 18, нет. 3, стр. 625–638, 1989.
4. Уилли, Джеймс К. Сложность параллельных вычислений, докторская диссертация, факультет компьютерных наук, Корнельский университет

• Эппштейн, Дэвид; Галил, Цви (1988), «Параллельные алгоритмические методы для комбинаторных вычислений», Annu. Ред. Компьютер. наук. , 3 : 233–283, doi : 10.1146/annurev.cs.03.060188.001313
• ДжаДжа, Джозеф (1992), Введение в параллельные алгоритмы , Аддисон-Уэсли, ISBN 0-201-54856-9
• Карп, Ричард М.; Рамачандран, Виджая (1988), Обзор параллельных алгоритмов для машин с общей памятью, Калифорнийский университет, Беркли, факультет EECS, Tech. Реп. UCB/CSD-88-408
• Келлер, Йорг; Кристоф Кесслер; Йеспер Трефф (2001). Практическое программирование PRAM . Джон Уайли и сыновья. ISBN 0-471-35351-5.
• Вишкин, Узи (2009), Параллельное мышление: некоторые базовые алгоритмы и методы параллельного анализа данных, 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технион
• Вишкин, Узи (2011), «Использование простой абстракции для нового изобретения вычислений для параллелизма», Communications of the ACM , 54 : 75–85, doi : 10.1145/1866739.1866757
• Карагеа, Джордж Константин; Вишкин, Узи (2011), «Краткое объявление: лучшее ускорение для параллельного максимального потока», Материалы 23-го симпозиума ACM по параллелизму в алгоритмах и архитектурах - SPAA '11 , стр. 131, номер домена : 10.1145/1989493.1989511, ISBN 9781450307437, S2CID  5511743
• Ганим, Фади; Вишкин, Узи; Баруа, Раджив (2018), «Простое высокопроизводительное параллельное программирование на основе PRAM с ICE», Транзакции IEEE в параллельных и распределенных системах , 29 (2): 377–390, doi : 10.1109/TPDS.2017.2754376 , hdl : 1903/ 18521

Внешние ссылки

• Прототип PRAM Саарского университета
• Прототип PRAM-On-Chip Университета Мэриленда. В этом прототипе предполагается разместить множество параллельных процессоров и структуру для их соединения на одном чипе.
• XMTC: PRAM-подобное программирование — выпуск программного обеспечения