Volume 2 (63)

Perminov P. O., Migov D. A. Calculation of the reliability of extended tri-connected networks
Malyshkin V. E., Perepelkin V. A. Definition of the Program Notion
Bystrov A. V., Virbitskaite I. B., Oshevskaya E. S. Stochastic Petri nets software tools
Kozlov M. A., Panova E. A., Meyerov I. B. Implementation of searching for the most frequent DNA sequences using the Kokkos library

Novosibirsk State University, 630090, Novosibirsk, Russia

Institute of Computational Mathematics and Mathematical Geophysics SB RAS,

630090, Novosibirsk, Russia

CALCULATION OF THE RELIABILITY OF EXTENDED TRI-CONNECTED NETWORKS

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

EDN: VZCSXV

When analyzing the reliability of networks for various purposes, the apparatus of random graphs is usually used. The most common indicator of reliability is the probability of connectivity of a random graph with unreliable edges, which describes the reliability of a network in terms of the ability to establish a connection between each pair of network nodes. However, the problem of calculating the probability of network connectivity is NP-hard. To reduce the dimensional when carrying out precise calculations, methods based on the use of structural features of networks are widely used, primarily various methods of reduction and decomposition.

Networks with an extended structure are used in number of applications. These are, for example, networks located in extended objects — mines, ships, other objects. Linear wireless sensor networks, designed for monitoring various long-distance objects, such as pipelines, bridges, roads, also have an extended structure. Despite their linear physical structure, the topological graph of such a network can be either linear or non-linear, since wireless communication channels are possible not only between the nearest neighboring nodes. For example, if each node can communicate with three nodes on the right and three nodes on the left, we obtain a network containing a group of three-vertex cross separators.

If the graph of an extended network is linear, then calculating its probabilistic connectivity is not difficult. The use of a serial-parallel transformation, or other techniques, allows us to make the calculation within polynomial complexity. If the network graph is biconnected and contains a separators of two nodes, then the calculation can be significantly accelerated by using decomposition along these separators.

In this paper, we study the possibility of quickly calculating the reliability of extended three-connected networks using decomposition according to the previously proposed formula. Such decomposition will lead to the production of 10 new extended graphs of a smaller size. As experiments have shown, this approach is quite effective and makes it possible to calculate the reliability of extended networks, for which it is not possible to calculate the reliability using an accurate method.

Key words: network reliability, random graph, triconnected graph, probabilistic connectivity, factorization method, network decomposition, cut, separator.

The work was carried out within the framework of the project N 0251-2021-0005 of a state assignment of the Institute of Computational Mathematics and Mathematical Geophysics SB RAS.

References

1. Zhukovskij М.Е., Rajgorodskij A.M. Sluchajny‘e grafy1: modeli i predel‘ny‘e xarakteristiki // Uspexi matematicheskix nauk. 2015. T. 70. N 1 (421). P. 35-88.

2. Mochalov V.A., Mochalova A.V. Primenenie e‘kspertny‘x sistem dlya rascheta veroyatnosti svyaznosti mezhdu uzlami grafa //V sbornike: Gibridny‘e i sinergeticheskie intellektual‘ny‘e sistemy1. Materialy1 V Vserossijskoj Pospelovskoj konferencii s mezhdunarodny‘m uchastiem. Pod redakeiej A. V. Kolesnikova. 2020. P. 226-235.

3. Rodionov A.S. Mozhno li dobit'sya daLnejshego uskoreniya rascheta xarakteristik svyaznosti sluchajnogo grafa? // Problemy1 informatiki. 2022. N 4 (57). P. 39-52.

4. Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. T. 8. N 3. P. 410-421.

5. 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.

6. Satyanarayana A., Wood R.K. A linear-time algorithm for computing К terminal reliability in series-parallel networks // SIAM. J. Comput. 1985. T. 14. P. 818-883.

7. Migov D., Rodionova O., Rodionov A., Choo H. Network probabilistic connectivity: using node cuts // Springer Lecture Notes in Computer Science (in EUC Workshops). V. 4097, 2006, P. 702-709.

