2024 № 2 (63)
СОДЕРЖАНИЕ
- Перминов П. О., Мигов Д. А. Расчет надежности протяженных трехсвязных сетей
- Малышкин В. Э., Перепелкин В. А. Определение понятия программы
- Быстров А. В., Вирбицкайте И. Б., Ошевская Е. С. Инструментальные системы, поддерживающие стохастические сетевые модели
- Козлов М.А., Панова Е.А., Мееров И. Б. Реализация поиска наиболее часто встречающихся последовательностей ДНК с использованием библиотеки Kokkos
РАСЧЕТ НАДЕЖНОСТИ ПРОТЯЖЕННЫХ ТРЕХСВЯЗНЫХ СЕТЕЙ
Рассматривается задача расчета вероятности связности протяженных сетей с ненадежными каналами связи. Точный расчет данного показателя — 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. Vs 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, Новосибирск, Россия
ОПРЕДЕЛЕНИЕ ПОНЯТИЯ ПРОГРАММЫ
При решении сложных задач в программировании важную роль играет определение понятия программы. От того, как понимается программа зависит подход к ее конструированию и ее свойства. В работе рассматривается понятие программы и дается ему определение на базе теории синтеза параллельных программ на вычислительных моделях. Предлагаемое определение отражает подход к процессу конструирования программы, определяемый этой теорией, начиная с описания задачи в терминах предметной области и заканчивая исполнением императивной программы с динамическими свойствами. Подход обладает рядом преимуществ, рассматриваемых в статье, таких как возможность выполнения алгоритмических оптимизаций, возможность автоматического конструирования программы, возможность обеспечения нефункциональных требований и проч. Рассматриваются параллели с другими определениями программ и особенности практического применения предлагаемого подхода.
Ключевые слова: понятие программы, автоматическое конструирование программ, активные знания.
Список литературы
-
Вальковский В. А., Малышкин В.Э. Синтез параллельных программ и систем на вычис-лительных моделях / . Отв. ред. В.Е. Котов; АН СССР, Сиб. отд-ние, ВЦ. Новосибирск: Наука. Сиб. отд-ние, 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, Новосибирск, Россия
ИНСТРУМЕНТАЛЬНЫЕ СИСТЕМЫ, ПОДДЕРЖИВАЮЩИЕ СТОХАСТИЧЕСКИЕ СЕТЕВЫЕ МОДЕЛИ
Ключевые слова: стохастические сети Петри, моделирование, анализ производительности, инструментальные системы.
Список литературы
-
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
Ключевые слова: 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