Дослідження паралелізм емпіричних моделей оптимальної складності за допомогою мережі Петрі

Автор(и)

  • Mikhail Gorbiychuk Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019, Україна https://orcid.org/0000-0002-8586-1883
  • Olga Bila Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019, Україна https://orcid.org/0000-0003-2245-7434
  • Taras Humeniuk Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019, Україна https://orcid.org/0000-0003-2610-2550

DOI:

https://doi.org/10.15587/1729-4061.2019.171632

Ключові слова:

емпірична модель, генетичний алгоритм, паралелізм, мережа Петрі, число операцій

Анотація

Багато фізичних процеси і явища, з огляду на свою складність, не можуть бути описані аналітично. У таких випадках застосовують емпіричне моделювання. Для побудови емпіричних моделей оптимальної складності, яка має вигляд полінома заданого степеня, в роботі використаний метод, в основі якого лежить генетичний підхід. Реалізація розробленого методу вимагає багаторазового розв’язування системи лінійних алгебраїчних рівнянь. Розв’язування системи лінійних алгебраїчних рівнянь здійснюється шляхом приведення відповідної матриці, до верхньої діагональної формі з одиницями на головній діагоналі. Аналіз алгоритму приведення матриці до верхнього діагонального вигляду  показав, що така процедура володіє внутрішнім паралелізмом. На основі створеної моделі обчислювального процесу у вигляді мережі Петрі розроблено стратегію побудови паралельного алгоритму для розв’язування системи лінійних алгебраїчних рівнянь. Суть стратегії в тому, що обчислення здійснюються на декількох паралельних процесорах. Одному з них присвоєні координуючі функції, і він названий майстром. Інші процесори - робітники - знаходяться в підпорядкуванні майстра. Поділ обсягу обчислень такий, що кількість рядків матриці, з якими оперує майстер, більша не менше ніж на одиницю, за відповідну  кількість рядків, відведених робітникові. Для запропонованої стратегії оцінена ефективність паралельного алгоритму за критерієм сумарної кількості арифметичних операцій. Запропонована стратегія є складовою частиною процесу синтезу емпіричної моделі оптимальної складності на основі генетичних алгоритмів. Поділ обчислювального навантаження між паралельно працюючими процесорами (майстром і робочими) забезпечує прискорення обчислювального процесу в п'ять і більше разів

Біографії авторів

Mikhail Gorbiychuk, Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019

Доктор технічних наук, професор

Кафедра комп’ютерних систем і мереж

Olga Bila, Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019

Аспірант

Кафедра комп’ютерних систем і мереж

Taras Humeniuk, Івано-Франківський національний технічний університет нафти і газу вул. Карпатська, 15, м. Івано-Франківськ, Україна, 76019

Кандидат технічних наук

Кафедра комп’ютерних систем і мереж

