A theoretical study on wire length estimation algorithms for placement with opaque blocks

被引：0

作者：

Yan, Tan ^{[1
]}

Li, Shuting ^{[1
]}

Takashima, Yasuhiro ^{[1
]}

Murata, Hiroshi ^{[1
]}

机构：

[1] Univ Kitakyushu, Grad Sch Environm Engn, 1-1 Hibikino, Kitakyushu, Fukuoka 8080135, Japan

来源：

PROCEEDINGS OF THE ASP-DAC 2007 | 2007年

关键词：

D O I：

暂无

中图分类号：

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

学科分类号：

0812 ;

摘要：

How to estimate the shortest routing length when certain blocks are considered as routing obstacles is becoming an essential problem for block placement because HPWL is no longer valid in this case. Although this problem is well studied in computational geometry [6], the research results are neither well-known to the CAD community nor presented in a way easy for CAD researchers to ultilize their establishment. With the help of some recent notions in block placement, this paper interprets the research result in [1,8], which gives the best algorithm for this problem as we know, in a way more concise and more friendly to CAD researchers. Besides, we also tailor its algorithm to VLSI CAD application. As the result, we present a method that estimates the shortest obstacle-avoiding routing length in O(M-2 + N) time for a placement with M blocks and N 2-pin nets.

引用

页码：268 / +

页数：2

共 10 条

[1] Atallah M. J., 1991, Computational Geometry: Theory and Applications, V1, P79, DOI 10.1016/0925-7721(91)90002-V
[2] CHAN HH, 2005, ISPD 05, P129
[3] Chang YC, 2000, DES AUT CON, P458
[4] CHENG CK, 2001, ASPDAC 01, P527
[5] De Rezende P.J., 1985, SCG 85, P204, DOI DOI 10.1145/323233.323260
[6] KODAMA C, 2004, ISCAS 04, P329
[7] Mitchell JSB, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P633, DOI 10.1016/B978-044482537-7/50016-4
[8] VLSI module placement based on rectangle-packing by the sequence-pair
Murata, H
Fujiyoshi, K
Nakatake, S
Kajitani, Y
[J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1996, 15 (12) : 1518 - 1524
[9] Sherwani NA, 1999, ALGORITHMS VLSI PHYS
[10] Space-planning: placement of modules with controlled empty area by Single-Sequence
Zhang, XL
Kajitani, Y
[J]. ASP-DAC 2004: PROCEEDINGS OF THE ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE, 2004, : 25 - 30

← 1 →