GPU-ACCELERATED VLSI ROUTING USING GROUP STEINER TREES

Volume 8, Issue 1 (February 2017), pp. 16–19

Download PDF

@article{jocse-8-1-4,
  author={Venkata Suhas Maringanti and Basileal Imana and Peter Yoon},
  title={GPU-ACCELERATED VLSI ROUTING USING GROUP STEINER TREES},
  journal={The Journal of Computational Science Education},
  year=2017,
  month=feb,
  volume=8,
  issue=1,
  pages={16--19},
  doi={https://doi.org/10.22369/issn.2153-4136/8/1/4}
}

The problem of interconnecting nets with multi-port terminals in VLSI circuits is a direct generalization of the Group Steiner Problem (GSP). The GSP is a combinatorial optimization problem which arises in the routing phase of VLSI circuit design. This problem has been intractable, making it impractical to be used in real-world VLSI applications. This paper presents our work on designing and implementing a parallel approximation algorithm for the GSP based off an existing heuristic on a distributed architecture. Our implementation uses the CUDA-aware MPI approach to compute the approximate minimum-cost Group Steiner tree for several industry-standard VLSI graphs. Our implementation achieves up to 103x speedup compared to the best known serial work for the same graph. We present the speedup results for graphs up to 3k vertices. We also investigate some performance bottleneck issues by analyzing and interpreting the program performance data.