Using Petri nets to design parallel applications

A set of CAA-M schemes corresponding to the most common workflow templates has been created. This makes it possible to use both approaches in order to transform the representations of the algorithm and use their features and advantages (modelling or a set of formal transformations). Using the consid...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2025
Автори:	Pogorilyy, S.D., Vitel, D.Yu.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	PROBLEMS IN PROGRAMMING 2025
Теми:	UDC 004.4
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/776
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-776
record_format	ojs
resource_txt_mv	ppisoftskievua/7a/89000e5c2a4c765a8dd1cf41f4bff87a.pdf
spelling	pp_isofts_kiev_ua-article-7762025-08-27T13:11:22Z Using Petri nets to design parallel applications Використання мереж Петрі для проектування паралельних застосувань Pogorilyy, S.D. Vitel, D.Yu. UDC 004.4 УДК 004.4 A set of CAA-M schemes corresponding to the most common workflow templates has been created. This makes it possible to use both approaches in order to transform the representations of the algorithm and use their features and advantages (modelling or a set of formal transformations). Using the considered templates, a generalised Petri net of the Floyd-Warschall algorithm for a set of parallel threads is constructed. This network is valid for a number of architectures (SMP, MPP, GPGPU technology architectures: Fermi, G80), but requires some specification of its elements for each of them, which is partially considered in the paper.Prombles in programming 2013; 2: 32-40 Створено сукупність САА-М схем, що відповідають найбільш поширеним workflow-шаблонам. Це надає змогу використовувати обидва підходи з метою перетворення представлень алгоритму і використання їх особливостей та переваг (проведення моделювання чи набору формальних трансформацій). З використанням розглянутих шаблонів побудовано узагальнену мережу Петрі алгоритму Флойда-Уоршала для набору паралельних потоків. Ця мережа справедлива для ряду архітектур (SMP, MPP, архітектури технології GPGPU: Fermi, G80), проте потребує певної конкретизації своїх елементів для кожної з них, що частково розглянуто в роботі.Prombles in programming 2013; 2: 32-40 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/776 PROBLEMS IN PROGRAMMING; No 2 (2013); 32-40 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2013); 32-40 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2013); 32-40 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/776/828 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-27T13:11:22Z
collection	OJS
language	Ukrainian
topic	UDC 004.4
spellingShingle	UDC 004.4 Pogorilyy, S.D. Vitel, D.Yu. Using Petri nets to design parallel applications
topic_facet	UDC 004.4 УДК 004.4
format	Article
author	Pogorilyy, S.D. Vitel, D.Yu.
author_facet	Pogorilyy, S.D. Vitel, D.Yu.
author_sort	Pogorilyy, S.D.
title	Using Petri nets to design parallel applications
title_short	Using Petri nets to design parallel applications
title_full	Using Petri nets to design parallel applications
title_fullStr	Using Petri nets to design parallel applications
title_full_unstemmed	Using Petri nets to design parallel applications
title_sort	using petri nets to design parallel applications
title_alt	Використання мереж Петрі для проектування паралельних застосувань
description	A set of CAA-M schemes corresponding to the most common workflow templates has been created. This makes it possible to use both approaches in order to transform the representations of the algorithm and use their features and advantages (modelling or a set of formal transformations). Using the considered templates, a generalised Petri net of the Floyd-Warschall algorithm for a set of parallel threads is constructed. This network is valid for a number of architectures (SMP, MPP, GPGPU technology architectures: Fermi, G80), but requires some specification of its elements for each of them, which is partially considered in the paper.Prombles in programming 2013; 2: 32-40
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/776
work_keys_str_mv	AT pogorilyysd usingpetrinetstodesignparallelapplications AT viteldyu usingpetrinetstodesignparallelapplications AT pogorilyysd vikoristannâmerežpetrídlâproektuvannâparalelʹnihzastosuvanʹ AT viteldyu vikoristannâmerežpetrídlâproektuvannâparalelʹnihzastosuvanʹ
first_indexed	2025-09-17T09:21:36Z
last_indexed	2025-09-17T09:21:36Z
_version_	1843502405331714048
fulltext	Моделі та засоби паралельних і розподілених програм © С.Д. Погорілий, Д.Ю. Вітель, 2013 32 ISSN 1727-4907. Проблеми програмування. 2013. № 2 УДК 004.4 С.Д. Погорілий, Д.Ю. Вітель ВИКОРИСТАННЯ МЕРЕЖ ПЕТРІ ДЛЯ ПРОЕКТУВАННЯ ПАРАЛЕЛЬНИХ ЗАСТОСУВАНЬ Створено сукупність САА-М схем, що відповідають найбільш поширеним workflow-шаблонам. Це надає змогу використовувати обидва підходи з метою перетворення представлень алгоритму і викори- стання їх особливостей та переваг (проведення моделювання чи набору формальних трансформацій). З використанням розглянутих шаблонів побудовано узагальнену мережу Петрі алгоритму Флойда- Уоршала для набору паралельних потоків. Ця мережа справедлива для ряду архітектур (SMP, MPP, ар- хітектури технології GPGPU: Fermi, G80), проте потребує певної конкретизації своїх елементів для кожної з них, що частково розглянуто в роботі. Вступ Алгоритм вирішення певної задачі може бути як централізованим, так і роз- поділеним [1]. У першому випадку він ви- конується на одному виділеному вузлі ме- режі, який володіє великим обсягом ресур- сів (пам'ять, кількість паралельних потоків обробки тощо). Тому такий вузол є муль- типроцесором (у частинному випадку – реалізація Simmetric MultiProcessing – SMP-архітектури). В другому випадку ал- горитм виконується на окремих вузлах ме- режі, що обмінюються даними між собою. Це відповідає концепції мульти- комп’ютерних систем (Massively Parallel Processing – MPP-архітектурі) – систем із масовим паралелізмом. Слід зазначити, що реалізація алго- ритму може також бути орієнтована на ге- терогенні системи (декілька виділених вуз- лів виконують алгоритм на всіх своїх про- цесорах, обмінюючись один з одним лока- льними даними). Доцільно також виділити застосування, які ґрунтуються на технології GPGPU (General purpose graphic processing unit) і використовують графічні адаптери архітектур Fermi, Tesla [2]. Ці системи про- понують принципово інші методи реалізації паралельних застосувань і орієнтовані на певний клас задач, на якому вони демон- струють максимальну продуктивність. Наявність значної сукупності па- ралельних архітектур суттєво диференці- ює методи побудови паралельних про- грам для них. Це створює додаткові ус- кладнення при розробці високопродук- тивних застосувань, оскільки вимагає від розробника необхідних знань особливос- тей побудови відповідної паралельної системи, а також відповідних парадигм паралельного програмування. Тому є важ- ливим етап формалізованого проектування застосувань. Потоки робіт (workflows) [3, 4] є представленням паралельного алгоритму чи системи у вигляді послідовності взає- мопов’язаних етапів чи кроків. Вони є фа- ктично функціональною декомпозицією, оскільки дозволяють виокремити в ній певні функції чи завдання (task). Кожне з таких завдань складається з процесів, що можуть виконуватись як паралельно, так і послідовно. Потоки робіт широко засто- совуються як представлення реальної ро- боти систем різного роду. Як метод фор- малізації окремих складових частин у та- кий спосіб представленої системи в біль- шості випадків використовують матема- тичний апарат мереж Петрі. Це надає мо- жливість проводити моделювання роботи та аналіз темпоральних характеристик ал- горитму або створюваної комп’ютерної системи. Шаблони потоків робіт та САА-М Далі розглянуто шаблони паралель- ного програмування і відповідні їм нота- ції схем паралельних алгоритмів з вико- ристанням математичного апарата модифі- кованих систем алгоритмічних алгебр (САА-М) [5 – 7]. Моделі та засоби паралельних і розподілених програм 33 Шаблон «Parallel split» описує роз- биття гілки виконання на дві або більше, що виконуються паралельно (рис. 1). Рис. 1 САА-М схема:  321 PPPlitparallelSp   – у випадку безпечної мережі (що зале- жить від способу її застосування в ієрархі- чній мережі). Якщо ж вхідне місце може приймати більше ніж одну мітку, то схема буде:   . 321 1 PPPlitparallelSp n i    Шаблон «Synchronization» – злиття декількох гілок виконання в одну послідо- вну гілку, виконання якої починається піс- ля закінчення роботи паралельних гілок (рис. 2). Рис. 2 Вважаючи мережу безпечною, схе- ма шаблону:          ,***** 231  STPPSTPsync   де  xT – оператор встановлення умови x ,  xS – оператор очікування встановлення цієї умови. У випадку небезпечної мережі схема узагальнюється аналогічно до попе- редніх схем. У програмуванні реалізується шля- хом очікування потоком завершення іншо- го потоку та виконання наступної дії. В цьому випадку даному потоку в мережі відповідатиме одна з паралельних та пос- лідовна гілки. Слід зазначити, що у випад- ку небезпечної мережі можливі тупикові ситуації (англ. deadlocks). Шаблон «Exclusive сhoice» – шаб- лон вибору певної гілки виконання в зале- жності від заданої умови (рис. 3). Викону- ється лише обрана гілка. Рис. 3 САА-М схема для безпечної мере- жі: )(* 321 PPPexclChoice cond  – 2 гілки виконання. Для n гілок отримаємо схему:         n n PP PexclChoice  ... ... * 1 1 0 . Відповідає оператору if, switch (case) в мовах програмування. Для випадку багатьох гілок виконання має бути перед- бачена гілка за замовчуванням. В іншому випадку потік виконання може бути прос- то знищений. «Simple merge» – шаблон злиття гі- лок виконання (рис. 4), що створені мере- жею Exclusive choice. Рис. 4 Моделі та засоби паралельних і розподілених програм 34 Тобто виконується одна з послідов- них гілок, а після цього виконуються спі- льні для них задачі. САА-М схема: .* ... ... 1 1 1         n n n P PP esimpleMerg  Місце 1P має містити не більше од- нієї мітки. Вибір декількох гілок (Multichoice) – у залежності від заданих умов відповідна гілка або буде виконуватись паралельно з іншими, або ні (рис. 5). Рис. 5 САА-М схема:  .** 1 0 xx n x PcondPemultiChoic    Використана альфа-фільтрація для обриву відповідної гілки обчислень. Злиття гілок (Multimerge) – створені паралельні гілки виконують специфічні для себе завдання, потім виконують за- вдання, що спільні для усіх (рис. 6). Рис. 6 САА схема:  .* 1 PPmultiMerge x n x   Етап (Milestone) – виконання певного процесу продовжується, якщо інший процес знаходиться в певному стані (рис. 7). Рис. 7 САА-М схема: )).(())(( 210  TPPSPMilestone   Цикли (Arbitrary Cycles) – шаблон, що описує циклічне виконання завдань. Об’єднує усі можливі цикли (рис. 8). Рис. 8 Моделі та засоби паралельних і розподілених програм 35 САА схема: }.{))((* 21 EDFECDBAcicles condcond  Тут E – не тотожний оператор (у термі- нах САА-М), а умова виходу з циклу від- бувається тоді коли друга умова буде false. Крім зазначених шаблонів існують інші, опис яких можна знайти в [3, 4]. Їх САА-М схеми можна подати в аналогіч- ний спосіб. Проектування алгоритму з використанням математичного апарату мереж Петрі Апарат мереж Петрі може бути ви- користаним як у процесі нисхідного, так і висхідного проектування. Проте, для скла- дних систем зазвичай використовують комбінацію цих двох підходів. У будь- якому випадку на певному етапі виникає питання про формалізацію структур даних системи чи алгоритму. Математичний апа- рат кольорових мереж Петрі надає мож- ливість створювати відповідні типи даних. Слід зазначити, що при декомпози- ції алгоритму доцільно використовувати наведені шаблони потоків робіт. Розгля- немо застосування мереж Петрі для реа- лізації паралельного алгоритму Флойда – Уоршала [8] з використанням шаблонів: Arbitrary Cycles – три вкладені цикли алго- ритму можна представити у вигляді однієї мережі цього шаблону з складеною умо- вою виходу; Multiple Instances with a Priori Design-Time Knowledge – використовуєть- ся для породження паралельних потоків; Parallel Split – використовується як для створення паралельних потоків (проте в однопотоковій мережі Петрі алгоритму використаний для паралельної ініціаліза- ції змінних-ітераторів); Sequence; Milestone – використаний для емалювання послідовного зчитування даних із пам’яті й т. д. Далі побудована однопотокова ме- режа алгоритму (рис. 9). Це ієрархічна мережа, що має наступні підмережі: Iter – перевіряє умову закінчення алгоритму та повертає нове значення змінних циклу; Select – вибірка із сховища даних за від- повідною адресою; Update – оновлення сховища за відповідною адресою. Сама дія алгоритму представлена у вигляді пе- реходу process. Дана мережа є WF- мережею, проте вхідне і вихідне місця її об’єднані в одне – Confirmation. При цьо- му використані мережі шаблонів були дещо спрощені. Потік в мережі формалі- зується міткою виконання, що на різних етапах може мати різні типи даних. Інший підхід до представлення системного пото- ку полягає у виділенні окремого типу ма- ркерів. Таким чином процес виконання полягає і переходах маркерів даного типу з одного місця на інше. Рис. 9 Моделі та засоби паралельних і розподілених програм 36 Слід зазначити, що дана мережа уніфікує доступ до сховища даних, тобто мережа не залежить від організації самого сховища. Воно, в свою чергу, може бути як розподіленим у системі, так і централізо- ваним. Далі наведено реалізації операцій роботи зі сховищем. Select-мережа. Дана мережа (рис. 10) приймає на вхід адресу комірки па- м’яті, що формалізована у вигляді двох індексів, та повертає саму комірку. При цьому місце address не є безпечним, що дозволяє фактично моделювати чергу ад- рес на зчитування даних. Саме зчитування йде послідовно. Рис. 10 Update-мережа. Приймає на вхід комірку пам’яті (тобто адресу і значення) для оновлення і видає підтвердження про оновлення сховища (рис. 11). Без даного підтвердження мережа була б описом аси- нхронної операції зміни. Рис. 11 Далі наведемо мережу Iter (рис. 12). Змінні циклів представлені у вигляді окремих місць, а cicle Controller забезпечує завершення роботи алгоритму. Викори- станий шаблон для циклічного виконання в загальній схемі має векторний ітератор. Перехід до мережі для паралельних архітектур (рис. 13) здійснюється наступ- ним чином. Кожен потік представлений у вигляді окремої мітки з індексом потоку. Локальні ресурси потоку помічаються та- кож його індексом. Крім того в мережу до- дається синхронізація потоків. У мережу додано додатковий етап ініціалізації – Initialize. Він призначений для створення паралельних потоків та іні- ціалізації їх локальних ресурсів. Перехід read file зчитує дані з файлу. Його викори- стання в мережі пояснюється лише тим, що остання використовується в процесі Рис. 12 Моделі та засоби паралельних і розподілених програм 37 моделювання роботи алгоритму та переві- рки результатів. Проте з точки зору проек- тування даний блок може бути або відсут- ній або має ініціалізувати сховище даних. Після виконання розглянутого пере- ходу сховища Storage та Iterator storage збе- рігатимуть необхідні дані. Також будуть створені мітки потоків, подальше виконан- ня яких не буде синхронізоване до перехо- ду Barrier у мережі Get iterators (рис. 14). Також потребують змін наведені мережі роботи зі сховищем. Було зміне- но тип даних вхідного місця мережі Select, що дозволило подавати їй на вхід список адресів, за якими йде послідовний вибір даних. При роботі із багатьма потоками слід також синхронізувати їх доступ до мереж Select та Update (зробити їх потокобезпечними). Рис. 13 Рис. 14 Моделі та засоби паралельних і розподілених програм 38 Нова мережа Select (рис. 15) має на- ступні особливості. Кожен із потоків подає на її вхід свій список адрес. Внутрішня си- нхронізація за допомогою місць SyncInOut1, SyncInOut2 вибирає із утворе- ної черги списки по одному, послідовно обробляючи їх. Використаний шаблон Critical Section. Останньою мережею, що не була розглянута є мережа End (рис. 17). Її задачі – конвертація даних у відповідний формат та запис у файл. Вона використовується при моделюванні. Для цілей проектування може бути замінена на іншу. Рис. 15 Мережа Update (рис. 16) виконує зміну комірок пам’яті за аналогічним принципом. У вхідному місці формується множина комірок на оновлення. Мережа в процесі роботи вибирає з неї по одній комірці та виконує оновлення. Слід за- значити, що роботу із сховищем можна організувати і в паралельний спосіб. Для цього в мережі Select слід ускладнити перехід selector, подаючи йому на вхід список адресів. Він, у свою чергу, має зробити перевірку наявності цих адресів у сховищі і повернути відповідний список комірок. Для операції Update виконуються аналогічні дії для її перет- ворення у паралельну операцію. Як і в попередньому випадку Update є реаліза- цією синхронного оновлення сховища. Рис. 16 Моделі та засоби паралельних і розподілених програм 39 Рис. 17 Виникає питання: для яких комп’ютерних архітектур справедлива ба- гатопотокова мережа Петрі представлення алгоритму? Вимоги до систем SMP-архітектури такі: всі потоки мають можливість доступу до усієї пам’яті системи і розглянуті мере- жі задовольняють цим вимогам. Для MPP-архітектури кожен потік володіє своїм сховищем даних, що виявляється розподіленим за всією системою. Тому на- явні операції зі сховищем не є придатни- ми. Але оскільки в ієрархічній схемі дані операції є узагальненими, то схема виявля- ється справедливою для цієї архітектури. Проте необхідна нова конкретизація мереж Update та Select. У цьому випадку зміню- ється тип даних місця Storage. Кожна мітка в даному місці є коміркою пам’яті, що несе інформацію як про свою адресу, так і про дані. Тому, переходячи до розподіленої системи формат адреси змінюється. Для MPP-архітектур він вклю- чатиме в себе номер підсистеми (тобто номер сховища), якому належить комірка. Отримана мережа буде більш загальною, оскільки для SMP-архітектури цей но- мер буде однаковим для усіх потоків. Крім того, для відображення нерівно- правного доступу потоків до певного схо- вища в розподіленій системі (локальний потік має прямий доступ до сховища, інші – через певний інтерфейс та мережу), схе- ма Select та Update мають включати додат- кову перевірку потоку на належність його номеру та даних, що запитуються одній підсистемі. Подібна ситуація виникає і для GPGPU-систем. У цьому випадку змін зазнає підмережа Initialize. Основний по- тік, що помічений вхідним маркером ме- режі є потоком CPU. Він ініціалізує дані сховища, що фактично є даними в глоба- льній пам’яті GPU. Створювані потоки мають вже номер, що складається із трьох компонент – номера групи потоків, та трьох компонент – номера потоку в групі. В системі такої архітектури доступ до пам’яті всіх потоків є спільним. Тому за- значені схеми операцій зі сховищем спра- ведливі в цьому випадку. Побудована ме- режа описує випадок, коли всі GPU пото- ки виконують цикл по всім трьом індек- сам. Це не є оптимальним рішенням для даної архітектури. Крім того бар’єрна си- нхронізація всіх потоків у всіх групах може призвести до тупикових ситуацій (deadlocks). Тобто багатопотокова мережа Петрі не відображає особливостей архіте- ктури GPGPU і тому вимагає подальшої конкретизації. Висновки Запропоновано використання апа- рату мереж Петрі для проектування па- ралельних застосувань суперкомп’ю- терних систем різної архітектури (SMP, MPP, архітектури технології GPGPU: Fermi, Tesla, Kepler). Створено сукупність САА-М схем, що відповідають найбільш поширеним workflow-шаблонам. Це надає змогу ви- користовувати обидва підходи з метою перетворення представлень алгоритму для цих підходів і використання їх особ- ливостей та переваг (проведення моде- лювання чи набору формальних трансфо- рмацій). З використанням розглянутих шаб- лонів побудовано мережу Петрі алгоритму Флойда–Уоршала для набору паралельних потоків (рис. 13). Отримана ієрархічна ме- режа є узагальненою, оскільки не містить в Моделі та засоби паралельних і розподілених програм 40 собі особливостей архітектури системи на які мають виконуватись паралельні пото- ки. З одного боку це дає змогу застосувати отримані мережі для різних архітектур, а з іншого, частина мереж потребує подаль- шої конкретизації, що дозволяє створити представлення застосування чи алгоритму у термінах відповідної цільової архітекту- ри. Наведено особливості модифікації ме- режі для різних архітектур. 1. Таненбаум Э. Архитектура комп’ютера / 5-е изд. – СПб.: Питер, 2007. P. 634–667. 2. David B. Kirk, Wen-mei Hwu. “Programming Massively Parallel Processors: A Hands-on Approach”. Published by Elsevier corp. 3. http://www.workflowpatterns.com/patterns/ 4. Russell N., ter Hofstede A.H.M., van der Aalst W.M.P., Mulyar N. Workflow Control-Flow Patterns : A Revised View. BPM Center Report BPM-06-22, BPMcenter.org, 2006. 5. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ. – М.: Финансы и статистика, 1989. – 192 с. 6. Погорілий С.Д., Мар’яновський В.А., Бойко Ю.В., Вітель Д.Ю. Формування узагальне- них паралельних схем алгоритму Флойда – Уоршала // Системні дослідження та інфо- рмаційні технології. – 2010. – № 1. – С. 52–69. 7. Погорілий С.Д., Трибрат М.І., Вітель Д.Ю. Дослідження паралельних версій алгорит- му Флойда – Уоршала для SMP- та MPP- архітектур. // Математичні машини і сис- теми. – 2011. – № 4. – С. 20–30. 8. Кормен Т., Лейзерсон Ч., Ривест Р. Алго- ритмы, построение и анализ; пер. з англ. Красикова И.В., Ореховой Н.А., Романова В.Н.; под ред. Красикова И.В. – М.: Издательский дом «Вильямс», 2005. – С. 719–725. Одержано 15.03.2012 Про авторів: Погорілий Сергій Демьянович, доктор технічних наук, професор, Вітель Дмитро Юрійович, аспірант першого року навчання. Місце роботи авторів: Київський національний університет імені Тараса Шевченка, 01601, м. Київ, вул. Володимирська, 60. Тел.: (093) 080 7975. E-mail: sdp@univ.net.ua, viteldmitry@gmail.com http://www.workflowpatterns.com/patterns/ mailto:sdp@univ.net.ua mailto:viteldmitry@gmail.com

Using Petri nets to design parallel applications

Репозитарії

Схожі ресурси