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

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

Конфликты чтения/записи [ править ]

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

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

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

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

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

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

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

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

Ограничений на количество процессоров в машине нет.
Любая ячейка памяти одинаково доступна из любого процессора.
Ограничений на объем разделяемой памяти в системе нет.
Конфликт за ресурсы отсутствует.
Программы, написанные на этих машинах, обычно относятся к типу 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  ) 
                 (  входной   бит   clock  ,   resetN  ,   входной   бит  [  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  ; 
                  конец 
                
                 MERGE:   начало 
                     для   (  я   =   0  ;   я   <   len  ;   я  ++  )   начало 
                         если   (  м  [  я  ]   ==   0  )   maxNo   <=   данные  [  я  ]; 
                      конечное 
                     состояние   <=   ГОТОВО  ; 
                  конец конца 
             корпуса 
         конец 
     конца 
 модуля

См. также [ править ]

Ссылки [ править ]

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

Эппштейн, Дэвид; Галил, Цви (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-подобное программирование — выпуск программного обеспечения

[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] Уилли, Джеймс К. Сложность параллельных вычислений , докторская диссертация, факультет компьютерных наук, Корнельский университет

[1]

[2]

[3]

[4]

v т Это Параллельные вычисления
Общий	Распределенных вычислений Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ Модель PEM Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Эффективность затрат Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН В С Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атеджи ПХ Способствовать росту Часовня HPX Очарование++ Силк Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления