2024 № 2 (63)

СОДЕРЖАНИЕ

Перминов П. О., Мигов Д. А. Расчет надежности протяженных трехсвязных сетей
Малышкин В. Э., Перепелкин В. А. Определение понятия программы
Быстров А. В., Вирбицкайте И. Б., Ошевская Е. С. Инструментальные системы, поддерживающие стохастические сетевые модели
Козлов М.А., Панова Е.А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos

П. О. Перминов, Д.А. Мигов

Новосибирский государственный университет, 630090, Новосибирск, Россия

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

РАСЧЕТ НАДЕЖНОСТИ ПРОТЯЖЕННЫХ ТРЕХСВЯЗНЫХ СЕТЕЙ

УДК 621.311.1+519.17

DOI: 10.24412/2073-0667-2024-2-5-15

EDN: VZCSXV

Рассматривается задача расчета вероятности связности протяженных сетей с ненадежными каналами связи. Точный расчет данного показателя — NP-трудная задача, что делает его затруднительным для сетей реальной размерности.

Предполагается, что сеть имеет протяженную структуру, что характерно для сетей, расположенных в шахтах, кораблях, другим протяженных обьектов, а также линейных беспроводных сенсорных сетей, предназначенных для мониторинга различных протяженных объектов, таких как трубопроводы. В отличие от ранее исследованного нами случая двусвязной сети, здесь мы предполагаем, что сеть трехсвязная и имеет группу поперечных сечений, т.е. вершинных разрезов.

Для ускорения расчета надежности подобных сетей предлагается использовать структурную декомпозиции сети на основе формулы разложения по трехвершинному сечению. Этот метод, с использованием рекурсивного обхода сечений, ускоряет расчет надежности протяженных сетей по сравнению с известными методами. Результаты численных экспериментов подтверждают эффективность предлагаемого подхода.

Ключевые слова: надежность сети, случайный граф, трехсвязный граф, вероятность связности, метод факторизации, декомпозиция сети, сечение, сепаратор.

Работа выполнена в рамках проекта № 0251-2021-0005 ПФИ ИВМиМГ СО РАН.

Список литературы

Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи математических наук. 2015. Т. 70. № 1 (421). С. 35-88.
Мочалов В.А., Мочалова А.В. Применение экспертных систем для расчета вероятности связности между узлами графа //В сборнике: Гибридные и синергетические интеллектуальные системы. Материалы V Всероссийской Поспеловской конференции с международным участием. Под редакцией А.В. Колесникова. 2020. С. 226-235.
Родионов А.С. Можно ли добиться дальнейшего ускорения расчета характеристик связности случайного графа? // Проблемы информатики. 2022. № 4 (57). С. 39-52.
Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. T. 8. № 3. P. 410-421.
Rodionova O.K., Rodionov A.S., Choo H. Network probabilistic connectivity: exact calculation with use of chains // Lecture Notes in Computer Science. 2004. T. 3045. C. 315-324.
Satyanarayana A., Wood R.K. A linear-time algorithm for computing K—terminal reliability in series-parallel networks // SIAM. J. Comput. 1985. T. 14. P. 818-883.
D. Migov, O. Rodionova, A. Rodionov, H. Choo. Network probabilistic connectivity: using node cuts // Springer Lecture Notes in Computer Science (in EUC Workshops). Vol. 4097, 2006, p. 702-709.
Тарханова О.Ю., Шахов В.В. К вопросу оценки эффективности беспроводных сенсорных сетей // Проблемы информатики. 2020. № 1 (46). С. 35-65.
Фархадов М.П.О., Блинова О.В., Васьковский С.В. Оценка надежности системы связи с подвижными узлами // Датчики и системы. 2018. V^s 5 (225). С. 3-8.
Шахов В.В., Чен X., Юргенсон А.Н., Лошкарев А.В. К вопросу оценки надежности линейных беспроводных сенсорных сетей // Проблемы информатики. 2022. № 4 (57). С. 120-128.
N. Mohamed, J. Al-Jaroodi, I. Jawhar and S. Lazarova-Molnar. Failure impact on coverage in linear wireless sensor networks // 2013 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), Toronto, ON, Canada. IEEE Press, 2013. P. 188-195.
Мигов. Д.А. Диссертация на соискание ученой степени кандидата физико-математических наук «Расчёт вероятности связности случайного графа с применением сечений». Новосибирск: ИВМиМГ СО РАН. 2008. 97 С.
Мигов Д.А. Использование вершинных разрезов для точного вычисления вероятности связности сети // Труды Международной конференции «Вычислительные и информационные технологии в науке, технике и образовании» (Павлодар, 20-22 сентября 2006 года) - Том II - С. 51-58.
Page L.B., Perry J.E. A Practical Implementation of the Factoring Theorem for Network Reliability // IEEE transactions on reliability. 1988. Vol. 37, n. 3. P. 259-267.
Мигов Д.А. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. No.47. С. 62-86. DOL 10.17223/20710410/47/6.
Burgos J.M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discrete Applied Mathematics. 2016. V. 198. P. 91-100.

