Актуальность исследования обусловлена необходимостью решения задач распараллеливания вычислений для класса NP-полных задач, поскольку вычислительные мощности позволяют использовать параллельные потоки и снижать время вычислений и энергозатраты на получение сложного вычислительного результата с помощью программных технологий распараллеливания вычислений. В связи с этим, данная статья направлена на опубликование результатов исследования, основанных на анализе эмпирических данных, доказывающем эффективность параллельных вычислений для класса NP-полных задач. В статье проводится сравнение работы однопоточного приложения и многопоточного приложений, использующего технологию OpenMP, на примере алгоритма Флойда-Уоршалла поиска кратчайшего пути. В ходе эксперимента получены данные о скорости выполнения последовательного и параллельного алгоритмов. Сделаны выводы о том, что параллельный алгоритм эффективнее последовательного. При росте вычислительной мощности алгоритма эффективность параллельных вычислений возрастает. Эксперимент проводился для вычислений при разной мощности набора исходных данных, данные представлены в виде таблиц и графиков. Дана оценка эффективности применения стандарта распараллеливания OpenMP. Материалы статьи представляют практическую значимость для студентов магистратуры, изучающих курс «Вычислительные системы», могут быть использованы для решения прикладных задач оптимизации.
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.
The authors declare that there are no conflicts of interest present.