8. Tarxanova O.Yu., Shaxov V. V. К voprosu ocenki e‘ffektivnosti besprovodny'x sensorny'x setej // Problemy1 informatiki. 2020. N 1 (46). P. 35-65.

9. Farxadov M.P. O., Blinova O.V., Vas'kovskij S.V. Ocenka nadezhnosti sistemy1 svyazi s podvizhny‘mi uzlami // Datchiki i sistemy1. 2018. N 5 (225). P. 3-8.

10. Shaxov V.V., Chen X., Yurgenson A.N., Loshkarev A.V. К voprosu ocenki nadezhnosti linejny‘x besprovodny‘x sensorny‘x setej // Problemy1 informatiki. 2022. N 4 (57). P. 120-128.

11. Mohamed N., Al-Jaroodi J., Jawhar L, Lazarova-Molnar S. 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.

12. Migov. D. A. Dissertaciya na soiskanie uchenoj stepeni kandidata fiziko-matematicheskix nauk “Raschyot veroyatnosti svyaznosti sluchajnogo grafa s primeneniem sechenij”. Novosibirsk: ICMMG SB RAS. 2008. 97 P.

13. Migov D.A. Ispolzovanie vershinnyx razrezov dlya tochnogo vychisleniya veroyatnosti svyaznosti seti // Trudy Mezhdunarodnoj konferencii “Vychislitelnye i informacionnye texnologii v nauke, texnike i obrazovanii” (Pavlodar, 20-22 sentyabrya 2006 goda) Tom II. S. 51-58.

14. Page L.B., Perry J.E. A Practical Implementation of the Factoring Theorem for Network Reliability // IEEE transactions on reliability. 1988. V. 37, N 3. P. 259-267.

15. D. Migov. Dekompoziciya seti po secheniyam pri raschyote eyo nadyozhnosti // Prikladnaya diskretnaya matematika. 2020. N 47. P. 62-86.

16. Burgos J.M. Factorization of network reliability with perfect nodes II: Connectivity matrix // Discrete Applied Mathematics. 2016. V. 198. P. 91-100.

Bibliographic reference: Perminov P. 0., Migov D. A. Calculation of the reliability of extended tri-connected networks //journal “Problems of informatics”. 2024, № 2. P.5-15. DOI: 10.24412/2073-0667-2024-5-15

article

V. E. Malyshkin, V.A. Perepelkin

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

Novosibirsk State University,630090, Novosibirsk, Russia

Novosibirsk State Technical University, 630073, Novosibirsk, Russia

DEFINITION OF THE PROGRAM NOTION

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

EDN: CEDVVD

When solving complex problems in programming an important role plays definition of the program notion. Depending on the way program is concerned an approach to its construction, as well as its properties, vary. In the paper the program notion is studied and defined based on the theory of parallel programs synthesis on the basis of computational models. The proposed definition conforms to the theory, starting from the description of the problem in the subject domain terms and up to imperative program execution with dynamic properties provided.

In programmers’ work it is not usual to employ a precise definition of the program notion. Usually some partial definition is used, which is applicable in particular circumstances. In practice there is no problem with that. Nevertheless, in solving problems of automatic construction of any kind of programs (sequential, parallel, distributed, real-time, numerical, etc.) in various computational model (in various models of informatics) and for different bases it becomes necessary to precisely define the program notion. This allows to precisely define objects and concepts of the theory and practice of informatics and use them in precise proofs/argumentation of various statements in different theories. That’s why we have chosen mathematical logic as the base theory within which all considerations in the papers are made.

The theory of synthesis of parallel programs and systems on the basis of computational models was originally formulated in [1] and further studied in [2, 3]. Computational model (CM) is a bipartite directed finite graph, the parts of which form two sets of vertices, called sets of operations and variables. The arcs entering and exiting the operation determine the input and output variables of this operation, respectively. A computational model describes a certain subject domain, where the properties of objects in the subject domain are described by the set of variables (property values are represented by variable values), and the ability to calculate the values of some properties from others is represented by the set of operations (see Fig. ??). CM defines an axiomatic theory.

