Software & Systems

Journal articles №4 2023

1. Extracting subsystems from a multilevel representation of a Boolean function system for joint logical minimization [№4 за 2023 год]
Authors: Bibilo, P.N. (bibilo@newman.bas-net.by) - United Institute of Informatics Problems of the National Academy of Sciences of Belarus (UIIP NASB) (Professor, Head of Laboratory), Ph.D; Kirienko, N.A. (kir@newman.bas-net.by) - United Institute of Informatics Problems of the National Academy of Sciences of Belarus (UIIP NASB) (Associate Professor, Senior Researcher), Ph.D; Romanov, V.I. (rom@newman.bas-net.by) - United Institute of Informatics Problems of the National Academy of Sciences of Belarus (UIIP NASB) (Associate Professor, Senior Researcher), Ph.D;
Abstract: The paper presents experimental results obtained from studying the effectiveness of programs for minimizing multilevel algebraic representations of Boolean function systems performed in combinational circuit synthesis. The resulting minimized logical descriptions are presented as Shannon expansion formulas or formulas defining Boolean networks. Three approaches are investigated: joint minimization of multilevel representations of Boolean function systems; separate minimization; selection of connected subsystems from an original system, where each connected subsystem is minimized separately, however functions that make up each subsystem are minimized together. After obtaining minimized descriptions of circuits given as a set of interrelated Shannon expansion formulas or as two-operand logical equations corresponding to Boolean networks, the synthesis of logic circuits is performed within the same library for designing custom digital CMOS VLSI (very large integrated circuits made using complementary metal oxide-semiconductor technology). The resulting logic circuits are compared in terms of a crystal area and speed (time delay). Experiments involve 39 industrial examples of circuits. Experimental results show competitiveness and expediency of all three considered approaches in practice. The improvement of circuit parameters (area, time delay) in approach 3 is achieved due to minimizing each selected subsystem on the basis of Shannon expansions in its own (for each subsystem) permutation of expansion variables. At the same time, minimizing multilevel representations based on Shannon expansions for function system matrix descriptions is more effective for one half of circuits; minimizing based on Shannon expansions of function systems presented as logical equations is effective for the other half. The practical significance of the study is that the developed software, which implements the proposed algorithm for extracting Boolean function subsystems, allows reducing the area and increasing the performance of functional blocks of custom CMOS VLSI in many cases.
Keywords: cmos, vlsi, vhdl, digital logic synthesis, Boolean net, Binary Decision Diagram (BDD), disjunctive normal form, disjunctive normal form (DNF), the system of boolean functions
Visitors: 3331

2. Quantum algorithmic gate-based computing: Grover quantum search algorithm design in quantum software engineering [№4 за 2023 год]
Authors: Ulyanov, S.V. (ulyanovsv46_46@mail.ru) - Dubna State University – Institute of System Analysis and Management, Joint Institute for Nuclear Research – Meshcheryakov Laboratory of Information Technologies (Professor), Ph.D; Ulyanov, V.S. (ulyanovik@mail.ru) - Moscow State University of Geodesy and Cartography (MIIGAiK) (Associate Professor), Ph.D;
Abstract: The difference between classical and quantum algorithms (QA) is following: problem solved by QA is coded in the structure of the quantum operators. Input to QA in this case is always the same. Output of QA says which problem coded. In some sense, give a function to QA to analyze and QA returns its property as an answer without quantitative computing. QA studies qualitative properties of the functions. The core of any QA is a set of unitary quantum operators or quantum gates. In practical representation, quantum gate is a unitary matrix with particular structure. The size of this matrix grows exponentially with an increase in the number of inputs, which significantly limits the QA simulation on a classical computer with von Neumann architecture. Quantum search algorithm (QSA) – models apply for the solution of computer science problems as searching in unstructured data base, quantum cryptography, engineering tasks, control system design, robotics, smart controllers, etc. Grover’s algorithm is explained in details along with implementations on a local computer simulator. The presented article describes a practical approach to modeling one of the most famous QA on classical computers, the Grover algorithm.
Keywords: quantum operators design, quantum algorithmic gate, quantum circuits, quantum search algorithms
Visitors: 2775

