Jump to content

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

(Перенаправлено с CRCW )

В информатике параллельная машина с произвольным доступом ( параллельное ОЗУ или 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 .

module FindMax #(parameter int len = 8)                (input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);    typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;                        State state;    bit 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;        end 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                    end                    state <= MERGE;                end                                MERGE: begin                    for (i = 0; i < len; i++) begin                        if (m[i] == 0) maxNo <= data[i];                    end                    state <= DONE;                end            endcase        end    endendmodule

См. также

[ редактировать ]
  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. ^ Уилли, Джеймс К. Сложность параллельных вычислений , докторская диссертация, факультет компьютерных наук, Корнельский университет
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d2fbdec7df162e8b52eec9ee45a888b7__1710046680
URL1:https://arc.ask3.ru/arc/aa/d2/b7/d2fbdec7df162e8b52eec9ee45a888b7.html
Заголовок, (Title) документа по адресу, URL1:
Parallel RAM - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)