Паралельна машина з довільним доступомВ інформатиці, паралельна машина з довільним доступом (англ. PRAM — паралельна рівнодоступна адресна машина) є абстрактною машиною з розділюваною пам'яттю. З назви можна зрозуміти, що PRAM було задумано як паралельно-обчислювальну аналогію до RAM-машини. RAM-машина використовується розробниками послідовних-алгоритмів для моделювання алгоритмічної продуктивності (наприклад, трудомісткості), а PRAM використовується розробниками паралельних алгоритмів для моделювання паралельної алгоритмічної продуктивності (наприклад, трудомісткості, де кількість процесорів, як правило, відома).[джерело?] Подібно до того, як модель RAM нехтує практичними питаннями, такими як час доступу до кеш-пам'яті в порівнянні з основною пам'яттю, модель PRAM нехтує такими питаннями, як синхронізація і комунікація, але забезпечує будь-яку кількість процесорів (в залежності від розміру проблеми). Вартість алгоритму, наприклад, оцінюється за допомогою двох параметрів O (часу) і O (час × кількість_процесорів). Конфлікти зчитування / записуКонфлікти зчитування / запису з одночасним доступом до однієї і тієї ж самої комірки пам'яті вирішуються однією з наступних стратегій:
Ексклюзивні зчитування не мають ніяких розбіжностей, але паралельні записи додатково визначається як:
Є кілька спрощень припущення, які були зроблені при розгляді розробки алгоритмів для PRAM:
Такі алгоритми корисні для розуміння експлуатації паралелізму. Розділивши основну задачу на подібні підзадачі можна вирішувати їх паралельно. Введення формальної моделі '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
Див. також
Примітки
Джерела
Посилання
|
Portal di Ensiklopedia Dunia
