Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Мережа процесів Кана (мережа процесів, мережа потоків даних) — це розподілена модель обчислень, в якій група детермінованих процесів взаємодіє через необмежені канали FIFO. Мережі процесів володіють детермінованою поведінкою, яка не залежить від обчислювальних і комунікаційних затримок. Спочатку розроблені для моделювання розподілених систем, мережі процесів виявилися ефективні також для моделювання систем обробки сигналів. Моделлю обчислень є орієнтований граф, вершини якого є обчислювальними процесами, а дуги — впорядкованими послідовностями елементів даних. Обчислювальні процеси постійно здійснюють обробку вхідних даних, породжуючи набори вихідних даних. Назва даної моделі пов'язана з тим, що мережі процесів були вперше описані Жілем Каном.
Модель виконання
KPN — загальна модель для опису систем обробки сигналу, де безкінечні потоки даних зі зростанням перетворюють процеси, що виконуються один за іншим або паралельно. Не дивлячись на паралельні процеси, багатозадачність або паралелізм не потрібні для виконання цієї моделі.
У KPN, процеси зв'язуються через безмежні канали FIFO. Процеси зчитують і пишуть атомні елементи даних, або альтернативно називаються знаками, від і до каналів. Запис до каналу є безперебійним, тобто це завжди має успіх і не зупиняє процес, поки читання з каналу є заблокованим, тобто процес, який читає з порожнього каналу, зупиниться і може продовжуватися, коли канал містить достатні елементи даних (знаки).
Процеси не дозволяють перевірити вхідний канал на існування знаків без вжитку їх. FIFO не можуть спожити багаторазові процеси, також не може відбутися багаторазове відтворення процесів в єдиний FIFO. Отримали специфічну вхідну (знак) історію для процесу, процес має бути детермінований таким чином, що це завжди відтворює, ту ж саму продуктивність (знаки). Розрахунок часу або замовлення виконання процесів не повинне впливати на результат і тому перевірка вхідних каналів для знаків заборонено.
Відмітки на процесах
- Процесу не потрібно зчитувати будь-які вхідні дані або мати будь-які вхідні канали, оскільки це, можливо, служить джерелом постійних даних
- Процесу не потрібно писати будь-які вихідні дані або мати будь-які вихідні канали
- Вхідні канали тестування для порожнечі (або безперебійного зчитування) може дозволятися для цілей оптимізації, але це не повинно зачіпати вихідні канал. Це може бути вигідне і/або можливо зробити що-небудь заздалегідь замість чекання для каналу. Наприклад, можна припустити, що було 2 зчитування з різних каналів. Якби перше зчитування зупинилось (дочекайтеся знаку) але друге зчитування могло зчитати знак безпосередньо, може бути вигідно зчитувати другий, щоб економити час, тому що, зчитування себе часто споживає деякий час (наприклад час для розміщення пам'яті або копіювання).
Процес звільнення семантики, як мереж Петрі
Припустимо, що процес P в KPN сконструйований таким чином, що він спершу читає дані з каналу А, потім канал B, обчислює що-небудь, а потім пише дані, щоб направити C, модель виконання процесу може моделюватися з мережею Петрі. Єдиний знак в PE місці ресурсу забороняє, виконання процесу одночасно для різних початкових даних. Коли дані прибувають в канал А або B, знаки розміщуються на місця FIFO А і FIFO B відповідно. Переміщення мережі Петрі асоційовані з відповідними діями I/O і обчисленнями. Коли дані був записані до каналу C, ресурс PE наповнюється його початковою маркіровкою знову, дозволяючи новим даним бути зчитаними.
Процес як закінчений апарат
Процес може моделюватися як закінчений апарат, який знаходиться в одному із двох станів:
- Активний; процес обчислює або пише дані
- В очікуванні; процес блокується (в очікуванні) для даних
Припустимо, що закінчений апарат зчитує елементи програми, що асоціюються з процесом, і може, прочитати три види знаків: «Обчислюють», «Читаються» і знак «Запису». Додатково, в стані Очікування можливо лише повернутися до Активного стану, зчитаючи спеціальний «Отримуючий знак», який означає, що канал зв'язку, що асоціюється з чеканням, містить чіткі дані.
Властивості
Необмежена кількість каналів
Канал строго обмежує {\displaystyle b} b, якщо це має як мінімум {\displaystyle b} b не реалізовані знаки для будь-якого можливого виконання. KPN строго обмежує {\displaystyle b} b, якщо всі канали строго обмежують {\displaystyle b} b.
Число не реалізованих знаків залежить від замовлення (планування) виконання процесів. Мимовільне джерело даних могло виробляти довільно багато знаків в каналі, якщо планувальник не зможе виконати процеси, використовуючи ті знаки.
Реальне застосування не обмежує FIFOs і тому планування і максимальна місткість FIFOs повинна проектуватися в практичному виконанні. Максимальна місткість FIFOs може управлятися декількома способами:
- Обмеження FIFO можуть бути математично отримані в проекті, щоб уникати надлишків FIFO. Проте це не можливо для всього KPNs. Це — нерозв'язна проблема, щоб перевірити чи KPN строго обмежує{\displaystyle b} b. Окрім того, в практичних ситуаціях, обмеження, можливо, є утриманням даних.[]
- Обмеження FIFO можуть бути побудовані за вимогою (запитом).
- Блокування записів може бути використане таким чином, процес блокується, якщо FIFO повний. Цей підхід, на жаль, приводить до штучної безвихідності, якби тільки проектувальник належним чином отримав безпечні обмеження для FIFOs (Parks, 1995). Місцеве штучне виявлення в часі виконання, можливо, необхідне, щоб гарантувати виробництво правильного вихідного каналу (вихідних даних).
Закриті (замкнуті) та відкриті системи
Закритий KPN не має жодних зовнішніх вхідних або вихідних каналів. Процеси, що не мають жодного вхідного каналу, діють як джерела даних і процеси, що не мають жодного вихідного каналу, діють як приймачі даних. У відкритому KPN кожен процес має як мінімум один вхідний і вихідний канал.
Детермінізм
Процеси KPN детерміновані. Для тієї ж вхідної історії вони повинні завжди виробляти точно такі самі вихідні. Процеси можуть моделюватися як послідовні програми, які зчитуються і пишуться для портів в будь-якому порядку або кількості, поки властивість детермінізму збережена. Як наслідок, модель KPN детермінована таким чином, що наступні чинники повністю визначають вихідні системи:
- процеси
- мережі
- початкові знаки
Віднині, розрахунок часу процесів не зачіпає вихідні системи.
Монотонність
Процеси KPN монотонні, це означає, що їм лише потрібна часткова інформація вхідного потоку для того, щоб виробляти часткову інформацію вихідного потоку. Монотонність дозволяє паралелізм. У KPN є повна почерговість подій усередині сигналу. Проте, немає жодного чергування зв'язків між подіями в різних сигналах. Тому, KPNs лише частково впорядковані, це класифікує їх як нехронометровану модель.
Додатки
Завдяки його високій виразності і стислості, KPNs, який лежить в основі моделі обчислення застосовується в декількох академічних моделюючих інструментах, щоб представити поточні додатки, які мають певні властивості (наприклад, орієнтованість на потік даних, поточність).
Відкрита вихідна структура Daedalus, підтримувана Лейден, заснувала Центр Досліджень в Лейденському Університеті, і прийняла послідовні програми, написані на C, і виробляє відповідний KPN. Це KPN зміг, наприклад, бути використаним, щоб нанести на карту KPN, на заснованій FPGA- платформі систематично.
Ambric Am2045 в широкому масштабі паралельний масив процесора — KPN, здійснюваний у кремнії. Тут 336 32-розрядних процесорів сполучено програмованим сполучним дротом відданого FIFOs. Тому його канали строго обмежують блокування записів.
Примітки
- Kahn, G. (1974). Rosenfeld, Jack L. (ред.). (PDF). Proc. IFIP Congress on Information Processing. North-Holland. ISBN . Архів оригіналу (PDF) за 17 листопада 2020. Процитовано 20 квітня 2020.
- Parks, Thomas M. (1995). (Ph. D.). University of California, Berkeley. Архів оригіналу за 20 жовтня 2017. Процитовано 20 квітня 2020.
- Geilen, Marc; Basten, Twan (2003). Degano, P. (ред.). Requirements on the Execution of Kahn Process Networks. Proc. 12th European Symposium on Programming Languages and Systems (ESOP). Springer. с. 319—334.
- Mike Butts, Anthony Mark Jones, Paul Wasson, «A Structural Object Programming Model, Architecture, Chip and Tools for Reconfigurable Computing», Proceedings of , April 2007, IEEE Computer Society
Подальше читання
- Lee, E.A.; Parks, T.M. (1995). Dataflow process networks (PDF). Proceedings of the IEEE. 83 (5): 773—801. doi:10.1109/5.381846. ISSN 0018-9219. Процитовано 13 лютого 2019.
- Josephs, Mark B. (2005). Models for Data-Flow Sequential Processes. У Ali E. Abdallah, Cliff B. Jones, Jeff W. Sanders (eds.) (ред.). Communicating Sequential Processes. The First 25 Years: Symposium on the Occasion of 25 Years of CSP, London, UK, July 7-8, 2004. Revised Invited Papers. Lecture Notes in Computer Science. Т. 3525. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 85—97. doi:10.1007/11423348_6. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Merezha procesiv Kana merezha procesiv merezha potokiv danih ce rozpodilena model obchislen v yakij grupa determinovanih procesiv vzayemodiye cherez neobmezheni kanali FIFO Merezhi procesiv volodiyut determinovanoyu povedinkoyu yaka ne zalezhit vid obchislyuvalnih i komunikacijnih zatrimok Spochatku rozrobleni dlya modelyuvannya rozpodilenih sistem merezhi procesiv viyavilisya efektivni takozh dlya modelyuvannya sistem obrobki signaliv Modellyu obchislen ye oriyentovanij graf vershini yakogo ye obchislyuvalnimi procesami a dugi vporyadkovanimi poslidovnostyami elementiv danih Obchislyuvalni procesi postijno zdijsnyuyut obrobku vhidnih danih porodzhuyuchi nabori vihidnih danih Nazva danoyi modeli pov yazana z tim sho merezhi procesiv buli vpershe opisani Zhilem Kanom Merezha Kana z troh procesiv bez zvorotnoyi komunikaciyi Rebra A B i C komunikacijni kanali P odin z procesiv Model vikonannyaKPN zagalna model dlya opisu sistem obrobki signalu de bezkinechni potoki danih zi zrostannyam peretvoryuyut procesi sho vikonuyutsya odin za inshim abo paralelno Ne divlyachis na paralelni procesi bagatozadachnist abo paralelizm ne potribni dlya vikonannya ciyeyi modeli U KPN procesi zv yazuyutsya cherez bezmezhni kanali FIFO Procesi zchituyut i pishut atomni elementi danih abo alternativno nazivayutsya znakami vid i do kanaliv Zapis do kanalu ye bezperebijnim tobto ce zavzhdi maye uspih i ne zupinyaye proces poki chitannya z kanalu ye zablokovanim tobto proces yakij chitaye z porozhnogo kanalu zupinitsya i mozhe prodovzhuvatisya koli kanal mistit dostatni elementi danih znaki Procesi ne dozvolyayut pereviriti vhidnij kanal na isnuvannya znakiv bez vzhitku yih FIFO ne mozhut spozhiti bagatorazovi procesi takozh ne mozhe vidbutisya bagatorazove vidtvorennya procesiv v yedinij FIFO Otrimali specifichnu vhidnu znak istoriyu dlya procesu proces maye buti determinovanij takim chinom sho ce zavzhdi vidtvoryuye tu zh samu produktivnist znaki Rozrahunok chasu abo zamovlennya vikonannya procesiv ne povinne vplivati na rezultat i tomu perevirka vhidnih kanaliv dlya znakiv zaboroneno Vidmitki na procesah Procesu ne potribno zchituvati bud yaki vhidni dani abo mati bud yaki vhidni kanali oskilki ce mozhlivo sluzhit dzherelom postijnih danih Procesu ne potribno pisati bud yaki vihidni dani abo mati bud yaki vihidni kanali Vhidni kanali testuvannya dlya porozhnechi abo bezperebijnogo zchituvannya mozhe dozvolyatisya dlya cilej optimizaciyi ale ce ne povinno zachipati vihidni kanal Ce mozhe buti vigidne i abo mozhlivo zrobiti sho nebud zazdalegid zamist chekannya dlya kanalu Napriklad mozhna pripustiti sho bulo 2 zchituvannya z riznih kanaliv Yakbi pershe zchituvannya zupinilos dochekajtesya znaku ale druge zchituvannya moglo zchitati znak bezposeredno mozhe buti vigidno zchituvati drugij shob ekonomiti chas tomu sho zchituvannya sebe chasto spozhivaye deyakij chas napriklad chas dlya rozmishennya pam yati abo kopiyuvannya Proces zvilnennya semantiki yak merezh Petri Firing semantics of process P modeled with a Petri net displayed in the image above Pripustimo sho proces P v KPN skonstrujovanij takim chinom sho vin spershu chitaye dani z kanalu A potim kanal B obchislyuye sho nebud a potim pishe dani shob napraviti C model vikonannya procesu mozhe modelyuvatisya z merezheyu Petri Yedinij znak v PE misci resursu zaboronyaye vikonannya procesu odnochasno dlya riznih pochatkovih danih Koli dani pribuvayut v kanal A abo B znaki rozmishuyutsya na miscya FIFO A i FIFO B vidpovidno Peremishennya merezhi Petri asocijovani z vidpovidnimi diyami I O i obchislennyami Koli dani buv zapisani do kanalu C resurs PE napovnyuyetsya jogo pochatkovoyu markirovkoyu znovu dozvolyayuchi novim danim buti zchitanimi Proces yak zakinchenij aparat A finite state machine of a process Proces mozhe modelyuvatisya yak zakinchenij aparat yakij znahoditsya v odnomu iz dvoh staniv Aktivnij proces obchislyuye abo pishe dani V ochikuvanni proces blokuyetsya v ochikuvanni dlya danih Pripustimo sho zakinchenij aparat zchituye elementi programi sho asociyuyutsya z procesom i mozhe prochitati tri vidi znakiv Obchislyuyut Chitayutsya i znak Zapisu Dodatkovo v stani Ochikuvannya mozhlivo lishe povernutisya do Aktivnogo stanu zchitayuchi specialnij Otrimuyuchij znak yakij oznachaye sho kanal zv yazku sho asociyuyetsya z chekannyam mistit chitki dani VlastivostiNeobmezhena kilkist kanaliv Kanal strogo obmezhuye displaystyle b b yaksho ce maye yak minimum displaystyle b b ne realizovani znaki dlya bud yakogo mozhlivogo vikonannya KPN strogo obmezhuye displaystyle b b yaksho vsi kanali strogo obmezhuyut displaystyle b b Chislo ne realizovanih znakiv zalezhit vid zamovlennya planuvannya vikonannya procesiv Mimovilne dzherelo danih moglo viroblyati dovilno bagato znakiv v kanali yaksho planuvalnik ne zmozhe vikonati procesi vikoristovuyuchi ti znaki Realne zastosuvannya ne obmezhuye FIFOs i tomu planuvannya i maksimalna mistkist FIFOs povinna proektuvatisya v praktichnomu vikonanni Maksimalna mistkist FIFOs mozhe upravlyatisya dekilkoma sposobami Obmezhennya FIFO mozhut buti matematichno otrimani v proekti shob unikati nadlishkiv FIFO Prote ce ne mozhlivo dlya vsogo KPNs Ce nerozv yazna problema shob pereviriti chi KPN strogo obmezhuye displaystyle b b Okrim togo v praktichnih situaciyah obmezhennya mozhlivo ye utrimannyam danih dzherelo Obmezhennya FIFO mozhut buti pobudovani za vimogoyu zapitom Blokuvannya zapisiv mozhe buti vikoristane takim chinom proces blokuyetsya yaksho FIFO povnij Cej pidhid na zhal privodit do shtuchnoyi bezvihidnosti yakbi tilki proektuvalnik nalezhnim chinom otrimav bezpechni obmezhennya dlya FIFOs Parks 1995 Misceve shtuchne viyavlennya v chasi vikonannya mozhlivo neobhidne shob garantuvati virobnictvo pravilnogo vihidnogo kanalu vihidnih danih Zakriti zamknuti ta vidkriti sistemi Zakritij KPN ne maye zhodnih zovnishnih vhidnih abo vihidnih kanaliv Procesi sho ne mayut zhodnogo vhidnogo kanalu diyut yak dzherela danih i procesi sho ne mayut zhodnogo vihidnogo kanalu diyut yak prijmachi danih U vidkritomu KPN kozhen proces maye yak minimum odin vhidnij i vihidnij kanal Determinizm Procesi KPN determinovani Dlya tiyeyi zh vhidnoyi istoriyi voni povinni zavzhdi viroblyati tochno taki sami vihidni Procesi mozhut modelyuvatisya yak poslidovni programi yaki zchituyutsya i pishutsya dlya portiv v bud yakomu poryadku abo kilkosti poki vlastivist determinizmu zberezhena Yak naslidok model KPN determinovana takim chinom sho nastupni chinniki povnistyu viznachayut vihidni sistemi procesi merezhi pochatkovi znaki Vidnini rozrahunok chasu procesiv ne zachipaye vihidni sistemi Monotonnist Procesi KPN monotonni ce oznachaye sho yim lishe potribna chastkova informaciya vhidnogo potoku dlya togo shob viroblyati chastkovu informaciyu vihidnogo potoku Monotonnist dozvolyaye paralelizm U KPN ye povna pochergovist podij useredini signalu Prote nemaye zhodnogo cherguvannya zv yazkiv mizh podiyami v riznih signalah Tomu KPNs lishe chastkovo vporyadkovani ce klasifikuye yih yak nehronometrovanu model DodatkiZavdyaki jogo visokij viraznosti i stislosti KPNs yakij lezhit v osnovi modeli obchislennya zastosovuyetsya v dekilkoh akademichnih modelyuyuchih instrumentah shob predstaviti potochni dodatki yaki mayut pevni vlastivosti napriklad oriyentovanist na potik danih potochnist Vidkrita vihidna struktura Daedalus pidtrimuvana Lejden zasnuvala Centr Doslidzhen v Lejdenskomu Universiteti i prijnyala poslidovni programi napisani na C i viroblyaye vidpovidnij KPN Ce KPN zmig napriklad buti vikoristanim shob nanesti na kartu KPN na zasnovanij FPGA platformi sistematichno Ambric Am2045 v shirokomu masshtabi paralelnij masiv procesora KPN zdijsnyuvanij u kremniyi Tut 336 32 rozryadnih procesoriv spolucheno programovanim spoluchnim drotom viddanogo FIFOs Tomu jogo kanali strogo obmezhuyut blokuvannya zapisiv PrimitkiKahn G 1974 Rosenfeld Jack L red PDF Proc IFIP Congress on Information Processing North Holland ISBN 0 7204 2803 3 Arhiv originalu PDF za 17 listopada 2020 Procitovano 20 kvitnya 2020 Parks Thomas M 1995 Ph D University of California Berkeley Arhiv originalu za 20 zhovtnya 2017 Procitovano 20 kvitnya 2020 Geilen Marc Basten Twan 2003 Degano P red Requirements on the Execution of Kahn Process Networks Proc 12th European Symposium on Programming Languages and Systems ESOP Springer s 319 334 Mike Butts Anthony Mark Jones Paul Wasson A Structural Object Programming Model Architecture Chip and Tools for Reconfigurable Computing Proceedings of April 2007 IEEE Computer SocietyPodalshe chitannyaLee E A Parks T M 1995 Dataflow process networks PDF Proceedings of the IEEE 83 5 773 801 doi 10 1109 5 381846 ISSN 0018 9219 Procitovano 13 lyutogo 2019 Josephs Mark B 2005 Models for Data Flow Sequential Processes U Ali E Abdallah Cliff B Jones Jeff W Sanders eds red Communicating Sequential Processes The First 25 Years Symposium on the Occasion of 25 Years of CSP London UK July 7 8 2004 Revised Invited Papers Lecture Notes in Computer Science T 3525 Berlin Heidelberg Springer Berlin Heidelberg s 85 97 doi 10 1007 11423348 6 ISBN 978 3 540 32265 8