OPENMP PARALLEL CALCULATIONS IN ALGORITHMS FOR SOLVING SHORTEST PATHS PROBLEM

The relevance of the study is due to the need to solve the problems of parallelization of calculations for the class of NP-complete problems, since computing power allows the use of parallel flows and reduce the computation time and energy consumption to obtain a complex computational result using software technologies of parallelization of calculations. In this regard, this article aims to publish the results of the study, based on the analysis of empirical data, proving the effectiveness of parallel calculations for the class of NP-complete problems. The article compares the work of a single-threaded application and multithreaded applications using OpenMP technology, on the example of the Floyd-Warshall Algorithm for finding the shortest path. During the experiment, data on the speed of serial and parallel algorithms were obtained. It is concluded that the parallel algorithm is more efficient than the serial one. With the growth of the computational power of the algorithm, the efficiency of parallel computing increases. The experiment was carried out for calculations at different power of a set of initial data, the data are presented in the form of tables and graphs. Evaluate the effectiveness of the use of standard parallelization and OpenMP. The materials of the article are of practical importance for master's students studying the course "Computer systems", can be used to solve applied optimization problems.

1. Gergel' V. P. Parallel'nyye vychisleniya: tekhnologii i chislennyye metody: Uchebnoye posobiye v 4 tomakh \\ V. P. Gergel' i dr. N. Novgorod: Izdatel'stvo Nizhegorodskogo gosuniversiteta, - 2013. - 239 s.

2. Levitin A. V. Glava 11. Preodoleniye ogranicheniy: Metod deleniya popolam // Algoritmy. Vvedeniye v razrabotku i analiz - M .: Vil'yams, 2006. - S. 349- 353. - 576 s.

3. Lavlinskaya O. Primeneniye teorii grafov v strukturno-topologicheskom analize informatsionnykh sistem \\ O. YU. Lavlinskaya, T. V. Kurchenkova. - Nauchnyye vedomosti Belgorodskogo gosudarstvennogo universiteta. Seriya: Ekonomika. Informatika. - 2017. - № 23 (272). - S. 105-112.

4. Tomas KH. Kormen i dr. Glava 34. NP-polnota // Algoritmy: postroyeniye i analiz. - 2-ye izd. - M .: «Vil'yams», - 2006. - S. 1296.

5. . Roy, Bernard (1959). «Tranzitiv i svyaz'». C. R. Acad. Sci. Parizh (angl.) Russk. 249: 216 - 218.

6. Karpov A. Otladka i optimizatsiya mnogopotochnykh OPENMP-programm \\ RSDN Magazine. - 2008. - № 4. - S. 32-36.