Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Обычный - все процессоры записывают одно и то же значение; в противном случае это незаконно
Произвольный - успешна только одна произвольная попытка, остальные удаляются.
Приоритет - ранг процессора указывает, кто имеет право писать
Другой вид операции сокращения массива, такой как СУММ, логическое И или МАКС.

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

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

Эти виды алгоритмов полезны для понимания использования параллелизма, разделения исходной проблемы на похожие подзадачи и их параллельного решения. Введение формальной модели «P-RAM» в диссертацию Уилли 1979 г. [2] имело целью количественный анализ параллельных алгоритмов аналогично машине Тьюринга . Анализ был сосредоточен на модели программирования 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 )  ( входной  бит  синхронизации ,  resetN ,  входной  бит [ 7 : 0 ]  данные [ len ],  выходной  бит [ 7 : 0 ]  maxNo );  typedef  enum  bit [ 1 : 0 ]  { СРАВНИТЬ ,  MERGE ,  DONE }  Состояние ;  Государственное  состояние ;  бит  m [ лен ];  int  i ,  j ;  always_ff  @ ( posedge  часы ,  negedge  resetN )  начать  если  ( ! resetN )  начинаются  для  ( я  =  0 ;  я  <  Len ,  я ++ )  м [ я ]  <=  0 ;  состояние  <=  СРАВНИТЬ ;  end  else  begin  case  ( состояние )  СРАВНИТЬ:  begin  for  ( i  =  0 ;  i <  len ;  i ++ )  begin  for  ( j  =  0 ;  j  <  len ;  j ++ )  begin  if  ( data [ i ]  <  data [ j ])  m [ i ]  <=  1 ;  конечное  конечное  состояние  <=  MERGE ;  конец  MERGE:  начало  для  ( я  =  0 ;  я  <  len ;  я ++ )  начало,  если  ( м [ я ]  ==  0 )  maxNo  <=  данные [ я ];  конечное  состояние  <=  ГОТОВО ;  конец  ENDCASE  конец  конец endmodule

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

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

  1. ^ Нил Иммерман, Выразимость и параллельная сложность . SIAM Journal on Computing, vol. 18, нет. 3. С. 625-638, 1989.
  2. ^ Уилли, Джеймс С. Сложность параллельных вычислений , докторская диссертация, кафедра компьютерных наук, Корнельский университет
  • Эпштейн, Дэвид; Галил, Цви (1988), "Параллельные алгоритмические методы комбинаторных вычислений", Annu. Rev. Comput. Sci. , 3 : 233-283, DOI : 10,1146 / annurev.cs.03.060188.001313
  • JaJa, Джозеф (1992), Введение в параллельные алгоритмы , Addison-Wesley, ISBN 0-201-54856-9
  • Карп, Ричард М .; Рамачандран, Виджая (1988), Обзор параллельных алгоритмов для машин с общей памятью , Калифорнийский университет, Беркли, Департамент EECS, Tech. Реп. UCB / CSD-88-408
  • Келлер, Йорг; Кристоф Кесслер; Джеспер Трэфф (2001). Практическое программирование PRAM . Джон Вили и сыновья. ISBN 0-471-35351-5.
  • Вишкин, Узи (2009), « Мышление параллельно: некоторые базовые алгоритмы и методы параллельного обмена данными», 104 страницы (PDF) , конспекты курсов по параллельным алгоритмам, которые преподаются с 1992 года в Университете Мэриленда, Колледж-Парк, Тель-Авивском университете и Технион
  • Vishkin, Узи (2011), "Использование простой абстракции изобрести вычисления для параллелизма", коммуникаций ACM , 54 : 75-85, DOI : 10,1145 / 1866739.1866757
  • Караджа, Джордж Константин; Вишкин, Узи (2011), «Краткое сообщение: Улучшение ускорения для параллельного максимального потока», Труды 23-го симпозиума ACM по параллелизму в алгоритмах и архитектурах - SPAA '11 , стр. 131, DOI : 10,1145 / 1989493,1989511 , ISBN 9781450307437
  • Ганим, Фади; Вишкин, Узи; Баруа, Райеев (2018), "Легкий PRAM основе высокая эффективность параллельного программирования с ICE", IEEE Transactions на параллельных и распределенных систем , 29 (2): 377-390, DOI : 10,1109 / TPDS.2017.2754376 , ЛВП : 1903 / 18521

Внешние ссылки [ править ]

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