Application of the design method for q-efficient programs implementing Dijkstra's algorithm

The problem of improving the efficiency of parallel computing is extremely relevant. The article demonstrates the initial application of the concept of Q-determinant for the effective implementation of graph algorithms. The concept of the Q-determinant is based on a unified representation of numerical algorithms in the form of the Q-determinant. The Q-determinant allows to express and evaluate the internal parallelism of the algorithm, as well as to show the method of its parallel execution. The article gives the main notions of the Q-determinant concept necessary for better understanding of our research. Also, we describe a method of designing effective programs for numerical algorithms on the base of the concept of the Q-determinant. As a result, we obtain the program, which uses the parallelism resource of the algorithm completely, and this program is called Q-effective. As the initial application of the method for design of Q-effective programs implementing graph algorithms, we describe the designing programs for Dijkstra’s algorithm implementation on parallel computing systems with shared and distributed memory. Finally, for the developed programs, we present the results of experiments on the Tornado SUSU supercomputer. Analyzing the results of the experimental study, we determine the effectiveness of the developed programs and identify features of their execution. The research described in the article leads to the conclusion that the application of the Q-determinant concept for the development of effective programs is possible not only for numerical algorithms, but also for graph algorithms.