Preview

Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS)

Advanced search
Vol 32, No 4 (2020)
View or download the full issue PDF (Russian)
7-20
Abstract

The term BigData causes a lot of controversy among specialists, many of whom note that it only means the volumes of accumulated data, but do not forget about the technical side, the considered direction includes technologies for computing, storage, and also service services. Big Data is a term that denotes technologies for processing large unstructured and structured data to obtain results that are understandable and useful to humans. In business, Big Data is used to support the adoption of transformations by a manager (for example, based on an analysis of financial indicators from an accounting system) or a marketer (for example, based on an analysis of customer preferences from social networks). By themselves, Big Data algorithms appeared with the introduction of the first mainframes (high–performance servers), which have the necessary resources for operational data processing and are suitable for computer calculations and subsequent data analysis. As the number of embedded computers rises due to falling processor prices and the ubiquity of the Internet, so too is the amount of data transferred and then processed (often in real time). Therefore, we can assume that the importance of cloud computing and the Internet of Things will increase in the coming years. It should be noted that Big Data processing technology boils down to three main areas that solve three types of tasks: (1) translation and storage of incoming information in gigabytes, terabytes, petabyte, etc. for their processing, storage and application in practice; (2) structuring of disparate content, namely: photos, texts, audio, video and all other types of data; (3) analysis of Big Data and the implementation of different methods of processing unstructured data, the creation of various analytical reports. In essence, the application of Big Data implies all areas of work with large volumes of the most disparate data, constantly updated and scattered across various sources. The goal is quite simple – the most efficient work, the introduction of new products and increased competitiveness. In this article, we will consider the features of solving the problems of using Big Data in international business.

21-40
Abstract
Sustainable development and increasing competitiveness are the main tasks of managing a scientific organization. The analysis of competencies provides a detailed understanding of the available resources when forming a development strategy, and their assessment - knowledge of the strengths and risks in its implementation. The development of competencies inevitably leads to the organizational consolidation of resources in the departments of a scientific organization - centers of competence. The aim of the study is to develop a methodological framework for identifying and assessing centers of competence in the field of aircraft construction. The proposed technique involves the use of full-text search and analysis tools for scientific and technical documents to identify research areas, technologies and affiliated centers. To obtain categorical assessments of the level of development of centers of competence, an original approach is proposed, including the approximation of the mass of scientific and technical documents using s-curves and their analysis using the theory of fuzzy sets. The article proposes a methodology for identifying and evaluating centers of scientific competence in aviation science and presents the results of its testing on the example of 143 such centers in the field of aircraft construction in Russia. The developed methodology allows the use of full-text search and analytical tools for the analysis of competencies, which ensures the formation of a detailed assessment of the available resources when planning the development of a scientific organization in the field of aircraft construction. In the future, it is planned to automate the proposed methodology by integrating the relevant modules into the developed expert information system for the search, analysis and accounting of knowledge in aircraft construction.
41-52
Abstract
Mathematical modeling allows to create a digital model of a product, the so-called digital twin. Such digital twins are quite complex mathematical models, the description of which, as well as the calculation of their parameters and characteristics, is a very serious computational problem that can be solved on high-performance computing systems. However, a building a high-performance supercomputing system designed for solving problems of computer simulation of various physical processes is a difficult time-consuming task. The paper discusses basic approaches to design a login nodes subsystem for such high-performance supercomputing system, allowing to systematize and simplify the process of its development. The analysis of the main factors affecting the structure and composition of the login nodes subsystem is carried out. These factors include the number of potential users of a high-performance computing system; availability of categories of users of the system and their percentage; characteristics of computing tasks solved on the system; hardware platform chosen for building systems. An example of a methodology for calculating of the login nodes subsystem size is given.
53-72
Abstract
The paper considers a single-pass scheme for rendering dynamic 3D scenes using modern GPUs and graphics interfaces. The following methods and techniques are used with this scheme: clipping of objects using spatial decomposition and indexing methods, hardware occlusion queries, fragmentation and caching of command buffers. These methods require significant computational resources to execute, and the amount of work in the stages of the graphics pipeline depends on their results. Therefore, a balanced use of resources when transferring graphics data and executing commands is important. A performance model of the graphics pipeline is proposed, which makes it possible to estimate the required resources depending on the applied base methods and characteristics of the displayed scene. Unlike existing methods and models, the proposed model allows to calculate the costs of composing command buffers using various recording techniques, the costs of sending, executing, and receiving the results of hardware occlusion queries. Formulas are derived to calculate frame rendering time depending on the number of occlusion queries. A method is proposed to estimate the number of occlusion queries for efficient rendering of dynamic scenes. Computational experiments are carried out to show the relevance of the proposed model and the effectiveness of the developed method when displaying large dynamic scenes. Section 1 provides an overview of related work as well as general purposes of given paper and its structure. Section 2 describes the proposed performance model and method used to calculate the number of occlusion queries for efficient rendering of dynamic scenes. Section 3 presents the performance analysis, which contains derived and measured rendering time when rendering scenes and employing frustum culling, occlusion queries. Section 4 summarizes the main conclusions.
73-88
Abstract
The paper deals with the task of creation and playback of panoramic video with 360-degree overview, which allows the researcher to be immersed in virtual medium outside parent virtual environment system (VES). To solve the task, the extension of the cubemap method is proposed, in which cubemap resolution is determined taking into account viewer camera field of view and screen resolution (Adequate Cubemap Projection, ACMP). The paper studies the influence of the camera orientation inside the cube on the "cubemap pixel / screen pixel" ratio determining panorama visualization quality. Based on this, a method to calculate cubemap resolution for high-quality panorama visualization for all possible camera orientations is proposed. The paper considers an efficient method and algorithm to create ACMP-video on the GPU using render-to-texture technology, which allow to synthesize panoramas with constant orientation or bound to the observer's view direction. In the research efficient methods and algorithms to play ACMP-video are also proposed, which are based on the visualization of visible cube faces and adaptive frame buffering. The obtained methods and algorithms are implemented in ACMP-video synthesis program complex (С++, OpenGL, FFmpeg) including frame capture module (embeddable into VES) and the player. The developed solution was tested in system «Virtual Earth» designed for training to observe Earth objects from the International Space Station (ISS). Using the capture module, an ACMP-video of the flight along the ISS orbit track was created. When playing this video, the trainee flies in orbit above virtual 3D surface of the Earth and can explore it by means of camera rotation. Testing of the complex confirmed the adequacy of the developed methods and algorithms to the task. The obtained scientific and practical results expand the capabilities and scope of application of VES, scientific visualization systems, video simulators and virtual laboratories; provide effective exchange of experience between researchers, etc.
89-96
Abstract