The interpretation function I is defined on the vertices of the graph. Each variable x has the value I (x), and each operation a computes a function I (a). To make computations available each operation has a computational module assigned. An example of such module is a conventional serial subroutine capable of computing values of output variables of the operation, provided values of operation’s input variables are submitted as inputs to the subroutine. Let’s define two subsets on the set of variables of the computational model - V and IE, and call them input and output variables of the problem. Values

This work was carried out under state contract with ICMMG SB RAS FWNM-2022-0005.

of all variables from V are considered given. In this ease, we will say that the VW-problem is posed on a computational model. If in a computational model there is a subset of operations, the ordered application of which to known values of variables will allow obtaining values of new variables until all variables from W obtain values, then this set defines a set of functional terms, each of which calculates one of the variables in W and is calculated from the variables of set V. We will call this set of functional terms a VW-plan (or simply a plan). To solve any VW-problem, generally, zero or more VW-plans can be constructed. Obviously, for a given VW-problem, one can set the task of finding a VW-plan, and if successful, compute the values of all variables from W, given the values of the variables from V.

The above allows us to give the following definition of the notion of a program. A program is a description of a process of computation of the values of the interpretation function for the variables included in the VW-plan, and only them.

Execution of a plan demands definition of control, i.e. the order in which operations are to be executed. That order must not contradict information dependencies between operations. Also the resources have to be assigned: each variable must have a memory extent to store its value and each operation must have a processor time to execute its corresponding module. Generally both control definition and resources assignment should be done partially statically and the rest - dynamically. This allows to provide static and dynamic properties of the program. Derivation of a VW-plan to solve the formulated problem can also be derived dynamically.

The proposed definition of the program notion has a number of advantages, considered in the paper. The advantages include the ability of algorithmic optimizations, the ability to optimize non-functional properties, etc. Also the process of programming in terms of computational models is described. Other program definitions are concerned in comparison.

Key words: Program concept, automatic program construction, active knowledge.

References

1. Sintez parallelnykh programm i sistem na vychislitelnykh modelyakh / V.A. Valkovsky, V.E. Malyshkin; Onv. red. V.E. Kotov; AN SSSR, Sib. otd-nie, VC. Novosibirsk : Nauka. Sib. otd-nie, 1988. 126 s. (In Russian)

2. Malyshkin V.E. Tekhnologiya fragmentirovannogo programmirovaniya // Vestnik YuUrGU. Seriya: Vychislitelnaya matematika i invormatika. 2012. No 46 (305). (In Russian) 3. 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.

4. Vychislimost v proizvolnykh oblyastyah i bazisakh: Sb. nauchn. st. - M: VINITI, 1982, P 3-58. (Semiotika i informatika; Vyp. No 19). (In Russian)

5. Yanov Yu.I. Metod svyortok dlya razresheniya svoystv formalnykh sistem. M.: IPM im. M.V. Keldysha, 1977. Vyp. 11. 41 c. (Institut prikladnoy matematiki AN SSSR. Preprint; No 11 za 1977 g.). URL: https://library.keldysh.ru/preprint.asp?id=1977-ll. (In Russian)

6. Valkovsky V.A. О sinteze optimalnykh programm na baze vychislitelnykh modeley // Programmirovanie. 1980. No 6. S. 27-36. (In Russian)

7. 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.

8. Kudryavtsev A.A., Malyshkin V.E., Nushtayev Yu. Yu. Perepelkin V.A., Spirin V.A. Effektivnaya fragmentirovannaya realizatsiya kraevoy zadachi filtratsii dvukhfaznoy zhidkosti // Problemy informatiki. 2023. No 2. S. 45-73. DOL 10.24412/2073-0667-2023-2-45-73 (In Russian)

9. 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.

10. Perepelkin V.A., Sofronov I.V., Tkacheva A.A. Avtomatizatsiya konstruirovaniya chislennykh parallelnykh programm s zadannymi nefunktsionalnymi svoystvami na baze vychislitelnykh modeley // Zhurnal Problemy informatiki, 2017. No 4, S. 47-60. (In Russian)