3. An integer programming solution: Iterative rounding of coordinates [№4 за 2023 год]
Authors: Ivanov, A.V. (lexuzieel@gmail.com) - Tver State Technical University (Postgraduate Student); Matveev, Yu.N. (matveev4700@mail.ru) - Tver State Technical University (Professor), Ph.D;
Abstract: The article proposes an algorithm for finding an integer solution using the idea of rounding coordinates of an optimal non-integer solution point and constructing a half-line directed deep into an acceptable solution area. The proposed algorithm is based on an iterative process of rounding coordinates of a point in the direction of a constructed half-line. The study educed that moving towards a half-line without going through all possible options simplifies the algorithm and avoids branching, which distinguishes this approach compared to other currently existing open methods, such as the method of clipping and the method of branches and boundaries. The aim of the work is to develop and study an algorithm for finding an optimal integer solution using the idea of rounding coordinates of a point of an optimal non-integer solution. During the study, the authors carried out description and experimental verification of this algorithm and the possibility of its application in different forms of an acceptable solution domain. The theoretical significance of the work is a development of a new algorithm that does not require performing a simplex-method at each stage, and uses a half-line instead of a plane at each algorithm step, which prevents an increase in problem spatial complexity compared to other methods. The study showed that the proposed algorithm has limitations; however, the main idea proved its operability, which is planned to be developed further.
Keywords: coordinate descent, algorithm, optimisation, , linear programming, mathematical programming
Visitors: 3185

4. Automatic runtime error localization for software debugging using neural networks [№4 за 2023 год]
Authors: Dostovalova, A.M. (dost.bmstu99@gmail.com) - Morinsis-Agat Concern JSC, Federal Research Center (Technical Fellow Programmer, Research-Engineer); Sherminskaya, A.A. (SherminskayaAA@yandex.ru) - Morinsis-Agat Concern JSC (Head of Sector);
Abstract: A new automatic runtime error localization method using a neural network was developed. The method determines bug position by program functions tracing data. The method matches an error containing probability for each function. This probability is proportional to the effect of each function parameter on a program execution result. A numerical characteristic calculated by Hashem algorithm determines a parameter effect. The method was applied for debugging several programs with nested functions. The most probable bug locations defined by the method were compared with their real positions. The developed method has some features. It is able to localize multiple bugs, nested function bugs, and bugs with unequal manifestation and location places. In all cases, bugged parameters had more weight in comparison with rest parameters. At the same time, method determines a full error trace for each bug. The trace consists of all program parameters related to a bug. Therefore, the method is able to localize logical errors in program. The method can be used for debugging both technical system software and hardware since method logic does not depend on source data.
Keywords: tracing, neural network, program debugging, runtime error, automatic bug localization
Visitors: 3166

5. Tools for vectorizing a flat loop body using AVX-512 vector instructions [№4 за 2023 год]
Authors: Rybakov, A.A. (rybakov@jscc.ru ) - Joint Supercomputer Center of RAS (Leading Researcher), Ph.D; Shvindt, A.N. (shvindt@ispras.ru) - Ivannikov Institute for System Programming of the Russian Academy of Sciences (ISP RAS) (Doctoral Student), Ph.D;
Abstract: The paper studies approaches to reducing program execution time using instructions from AVX-512 set to increase program code vectorization efficiency. Vectorization is a basic low-level optimization that can speed up program execution by several times; AVX-512 instruction set has a number of unique features that allow applying vectorization in complex program contexts. The paper investigates a special type program context – a flat loop, which can be vectorized using AVX-512 instructions with almost arbitrary body complexity if meeting a number of requirements. However, quite often an optimizing compiler fails to automatically vectorize flat loops due to complex control, function calls, nested loops, and other constructs. This leads to manual vectorization using special intrinsic functions. Vectorization efficiency directly depends on the density of vector operation masks, which turn out to be sparse with a highly branched control inside a flat loop body. The paper proposes a toolkit that allows simultaneous creating a scalar and vector version of a flat loop and analyzing performed vectorization effectiveness. At the same time, there are two modes of assembling the code under test: a scalar version with emulation and monitoring of vector instructions and a vector version for execution on a target machine. On the one hand, this allows controlling code transformations to be correct; on the other hand, this allows tracking program execution paths with a low probability for their localization or removal from a loop body. The created tools enabled identifying hot flat loops of some real applications and increasing their vectorization efficiency.
Keywords: computer applications, low-level optimization, avx-512, flat loop, vectorization
Visitors: 2850

