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

Матеріал з Вікіпедії — вільної енциклопедії.
Jump to navigation Jump to search

В інформатиці, паралельна машина з довільним доступом (англ. PRAM — паралельна рівнодоступна адресна машина, скорочено ПРАМ) є абстрактною машиною з розділюваною пам'яттю. По назві можна зрозуміти, що ПРАМ було задумано як паралельно-обчислювальну аналогію до машини з довільним доступом (РАМ). Таким чином, що РАМ використовується розробниками послідовних-алгоритмів для моделювання алгоритмічної продуктивності (наприклад, трудомісткості), а ПРАМ використовується розробниками паралельних алгоритмів для моделювання паралельної алгоритмічної продуктивності (наприклад, трудомісткості, де кількість процесорів, як правило, відома). Подібно до того, як модель РАМ нехтує практичними питаннями, такими як час доступу до кеш-пам'яті в порівнянні з основною пам'яттю, модель ПРАМ нехтує такими питаннями, як синхронізація і комунікація, але забезпечує будь-яку кількість процесорів (в залежності від розміру проблеми). Вартість алгоритму, наприклад, оцінюється за допомогою двох параметрів O (часу) і O (час × кількість_процесорів).

Конфлікти зчитування / запису[ред.ред. код]

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

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

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

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

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

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

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

Реалізація[ред.ред. код]

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

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

Приклад коду[ред.ред. код]

Це приклад 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

Дивіться також[ред.ред. код]

Примітки[ред.ред. код]

  1. Neil Immerman, Expressibility and parallel complexity.

Посилання[ред.ред. код]

  • 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. 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. 

Зовнішні посилання[ред.ред. код]