Despite the fact that software development uses various technologies and approaches to diagnose errors in the early stages of development and testing, some errors are discovered during operation. To the user, errors often look like a program crash while running. To collect reports on program crashes, a special analysis component is built into the operating system. Such a component is present in both Windows OS and Linux-based OS, in particular Ubuntu. An important parameter is the severity of the error found, and this information is useful to both the developer of the distribution kit and the user. In particular, users with such diagnostics can take organizational and technical measures before the release of a bug fix from the software developer. The article introduces CASR: a tool for analyzing a memory image at the time of a process termination (coredump) and reporting errors. The tool allows you to assess the severity of the detected crash by analyzing the memory image, as well as collect the necessary information for the developer to help fix the defect. Such information is: OS distribution version, package version, process memory card, state of registers, values of environment variables, call stack, signal number that led to abnormal termination, etc. Severity assessment enables the software developer to correct errors, which are the most dangerous in the first place. CASR can detect files and network connections that were open at the time of the crash. This information will help reproduce the error, and will help users and administrators take action in the event of an attack on the system. The tool is designed to work on Linux OS and supports x86 / 64, armv7 architectures and can be supplied as a package for Debian-based distributions. The tool has been successfully tested with several open source bugs.

97-114
Abstract

The paper presents a debugger for parallel programs in С/C++, or FORTRAN, which are executed in high-performance computers. The debugger’s program components and mechanism of their interaction are described. The graphic user’s interface capabilities are discussed and the profiling procedure using built-in profiling tools is described. The paper contains of the description of the new parallel debugger capabilities such as a communication treelike scheme of his components connection, and a non-interactive debugging mode, and the support of Nvidia’s graphic accelerators. Currently, the debugger provides launching of debug jobs in the systems of batch processing of jobs such as Open PBS / Torque, SLURM, and CSP JAM but it can be configured for other systems. The PD debugger allows to debug program processes and threads, manage breakpoints and watchpoints, logically divide program processes into subsets, manage them, change and view variables, and profile the debugged program using the free Google Performance Tools and mpiP. The PD debugger is written in the Java programming language, intended for debugging programs on Unix / Linux operating systems, and it uses free software components such as SwingX, JHDF5, Jzy3D, RSyntaxTextArea, and OpenGL.