6. Developing a mobile application life cycle model for people with intellectual disabilities [№4 за 2023 год]
Authors: Guryev, V.V. (vladgurjev@mail.ru) - Volgograd State Technical University (Postgraduate Student); Shabalina, O.A. (o.a.shabalina@gmail.com) - Volgograd State Technical University (Associate Professor), Ph.D; Sadovnikova, N.P. (npsn1@ya.ru) - Volgograd State Technical University (Professor), Ph.D; Voronina, A.A. (angelina.vaa@gmail.com) - Volgograd State Technical University (Postgraduate Student);
Abstract: The article discusses life cycle models and software tools for supporting mobile application development. It also analyzes peculiarities of developing mobile applications for people with intellectual disabilities. One way to increase the accessibility of applications is to make them adaptable. Such adaptation requires supporting an application dynamic content, therefore, these features must be already provided at life cycle design and implementation stages. The paper proposes a mobile application development lifecycle (MADLC) model that provides end-to-end support for the stages of design, implementation and maintenance of mobile applications for users with intellectual disabilities. There is a developed mobile application design technology based on a multi-module architecture, which includes developing ready-made architectural templates for generating a basic application code and reuse of successful design solutions. The paper describes the devel-oped adaptable interface design technology based on Pattern-Based user Interface Design Approach. The technology includes developing screen templates, separating template elements into mandatory and optional ones, matching each GUI element with a predefined set of its possible visual representation, and attaching elements in place. A mobile application management system implements CALS technology of end-to-end support for the stages of mobile application design, im-plementation and operation. The paper proposes a method for adapting a mobile application interface using a configuration panel built into the system. There is an example of developing a mobile game for training shopping skills for people with intellectual disabilities. It is shown that the mobile application management system can significantly reduce time spent on developing mobile applications. Using architecture templates and ready-made solutions expands the range of system users and makes it available to developers whose professional activities are related to supporting people with intellectual disabilities.
Keywords: adaptable mobile application, user with intellectual disabilities, MADLC model, mobile application life cycle model, mobile application life cycle
Visitors: 2462

7. Simulation of hydraulic actuator dynamics in virtual environment systems [№4 за 2023 год]
Authors: Strashnov, E.V. (strashnov_evg@mail.ru) - Federal State Institution "Scientific Research Institute for System Analysis of the Russian Academy of Sciences" (SRISA RAS) (Research Associate); Mironenko, I.N. (vstudio@niisi.ras.ru) - Federal State Institution "Scientific Research Institute for System Analysis of the Russian Academy of Sciences" (SRISA RAS) (Research Associate);
Abstract: The development of computer graphics and computing machinery has led to active using of virtual environment systems in many areas of human activity. In particular, virtual (computer) training complexes for simulation and control of complex mechanical systems are widely used. Some of these systems are equipped with hydraulic actuators. This paper considers real-time simulation of hydraulic actuators dynamics in virtual environment systems. The authors propose solving this problem based on an approach with co-simulation dynamics of hydraulic actuators and articulated rigid bodies. To this end, the authors used a sequential impulses method that resulted in obtaining coordinates and velocities of piston and two linked bodies. The approach assumes that, first, piston velocity is computed by integrating hydraulic equations using a semi-implicit Euler scheme without taking load into account. Then, the obtained velocity is adjusted by an impulse that limits velocities of a piston and two linked bodies. The proposed approach is iterative and makes it possible to implement dynamics of articulated body systems with a hydraulic actuator in real time. The main result of the study is in flexibility of the developed approach for simulating hydraulic actuator dynamics based on a sequential impulses method; it allows ensuring all constraints in a multibody system in a unified way. Unlike other similar solutions, this approach does not require cumbersome matrix calculations and solving large dimension linear equation systems. Approbation in the created VirSim software package showed adequacy and effectiveness of the solutions proposed in the paper. The practical significance of the work is that the proposed methods and approaches for simulating hydraulic actuators dynamics can be used in simulators for training operators of skills for controlling robots, machines of various types, mechanisms, equipment, etc.
Keywords: virtual environment systems, semi-implicit Euler scheme, sequential impulses method, directional control valve, hydraulic actuator, dynamics modeling
Visitors: 2497

8. Neural network-based approach for identifying fake news [№4 за 2023 год]
Authors: Tumbinskaya, M.V. (tumbinskaya@inbox.ru) - National Research Technical University (Associate Professor, Department of Information Security Systems), Ph.D; Galiev, R.A. (renat5390@yandex.ru) - Kazan National Research Technical University named after A.N. Tupolev (Student);
Abstract: Currently, telecommunication facilities actively disseminate news. Identification of fake news based on their headlines has become a relevant problem. The purpose of this study is to increase a user information reliability level in browser environment. Automated recognition of fake news based on their headlines in the browser environment can achieve this goal. The paper proposes using neural networks that allow analyzing fake news headlines semantically and processing large amounts of data. The article examines popular foreign and domestic web resources for identifying fake news, their distinctive features. The authors carried out an analysis and selected neural network models BERT-MLP, BERT-CNN, BERT-LSTM to be a basis for developing a web resource. They used samples of Russian-language news headlines to train neural network models. An experimental study was carried out to assess the quality and adequacy of neural network models on test and validation data samples including news headlines on various topics. The developed web resource based on the BERT-CNN, BERT-GRU, BERT-LSTM models showed good results. The reliability of identifying fake news was 86,29%. The practical value of the work is in the fact that the developed web resource can be used as a tool for recognizing fake news by specialists in counteracting destructive political technologies, as well as information security specialists. To im-prove classification accuracy, it is advisable to expand a training data set, which allows identifying more complex dependencies in data.
Keywords: illegitimate news, web resource, news headline, lstm, GRU, CNN, BERT, a neural network, fake news
Visitors: 2752

