Development of a Hardware and Software Package for the Implementation of a Method for Constructing All Routes in a Graph Using Database Tools
Abstract
This article is devoted to the design and implementation of software and hardware components of a system that implements an algorithm for constructing all routes in a graph, described in terms of relational algebra. Based on the belonging of the considered problem to the NP-complete class and the characteristics of the proposed parallel method, this paper describes a method for developing a MIMD system presented in the cluster format, on the computing nodes of which the required operations are performed on fragments of source data. Using a scalable parallel system allows you to obtain a sufficient level of performance to test the proposed method on graphs with a large number of vertices. The hardware and software complex described in the main part of this article has the property of universality in relation to the database management systems used and the number of possible dedicated processes. In addition, for the case of a heterogeneous cluster system, a variant of balancing computational volumes is proposed, depending on the technical characteristics of the node that affect the algorithm execution process. This article also describes an experimental analysis of the developed hardware and software complex, which was carried out in order to test the system for scalability, that is, to increase the number of computing nodes that perform the construction of all routes in a large-dimensional graph. This step is performed using the example of a specific implementation using a network of homogeneous workstations acting as cluster nodes with an installed MS SQL Server DBMS. The splitting of the source data into fragments, their subsequent distribution, the allocation of processes and the sending of commands to execute stored procedures that implement the proposed algorithm for constructing all routes in the graph are performed on a separate PC, which is the host. At the same time, communication with database instances installed on the computing nodes of the cluster is implemented using technology ADO.NET.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
