Данная работа посвящена реализации на GPU и оптимизации одного из алгоритмов поиска дерева Штейнера, а именно алгоритма KMB. Алгоритм KMB существует в двух вариантах, первый (оригинальный) предназначен для работы на неориентированных графах, а второй - на ориентированных. Неориентированный KMB имеет вычислительную сложность O(|V|^2+|E|) с учетом существующей оптимизации, а ориентированный - O(|T||V|^2). В данной работе неориентированный KMB был эффективно распараллелен и реализован на GPU, а для его ориентированного варианта была разработана оптимизация, снижающая его вычислительную сложность до O(|V|^2+|E|). В данной работе представлена оценка производительности трех реализованных программ: неориентированного KMB, ориентированного KMB и неориентированного KMB на GPU. Результаты показали, что программа на GPU начинает выигрывать в производительности на графах с 60 000 ребрами и более. Также, было произведено сравнение практических точностей неориентированного и ориентированного алгоритмов KMB. При сравнении на графах от 50 до 2500 вершин оказалось, что в среднем их точности примерно равны. Среднее отличие приближенного дерева Штейнера от оптимального решения для неориентированного KMB составило 10,2%, а для ориентированного KMB – 10,1%.

This work dedicated to the development of GPU-based KMB algorithm that finds an approximate Steiner tree on undirected graphs. Moreover, this work proposes an optimization for directed version of KMB algorithm. Undirected KMB have time complexity of O(|V|^2+|E|) with optimization, while directed KMB have time complexity of O(|T||V|^2). The optimization that is proposed in this work make time complexity for directed KMB of O(|V|^2+|E|). This paper presents an assessment of the performance of three implemented programs: undirected KMB, directed KMB and undirected GPU-based KMB. Experiments have shown that GPU-based KMB have better performance than other two programs on graphs with 60 000 edges and more. Moreover, in this work was produced a comparison of accuracy for directed and undirected KMB by experiments. Experiments was conducted on graphs with number of vertices from 50 to 2500. It shown that accuracy of directed and undirected KMB approximately equal. Average difference of given solution from optimal solution for undirected KMB is 10,2%, and for directed KMB is 10,1%.