Research On A GPU Accelerated High Efficiency Algorithm For Directed Steiner Tree Problem

The directed Steiner tree problem is formulated as follows: Given a directed graph G=(V, A) and a specified root Vr ?, and a set of terminals X ? V(|X|=k), the goal is to find the minimum cost tree rooted at r and spanning all the v ertices in X. Many problems in various areas can be abstracted into directed Steiner tree problem. VLSI routing, wire-length estimation and quality-of-service routing in networking all can be modeled as directed Steiner tree problem. Therefore, solving the directed Steiner tree problem is of great importance. The Steiner tree problem is proved NP-complete for general graphs, hence the mainstream of the research are focused on approximation algorithms.This dissertation provides a High Efficiency algorithm(HEA) that has time complexity of O(k2n3), and achieves 2k-? approximation ratio. This dissertation improves TM algorithm, and amends it's time complexity under directed graph. The time complexity of the improved TM algorithm is O(kn). And then this dissertation modifies the subtree connection method of Charikar algorithm, which reduces the error ratio of Charikar algorithm in low level circumstance. Experimental results shows that the HEA algorithm out performs many traditional directed Steiner tree algorithms in experimental results.We also apply some GPU parallel computing technology into this algorithm in order to accelerate it further more. First this dissertation brings up a parallel binary-heap APSP(all pairs shortest paths) algorithm. This algorithm calculates the shortest path for each node on graph in multi-threads. Then this dissertation proposes a parallel 2-level tree construction algorithm which can calculate 2-level Steiner trees for all of the initial trees at one time. Experimental results proves that algorithms are effective.Comparing with a high accuracy algorithm Hsieh algorithm, HEA achieves at least 25 times acceleration without loss of accuracy. After GPU parallel computing is applied, the Shortest Path part of HEA achieves 10 to 40 times acceleration and parallel 2-level tree construction algorithm achieves 1.23 to 7.88 times acceleration further more.