9. Integration of reinforcement learning methods and fuzzy logic for intelligent real-time systems [№4 за 2023 год]
Authors: Eremeev, A.P. (eremeev@appmat.ru) - National Research University “MPEI” (Professor), Ph.D; Sergeev, M.D. (SergeevMD@mpei.ru) - National research University "MPEI" (Postgraduate Student); Petrov, V.S. (PetrovVS@mpei.ru) - National research University "MPEI" (Student);
Abstract: The paper considers the possibilities of integrating reinforcement learning methods and fuzzy logic in terms of improving the efficiency of reinforcement learning algorithms. The main focus is on applying such integrated methods in real-time intelligent systems, especially in decision support systems for monitoring and controlling complex technical objects. The basis is a reinforcement learning method based on temporal differences; an environmental state and the reward signal are formed using fuzzy logic. The paper presents software implementation and the data of computer simulation of deep learning methods with reinforcement based on temporal differences obtained from a comparative analysis of a fuzzy logic algorithm and neural network algorithms. The authors of the paper show that the main advantages of reinforcement learning algorithms using fuzzy logic are: training effectiveness in terms of minimizing the number of episodes, which is especially important regarding the availability of limited data for training or rapid adaptation of real-time training; resistance to noise and outliers in data, which is important in real environments with noise or data changes; interpretability - fuzzy logic algorithms provide interpretable rules and conclusions based on fuzzy logic; extension of a reinforcement learning scope to subject/problem areas and tasks with a continuous state space. These researches and developments are carried out in terms of designing intelligent real-time decision support systems. Such systems are designed to help operational dispatch personnel (decision makers) in monitoring and managing complex technical and organizational systems under fairly severe time constraints and various types of uncertainties (inaccuracies, fuzziness, inconsistencies) in the information entering a system, i.e. in the presence of so-called noisy data.
Keywords: decision support, real time, intellectual system, fuzzy logic, time, reinforcem ent learnin, artificial intelligence
Visitors: 3444

10. Using MPI library for parallel implementation of a brute-force algorithm [№4 за 2023 год]
Authors: Aye Min Thike (ayeminthike52@gmail.com) - National Research University of Electronic Technology, MIET (Doctoral Student), Ph.D; Lupin, S.A. (lupin@miee.ru) - National Research University of Electronic Technology, MIET, Joint Supercomputer Center of RAS (Professor), Ph.D; Fedyashin, D.A. (fedyashinda@gmail.com) - National Research University of Electronic Technology, MIET (Head of Computer Center);
Abstract: The paper presents results of studying the effectiveness of a parallel application for solving a quadratic assignment problem. The application uses a brute-force algorithm and a Message Passing Interface (MPI) to ensure interprocess communication in a distributed computing environment. Solution options are generated by a lexicographic permutation method, which is well parallelized and ensures load balancing of nodes. The range of brute-force algorithm use to large scale optimization problems is expanded by dividing a search space into parts, which significantly reduces the number of options under consideration. The experiments were conducted in a distributed environment containing 50 nodes with the 7th generation Intel ® Core ™ i5 processors. A parallel application for solving a large-scale problem (n = 24) demonstrated the possibility accelerating calculations in the range from 99 to 95 % from the maximum possible one; an exact solution was found in all cases. This confirms the correctness of methods used for load distribution and for computational complex-ity reduction of tasks. Further work will be aimed at exploring the possibility of using the proposed approaches to implementing a brute-force algorithm and as hybrid applications, which is relevant for heterogeneous computing environments. Since a quadratic assignment problem is a discrete optimization problem, the obtained results suggest that the proposed approaches are effective for other problems of this class.
Keywords: hpc, MPI, distributed computing, brute-force algorithm, quadratic assignment problem, combinatorial optimization
Visitors: 3074

| 1 | 2 | Next → ►