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

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

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

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

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

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

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

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

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

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

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

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

Подобные алгоритмы полезны для понимания использования параллелизма, разделения исходной проблемы на схожие подзадачи и их параллельного решения. Введение формальной модели P-RAM в диссертации Уилли 1979 года. имел целью количественный анализ параллельных алгоритмов способом, аналогичным машине Тьюринга . Анализ был сосредоточен на модели программирования 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
    end
endmodule

См. также

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

Ссылки

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