115-132
Abstract
We define a problem of certifying computation integrity performed by some remote party we do not necessarily trust. We present a multi-party interactive protocol that solves this problem under specified constraints. The protocol rely on a computing entity called weak reliable computing device that is able to produce certificate for a tiny computation. A complex computation of a user can be certified by relying on such weak entity if we translate the user program into an iterative form that converges to the result, a style resembling continuation-passing style programming paradigm. Each iteration of the computation can then be certified by the weak reliable computing device. To ensure the user that computation result was computed fairly and correctly, we put this mechanism into a multi-party incentivized context of several computing providers competing with each other for publishing the result and taking the reward, or finding an error in the published result of other parties. Together with computation result, the computation certificate is published. The certificate is constructed in such a way that other fair parties (auditors) are able to find divergent computation step in O(logn) steps, where n is a number of computing steps taken before reaching the result. If error is found, the auditor sends proof of the error (called refutation) in the trusted weak computing device that plays the role of autonomous transparent arbiter able to check refutation by replaying a tiny fraction of the computation.  Comparing to the nearest related work, our protocol reduces a proof construction complexity from O(nlogn) to O(n), turning a communication complexity to exactly one round using a certificate of a comparable length. We also give the formal specification for the protocol and prove some of its security properties in a specified threat-model. Experimental evaluation of the protocol in a model setting is provided.
133-140
Abstract
The scope of voluntary computing systems is constantly expanding. The BOINC system is currently the most famous for organizing volunteer computing. There are many scientific papers on the adaptation of various computational algorithms to the BOINC. The topic of the presented work is the effective adaptation of the evolutionary algorithm to voluntary computing systems. The reasons for productivity losses are considered, criteria and metrics for evaluating the quality of the algorithm are introduced. The content of the article consists of two main parts. The first part of the article discusses general metrics that can be used to assess the performance of various computational algorithms within BOINC. The problem of adaptation of the evolutionary algorithm is considered in the second part of the article. Two main problem-specific causes of productivity loss are considered: the effect of waiting for the last job and the effect of a common queue. Methods are proposed for quantitative assessment of the influence of various systemic effects on the performance of an evolutionary algorithm. The proposed metrics can be used in a comparative analysis of various job scheduling policies when performing calculations. The metrics can be calculated both during the actual and simulated calculations.
141-154
Abstract

This paper presents the results of the application of a convolutional neural network to diagnose left atrial and left ventricular hypertrophies by analyzing 12-lead electrocardiograms (ECG). During the study, a new unique dataset containing 64 thousand ECG records was collected and processed. Labels for the two classes under consideration, left ventricular hypertrophy and left atrial hypertrophy, were generated from the accompanying medical reports. A set of signals and obtained labels were used to train a deep convolutional neural network with residual blocks; the resulting model is capable of detecting left ventricular hypertrophy with F-score more than 0.82 and left atrial hypertrophy with F1-score over 0.78. In addition, the search for optimal neural network architecture was carried out and the experimental evaluation of the effect of including patient metadata into the model and signal preprocessing was conducted. Besides, the paper provides a comparative analysis of the difficulty of detecting left ventricular and left atrial hypertrophies in relation to the other two frequently occurring heart activity disorders, namely atrial fibrillation and left bundle branch block.

155-164
Abstract
The article substantiates the relevance of steganalysis, as a determination of the presence of a hidden channel in telecommunication systems, whose nodes exchange digital images. The article deals with the application of convolutional neural networks to solve this problem. It is assumed that the probability of correct image classification using a well-trained convolutional neural network will be comparable or even better than characteristics of statistical algorithms or the RM model. We introduce principles of construction and capabilities of convolutional neural networks in the framework of their applicability to solving the problem of steganalysis. To improve the efficiency and effectiveness of the stegocontainer recognition process, a version of the image classification model for a convolutional neural network is proposed. It is based on combination of several convolutional and fully connected layers. We have developed software for this model version with the ability to train a neural network and evaluate the quality of classification. The analysis of existing software products designed for the task of determining the fact of using steganography in digital images is carried out. The advantage of classifiers based on neural networks in comparison with statistical ones is proved. Using the developed software, an experimental study of classification model on sets of digital images contained in open sources has been carried out. The article presents the results of neural network training, as well as an analysis of the strengths and weaknesses of the selected model.
165-174
Abstract