Посилання

  1. Gorbiychuk, M. I., Schupak, I. V., Oskolip, T. (2011). Metod sinteza empiricheskih modeley s uchetom pogreshnostey izmereniy. Metody i pribory kontrolya kachestva, 2 (27), 67–76.
  2. Gorbiychuk, M. I., Shufnarovych, M. A. (2010). The Method of Constructing Mathematical Models of Complex Processes on the Basis of Genetic Algorithms. Iskusstvenniy intellekt, 4, 50–57.
  3. Gorbiychuk, M. I., Kohutiak, M. I., Vasylenko, O. B., Shchupak, I. V. (2009). Metod syntezu empirychnykh modelei na zasadakh henetychnykh alhorytmiv. Rozvidka ta rozrobka naftovykh i hazovykh rodovyshch, 4, 72–79.
  4. Stepashko, V. S., Bulgakova, A. S. (2013). Obobschennyy iteratsionnyy algoritm metoda gruppovogo ucheta argumentov. Upravlyayuschie sistemy i mashiny, 2, 5–17.
  5. Gupta, S., Bhardwaj, S., Bhatia, P. K. (2011). A reminiscent study of nature inspired computation. International Journal of Advances in Engineering & Technology, 1 (2), 117–125.
  6. Voevodin, V., Antonov, A., Popova, N. (2019). Studying the Structure of Parallel Algorithms as a Key Element of High-Performance Computing Education. Lecture Notes in Computer Science, 199–210. doi: https://doi.org/10.1007/978-3-030-10549-5_16
  7. Ortega, J. M. (1988). Introduction to parallel and vector solution of linear systems. Springer. doi: https://doi.org/10.1007/978-1-4899-2112-3
  8. Dvukhglavov, D. E., Kulynych, V. E. (2017). Development of software solution for building route of a orders group delivery in presence of time constraints. Bulletin of National Technical University "KhPI". Series: System Analysis, Control and Information Technologies, 55, 64–71. doi: https://doi.org/10.20998/2079-0023.2017.55.11
  9. Himich, A. N., Molchanov, I. N., Popov, A. V., Chistyakova, T. V., Yakovlev, M. F. (2008). Parallel'nye algoritmy resheniya zadach vychislitel'noy matematiki. Kyiv: Naukova dumka, 248.
  10. Khimich, A. N., Popov, A. V., Polyankoa, V. V. (2011). Algorithms of parallel computations for linear algebra problems with irregularly structured matrices. Cybernetics and Systems Analysis, 47 (6), 973–985. doi: https://doi.org/10.1007/s10559-011-9377-4
  11. Rutkovskaya, D., Pilin'skiy, M., Rutkovskiy, L. (2004). Neyronnye seti, geneticheskie algoritmy i nechetkie sistemy. Moscow: Goryachaya liniya-Telekom, 452.
  12. Bogatyrev, M. Yu. Invarianty i simmetrii v geneticheskih algoritmah. Available at: http://www.raai.org/conference/cai-08/files/cai-08_paper_287.pdf
  13. Gladkov, L. A., Kureychik, V. V., Kureychik, V. M. (2006). Geneticheskie algoritmy. Moscow: FIZMATLIT, 320.
  14. Gorbiychuk, M. I., Medvedchuk, V. M., Pashkovskyi, B. V. (2014). The parallelism in the algorithm of the synthesis of models of optimal complexity based on the genetic algorithms. Eastern-European Journal of Enterprise Technologies, 4 (2 (70)), 42–48. doi: https://doi.org/10.15587/1729-4061.2014.26305
  15. Gorbiychuk, M. I., Shufnarovych, M. A. (2010). Metod syntezu matematychnykh modelei kolyvnykh protsesiv z nekratnymy chastotamy. Naukovyi visnyk Ivano-Frankivskoho natsionalnoho tekhnichnoho universytetu nafty i hazu, 1, 105–112.
  16. Luszczek, P. (2009). Parallel Programming in MATLAB. The International Journal of High Performance Computing Applications, 23 (3), 277–283. doi: https://doi.org/10.1177/1094342009106194
  17. Verzhbitskiy, V. M. (2002). Osnovy chislennyh metodov. Moscow: Vysshaya shkola, 840.
  18. Paterson, Dzh. (2000). Teoriya setey Petri i modelirovanie sistem. Moscow: Mir, 263.
  19. Marahovskiy, V. B., Rozenblyum, L. Ya., Yakovlev, A. V. (2014). Modelirovanie parallel'nyh protsessov. Seti Petri: kurs dlya sistemnyh arhitektorov, programmistov, sistemnyh analitikov, proektirovschikov slozhnyh sistem upravleniya. Sankt-Peterburg: Professional'naya literatura, 398.
  20. Gorbiychuk, M. I., Medvedchuk, V. M., Lazoriv, A. N. (2016). Analysis of Parallel Algorithm of Empirical Models Synthesis on Principles of Genetic Algorithms. Journal of Automation and Information Sciences, 48 (2), 54–73. doi: https://doi.org/10.1615/jautomatinfscien.v48.i2.60
  21. Korn, G., Korn, T. (1978). Spravochnik po matematike dlya nauchnyh rabotnikov i inzhenerov. Moscow: Nauka, 832.
  22. Volkov, E. A. (1987). Chislennye metody. Moscow: Nauka, 248.

##submission.downloads##

Опубліковано

2019-06-26

Як цитувати

Gorbiychuk, M., Bila, O., & Humeniuk, T. (2019). Дослідження паралелізм емпіричних моделей оптимальної складності за допомогою мережі Петрі. Eastern-European Journal of Enterprise Technologies, 3(4 (99), 56–68. https://doi.org/10.15587/1729-4061.2019.171632

Номер

Том 3 № 4 (99) (2019): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2019 Mikhail Gorbiychuk, Olga Bila, Taras Humeniuk

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.