статья

Библиографическая ссылка: Перминов П. О., Мигов Д. А. Расчет надежности протяженных трехсвязных сетей //"Проблемы информатики", 2024, № 2, с.5-15. DOI: 10.24412/2073-0667-2024-2-5-15. - EDN: VZCSXV

В.Э. Малышкин, В. А. Перепелкин

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

ОПРЕДЕЛЕНИЕ ПОНЯТИЯ ПРОГРАММЫ

УДК 004.4

DOI: 10.24412/2073-0667-2024-2-16-31

EDN: CEDVVD

При решении сложных задач в программировании важную роль играет определение понятия программы. От того, как понимается программа зависит подход к ее конструированию и ее свойства. В работе рассматривается понятие программы и дается ему определение на базе теории синтеза параллельных программ на вычислительных моделях. Предлагаемое определение отражает подход к процессу конструирования программы, определяемый этой теорией, начиная с описания задачи в терминах предметной области и заканчивая исполнением императивной программы с динамическими свойствами. Подход обладает рядом преимуществ, рассматриваемых в статье, таких как возможность выполнения алгоритмических оптимизаций, возможность автоматического конструирования программы, возможность обеспечения нефункциональных требований и проч. Рассматриваются параллели с другими определениями программ и особенности практического применения предлагаемого подхода.

Ключевые слова: понятие программы, автоматическое конструирование программ, активные знания.

Список литературы

