В информатике параллельная машина с произвольным доступом ( параллельная RAM или PRAM ) — это абстрактная машина с общей памятью . Как следует из названия, PRAM предназначена как аналогия параллельных вычислений для машины с произвольным доступом (RAM) (не путать с памятью с произвольным доступом ). [1] Точно так же, как RAM используется разработчиками последовательных алгоритмов для моделирования алгоритмической производительности (такой как временная сложность), PRAM используется разработчиками параллельных алгоритмов для моделирования параллельной алгоритмической производительности (такой как временная сложность, где предполагаемое количество процессоров обычно также указывается). Подобно тому, как модель RAM игнорирует практические вопросы, такие как время доступа к кэш-памяти по сравнению с основной памятью, модель PRAM игнорирует такие вопросы, как синхронизация и связь , но предоставляет любое (зависящее от размера задачи) количество процессоров. Стоимость алгоритма, например, оценивается с использованием двух параметров O(время) и O(время × номер_процессора).
Конфликты чтения/записи, обычно называемые блокировкой при одновременном доступе к одной и той же общей области памяти, разрешаются с помощью одной из следующих стратегий:
Здесь E и C обозначают «исключительный» и «конкурентный» соответственно. Чтение не вызывает никаких расхождений, тогда как конкуренциональная запись далее определяется как:
При рассмотрении разработки алгоритмов для PRAM делается несколько упрощающих предположений. Они следующие:
Эти типы алгоритмов полезны для понимания эксплуатации параллелизма, разделения исходной проблемы на схожие подзадачи и их параллельного решения. Введение формальной модели «P-RAM» в диссертации Уилли 1979 года [4] имело целью количественное определение анализа параллельных алгоритмов способом, аналогичным машине Тьюринга . Анализ был сосредоточен на модели MIMD программирования с использованием модели CREW, но показал, что многие варианты, включая реализацию модели CRCW и реализацию на машине SIMD, были возможны только с постоянными накладными расходами.
Алгоритмы PRAM не могут быть распараллелены с помощью комбинации ЦП и динамической памяти с произвольным доступом (DRAM), поскольку DRAM не допускает одновременного доступа к одному банку (даже к разным адресам в банке); но их можно реализовать аппаратно или считывать/записывать во внутренние блоки статической памяти с произвольным доступом (SRAM) программируемой пользователем вентильной матрицы (FPGA); это можно сделать с помощью алгоритма CRCW.
Однако проверка практической значимости алгоритмов PRAM (или RAM) зависит от того, обеспечивает ли их модель затрат эффективную абстракцию некоторого компьютера; структура этого компьютера может существенно отличаться от абстрактной модели. Знание слоев программного и аппаратного обеспечения, которые необходимо вставить, выходит за рамки этой статьи. Но такие статьи, как Vishkin (2011), демонстрируют, как абстракция, подобная PRAM, может поддерживаться парадигмой явной многопоточности (XMT), а такие статьи, как Caragea & Vishkin (2011), демонстрируют, что алгоритм PRAM для задачи максимального потока может обеспечить значительное ускорение по сравнению с самой быстрой последовательной программой для той же задачи. Статья Ghanim, Vishkin & Barua (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 ; Состояние state ; бит m [ len ]; int i , j ; always_ff @( posedge clock , negedge resetN ) begin if ( ! resetN ) begin for ( i = 0 ; i < len ; i ++ ) m [ i ] <= 0 ; state <= COMPARE ; конец else begin case ( state ) COMPARE: begin for ( i = 0 ; i < len ; i ++ ) begin for ( j = 0 ; j < len ; j ++ ) begin if ( data [ i ] < data [ j ]) m [ i ] <= 1 ; конец end state <= MERGE ; конец MERGE: begin for ( i = 0 ; i < len ; i ++ ) begin if ( m [ i ] == 0 ) maxNo <= data [ i ]; конечное состояние <= DONE ; конец endcase конец конец endmodule