11. 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

12. 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

13. 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.

14. 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.

15. Malyshkin V.E., Perepelkin V.A. Multiagentniy podkhod к povysheniyu effektivnosti ispolneniya fragmentirovannykh programm v sisteme LuNA // Problemy informatiki, 2023, No 3, s. 55-67. DOL 10.24412/2073-0667-2023-3-55-67. (In Russian) '

16. 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

Bibliographic reference: Malyshkin V. E., Perepelkin V. A. Definition of the Program Notion //journal “Problems of informatics”. 2024, № 2. P.16-31. DOI: 10.24412/2073-0667-2024-16-31

article

A.V. Bystrov, I. B. Virbitskaite, E.S. Oshevskaya

A. P. Ershov Institute of Informatics Systems, 630090, Novosibirsk, Russia

STOCHASTIC PETRI NETS SOFTWARE TOOLS

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

EDN: KNBRYZ

The behavior of a wide variety of systems, biochemical, transport, industrial, software, and so on, is inherently parallel, non-deterministic, and stochastic. The study and design of these systems requires the use of models that take into account all these aspects, as well as appropriate software tools. Stochastic Petri nets and their various extensions are successfully used as such models. They combine the clarity and intuitiveness of the graphical representation with well-developed mathematical and algorithmic apparatus of analysis. These models allow us to study not only qualitative but also quantitative properties of systems, such as bandwidth, reliability, waiting time, etc. Software tools that support the construction, modification and analysis of system models based on various variants of stochastic Petri nets have already been developed and continue to appear.

This paper provides a detailed overview of several such multiplatfom software tools, namely, GreatSPN, ORIS, PetriNuts, TimeNet and PIPE2 that are available on the Internet, and got recognized by users. The introduction, informally, but with proper references to the literature, gives the basic concepts, defines the classes of Petri nets and terms used later. Then, for each of the software tools, its structure, features and peculiarities are considered. The tools are then compared in terms of their functional and performance analysis capabilities, and recommendations to users on how to use the tools depending on what type of stochastic models need to be investigated are discussed. The main purpose of the paper is to facilitate the researcher and engineer in selecting the most appropriate modeling and analysis tool for the task at hand.

Key words: stochastic Petri nets, modelling, simulation, performance analysis, Petri net tools.

References

1. Reisig W. Petri Nets: An Introduction. Vol. 4. Springer, 1985. (EATCS Monographs on Theoretical Computer Science), doi: 10.1007/978-3-642-69968-9

2. 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.

3. 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

4. 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

5. 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

6. 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

7. Ajmone Marsan М. 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

8. Ajmone Marsan M., Chiola G. On Petri nets with deterministic and exponentially distributed Bring 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

9. 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.

10. 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

11. 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. doi: 10.1016/0166- 5316(94)90020-5

12. Stoxasticheskie seti Petri — formalizm dlya modelirovaniya i analiza proizvoditcl’nosti vychislitel’nyx processov // Sistemnaya Informatika. Novosobirsk, 2004. S. 135-193. (In Russian)

13. German R. Performance analysis of communication systems — modelling with non- Markovian stochastic Petri nets : Modeling with Non-Markovian Stochastic Petri Nets. Wiley, 2000. P. 456.

14. 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. doi: 10.1007/978-3-319-66335-7_2

15. Martina S. et al. Performance Evaluation of Fischer’s Protocol through SteadyState Analysis of Markov Regenerative Processes // IEEE 24th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS). 09/2016. P. 355-360. doi: 10.1109/MASCOTS.2016.72

16. Horvath A. et al. Transient analysis of non-Markovian models using stochastic state classes // Performance Evaluation. 2012. Vol. 69, no. 7/8. P. 315-335. doi: 10.1016/j.peva.2011.11.002

17. Amparore E. 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

18. Amparore E. et al. 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-319-30599¬8-9