Вальковский В. А., Малышкин В.Э. Синтез параллельных программ и систем на вычис-лительных моделях / . Отв. ред. В.Е. Котов; АН СССР, Сиб. отд-ние, ВЦ. Новосибирск: Наука. Сиб. отд-ние, 1988.— 126 с.
Малышкин В.Э. Технология фрагментированного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2012. №46 (305).
Victor Malyshkin. Active Knowledge, LuNA and Literacy for Oncoming Centuries. In Essays Dedicated to Pierpaolo Degano on Programming Languages with Applications to Biology and Security - Volume 9465. Springer-Verlag, Berlin, Heidelberg, 2015. p. 292-303.
Вычислимость в произвольных областях и базисах: Сб. научн. ст. — М: ВИНИТИ, 1982. — С. 3—58. — (Семиотика и информатика; Вып. № 19).
Янов, Ю.И. Метод сверток для разрешения свойств формальных систем. — М. : ИПМ им. М.В.Келдыша, 1977. — Вып. 11. — 41 с. — (Институт прикладной математики АН СССР. Препринт; № 11 за 1977 г.). — URL: https://library.keldysh.ru/preprint.asp?id=1977-ll.
Вальковский В.А. О синтезе оптимальных программ на базе вычислительных моделей // Программирование. — 1980. — №6. — С. 27-36
Malyshkin. V., Perepelkin. V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // Journal of Supercomputing, S.I.: Parallel Computing Technologies - 2017. Springer, 2017. pp. 1-7. DOI: 10.1007/sll227-016-1781-0.
Кудрявцев А. А., Малышкин В. Э., Нуштаев Ю. Ю., Перепелкин В. А., Спирин В. А. Эффективная фрагментированная реализация краевой задачи фильтрации двухфазной жидкости // Проблемы информатики. 2023. № 2. С. 45-73. DOI: 10.24412/2073-0667-2023-2-45-73
Akhmed-Zaki, D., Lebedev, D., Perepelkin, V. Implementation of a three dimensional three-phase fluid flow (“oil-water-gas”) numerical model in LuNA fragmented programming system // Journal of Supercomputing (2017). - 73(2). Springer, 2017. pp. 624-630. DOI: 10.1007/sll227-016-1780-l.
Перепелкин В.А., Софронов И.В., Ткачева А.А. Автоматизация конструирования численных параллельных программ с заданными нефункциональными свойствами на базе вычислительных моделей //журнал Проблемы информатики, 2017, № 4. С.47-60.
Malyshkin, V.E., Perepelkin, V.A. (2011). LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2011. Lecture Notes in Computer Science, vol 6873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23178-0_5
Victor Malyshkin, Vladislav Perepelkin, and Artem Lyamin. 2023. Trace Balancing Technique for Trace Playback in LuNA System. In Parallel Computing Technologies: 17th International Conference, PaCT 2023, Astana, Kazakhstan, August 21-25, 2023, Proceedings. Springer-Verlag, Berlin, Heidelberg, 42-50. https://doi.org/10.1007/978-3-031-41673-6_4
Perepelkin V., Malkhanov V., Zakirov V. Preliminary results on fault tolerance support in LuNA system // Bull. Nov. Comp. Center, Comp. Science, 46 (2022), P. 43-55.
Malyshkin, V., Akhmed-Zaki, D., Perepelkin, V. Parallel programs execution optimization using behavior control in LuNA system //J Supercomput. — Springer, 2021. — C. 9771-9779. — DOI: 10.1007/sll227-021-03654-2.
Малышкин В. Э., Перепелкин В. А. Мультиагентный подход к повышению эффективности исполнения фрагментированных программ в системе LuNA //"Проблемы информатики 2023, № 3, с.55-67. DOL 10.24412/2073-0667-2023-3-55-67.
Belyaev, N., Kireev, S. (2019). LuNA-ICLU Compiler for Automated Generation of Iterative Fragmented Programs. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2019. Lecture Notes in Computer Science(), vol 11657. Springer, Cham, https://doi.org/10.1007/978-3-030-25636- 4 2

статья

Библиографическая ссылка: Малышкин В. Э., Перепелкин В. А. Определение понятия программы //"Проблемы информатики", 2024, № 2, с.16-31. DOI: 10.24412/2073-0667-2024-2-16-31. - EDN: CEDVVD

А. В. Быстров, И. Б. Вирбицкайте, Е.С. Ошевская

Институт систем информатики им. А. П. Ершова, 630090, Новосибирск, Россия

ИНСТРУМЕНТАЛЬНЫЕ СИСТЕМЫ, ПОДДЕРЖИВАЮЩИЕ СТОХАСТИЧЕСКИЕ СЕТЕВЫЕ МОДЕЛИ

УДК 004.94+519.876.5

DOI: 10.24412/2073-0667-2024-2-32-57

EDN:KNBRYZ

Стохастические сети Петри - мощное средство моделирования параллельных недетерминированных систем с вероятностными характеристиками, применяемое в самых разных областях человеческой деятельности. Они сочетают наглядность графического представления с развитым математическим и алгоритмическим аппаратом анализа, позволяют изучать не только качественные, но и количественные свойства систем, такие как пропускная способность, надежность, время ожидания и т. и. Разработаны и продолжают появляться новые программные инструменты, поддерживающие создание, модификацию и анализ свойств моделей систем на основе различных вариантов стохастических сетей Петри. В данной работе рассматриваются несколько таких инструментов, доступных в сети Интернет и получивших признание пользователей, обсуждаются предоставляемые ими возможности и проводится их сравнение. Основная цель работы - облегчить исследователю и инженеру выбор наиболее подходящего инструмента моделирования и анализа для решения стоящей перед ним задачи.

Ключевые слова: стохастические сети Петри, моделирование, анализ производительности, инструментальные системы.

Список литературы

