Кіріспе
Есептеу моделі
Кан процесінің желісі (KPN, немесе процестер желісі) – есептеудің таратылған моделі, онда детерминистік тізбекті процестердің тобы шексіз бірінші кірген, бірінші шыққан арналар арқылы байланысады. Модельде арнадан мәлімет оқу тоқтатылады, ал жазу тоқтатылмайды. Осы негізгі шектеулерге байланысты, пайда болған процестер желісі есептеу уақытына немесе байланыс кешігуіне тәуелді емес, детерминистік мінез-құлық көрсетеді. Кан процесінің желілері бастапқыда параллель бағдарламаларды модельдеу үшін жасалған, бірақ кіріктірілген жүйелерді, жоғары өнімді есептеу жүйелерін, сигналды өңдеу жүйелерін, ағынды өңдеу жүйелерін, дерек ағыны бағдарламалау тілдерін және басқа да есептеу тапсырмаларын модельдеуге қолайлы болып табылды. KPN-ді 1974 жылы Жиль Кан ұсынды.
A Kahn process network (KPN, or process network) is a distributed model of computation in which a group of deterministic sequential processes communicate through unbounded first in, first out channels. The model requires that reading from a channel is blocking while writing is non blocking. Due to these key restrictions, the resulting process network exhibits deterministic behavior that does not depend on the timing of computation nor on communication delays. Kahn process networks were originally developed for modeling parallel programs, but have proven convenient for modeling embedded systems, high performance computing systems, signal processing systems, stream processing systems, dataflow programming languages, and other computational tasks. KPNs were introduced by Gilles Kahn in 1974.
Орындау үлгісі
KPN – сигналды өңдеу жүйелерін сипаттауға арналған кең таралған модель, онда деректердің шексіз ағыны тізбектей немесе параллель орындалатын процестер арқылы кезең-кезеңімен өңделеді. Параллель процестер болғанымен, бұл модельді іске асыру үшін көп тапсырмалылық немесе параллелизм қажет емес. KPN-де процестер шексіз FIFO арналары арқылы байланысады. Процестер атомдық дерек элементтерін, басқаша айтқанда токендерді, арналардан оқиды және арналарға жазады. Арнаға жазу – бұғаттау емес операция, яғни ол әрқашан сәтті аяқталады және процесті тоқтатпайды, ал арнадан оқу – бұғаттау операциясы, яғни бос арнадан оқуға тырысатын процесс тоқтап, арнада жеткілікті дерек элементтері (токендер) пайда болғанға дейін жалғаса алмайды. Процестерге кіріс арнасында токендердің бар-жоғын токендерді тұтына алмайынша тексеруге рұқсат етілмейді. Бір FIFO бірнеше процесспен тұтынылмайды, және бірнеше процесс бір FIFO-ға жаза алмайды. Процеске берілген нақты кіріс (токендер) тарихы бойынша, процесс әрқашан бірдей нәтижелерді (токендерді) беретін детерминистік болуы тиіс. Процестердің уақыты немесе орындалу реті нәтижеге әсер етуі керек емес, сондықтан кіріс арналарын токендерге тексеруге тыйым салынады.
Семантиканы Петри торлары ретінде өңдеу
Жоғарыда көрсетілген KPN-дегі P процесі егер алдымен A арнасынан, содан кейін B арнасынан деректерді оқып, кейбір есептеулер жасап, нәтижені C арнасына жазатын болса, онда осы процестің орындалу моделін оң жақта көрсетілген Петри желісімен модельдеуге болады. PE ресурстық орнындағы жалғыз марке процестің әртүрлі кіріс деректері үшін бір уақытта орындалуына тыйым салады. A немесе B арнасына дерек келгенде, маркелер тиісінше FIFO A және FIFO B орындарына қойылады. Петри желісінің өтулері тиісті I/O операцияларымен және есептеулермен байланыстырылған. Дерек C арнасына жазылғаннан кейін, PE ресурсы бастапқы күйіне қайта келіп, жаңа деректерді оқуға мүмкіндік береді.
Каналдардың шектелуі
Канал егер кез келген мүмкін орындалуда ең көп дегенде тұтылмаған токендері болса, қатаң шектелген болып есептеледі. KPN егер барлық каналдары қатаң шектелген болса, қатаң шектелген болып табылады. Тұтылмаған токендердің саны процестердің орындалу ретіне (жоспарлауға) байланысты. Өздігінен дерек көзі жоспарлаушы осы токендерді тұтынатын процестерді орындамаса, каналға шексіз көп токендерді шығара алады. Нақты қолданбада шексіз FIFO болуы мүмкін емес, сондықтан FIFO-ның жоспарлауы және ең жоғары сыйымдылығы практикалық іске асыру үшін ескерілуі керек. FIFO-ның ең жоғары сыйымдылығын бірнеше тәсілмен басқаруға болады: FIFO-ның шектері FIFO-ның ағып кетуін болдырмау үшін жобалау кезінде математикалық түрде есептелуі мүмкін. Дегенмен, бұл барлық KPN үшін мүмкін емес. KPN-нің қатаң шектелгенін тексеру – шешілмейтін мәселе. Сонымен қатар, практикалық жағдайларда шектелген деректерге тәуелді болуы мүмкін. FIFO шектерін қажеттікке қарай арттыруға болады. Блоктау жазуларын пайдалануға болады, осылайша FIFO толған кезде процесс тоқтатылады. Алайда, егер жобалаушы FIFO үшін қауіпсіз шекараларды дұрыс анықтамаса, бұл тәсіл жасанды тұйыққа алып келуі мүмкін (Parks, 1995). Дұрыс нәтижені алуды қамтамасыз ету үшін орындалу кезінде жергілікті жасанды анықтау қажет болуы мүмкін.
The number of unconsumed tokens depends on the execution order (scheduling) of processes. A spontaneous data source could produce arbitrarily many tokens into a channel if the scheduler would not execute processes consuming those tokens. A real application can not have unbounded FIFOs and therefore scheduling and maximum capacity of FIFOs must be designed into a practical implementation. The maximum capacity of FIFOs can be handled in several ways:
FIFO bounds can be mathematically derived in design to avoid FIFO overflows. This is however not possible for all KPNs. It is an undecidable problem to test whether a KPN is strictly bounded by Moreover, in practical situations, the bound may be data dependent. FIFO bounds can be grown on demand. Blocking writes can be used so that a process blocks if a FIFO is full. This approach may unfortunately lead to an artificial deadlock unless the designer properly derives safe bounds for FIFOs (Parks, 1995). Local artificial detection at run time may be necessary to guarantee the production of the correct output.
Жабық және ашық жүйелер
Жабық KPN-де сыртқы кіріс немесе шығыс арналары болмайды. Кіріс арналары жоқ процестер дерек көздері болып табылады, ал шығыс арналары жоқ процестер дерек тұндырғыштары болып табылады. Ашық KPN-де әрбір процесс кем дегенде бір кіріс және бір шығыс арнасына ие.
Біртектілік
KPN процестері монотонды. Көбірек таңбаларды оқу тек көбірек таңбаларды жазуға ғана алып келеді. Болашақта оқылған таңбалар болашақта жазылған таңбаларға ғана әсер ете алады. KPN-да сигналдың ішіндегі оқиғалардың толық реті болады. Дегенмен, әртүрлі сигналдардағы оқиғалардың арасында реттелу қатынасы жоқ. Осылайша, KPN-лер тек ішінара реттелген, оларды уақытталмаған модель ретінде жіктеуге болады.
Қолданбалар
Жоғары экспрессивтілігі мен лаконизмдігінің арқасында, KPN есептеу моделінің негізі ретінде, белгілі бір қасиеттері бар (мысалы, дерек ағынына бағытталған, ағынға негізделген) ағынды қосымшаларды ұсыну үшін бірнеше академиялық модельдеу құралдарында қолданылады. Лейден университетінің Лейден кіріктірілген зерттеу орталығымен қолдау көрсетілетін ашық кодты Daedalus фреймворкі C тілінде жазылған тізбекті бағдарламаларды қабылдайды және оған сәйкес KPN құрайды. Бұл KPN-ді, мысалы, KPN-ді FPGA негізделген платформаға жүйелі түрде бейімдеу үшін пайдалануға болады. Ambric Am2045 массивті параллель процессорлар массиві – нақты кремнийде іске асырылған KPN. Оның 336 32 биттік процессорлары арнайы FIFO-лардан тұратын бағдарламаланатын өзара байланыс арқылы қосылған. Осылайша, оның арналары жазу кезінде тоқтаумен қатаң шектелген. Кейбір AMD Xilinx Versals-тегі AI Engine-дер Kahn Process Network-тің құрылыс блоктары болып табылады.