19. K. J., Kristensen L. Coloured Petri Nets. Springer Berlin Heidelberg, 2009. doi: 10.1007/b95112

20. ISO/IEC. Software and Systems Engineering - High-level Petri Nets, Part 2: Transfer Format, International Standard ISO/IEC 15909, February 2011.

21. Kindler E. The Petri Net Markup Language and ISO/IEC 15909-2: Concepts, Status, and Future Directions // Tagungsband Entwurf komplcxcr Automatisierungssysteme EKA. 2006. P. 35-55.

22. 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.

23. Deharbe 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

24. 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

25. Emerson Е., Sistla A. Symmetry and model checking // Formal Methods in System Design. 1996. Vol. 9, no. 1. P. 105-131. doi: 10.1007/BF00625970

26. Babar J. et al. GrcatSPN 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.

27. 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

28. R. R., S. B., 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. doi: 10.1109/TSMC.2018.2837643

29. 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/978-3-030-63061-4 26

30. 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.

31. Richard L. Performance Results for the CSMA/CD Protocol Using GrcatSPN // Journal of Systems and Software. 1997. Vol. 37, no. 1. P. 75-90. doi: 10.1016/S0164-1212(96)00041-6

32. Amparore E., Donatelli S. GreatTeach: A Tool for Teaching (Stochastic) Petri Nets // Application nd Theory of Petri Nets and Concurrency. Springer International Publishing, 2018. P. 416-425. doi: 10.1007/978-3-319-91268-4_24

33. Castagno P. et al. A computational framework for modeling and studying pertussis epidemiology and vaccination // BMC Bioinformatics. 2020. Vol. 21, no. 8. P. 344. doi: 10.1186/S12859-020-03648-6

34. The GrcatSPN Framework. [El. Res.]: https://github.com/greatspn/SOURCES. Accessed: 2024-03-15.

35. 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

36. Carnevali L., Paolieri M., Vicario E. 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

37. Stewart W. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1995. doi: 10.1515/9780691223384

38. 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), doi: 10.1007/978-3-319-23267-6_4

39. 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. doi: 10.1145/3284037

40. 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. doi: 10.1109/TSMC.2017.2783188

41. Carnevali L. et al. Using the ORIS Tool and the SIRIO Library for Model- Driven Engineering of Quantitative Analytics // Computer Performance Engineering / ed. byK. Gilly, N. Thomas. Cham : Springer International Publishing, 2023. P. 200-215. doi: 10.1007/978-3-031-25049-1 13

42. ORIS Tool. [El. Res.]: http://www.oris-tool.org. Accessed: 2024-03-15.

43. ORIS Tool: The Sirio Library. [El. Res.]: https://github.com/oris-tool/sirio. Accessed: 2024-03¬15.

44. Heiner М. 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), doi: 10.1007/978-3-642-31131-4_22

45. David R., Alla H. Discrete, Continuous, and Hybrid Petri Nets. Springer Berlin Heidelberg, 2010. P. 550. doi: 10.1007/978-3-642-10669-9

46. 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. doi: 10.1093/bib/bbyll8

47. 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. doi: 10.1023/A: 1008647823331

48. 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. doi: 10.2390/biecoll-jib-2015-271

49. 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. doi: 10.1007/978-3-319-19488-2 10

50. Heiner M., Rohr C., Schwarick M. MARGIE — 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

51. 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.

52. 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.

53. Chodak J., Heiner M. Spike — Reproducible Simulation Experiments with Configuration File Branching // Computational Methods in Systems Biology. Springer International Publishing, 2019. P. 315-321. doi: 10.1007/978-3-030-31304-3_19

54. 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.

55. 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

56. Hcrajy 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/S12918-017-0449-6

57. 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

58. 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

59. Zimmermann A. et al. Analysis of Safety-Critical Cloud Architectures with MultiTrajectory Simulation // Annual Reliability and Maintainability Symposium (RAMS). 01/2022. P. 1-7. doi: 10.1109/RAMS51457.2022.9893923

60. 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

61. 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