Reisig W. Petri Nets: An Introduction. Vol. 4. Springer, 1985. (EATCS Monographs on Theoretical Computer Science). DOI: 10.1007/978-3-642-69968-9.
Boyer M., Roux O. On the Compared Expressiveness of Arc, Place and Transition Time Petri Nets // Fundamenta Informaticae. 2008. Jan. Vol. 88. P. 225-249.
Berthomieu B., Diaz M. Modeling and verification of time dependent systems using time Petri nets // IEEE Transactions on Software Engineering. 1991. Mar. Vol. 17, no. 3. P. 259-273. DOI: 10.1109/32.75415.
Molloy M. Performance Analysis Using Stochastic Petri Nets // IEEE Trans. Computers. 1982. Vol. 31, no. 9. P. 913-917. DOI: 10.1109/TC.1982.1676110.
Vicario E., Sassoli L., Carnevali L. Using Stochastic State Classes in Quantitative Evaluation of Dense-Time Reactive Systems // IEEE Trans. Software Eng. 2009. Vol. 35, no. 5. P. 703-719. DOI: 10.1109/TSE.2009.36.
Wang J. Stochastic Timed Petri Nets and Stochastic Petri Nets // Timed Petri Nets: Theory and Application. Boston, MA : Springer US, 1998. P. 125-153. DOI: 10.1007/978-1-4615-5537-7,5.
Ajmone Marsan M. [et al.]. An introduction to generalized stochastic Petri nets // Microelectronics Reliability. 1991. Jan. Vol. 31, no. 4. P. 699-725. DOI: 10.1016/0026-2714(91)90010-5.
Ajmone Marsan M., Chiola G. On Petri nets with deterministic and exponentially distributed firing times // Advances in Petri Nets 1987, covers the 7th European Workshop on Applications and Theory of Petri Nets, Oxford, UK, June 1986. Vol. 266 / ed. by G. Rozenberg. Springer, 1986. P. 132-145. (Lecture Notes in Computer Science). DOI: 10.1007/3-540-18086-9,23.
Dugan J. [et al.]. Extended Stochastic Petri Nets: Applications and Analysis // Performance ’84, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation / ed. by E. Gelenbe. North-Holland, 1984. P. 507-519.
Ajmone Marsan M. [et al.]. The Effect of Execution Policies on the Semantics and Analysis of Stochastic Petri Nets // IEEE Trans. Software Eng. 1989. Vol. 15, no. 7. P. 832-846. DOI: 10.1109/32.29483.
German R., Lindemann C. Analysis of stochastic Petri nets by the method of supplementary variables // Performance Evaluation. 1994. May. Vol. 20, no. 1-3. P. 317-335. DOL 10.1016/0166- 5316(94)90020-5.
Тарасюк И. В. Стохастические сети Петри - формализм для моделирования и анализа производительности вычислительных процессов // Системная информатика. Новосибирск, 2004. С. 135-194.
German R. Performance analysis of communication systems : modelling with non- Markovian stochastic Petri nets. Wiley, 2000. P. 464.
Biagi M. [et al.]. Exploiting Non-deterministic Analysis in the Integration of Transient Solution Techniques for Markov Regenerative Processes // Quantitative Evaluation of Systems. Springer International Publishing, 2017. P. 20-35. DOL 10.1007/978-3-319-66335-7 2.
Martina S. [et al.]. Performance Evaluation of Fischer’s Protocol through SteadyState Analysis of Markov Regenerative Processes // 2016 IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). 09/2016. P. 355-360. DOL 10.1109/MASCOTS.2016.72.
Horva’th A. [et al.]. Transient analysis of non-Markovian models using stochastic state classes // Performance Evaluation. 2012. Vol. 69, no. 7/8. P. 315-335. DOL 10.1016/j.peva.2011.11.002.
Amparore Е. Stochastic Modelling and Evaluation Using GreatSPN // ACM SIGMETRICS Performance Evaluation Review. New York, NY, USA, 2022. June. Vol. 49, no. 4. P. 87-91. DOI: 10.1145/3543146.3543165.
Amparore E. [et al.]. 30 Years of GreatSPN // Principles of Performance and Reliability Modeling and Evaluation: Essays in Honor of Kishor Trivedi on his 70th Birthday / ed. by L. Fiondella, A. Puliafito. Cham : Springer International Publishing, 2016. P. 227-254. DOI: 10.1007/978-3-31930599-8-9.
K. J., Kristensen L. Coloured Petri Nets. Springer Berlin Heidelberg, 2009. DOI: 10.1007/b95112.
ISO/IEC. Software and Systems Engineering - High-level Petri Nets, Part 2: Transfer Format, International Standard ISO/IEC 15909, February 2011.
Kindler E. The Petri Net Markup Language and ISO/IEC 15909-2: Concepts, Status, and Future Directions // Tagungsband Entwurf komplexer Automatisierungssysteme EKA. 2006. P. 35-55.
Clarke E., Emerson E. Design and synthesis of synchronization skeletons using branching time temporal logic // Logics of Programs / ed. by D. Kozen. Springer Berlin Heidelberg, 1982. P. 52-71.
De’harbe D. A Tutorial Introduction to Symbolic Model Checking // Logic for Concurrency and Synchronisation / ed. by R. de Queiroz. Dordrecht : Springer Netherlands, 2003. P. 215-237. DOI: 10.1007/0-306-48088-3_5.
Beccuti M., Franceschinis G., Haddad S. Markov Decision Petri Net and Markov Decision Well- Formed Net Formalisms // Petri Nets and Other Models of Concurrency - ICATPN 2007 / ed. by J. Kleijn, A. Yakovlev. Springer Berlin Heidelberg, 2007. P. 43-62. DOI: 10.1007/978-3-540-73094-1-6.
Emerson E., Sistla A. Symmetry and model checking // Formal Methods in System Design. 1996. Vol. 9, no. 1. P. 105-131. DOL 10.1007/BF00625970.
Babar J. [et al.]. GreatSPN Enhanced with Decision Diagram Data Structures // Applications and Theory of Petri Nets / ed. by J. Lilius, W. Penczek. Springer Berlin Heidelberg, 2010. P. 308-317.
Chaki S., Gurfinkel A. BDD-Based Symbolic Model Checking // Handbook of Model Checking / ed. by E. Clarke [et al.]. Springer, 2018. P. 219-245. DOI: 10.1007/978-3-319-10575-8-8.
Rodriguez R., Bernardi S., Zimmermann A. An Evaluation Framework for Comparative Analysis of Generalized Stochastic Petri Net Simulation Techniques // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2020. Vol. 50. P. 2834-2844. DOL 10.1109/TSMC.2018.2837643.
Pernice S. [et al.]. Multiple Sclerosis Disease: A Computational Approach for Investigating Its Drug Interactions // Computational Intelligence Methods for Bioinformatics and Biostatistics / ed. by P. Cazzaniga [et al.]. Cham : Springer International Publishing, 2020. P. 299-308. DOI: 10.1007/9783-030-63061-4 26.
Amparore E., Donatelli S., Landini E. Modelling and Evaluation of a Control Room Application // Application and Theory of Petri Nets and Concurrency / ed. by W. van der Aalst, E. Best. Cham : Springer International Publishing, 2017. P. 243-263.
Richard L. Performance Results for the CSMA/CD Protocol Using GreatSPN // Journal of Systems and Software. 1997. Vol. 37, no. 1. P. 75-90. DOI: 10.1016/S0164-1212(96)00041-6.
Amparore E., Donatelli S. GreatTeach: A Tool for Teaching (Stochastic) Petri Nets // Application and Theory of Petri Nets and Concurrency. Springer International Publishing, 2018. P. 416-425. DOL 10.1007/978-3-319-91268-4_24.
Castagno P. [et al.]. A computational framework for modeling and studying pertussis epidemiology and vaccination // BMC Bioinformatics. 2020. Vol. 21, no. 8. P. 344. DOL 10.1186/sl2859-020-03648-6.
The GreatSPN Framework. URL: https://github.com/greatspn/SOURCES Accessed: 01/12/2024.
Paolieri M. [et al.]. The ORIS Tool: Quantitative Evaluation of Non-Markovian Systems // IEEE Trans. Software Eng. 2021. Vol. 47, no. 6. P. 1211-1225. DOI: 10.1109/TSE.2019.2917202.
Carnevali L., Paolieri М., Vicario Е. The ORIS tool: app, library, and toolkit for quantitative evaluation of non-Markovian systems // ACM SIGMETRICS Performance Evaluation Review. 2022. Vol. 49, no. 4. P. 81-86. DOI: 10.1145/3543146.3543164.
Stewart W. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1995. DOI: 10.1515/9780691223384.
Carnevali L. [et al.]. Non-Markovian Performability Evaluation of ERTMS/ETCS Level 3 // Computer Performance Engineering - 12th European Workshop, EPEW 2015. Vol. 9272 / ed. by M. Beltran, W. Knottenbelt, J. Bradley. Cham : Springer, 2015. P. 47-62. (Lecture Notes in Computer Science). DOL 10.1007/978-3-319-23267-6_4.
Biagi M. [et al.]. Model-Based Quantitative Evaluation of Repair Procedures in Gas Distribution Networks // ACM Trans. Cyber Phys. Syst. 2019. Vol. 3, no. 2. 19:1-19:26. DOL 10.1145/3284037.
Carnevali L., Tarani F., Vicario F. Performability Evaluation of Water Distribution Systems During Maintenance Procedures // IEEE Trans. Syst. Man Cybern. Syst. 2020. Vol. 50, no. 5. P. 1704-1720. DOL 10.1109/TSMC.2017.2783188.
Carnevali L. [et al.]. Using the ORIS Tool and the SIRIO Library for Model- Driven Engineering of Quantitative Analytics // Computer Performance Engineering / ed. by K. Gilly, N. Thomas. Cham : Springer International Publishing, 2023. P. 200-215. DOL 10.1007/978-3-031-25049-1,13.
ORIS Tool. URL: http://www.oris-tool.org Accessed: 01/12/2024.
ORIS Tool: The Sirio Library. URL: https://github.com/oris-tool/sirio Accessed: 01/12/2024.
Heiner M. [et al.]. Snoopy - A Unifying Petri Net Tool // Application and Theory of Petri Nets. PETRI NETS 2012. Vol. 7347 / ed. by S. Haddad, L. Pomello. Springer Berlin Heidelberg, 2012. P. 398-407. (Lecture Notes in Computer Science). DOL 10.1007/978-3-642-31131-4_22.
David R., Alla H. Discrete, Continuous, and Hybrid Petri Nets. Springer Berlin Heidelberg, 2010. P. 550. DOL 10.1007/978-3-642-10669-9.
Liu F., Heiner M., Gilbert D. Fuzzy Petri nets for modelling of uncertain biological systems // Briefings in Bioinformatics. 2018. Dec. Vol. 21, no. 1. P. 198-210. DOL 10.1093/bib/bbyll8.
Fujita M., McGeer P., Yang J. Multi-Terminal Binary Decision Diagrams: An Efficient DataStructure for Matrix Representation // Form. Methods Syst. Des. USA, 1997. Apr. Vol. 10, no. 2/3. P. 149-169. DOL 10.1023/A: 1008647823331.
Hucka M. [et al.]. Systems Biology Markup Language (SBML) Level 2 Version 5: Structures and Facilities for Model Definitions // Journal of Integrative Bioinformatics. 2015. Vol. 12, no. 2. P. 731-901. DOL 10.2390/biecoll-jib-2015-271.
Heiner M., Schwarick M., Wegener J.-T. Charlie - An Extensible Petri Net Analysis Tool // Application and Theory of Petri Nets and Concurrency / ed. by R. Devillers, A. Valmari. Cham : Springer International Publishing, 2015. P. 200-211. DOL 10.1007/978-3-319-19488-2 10.
Heiner M., Rohr C., Schwarick M. MARCIE - Model Checking and Reachability Analysis Done Efficiently // Application and Theory of Petri Nets and Concurrency / ed. by J.-M. Colom, J. Desel. Springer Berlin Heidelberg, 2013. P. 389-399. DOI: 10.1007/978-3-642-38697-8-21.
Baier C. [et al.]. Model Checking Continuous-Time Markov Chains by Transient Analysis // Computer Aided Verification / ed. by E. Emerson, A. Sistla. Springer Berlin Heidelberg, 2000. P. 358-372.
Donaldson R., Gilbert D. A Model Checking Approach to the Parameter Estimation of Biochemical Pathways // Computational Methods in Systems Biology / ed. by M. Heiner, A. M. Uhrmacher. Springer Berlin Heidelberg, 2008. P. 269-287.
Chodak J., Heiner M. Spike - Reproducible Simulation Experiments with Configuration File Branching // Computational Methods in Systems Biology. Springer International Publishing, 2019. P. 315-321. DOL 10.1007/978-3-030-31304-3_19.
Gilbert D., Donaldson R. A Monte Carlo model checker for probabilistic LTL with numerical constraints : tech. rep. / Bioinformatics Research Centre, University of Glasgow. 01/2008.
Gilbert D. [et al.]. Spatial quorum sensing modelling using coloured hybrid Petri nets and simulative model checking // BMC Bioinformatics. 2019. Vol. 20, supplement 4. DOI: 10.1186/sl2859- 019-2690-z.
Herajy M. [et al.]. Snoopy’s hybrid simulator: a tool to construct and simulate hybrid biological models // BMC Systems Biology. 2017. July. Vol. 11, no. 1. DOI: 10.1186/sl2918-017-0449-6.
Zimmermann A. Modelling and Performance Evaluation with TimeNET 4.4 // Quantitative Evaluation of Systems - 14th International Conference, QEST 2017. Vol. 10503 / ed. by N. Bertrand, L. Bortolussi. Springer, 2017. P. 300-303. (Lecture Notes in Computer Science). DOI: 10.1007/978-3- 319-66335-7_19.
Selic B. Modeling And Analysis Of Realtime And Embedded Systems With Umi And Marte Developing Cyberphysical Systems. Elsevier Science & Technology, 2014. DOI: 10.1016/C2012-0-13536- 5.
Zimmermann A. [et al.]. Analysis of Safety-Critical Cloud Architectures with MultiTrajectory Simulation // 2022 Annual Reliability and Maintainability Symposium (RAMS). 01/2022. P. 1-7. DOI: 10.1109/RAMS51457.2022.9893923.
Fedorova A., Beliautsou V., Zimmermann A. Colored Petri Net Modelling and Evaluation of Drone Inspection Methods for Distribution Networks // Sensors. 2022. Vol. 22, no. 9. DOI: 10.3390/s22093418.
Dingle N., Knottenbelt W., Suto T. PIPE2: A Tool for the Performance Evaluation of Generalised Stochastic Petri Nets // SIGMETRICS Performance Evaluation Review ACM. New York, NY, USA, 2009. Mar. Vol. 36, no. 4. P. 34-39. DOI: 10.1145/1530873.1530881.
Platform Independent Petri Net Editor v4. URL: https://sourceforge.net/projects/pipe2 Accessed: 01/12/2024.
PIPE 5. URL: https://github.com/sarahtattersall/PIPE Accessed: 01/12/2024.

