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 条

[11]

Huang T, 2011, DES AUT CON, P164

[12]

Li LY, 2008, POLYOLEFIN COMPOSITES, P523, DOI 10.1109/ICCAD.2008.4681625

[13]

Lin Chung-Wei, 2007, P ISPD

[14]

Liu CH, 2009, DES AUT CON, P314

[15] EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithm [J].

Long, Jieyi ;

Zhou, Hai ;

Memik, Seda Ogrenci .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2008, 27 (12) :2169-2182

[16] Efficient Rectilinear Steiner Tree construction with Rectilinear Blockages [J].

Shen, Z ;

Chu, CCN ;

Li, YM .

2005 IEEE INTERNATIONAL CONFERENCE ON COMPUTER DESIGN: VLSI IN COMPUTERS & PROCESSORS, PROCEEDINGS, 2005, :38-44

[17]

SHI Y, 2006, P ASP DAC

[18]

Wu PC, 2007, ASIA S PACIF DES AUT, P262

[19] RECTILINEAR SHORTEST PATHS AND MINIMUM SPANNING-TREES IN THE PRESENCE OF RECTILINEAR OBSTACLES [J].

WU, YF ;

WIDMAYER, P ;

SCHLAG, MDF ;

WONG, CK .

IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (03) :321-331

[20] Rectilinear Steiner minimal tree among obstacles [J].

Yang, Y ;

Zhu, Q ;

Jing, T ;

Hong, XL ;

Wang, Y .

2003 5TH INTERNATIONAL CONFERENCE ON ASIC, VOLS 1 AND 2, PROCEEDINGS, 2003, :348-351

← 1 2 3 →