62. Platform Independent Petri Net Editor v4. [El. Res.]: https://sourceforge.net/projects/pipe2. Accessed: 2024-03-15.

PIPE 5. [El. Res.]: https://github.com/sarahtattersall/PIPE. Accessed: 2024-03-15.

Bibliographic reference: Bystrov A. V., Virbitskaite I. B., Oshevskaya E. S. Stochastic Petri nets software tools //journal “Problems of informatics”. 2024, № 2. P.32-57. DOI: 10.24412/2073-0667-2024-32-57

article

M. Kozlov, E. Panova, I. Meyerov

Lobachevsky State University of Nizhny Novgorod, 603950, Nizhny Novgorod, Russia

IMPLEMENTATION OF SEARCHING FOR THE MOST FREQUENT DNA SEQUENCES USING THE KOKKOS LIBRARY

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

EDN: TGQKBV

Nowadays, the wide variety of existing architectures raises the problem of developing universal approaches to programming. Various frameworks enable single-source code creation for multiple devices, for example, CPU, GPU, FPGA. Such frameworks include OpenCL, OpenACC, Kokkos, Alpaka and others. However, the problem of efficiency and performance portability remains relevant. It is not always possible to create one code that works efficiently on different devices because of their specific architectures. This article discusses performance aspects in relation to the Kokkos library, a widely used framework for creating cross-platform code.

As a benchmark, we consider a bioinformatics problem to find the most frequent DNA sequences of certain length. It is assumed that important genetic information can be encrypted in such sequences. DNA sequence can be represented as a string consisting of four characters “A”, “C”, “G”, “T”, which denote corresponding nucleobases. Therefore, the problem reduces to counting fixed-length patterns in DNA and can be solved using existing string matching algorithms. Faro and Lecroq (2013) reviewed and classified exact string matching algorithms and experimentally evaluated them on different kinds of texts. Hakak et al. (2019) showed the latest advancements in the field of string matching algorithms and designated modern trends and challenges. They analyzed various classes of algorithms and drew conclusions about the limitations and effectiveness of different string matching algorithms for various applications. In this article, we have chosen two algorithms for consideration: the well-known Rabin- Karp algorithm and the Hash3 algorithm from the Hashg family [Lecroq 2007]. The Hash3 algorithm is one of the most effective algorithms for short-length patterns of approximately 8 to 128 characters long. Both these algorithms are based on hashing and are well applicable for genome analysis. For verification and comparison, we also consider a simple naive algorithm based on sequential pattern matching.

The naive algorithm consists of character-by-character comparison of all fixed-length patterns. This algorithm is not effective enough, but has great potential for parallelization. We received an acceleration of up to 35 times when ported the parallel naive algorithm from CPU to GPU. The Rabin- Karp algorithm allows us to eliminate character-by-character comparisons effectively using hashing and shows better efficiency compared to the naive algorithm on both CPU and GPU. Our cross-platform parallel implementation of the Rabin-Karp algorithm is approximately 1.25 times faster than the naive algorithm on CPU and 2 times faster on GPU. The Hash3 algorithm cuts off character-by-character comparisons extremely efficiently. Because of this, the Hash3 algorithm is an order of magnitude faster than the naive algorithm. Due to the almost absence of character-by-character comparisons,

the algorithm is memory bound and has less potential for parallelization. The Hash3 algorithm was accelerated by 7 times on GPU relative to CPU.

We implement these algorithms for CPU and GPU using OpenMP, Cuda and Kokkos technologies. We demonstrate that when using Kokkos with a naive algorithm, the performance loss does not exceed 10% relative to the OpenMP version. Losses are caused by the compiler making more efficient use of SIMD calculations in the OpenMP implementation when matching patterns. There is no performance loss for the Rabin-Karp and Hash3 algorithms when porting the OpenMP version to Kokkos. Speedup of all algorithms is about 14 times on 16 physical cores. It is worth noting that the Hash3 algorithm showed a noticeable improvement on the CPU when using hyper-threading, unlike other algorithms under consideration. This can be explained by more efficient memory management. Speedup on 32 threads and 16 physical cores for the naive algorithm and the Rabin-Karp algorithm is 16-17 times, while for the Hash3 algorithm it is 25 times.