статья

Библиографическая ссылка: Быстров А. В., Вирбицкайте И. Б., Ошевская Е. С. Инструментальные системы, поддер-живающие стохастические сетевые модели //"Проблемы информатики", 2024, № 2, с.32-57. DOI: 10.24412/2073-0667-2024-2-32-57. - EDN: KNBRYZ

М.А. Козлов, Е.А. Панова, И. Б. Мееров

Национальный исследовательский Нижегородский государственный университет
им. Н. И. Лобачевского, 603950, Нижний Новгород, Россия

РЕАЛИЗАЦИЯ ПОИСКА НАИБОЛЕЕ ЧАСТО ВСТРЕЧАЮЩИХСЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДНК С ИСПОЛЬЗОВАНИЕМ БИБЛИОТЕКИ KOKKOS

УДК 004.424, 575.112

DOI: 10.24412/2073-0667-2024-2-58-71

EDN: TGQKBV

Существующее на текущий день большое разнообразие архитектур ставит вопрос разработки универсального программного обеспечения. В связи с этим появляются и развиваются различные программные средства, позволяющие создавать единый кроссплатформенный код для запуска на CPU, GPU, FPGA и других архитектурах. Тем не менее, остается вопрос эффективности и переносимости производительности разработанного кода. В данной работе мы исследуем этот и другие аспекты применительно к библиотеке Kokkos, которая на сегодняшний день является одним из наиболее популярных средств для создания кроссплатформенного кода. В качестве бенчмарка мы рассматриваем задачу из области биоинформатики по поиску наиболее часто встречающихся последовательностей ДНК, которая решается с использованием строковых алгоритмов. Мы приводим несколько алгоритмов решения задачи, реализуем их с использованием технологий OpenMP, Cuda и Kokkos и демонстрируем, что потери производительности при использовании Kokkos не превышают 10%, в то время как код может быть запущен как на CPU, так и на GPU.

