Volume 1(62)

CONTENTS

1. Zubarev A.Y. Hierarchy of equivalences on time petri nets with weak time policy
2. Starchenko A. V. Parallel numerical method for solution of hydrodynamic equations in the shallow water approximation for shared memory computers
3. Nosov V. S., Sonkin D.M., Sonkin M.A., Chursin Yu. A. A method for organizing functional diagnostics in regional public warning systems
4. UlyanicheI.S.V, Wiens D.V. Architecture of a distributed computing system based on mobile devices

A.Y. Zubarev

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

HIERARCHY OF EQUIVALENCES ON TIME PETRI NETS WITH WEAK TIME POLICY

The security of many information systems is critically important, since their failure can lead to large economic losses and human casualties. Equivalences allow comparing systems and specifications in terms of different aspects of their behavior. In this wav, they are used to verify and reduce systems. Models of concurrent and distributed systems are compared in the dichotomies of “linear time — branching time" and “interleaving — partial order" in the literature. The first criterion of comparison is a degree of conflict accounting (a moment of choosing between several “branches” of computing). The semantics of linear time ignores the points of choice, and the behavior is described by the set of all executions (processes). Trace equivalence is a typical example of such equivalence. On the contrary, branching time semantics takes into account the branching structure of the system’s behaviors. The second criterion of comparison is the degree of partial order accounting. Interleaving semantics ignores partial order. The concurrency is reduced to a nondeterministic choice between executions of linearly ordered actions. On the other hand, “true concurrency” models preserve causality and concurrency between actions.