Next, we run the developed code on the GPU and show that the Kokkos version of the Rabin-Karp algorithm loses to the Cuda version on the GPU by no more than 10%. At the same time, the Kokkos versions of the naive and Rabin-Karp algorithms outperform our Cuda baseline version by 10-20%. The authors did not set themselves the goal of optimizing the Cuda code. We believe that it is possible to optimize the Cuda code to match the performance of the Kokkos version. However, it is noteworthy that sometimes the baseline Kokkos version runs faster than the baseline Cuda version.

Overall, we demonstrate that in many cases the Kokkos version works as well as native OpenMP or Cuda code. In the worst case, the performance loss was no more than 10%. We believe that paying this price is reasonable in order to run a single code on different devices.

Key words: Kokkos, single-source programming, cross-platform software, heterogeneous computing, program performance, string matching algorithms, bioinformatics.

This work was funded by the Ministry of Science and Higher Education of the Russian Federation, project No. FSWR-2023-0034.

References

1. Gaster B., Howes L., Kaeli D. R., Mistry P., and Schaa D. Heterogeneous computing with openCL: revised openCL. Newnes, 2012.

2. Farber R. Parallel programming with OpenACC. Newnes, 2016.

3. 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.

4. 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.

5. Reinders J. et al. Data parallel C++: mastering DPC++ for programming of heterogeneous systems using C++ and SYCL. Springer Nature, 2021. P. 548.

6. The Kokkos library. URL: https://github.com/kokkos/kokkos. Date of access: 10.01.2024.

7. 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.

8. 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.

9. Exact string matching algorithms: survey, issues, and future research directions / Hakak S. L, Kamsin A., Shivakumara P., Gilkar G. A., Khan W. Z., and Imran M. // IEEE access. 2019. Vol. 7. P. 69614-69637.

10. Stephen G. A. String searching algorithms. World Scientific, 1994.

11. Al-Khamaiseh K., Alshagarin S. A survey of string matching algorithms // Int. J. Eng. Res. Appl. 2014. Vol. 4, no. 7. P. 144-156.

12. Karp R. М., Rabin М. О. Efficient randomized patternmatching algorithms // IBM Journal of Research and Development. 1987.Vol. 31, no. 2. P. 249-260.

13. Lecroq T. Fast exact string matching algorithms // Information Processing Letters. 2007. Vol. 102, no. 6. P. 229-235.

14. Galil Z. A constant-time optimal parallel string-matching algorithm // Journal of the ACM (JACM). 1995. Vol. 42, no. 4. P. 908-918.

15. Park J. H., George К. M. Efficient parallel hardware algorithms for string matching // Microprocessors and Microsystems. 1999. Vol. 23,no. 3. P. 155-168.

16. 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.

17. 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.

18. Kozlov M. A., Panova E. A., Meerov I. B. Implementation of searching for the most frequent DNA sequences using the Kokkos library // Mathematical modeling and supercomputer technologies. Proceedings of the XXIII International Conference (N. Novgorod, November 13-16, 2023) / Ed. prof. D.V. Balandina. Nizhny Novgorod: Publishing House of Nizhny Novgorod State University, 2023. ISBN 978-5-91326-834-1. 2023. P. 73-78.

19. Benchmark source code. URL: https://github.com/Mishaizlesa/ most_common_string_kokkos. Date of access: 10.01.2024.DNA Bank (National library of medicine). URL: https://www.ncbi.nlm.nih.gov/genbank. Date of access: 10.01.2024.

Bibliographic reference: Kozlov M. A., Panova E. A., Meyerov I. B. Implementation of searching for the most frequent DNA sequences using the Kokkos library //journal “Problems of informatics”. 2024, № 2. P.58-71. DOI: 10.24412/2073-0667-2024-58-71

article

Main menu

Volume 2 (63)

CONTENTS

Languages

Main menu

You are here

Volume 2 (63)

CONTENTS

Languages