Ключевые слова: Kokkos, кроссплатформенное ПО, гетерогенные вычисления, оптимизация программ, строковые алгоритмы, биоинформатика.

Список литературы

Gaster В., Howes L., Kaeli D. R., Mistry P., and Schaa D. Heterogeneous computing with openCL: revised openCL. Newnes, 2012.
Farber R. Parallel programming with OpenACC. Newnes, 2016.
Kokkos 3: Programming model extensions for the exascale era / Trott C. R., Damien LG, Arndt D., Ciesko J., Dang V., Ellingwood N., Gayatri R., Harvey E., Hollman D. S., Ibanez D., et al. // IEEE Transactions on Paralleland Distributed Systems. 2021. Vol. 33, no. 4. P. 805-817.
Alpaka - an abstraction library for parallel kernel acceleration / Zenker E., Worpitz B., Widera R., Huebl A., Juckeland G., Knupfer A., Nagel W. E., and Bussmann M. // 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) / IEEE. 2016. P. 631-640.
Reinders J. et al. Data parallel C++: mastering DPC++ for programming of heterogeneous systems using C++ and SYCL. Springer Nature, 2021. P. 548.
Библиотека Kokkos. URL: https://github.com/kokkos/kokkos. Дата доступа: 10.01.2024.
Subirana J. A., Messeguer X.. The most frequent short sequences in non-coding DNA // Nucleic acids research. 2010. Vol. 38, no. 4. P. 1172-1181.
Faro S., Lecroq T. The exact online string matching problem: A review of the most recent results // ACM Computing Surveys(CSUR). 2013. Vol. 45, no. 2. P. 1-42.
Exact string matching algorithms: survey, issues, and future research directions / Hakak S. I., Kamsin A., Shivakumara P., Gilkar G. A., Khan W. Z., and Imran M. // IEEE access. 2019. Vol. 7. P. 69614-69637.
Stephen G. A. String searching algorithms. World Scientific, 1994.
Al-Khamaiseh K., Alshagarin S. A survey of string matching algorithms // Int. J. Eng. Res. Appl. 2014. Vol. 4, no. 7. P. 144-156.
Karp R. M., Rabin M. O. Efficient randomized patternmatching algorithms // IBM Journal of Research and Development. 1987.Vol. 31, no. 2. P. 249-260.
Lecroq T. Fast exact string matching algorithms // Information Processing Letters. 2007. Vol. 102, no. 6. P. 229-235.
Galil Z. A constant-time optimal parallel string-matching algorithm // Journal of the ACM (JACM). 1995. Vol. 42, no. 4. P. 908-918.
Park J. H., George К. M. Efficient parallel hardware algorithms for string matching // Microprocessors and Microsystems. 1999. Vol. 23,no. 3. P. 155-168.
Accelerating string matching using multi-threaded algorithm on GPU / Lin С. H., Tsai S. Y., Liu С. H., Chang S. C., and Shyu J. M. // 2010 IEEE Global Telecommunications Conference GLOBECOM 2010 / IEEE. 2010. P. 1-5.
Kouzinopoulos C. S., Michailidis P. D., Margaritis K. G. Multiple string matching on a GPU using cudas //Scalable Computing: Practice and Experience. 2015. Vol. 16, no. 2. P. 121-138.
Козлов M. А., Панова E. А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos // Математическое моделирование и суперкомпьютерные технологии. Труды XXIII Международной конференции (И. Новгород, 13-16 ноября 2023 г.) / Под ред. проф. Д.В. Баландина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2023. ISBN 978-5-91326-834-1. 2023. С. 73-78.
Открытый исходный код бенчмарка. URL: https://github.com/Mishaizlesa/ most_common_string_kokkos. Дата доступа: 10.01.2024.
DNA Bank (National library of medicine). URL: https://www.ncbi.nlm.nih.gov/genbank.

статья

Библиографическая ссылка: Козлов М.А., Панова Е.А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos //"Проблемы информатики", 2024, № 2, с.58-71. DOI: 10.24412/2073-0667-2024-2-58-71. - EDN: TGQKBV

Main menu

You are here

2024 № 2 (63)