Fractional cut: Improved recursive bisection placement

被引：50

作者：

Agnihotri, A ^{[1
]}

Yildiz, MC ^{[1
]}

Khatkhate, A ^{[1
]}

Mathur, A ^{[1
]}

Ono, S ^{[1
]}

Madden, PH ^{[1
]}

机构：

[1] SUNY Binghamton, Dept Comp Sci, Binghamton, NY 13902 USA

来源：

ICCAD-2003: IEEE/ACM DIGEST OF TECHNICAL PAPERS | 2003年

关键词：

D O I：

10.1109/ICCAD.2003.1257685

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this paper, we present improvements to recursive bisection based placement. In contrast to prior work, our horizontal cut lines are not restricted to row boundaries; this avoids a "narrow region" problem. To support these new cut line positions, a dynamic programming based legalization algorithm has been developed. The combination of these has improved the stability and lowered the wire lengths produced by our Feng Shui placement tool. On benchmarks derived from industry partitioning examples, our results are close to those of the annealing based tool Dragon, while taking only a fraction of the run time. On synthetic benchmarks, our wire lengths are nearly 23% better than those of Dragon. For both benchmark suites, our results are substantially better than those of the recursive bisection based tool Capo and the analytic placement tool Kraftwerk.

引用

页码：307 / 310

页数：4

共 18 条

[1]

Adya S.N., 2003, Proc. ACM/IEEE International Symposium on Physical Design, P95

[2]

Caldwell A. E., 2000, Proceedings ASP-DAC 2000. Asia and South Pacific Design Automation Conference 2000 with EDA TechnoFair 2000. (Cat. No.00EX389), P661, DOI 10.1109/ASPDAC.2000.835182

[3]

Caldwell AE, 2000, DES AUT CON, P477

[4] Optimal partitioners and end-case placers for standard-cell layout [J].

Caldwell, AE ;

Kahng, AB ;

Markov, IL .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2000, 19 (11) :1304-1313

[5]

Cormen T. H., 1990, INTRO ALGORITHMS

[6] A PROCEDURE FOR PLACEMENT OF STANDARD-CELL VLSI CIRCUITS [J].

DUNLOP, AE ;

KERNIGHAN, BW .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1985, 4 (01) :92-98

[7]

Eisenmann H, 1998, 1998 DESIGN AUTOMATION CONFERENCE, PROCEEDINGS, P269, DOI 10.1109/DAC.1998.724480

[8]

Karypis G, 1997, DES AUT CON, P526, DOI 10.1145/266021.266273

[9] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[10] A THEORY OF STRATEGIC CULTURE [J].

KLEIN, Y .

COMPARATIVE STRATEGY, 1991, 10 (01) :3-23

← 1 2 →