Amount of news is rapidly growing up in recent years. People cannot handle them effectively. This is the main reason why automatic methods of news stream analysis have become an important part of modern science. The paper is devoted to the part of the news stream analysis which is called “event detection”. “Event” is a group of news dedicated to one real-world event. We study news from Russian news agencies. We consider this task as clusterization on news and compare algorithms by external clusterization metrics. The paper introduces a novel approach to detect events at news in Russian language. We propose a two-staged clustering method. It comprises “rough” clustering algorithm at the first stage and clarifying classifier at the second stage. At the first stage, a combination of shingles method and naive named entity based clusterization is used. Also we present a labeled dataset of news event detection based on «Yandex News» service. This manually labeled dataset can be used to estimate event detection methods performance. Empirical evaluation on these corpora proved the effectiveness of the proposed method for event detection at news texts.

175-188
Abstract

Logical structure extraction from various documents has been a longstanding research topic because of its high influence on a wide range of practical applications. A huge variety of different types of documents and, as a consequence, the variety of possible document structures make this task particularly difficult. The purpose of this work is to show one of the ways to represent and extract the structure of documents of a special type. We consider scanned documents without a text layer. This means that the text in such documents cannot be selected or copied. Moreover, you cannot search for the content of such documents. However, a huge number of scanned documents exist that one needs to work with. Understanding the information in such documents may be useful for their analysis, e. g. for the effective search within documents, navigation and summarization. To cope with a large collection of documents the task should be performed automatically. The paper describes the pipeline for scanned documents processing. The method is based on the multiclass classification of document lines. The set of classes include textual lines, headers and lists. Firstly, text and bounding boxes for document lines are extracted using OCR methods, then different features are generated for each line, which are the input of the classifier. We also made available dataset of documents, which includes bounding boxes and labels for each document line; evaluated the effectiveness of our approach using this dataset and described the possible future work in the field of document processing.

189-202
Abstract

In this paper, we propose an approach to the document images segmentation in a case of limited set of real data for training. The main idea of our approach is to use artificially created data for training and post-processing. The domain of the paper is PDF documents, such as scanned contracts, commercial proposals and technical specifications without a text layer is considered as data. As part of the task of automatic document analysis, we solve the problem of segmentation of DLA documents (Document Layout Analysis). In the paper we train the known high-level FasterRCNN \cite{ren2015faster} model to segment text blocks, tables, stamps and captions on images of the domain. The aim of the paper is to generate synthetic data similar to real data of the domain. It is necessary because the model needs a large dataset for training and the high labor intensity of their preparation. In the paper, we describe the post-processing stage to eliminate artifacts that are obtained as a result of the segmentation. We tested and compared the quality of a model trained on different datasets (with / without synthetic data, small / large set of real data, with / without post-processing stage). As a result, we show that the generation of synthetic data and the use of post-processing increase the quality of the model with a small real training data.

203-216
Abstract

Nowadays the problem of legal regulation of automatic collection of information from sites is being actively solved. This means that interest in tools and programs for automatic data collection is growing and that's why interest in automatic programs for solving CAPTCHA («Completely Automated Public Turing test to tell Computers and Humans Apart») is increasing too. In spite of сreation of more advanced types of captcha, nowadays text captcha is quite common. For instance, such large services as Yandex, Google, Wikipedia, VK continue to use them. There are many methods of breaking text captchas in literature, however, it should be noted that most of them have a limitation to priori know the length of the text on the image, which is not always the case in the real world. Also, many methods are multi-stage, which brings additional inconvenience to their implementation and application. Moreover, some methods use a large number of labeled pictures for training, but in reality, to collect data one has to be able to solve captchas from different sites. Respectively, manually labeling dozens of thousands of examples for training for each new type of captcha is an unrealistically difficult action. In this paper we propose a one-step algorithm of attack on text captchas. This approach does not require a priori knowledge of the text's length on the image. It has been shown experimentally that the usage of this algorithm in conjunction with the adversarial learning method allows one to achieve high quality on real data, using the low number (200-500) of labeled examples for training. An experimental comparison of the developed method with modern analogs showed that using the same number of real examples for training, our algorithm shows a comparable or higher quality, while it has a higher speed of working and training.

