Паралельна машина з довільним доступом

В інформатиці, паралельна машина з довільним доступом (англ. PRAM — паралельна рівнодоступна адресна машина) є абстрактною машиною з розділюваною пам'яттю. З назви можна зрозуміти, що PRAM було задумано як паралельно-обчислювальну аналогію до RAM-машини. RAM-машина використовується розробниками послідовних-алгоритмів для моделювання алгоритмічної продуктивності (наприклад, трудомісткості), а PRAM використовується розробниками паралельних алгоритмів для моделювання паралельної алгоритмічної продуктивності (наприклад, трудомісткості, де кількість процесорів, як правило, відома).^{[джерело?]} Подібно до того, як модель RAM нехтує практичними питаннями, такими як час доступу до кеш-пам'яті в порівнянні з основною пам'яттю, модель PRAM нехтує такими питаннями, як синхронізація і комунікація, але забезпечує будь-яку кількість процесорів (в залежності від розміру проблеми). Вартість алгоритму, наприклад, оцінюється за допомогою двох параметрів O (часу) і O (час × кількість_процесорів).

Конфлікти зчитування / запису

Конфлікти зчитування / запису з одночасним доступом до однієї і тієї ж самої комірки пам'яті вирішуються однією з наступних стратегій:

1. Ексклюзивне зчитування, ексклюзивний запис — доступ до комірки пам'яті для зчитування або запису може мати тільки один процес в певний проміжок часу; 
2. Паралельне зчитування, ексклюзивний запис — кілька процесорів можуть читати певну комірку пам'яті, але тільки один може виконати запис в цей час; 
3. Ексклюзивне зчитування, паралельний запис — кілька процесорів можуть виконати запис в певну комірку пам'яті, але тільки один може виконати зчитування в цей час; 
4. Паралельне зчитування, паралельний запис — кілька процесорів можуть зчитувати і записувати. PRAM використовуючу дану стратегію іноді називають паралельною машиною з довільним доступом.

Ексклюзивні зчитування не мають ніяких розбіжностей, але паралельні записи додатково визначається як:

Загальні — всі процесори записують певне значення; інші випадки недопустимі. 

Довільні — тільки одна довільна спроба успішна, інші відхиляються. 

Пріоритетні — ранг процесору вказує на те, хто буде записувати інший вид операції редукції масиву, наприклад SUM, логічні AND чи MAX.

Є кілька спрощень припущення, які були зроблені при розгляді розробки алгоритмів для PRAM:

1. Немає обмежень на кількість процесорів в машині.
2. Кожна комірка пам'яті рівномірно доступна з будь-якого процесору.
3. Немає обмеження на кількість спільно використовуваної пам'яті в системі.
4. Конфлікти ресурсів відсутні.
   
5. Програми, написані на цих машинах, зазвичай, припадають до типу SIMD (один потік команд, багато потоків даних).
   

Такі алгоритми корисні для розуміння експлуатації паралелізму. Розділивши основну задачу на подібні підзадачі можна вирішувати їх паралельно. Введення формальної моделі 'P-RAM " в 1979 році на дисертації Віллі мала на меті кількісний аналіз паралельних алгоритмів в порівнянні з аналогічною машиною Тюрінга. Аналіз був зосереджений на моделі програмування MIMD (багато потоків команд, багато потоків даних) з використанням моделі паралельних зчитувань, ексклюзивних записів. Але аналіз показав, що більшість варіантів, в тому числі варіантів реалізації моделі паралельних зчитувань, паралельних записів і варіантів реалізації на машині SIMD (один потік команд, багато потоків даних), були можливі тільки з постійними накладними витратами.

Реалізація

Алгоритми PRAM не можуть бути розпаралелені за допомогою комбінації CPU і динамічної пам'яті з довільним доступом (DRAM), тому що DRAM не допускає одночасного доступу; але вони можуть бути реалізовані на апаратних засобах зчитування / запису до внутрішньої статичної оперативної пам'яті з довільним доступом (SRAM) блоків програмованої користувачем вентильної матриці (FPGA), це може бути зроблено за допомогою алгоритму паралельного зчитування, паралельного запису.

Проте, тест на практичну значимість алгоритмів PRAM (або RAM) залежить від того, чи їх вартість забезпечує модель ефективної абстракції деякого комп'ютера; структура цього комп'ютера може бути зовсім іншою, ніж структура абстрактної моделі. Знання шарів програмного забезпечення та апаратних засобів, виходять за рамки даної статті. Але такі статті, як Vishkin (2011) демонструють, як PRAM подібні абстракції можуть бути підтримані явною багатопоточністю (XMT) парадигми і такі статті, як Caragea & Vishkin (2011) показують, що алгоритм PRAM для максимального потоку завдань може забезпечувати сильне прискорення по відношенню до найшвидшої серійної програми для тієї ж задачі.

Приклад коду

Це приклад SystemVerilog коду, який знаходить максимальне значення в масиві всього лиш за 2 такти. Він порівнює всі комбінації елементів в масиві на першій тактовій частоті, і зливає результат з другою тактовою частотою. Він використовує пам'ять паралельного зчитування, паралельного запису; m[i] <= 1 and 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

Див. також

• Аналіз паралельних алгоритмів
• Таксономія Флінна
• Алгоритми без блокування та очікування
• RAM-машина
• Розпаралелювання програм
• XMTC

Посилання

• Neil Immerman, Expressibility and parallel complexity.
• Eppstein, David; Galil, Zvi (1988), Parallel algorithmic techniques for combinatorial computation, Annu. Rev. Comput. Sci., 3: 233—283, doi:10.1146/annurev.cs.03.060188.001313
• JaJa, Joseph (1992), An Introduction to Parallel Algorithms, Addison-Wesley, ISBN 0-201-54856-9
• Karp, Richard M.; Ramachandran, Vijaya (1988), A Survey of Parallel Algorithms for Shared-Memory Machines, University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408
• Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons. ISBN 0-471-35351-5. 
• Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF), Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion
• Vishkin, Uzi (2011), Using simple abstraction to reinvent computing for parallelism, Communications of the ACM, 54: 75—85, doi:10.1145/1866739.1866757
• Caragea, George Constantin; Vishkin, Uzi (2011), Better speedups for parallel max-flow, ACM SPAA, doi:10.1145/1989493.1989511

Посилання

• Saarland University's prototype PRAM
• University Of Maryland's PRAM-On-Chip prototype. This prototype seeks to put many parallel processors and the fabric for inter-connecting them on a single chip
• XMTC: PRAM-like Programming - Software release