Научный журнал Моделирование, оптимизация и информационные технологииThe scientific journal Modeling, Optimization and Information Technology
cетевое издание
issn 2310-6018

OPENMP PARALLEL CALCULATIONS IN ALGORITHMS FOR SOLVING SHORTEST PATHS PROBLEM

Lavlinskaya O.Y.   Bernikov V.V.   Grigorova O.N.  

UDC 681.3
DOI: 10.26102/2310-6018/2019.25.2.004

  • Abstract
  • List of references
  • About authors

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.

Lavlinskaya Oksana Yuryevna
Candidate of Technical Sciences Associate Professor
Email: lavlin2010@yandex.ru

Voronezh Institute of High Technologies

Voronezh, Russian Federation

Bernikov Vladislav Valeryevich

Email: vladislavbernikov@gmail.com

Voronezh Institute of High Technologies

Voronezh, Russian Federation

Grigorova Olga Nikolaevna
Candidate of Economic Sciences Associate Professor
Email: grigorova@mail.ru

Voronezh Institute of High Technologies

Voronezh, Russian Federation

Keywords: openmp, parallelization, search of ways, floyd-warshall algorithm

For citation: Lavlinskaya O.Y. Bernikov V.V. Grigorova O.N. OPENMP PARALLEL CALCULATIONS IN ALGORITHMS FOR SOLVING SHORTEST PATHS PROBLEM. Modeling, Optimization and Information Technology. 2019;7(2). Available from: https://moit.vivt.ru/wp-content/uploads/2019/05/LavlinskayaSoavtori_2_19_1.pdf DOI: 10.26102/2310-6018/2019.25.2.004 (In Russ).

143

Full text in PDF