Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В інформатиці, паралельна машина з довільним доступом (англ. PRAM — паралельна рівнодоступна адресна машина) є абстрактною машиною з розділюваною пам'яттю. З назви можна зрозуміти, що PRAM було задумано як паралельно-обчислювальну аналогію до RAM-машини. RAM-машина використовується розробниками послідовних-алгоритмів для моделювання алгоритмічної продуктивності (наприклад, трудомісткості), а PRAM використовується розробниками паралельних алгоритмів для моделювання паралельної алгоритмічної продуктивності (наприклад, трудомісткості, де кількість процесорів, як правило, відома).[] Подібно до того, як модель RAM нехтує практичними питаннями, такими як час доступу до кеш-пам'яті в порівнянні з основною пам'яттю, модель PRAM нехтує такими питаннями, як синхронізація і комунікація, але забезпечує будь-яку кількість процесорів (в залежності від розміру проблеми). Вартість алгоритму, наприклад, оцінюється за допомогою двох параметрів O (часу) і O (час × кількість_процесорів).
Конфлікти зчитування / запису
Конфлікти зчитування / запису з одночасним доступом до однієї і тієї ж самої комірки пам'яті вирішуються однією з наступних стратегій:
- Ексклюзивне зчитування, ексклюзивний запис — доступ до комірки пам'яті для зчитування або запису може мати тільки один процес в певний проміжок часу;
- Паралельне зчитування, ексклюзивний запис — кілька процесорів можуть читати певну комірку пам'яті, але тільки один може виконати запис в цей час;
- Ексклюзивне зчитування, паралельний запис — кілька процесорів можуть виконати запис в певну комірку пам'яті, але тільки один може виконати зчитування в цей час;
- Паралельне зчитування, паралельний запис — кілька процесорів можуть зчитувати і записувати. PRAM використовуючу дану стратегію іноді називають паралельною машиною з довільним доступом.
Ексклюзивні зчитування не мають ніяких розбіжностей, але паралельні записи додатково визначається як:
- Загальні — всі процесори записують певне значення; інші випадки недопустимі.
- Довільні — тільки одна довільна спроба успішна, інші відхиляються.
- Пріоритетні — ранг процесору вказує на те, хто буде записувати інший вид операції редукції масиву, наприклад SUM, логічні AND чи MAX.
Є кілька спрощень припущення, які були зроблені при розгляді розробки алгоритмів для PRAM:
- Немає обмежень на кількість процесорів в машині.
- Кожна комірка пам'яті рівномірно доступна з будь-якого процесору.
- Немає обмеження на кількість спільно використовуваної пам'яті в системі.
- Конфлікти ресурсів відсутні.
- Програми, написані на цих машинах, зазвичай, припадають до типу 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 Див. також
Примітки
- 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
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici paralelna mashina z dovilnim dostupom angl PRAM paralelna rivnodostupna adresna mashina ye abstraktnoyu mashinoyu z rozdilyuvanoyu pam yattyu Z nazvi mozhna zrozumiti sho PRAM bulo zadumano yak paralelno obchislyuvalnu analogiyu do RAM mashini RAM mashina vikoristovuyetsya rozrobnikami poslidovnih algoritmiv dlya modelyuvannya algoritmichnoyi produktivnosti napriklad trudomistkosti a PRAM vikoristovuyetsya rozrobnikami paralelnih algoritmiv dlya modelyuvannya paralelnoyi algoritmichnoyi produktivnosti napriklad trudomistkosti de kilkist procesoriv yak pravilo vidoma dzherelo Podibno do togo yak model RAM nehtuye praktichnimi pitannyami takimi yak chas dostupu do kesh pam yati v porivnyanni z osnovnoyu pam yattyu model PRAM nehtuye takimi pitannyami yak sinhronizaciya i komunikaciya ale zabezpechuye bud yaku kilkist procesoriv v zalezhnosti vid rozmiru problemi Vartist algoritmu napriklad ocinyuyetsya za dopomogoyu dvoh parametriv O chasu i O chas kilkist procesoriv Konflikti zchituvannya zapisuKonflikti zchituvannya zapisu z odnochasnim dostupom do odniyeyi i tiyeyi zh samoyi komirki pam yati virishuyutsya odniyeyu z nastupnih strategij Eksklyuzivne zchituvannya eksklyuzivnij zapis dostup do komirki pam yati dlya zchituvannya abo zapisu mozhe mati tilki odin proces v pevnij promizhok chasu Paralelne zchituvannya eksklyuzivnij zapis kilka procesoriv mozhut chitati pevnu komirku pam yati ale tilki odin mozhe vikonati zapis v cej chas Eksklyuzivne zchituvannya paralelnij zapis kilka procesoriv mozhut vikonati zapis v pevnu komirku pam yati ale tilki odin mozhe vikonati zchituvannya v cej chas Paralelne zchituvannya paralelnij zapis kilka procesoriv mozhut zchituvati i zapisuvati PRAM vikoristovuyuchu danu strategiyu inodi nazivayut paralelnoyu mashinoyu z dovilnim dostupom Eksklyuzivni zchituvannya ne mayut niyakih rozbizhnostej ale paralelni zapisi dodatkovo viznachayetsya yak Zagalni vsi procesori zapisuyut pevne znachennya inshi vipadki nedopustimi Dovilni tilki odna dovilna sproba uspishna inshi vidhilyayutsya Prioritetni rang procesoru vkazuye na te hto bude zapisuvati inshij vid operaciyi redukciyi masivu napriklad SUM logichni AND chi MAX dd Ye kilka sproshen pripushennya yaki buli zrobleni pri rozglyadi rozrobki algoritmiv dlya PRAM Nemaye obmezhen na kilkist procesoriv v mashini Kozhna komirka pam yati rivnomirno dostupna z bud yakogo procesoru Nemaye obmezhennya na kilkist spilno vikoristovuvanoyi pam yati v sistemi Konflikti resursiv vidsutni Programi napisani na cih mashinah zazvichaj pripadayut do tipu SIMD odin potik komand bagato potokiv danih Taki algoritmi korisni dlya rozuminnya ekspluataciyi paralelizmu Rozdilivshi osnovnu zadachu na podibni pidzadachi mozhna virishuvati yih paralelno Vvedennya formalnoyi modeli P RAM v 1979 roci na disertaciyi Villi mala na meti kilkisnij analiz paralelnih algoritmiv v porivnyanni z analogichnoyu mashinoyu Tyuringa Analiz buv zoseredzhenij na modeli programuvannya MIMD bagato potokiv komand bagato potokiv danih z vikoristannyam modeli paralelnih zchituvan eksklyuzivnih zapisiv Ale analiz pokazav sho bilshist variantiv v tomu chisli variantiv realizaciyi modeli paralelnih zchituvan paralelnih zapisiv i variantiv realizaciyi na mashini SIMD odin potik komand bagato potokiv danih buli mozhlivi tilki z postijnimi nakladnimi vitratami RealizaciyaAlgoritmi PRAM ne mozhut buti rozparaleleni za dopomogoyu kombinaciyi CPU i dinamichnoyi pam yati z dovilnim dostupom DRAM tomu sho DRAM ne dopuskaye odnochasnogo dostupu ale voni mozhut buti realizovani na aparatnih zasobah zchituvannya zapisu do vnutrishnoyi statichnoyi operativnoyi pam yati z dovilnim dostupom SRAM blokiv programovanoyi koristuvachem ventilnoyi matrici FPGA ce mozhe buti zrobleno za dopomogoyu algoritmu paralelnogo zchituvannya paralelnogo zapisu Prote test na praktichnu znachimist algoritmiv PRAM abo RAM zalezhit vid togo chi yih vartist zabezpechuye model efektivnoyi abstrakciyi deyakogo komp yutera struktura cogo komp yutera mozhe buti zovsim inshoyu nizh struktura abstraktnoyi modeli Znannya shariv programnogo zabezpechennya ta aparatnih zasobiv vihodyat za ramki danoyi statti Ale taki statti yak Vishkin 2011 demonstruyut yak PRAM podibni abstrakciyi mozhut buti pidtrimani yavnoyu bagatopotochnistyu XMT paradigmi i taki statti yak Caragea amp Vishkin 2011 pokazuyut sho algoritm PRAM dlya maksimalnogo potoku zavdan mozhe zabezpechuvati silne priskorennya po vidnoshennyu do najshvidshoyi serijnoyi programi dlya tiyeyi zh zadachi Priklad koduCe priklad SystemVerilog kodu yakij znahodit maksimalne znachennya v masivi vsogo lish za 2 takti Vin porivnyuye vsi kombinaciyi elementiv v masivi na pershij taktovij chastoti i zlivaye rezultat z drugoyu taktovoyu chastotoyu Vin vikoristovuye pam yat paralelnogo zchituvannya paralelnogo zapisu m i lt 1 and maxNo lt data i zapisuyutsya odnochasno Paralelizm ne viklikaye niyakih konfliktiv tomu sho algoritm garantuye sho te zh same znachennya zapisuyetsya v cij zhe komirci pam yati Cej kod mozhe buti zapushenij na FPGA obladnanni 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 lt len i m i lt 0 state lt COMPARE end else begin case state COMPARE begin for i 0 i lt len i begin for j 0 j lt len j begin if data i lt data j m i lt 1 end end state lt MERGE end MERGE begin for i 0 i lt len i begin if m i 0 maxNo lt data i end state lt DONE end endcase end end endmoduleDiv takozhAnaliz paralelnih algoritmiv Taksonomiya Flinna RAM mashina Rozparalelyuvannya programPrimitkiNeil Immerman Expressibility and parallel complexity PosilannyaNeil 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 Jorg Christoph Kessler Jesper Traff 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 1989511PosilannyaSaarland 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