217-234
Abstract

Currently, RF is actively developing the Northern territories. Questions of studying the physical processes of icing are relevant, since climate conditions affect the surface of the objects under study (power lines, residential buildings, power plants, aircraft), human safety and ecology. In clouds, the appearance and movement of liquid droplets-particles is possible. When studying two-phase flows containing a suspension of aerosol particles (dispersed phase) in the carrier medium (dispersion medium) in the atmosphere, it is important to correctly evaluate the main parameters that define the system, and adequately describe the real process using a formulated mathematical model. This article is devoted to the development of a new iceFoam solver as part of the OpenFOAM v1912 package for modeling the icing process at a typical particle size of about 40 microns, which corresponds to Annex C of the AP-25 Aviation rules. The Euler-Lagrangian approach and finite volume method are used to describe the dynamics of liquid droplets. A modified liquid film model based on the shallow water theory is used as a thermodynamic model. The results of calculation for the case of flow around the cylinder and airfoil NACA 0012 using the URANS method and Spalart-Allmaras turbulence model are presented. In the calculation domain, two variants of grids are constructed: for an external gas-drop flow and for a liquid thin film with a thickness of one cell in height. Patterns of ice thickness distribution are given. When developing the source code using C++ language, the technology of inheritance was used, i.e. creating base and derived classes. As a result, a parallel iceFoam solver was developed for simulating the motion of liquid particles and the formation of ice on the bodies’ surface. For the calculation of one test case 8-32 computing cores were used on the ISP RAS HPC.

235-244
Abstract

The creation of high-performance methods for calculating the interaction of aerosol flows with a solid is of great practical interest in the problems of preventing surfaces from icing, predicting climatic phenomena, metallurgy and astronomical processes. One of the methods of icing diminishing is the use of hydrophobic coatings, which, as a rule, work effectively with insignificant ratios of inertial forces to the forces of surface tension of a liquid near the relief of the streamlined body. However, when the surface density of the kinetic energy of the supercooled drop exceeds a certain critical value, the ice-phobic properties lead to negative effects due to the penetration of the supercooled liquid into the depressions and solidification in them. A method is developed for calculating the interaction of supercooled drops with a relief solids, which have various degrees of hydrophobicity. Basic criteria for corresponding the results of molecular modeling to physical reality are formulated. The need to develop algorithms for numerical simulation is due to the fact that significant computational resources are required even for calculating small droplets which are several tens of nanometers in size. Numerical estimates of the parameters of the relief of a hydrophobic surface of a solid are obtained depending on the dimensionless dynamic parameters of the impact of supercooled drops. Moving interface – the crystallization front in supercooled metastable liquid droplets has specific properties. On the basis of previously carried out experimental studies, theoretical estimates, analytical and experimental data of other researchers, in present work mathematical models of the crystallization features of a supercooled metastable liquid are developed. Estimates of the parameters of the processes accompanying the movement of the crystallization front in supercooled metastable water droplets are obtained with application to the problem of icing of aircraft.

245-260
Abstract

The paper investigates the implementation of virtual networks on the SDN data plane which is modeled by a graph of physical connections between network nodes. A virtual network is defined as a set of ordered host pairs (sender, receiver), and it is implemented by a set of host-host paths that uniquely determine the switch settings. A set of paths is perfect if any subset of its paths can be loop-free implemented, i.e., can be implemented without the occurrence of an endless movement of packets in a loop, without duplicate paths, when the host receives the same packet several times, and without unintended paths when the host receives the packet that was directed to another host. For the case when the switchgraph is a complete graph, sufficient conditions for the existence of the largest perfect set of paths connecting all pairs of different hosts are established. Algorithms for constructing such a largest perfect set are proposed with the estimates of their complexity. The paper also has the preliminary results of computer experiments which show that proposed sufficient conditions are not necessary conditions.

261-284
Abstract

In this paper, we present a method for state space reduction of dense-time Petri nets (TPNs) – an extension of Petri nets by adding a time interval to every transition for its firing. The time elapsing and memory operating policies define different semantics for TPNs. The decidability of many standard problems in the context of TPNs depends on the choice of their semantics. The state space of the TPN is infinite and non-discrete, in general, and, therefore, the analysis of its behavior is rather complicated. To cope with the problem, we elaborate a state space discretization technique and develop a partial order semantics for TPNs equipped with weak time elapsing and intermediate memory policies.



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)