Petri nets (PN) are one of the generally accepted tools for modeling and analyzing concurrent and distributed systems. The (PN) consists of two different sets of elements — transitions (system events) and places (conditions for events). This model is represented as an oriented bipartite graph. A state of the PN is a marking (a set of places with tokens'). All conditions for an event are met if there is a token in each input place of the corresponding transition. This transition is called enabled and can fire, i. e. change the marking. The new marking is obtained as a result of removing tokens from the input places and creating new tokens in the output transition places. It is often necessary to take into account time or quantitative characteristics when verifying systems. Various time extensions of Petri nets have been defined for these purposes. Time Petri Nets (TPNs) are model where each transition has its own clock and time interval. A state of the model is defined by the marking and the clock readings of enabled transitions. A transition can fire if it is enabled in the marking and its clock readings are in its interval. Firing the transition changes the marking, disables the clock for not enabled transitions, and initializes (resets) a clock for some enabled transitions.

There is an intermediate, atomic and persistent atomic clock reset policy. Intermediate policy takes into account the marking before the creation of new tokens and after the removal of old tokens (intermediate marking). A transition clock will be disabled if the transition was not enabled in the intermediate marking. If a transition became enabled after the creation of new tokens, then its clock will take a zero value. The atomic policy does not consider intermediate states. Resetting clock will only happen if the transition is disabled in the new marking. The transition clock that is fired is always reset in the case of an intermediate and atomic policy (unlike persistent atomic). It is shown in [1] and [2] that the persistent atomic policy is strictly more expressive than the atomic one. The atomic policy is not less expressive than the intermediate one. In addition, the authors give examples of models of systems where the atomic policy is more preferable.

Time elapsing increases the readings of the local clock of enabled transitions. Strong and weak time policies are presented in the literature. The strong policy restricts time elapsing. The value of a transition clock cannot go beyond the upper limit of the time interval. The transition must either fire or become disabled. In the weak policy, there are no restrictions on time elapsing. As it was shown in [3], strong and weak policies of time elapsing are incomparable in expressiveness.

Definition and analysis of equivalence relations in the “linear time — branching time” and “interleaving — partial order” spectra is one of the important tasks for models of concurrency and distributed systems. In [4], a hierarchy of equivalences for time-free Petri nets is presented. In [5], the authors developed and investigated the simple bisimulation and forward-backward equivalences for the TPNs with the strong time policy and intermediate clock reset strategy. In [6], the semantic models in the “interleaving — partial order” spectrum were defined in terms of weak TPNs. In [7], trace and simple bisimulation equivalences were developed for the TPNs with an intermediate clock reset policy. As far as we know, there are no equivalences in the literature for TPNs with a weak time policy and with a persistent atomic method of resetting the clock. The purpose of this work is to define and study the relationships of trace, simple bisimulation, forward-backward bisimulation and history-preserving bisimulation equivalences for weak TPNs with a persistent atomic clock reset policy.

Key words: time Petri nets, weak time policy, persistent atomic clock reset policy, behavioral equivalences, interleaving semantics, partial order semantics, time processes, trace and bisimulation equivalences, forward-backward bisimulation, history-preserving bisimulation.

Bibliographic reference: A.Y. Zubarev. Hierarchy of equivalences on time petri nets with weak time policy //journal “Problems of informatics”. 2024, № 1. P.5-40. DOI: 10.24412/2073-0667-2024-1-5-40.

article

PARALLEL NUMERICAL METHOD FOR SOLUTION OF HYDRODYNAMIC EQUATIONS IN THE SHALLOW WATER APPROXIMATION FOR SHARED MEMORY COMPUTERS

Modeling of natural phenomena such as tsunamis, floods, ocean and river currents, and dam breaks are pressing environmental problems. Due to the significant difference in the vertical and horizontal dimensions of the study area, non-stationary two-dimensional hydrodynamic equations in the shallow water approximation have become very popular among researchers of the processes under consideration using mathematical modeling methods, which makes it possible to significantly simplify the mathematical formulation of the problems under consideration. Note, that the accuracy of numerical prediction using such equations depends on a number of conditions, among which the main ones are the spatial resolution of the study area and the quality of the selected numerical methods. However, increasing the spatial resolution significantly increases the time required to obtain a numerical solution, since in the numerical modeling of processes in the environment, as a rule, explicit or semi- implicit difference schemes are used with a limitation on the time step, depending on the size of the spatial grid steps. That is, as a result, due to the need to carry out calculations with a large number of grid nodes and a smaller time step, calculations on a computer with a sequential architecture can take quite a long time.

The turbulent isothermal motion of an incompressible Newtonian fluid in a river flow is considered. The study area is an open river channel with islands and irregular bottom topography. Current characteristics can vary significantly over time, and therefore the current is considered unsteady with potential flooding of coastal areas. The movement of water in a river is determined by the forces of gravity and friction. In addition, the influence of the Coriolis force and turbulent diffusion on the flow is taken in to account. It is assumed that the horizontal dimensions of the region significantly exceed the vertical ones, the Reynolds-averaged flow characteristics change slightly in the vertical direction, and the vertical pressure distribution is hydrostatic. The thermophysical properties of water (viscosity, density) are considered constant. For numerical modeling of unsteady isothermal turbulent flows in river flows, a mathematical model is formulated based on the shallow water approximation for the Reynolds equations for an incompressible fluid. To take into account the transport, generation, diffusion and dissipation of turbulent vortices, this work uses the k — ε turbulence model constructed by Rastogi and Rodi from the original k — ε model of Launder and Spalding to close the Reynolds shallow water equations.

To construct a discrete analogue of the developed mathematical model, the rectangular computational domain in which the flow with variable boundaries is studied is covered with a structured mesh with steps ∆x, ∆y, respectively. According to the concept of the finite volume method, each internal mesh node appears in a separate finite volume. In this case, the values of the flow depth, bottom topography (and turbulence model parameters) are determined at the nodes of the computational grid, and the velocity vector components are determined at the midpoints of the corresponding faces of the finite volumes. The differential equations of the model are integrated over each finite volume. The equations of motion are approximated in cells shifted by ∆x/2, ∆y/2, respectively. For approximate calculation of integrals, quadrature formulas of average rectangles are used, derivatives are approximately calculated using central-difference formulas. To calculate fluxes on the faces of finite volumes, monotonized upstream van Leer approximations [1] with a limiter [2] are used. When approximating equations in time, conditionally stable semi-implicit difference schemes are used, which are conservative not only for the continuity equation, but also for the equations of motion, which is very important for obtaining non-negative values of flow depth [3]. As a result, semi-implicit difference schemes of first order approximation in time and second order in spatial coordinates are obtained.

The classical two-dimensional Thacker problem of fluid oscillations without friction in a reservoir whose bottom is a paraboloid was considered as a problem on which the accuracy of calculations and the quality of parallelization were tested. Satisfactory agreement between the calculated values of the flow depth and the analytical solution was obtained.

The constructed semi-implicit difference scheme on staggered difference grids has great potential for creating an efficient parallel program, since at each time step, calculations of depth or velocity components can be performed simultaneously and independently in each computational node of the grid. On a server with a total memory of 192 GB and two twelve-core Intel Xeon Silver 4214 2.2 GHz processors and one NVIDIA GeForce RTX2080 Ti graphics card, a study was conducted of the effectiveness of parallel programs built using low-cost parallel programming technologies Open Multi-Processing and Open Accelerators. In these programs, using OpenMP or OpenACC parallel technologies, the execution of iterations of nested loops was evenly distributed among the active threads/processes of the central or graphic processor cores.

The calculation using a sequential program for the conditions under consideration on the server was 547.7 s (500x500 grid) and 4606.4 s (1000x1000 grid). Parallel calculations showed that the use of OpenMP technology for two twelve-core central processors makes it possible to speed up the computing process by more than 15 times. Using OpenACC technology when calculating on the same multi-core system and the NVIDIA GeForce RTX2080 Ti graphics processor gives a speedup of more than 25.

Key words: parallel computations, shallow water equations, shared memory computers, OpenMP, OpenACC.

Bibliographic reference: A. V. Starchenko. Parallel numerical method for solution of hydrodynamic equations in the shallow water approximation for shared memory computers //journal “Problems of informatics”. 2024, № 1. P.41-56. DOI: 10.24412/2073-0667-2024-1-41-56.

article

A METHOD FOR ORGANIZING FUNCTIONAL DIAGNOSTICS IN REGIONAL PUBLIC WARNING SYSTEMS

Key words: warning systems, functional diagnostics, graph traversal algorithms.

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

ARCHITECTURE OF A DISTRIBUTED COMPUTING SYSTEM BASED ON MOBILE DEVICES

The article outlines the architecture of the mathematical and software of a distributed computing system based on many mobile devices integrated into a common network infrastructure. The distributed computing system is based on a problem-oriented task execution model (known in foreign literature as the Task-Based Execution Model). This model of distributed computing is most preferable when solving optimization and inverse problems, when the set of admissible sets of input parameters is sufficiently large. At the same time, the tasks themselves are performed independently, but require significant time expenditures to solve each specific task, comparable to the “lifetime” of a computing node. The Task-Based Execution Model approach allows you to reduce the amount of information transferred between the server and the node, which in turn improves overall performance.

The DHCA system we offer has a client-server architecture and is tailored for the Android system. The mobile client is written using the latest Android approaches to background computing, which allows for increased performance as well as improved security for end users. The system takes into account all the features of the interaction of client-server architecture for distributed systems, and also solves the problem associated with the unavailability of computing nodes by automatically redistributing tasks. Open source code increases trust in the system from end users, which can have a beneficial effect on the number of active

The web client is a web application written in PHP. User interaction with the web client interface is carried out using the jQuery JavaScript library, which allows you to send requests and receive data from the server asynchronously. Interaction with the server is carried out through HTTP requests to the REST API, written in PHP.

The mobile client carries out all interactions with the server API using the Retrofit library, designed for processing HTTP requests. All data is returned in JSON format. Information messages are sent to the mobile client by the Firebase Cloud Messaging (FCM) library.

To derive a formula for assessing scalability for the presented architecture, we take into account the following parameters: t — time required to calculate one data block; N — number of blocks to be calculated (in the case of a ray tracing problem, number of pixels); P is the number of devices involved in the calculation, t₀ is the time required for the initial breakdown of the source data into computational blocks; t_w — time of writing one initial block to the database after splitting; t_s — time required for the client to receive one block of data from the server (send); t_r  — time required for the server to receive the calculated data block from the client (receive); t_v — time required to write the result of the calculated block to the database (saVe). We obtain the calculation time on p devices T(P). Through acceleration as the ratio of T(l) to T(P), we obtain P devices at which maximum acceleration is achieved. To demonstrate the robustness of the developed system, a solution to three problems is presented, in which each elementary task has a different load on the processor and on the network infrastructure. Let us highlight three such tasks:

1. The problem of inverse ray tracing, which is characterized by a significant amount of transmitted data to form a scene and the received data of a full image block. At the same time, the time for ray tracing is much longer relative to the data transmission time.
2. The white dwarf collision problem, which is formulated in a one-dimensional formulation and is characterized by the transmission of only six values to describe the state of the dwarfs before the collision and one output value describing the maximum temperature during the collision. In this case, the calculation time is comparable to the data transmission time. The problem has an analytical solution that requires the resolution of nonlinear equations and is described in detail in the work.
3. The problem of nuclear combustion of carbon in white dwarfs, which is formulated in the form of changes in the concentrations of the main isotopes during nuclear combustion of carbon during the solution of the ODE system. The problem is characterized by input data in the form of two values (initial temperature and carbon density), describing the state of the degenerate gas, and a time parameter in which the evolution of isotopes occurs. The result is represented as seven return values describing the concentration of each isotope. Note that the ODE calculation time significantly exceeds the data transmission time. The formulation of the problem and the results obtained are described in detail in the work.

The architecture proposed in the article makes it possible to take into account the reconfiguration of a network of computing devices and build a guaranteed assessment of the scalability of a distributed heterogeneous computing system.

Key words: Task-Based Execution Model, mobile computing, distributed computing systems.

Bibliographic reference: I.S. Ulyanichev, D.V. Wiens. Architecture of a distributed computing system based on mobile devices //journal “Problems of informatics”. 2024, № 1. P. 74-97. DOI: 10.24412/2073-0667-2024-1-74-97.

article