title: Ð Ð°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¿Ð°ÑÐ°Ð»Ð»ÐµÐ»ÑÐ½Ð¾Ð³Ð¾ Ð¿ÑÐ¸Ð±Ð»Ð¸Ð¶ÐµÐ½Ð½Ð¾Ð³Ð¾ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° Ð¿Ð¾Ð¸ÑÐºÐ° Ð´ÐµÑÐµÐ²Ð° Ð¨ÑÐµÐ¹Ð½ÐµÑÐ° Ð½Ð° GPU
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¼Ð°Ð³Ð¸ÑÑÑÐ°
titleType: Subtitle
title: Development of a parallel GPU-based approximate algorithm for finding a Steiner tree
Creators: name: Ð§ÐµÑÐ½Ð¾Ð²Ð°, ÐÐµÑÐ¾Ð½Ð¸ÐºÐ°
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2021
Subjects: ÐÐ»Ð³Ð¾ÑÐ¸ÑÐ¼Ñ
ÐÐ°ÑÑÑÑÑÐ¸Ð·Ð°ÑÐ¾ÑÑ
Ð´ÐµÑÐµÐ²Ð¾ Ð¨ÑÐµÐ¹Ð½ÐµÑÐ°
Steiner tree

description: ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ Ð½Ð° 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%.
description: 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%.