Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach

被引：19

作者：

Chow, Wing-Kai ^{[1
]}

Li, Liang ^{[1
]}

Young, Evangeline F. Y. ^{[1
]}

Sham, Chiu-Wing ^{[2
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China

[2] Hong Kong Polytech Univ, Dept Elect & Informat Engn, Hong Kong, Hong Kong, Peoples R China

来源：

INTEGRATION-THE VLSI JOURNAL | 2014年 / 47卷 / 01期

关键词：

Obstacle-avoiding maze routing; GPU; Parallel computing; ALGORITHM;

D O I：

10.1016/j.vlsi.2013.08.001

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Rectilinear Steiner Minimum Tree (RSMT) problem is a fundamental one in VLSI physical design. In this paper, we present a maze routing based heuristics to solve the obstacle-avoiding RSMT (OARSMT) problem. Our approach can handle multi-pin nets in good quality and reasonable running time. We also present an implementation of the heuristics in parallel approach with the aid of graphic processing units (GPU). The parallel algorithm is implemented by using CUDA and has been tested on a NVIDIA graphic card. Our experimental results show that our parallel algorithm has promising speedups over our sequential approach. This work demonstrates that we can apply a parallel algorithm to solve the OARSMT problem with the aid of GPU. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：105 / 114

页数：10

共 23 条

[1]

Ajwani G., 2010, Proc. Int. Symp. Phys. Des, P27

[2]

Chih-Hung Liu, 2009, Proceedings of the 2009 IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), P26

[3]

Clarkson K., 1987, P 3 ANN ACM S COMP G, P251, DOI DOI 10.1145/41958.41985

[4]

Feng Z., 2006, Proc. Int. Symp. Phys. Des, P48

[5]

Ganley J. L., 1994, 1994 IEEE International Symposium on Circuits and Systems (Cat. No.94CH3435-5), P113, DOI 10.1109/ISCAS.1994.408768

[6] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834

[7]

Han Y., 2011, 12th International Symposium on Quality Electronic Design, Santa Clara, CA, P1, DOI DOI 10.1109/ISQED.2011.5770735

[8]

Hentschke R., 2007, P ISPD

[9]

Hu Y., 2004, Journal of Information and Computational Science, P107, DOI DOI 10.31274/ETD-180810-2776

[10]

Hu Y, 2005, ASIA S PACIF DES AUT, P7

← 1 2 3 →