Article

Free access

An efficient placement method for large standard-cell and sea-of-gates designs

Authors:

H. J. Kappen,

F. M. J. de BontAuthors Info & Claims

EURO-DAC '90: Proceedings of the conference on European design automation

Pages 312 - 316

Published: 12 March 1990 Publication History

PDF eReader

Abstract

A fast placement algorithm is presented for large Standard-Cell and Sea-of-Gates placement problems. The time complexity of the algorithm is O (n log²n). In comparison with a state of the art conventional placement and routing tool it yields more than 10 % smaller layouts with significantly better timing characteristics. The method underlying this algorithm uses a quadratic cost function of the wire length and has a wider applicability than existing methods. We expect that with this algorithm high quality placements upto 100000 cells can be obtained.

References

[1]

S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, "Optimization by Simulated Annealing", Science Vol. 220 (1983) 671.

Crossref

Google Scholar

[2]

C-K. Cheng and E. S. Kuh, "Module Placement Based on Resistive Network Optimization", IEEE Trans. Computer-Aided Design, Vol. CAD-3, No. 3, (1984) 218--225.

Google Scholar

[3]

R-S. Tsay and E. Kuh, "A Unified Approach to Circuit Partitioning and Placement", Proc. Princeton Conf. Information Sciences and Systems, (1986) 155--160.

Google Scholar

[4]

H. J. Kappen. "An efficient heuristic for Standard-Cell Placement" submitted to Integration.

Digital Library

Google Scholar

[5]

M. R. Garey and D. S. Johnson, "Computers and Intractability. A guide to the Theory of NP-Completeness". W. H. Freeman and Company, New York 1979.

Digital Library

Google Scholar

[6]

R. S. Tsay, E. S. Kuh and C. P Hsu, "Proud: a Sea-of-Gates placement algorithm", IEEE Design & Test of Computers, (1988)44.

Digital Library

Google Scholar

[7]

Nag Fortran Library, The Numerical Algorithms Group Ltd, Oxford, UK.

Google Scholar

[8]

A. E. Dunlop and B. W. Kernighan, "A procedure for placement of Standard-Cell VLSI circuits", IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 1, (1985).

Google Scholar

[9]

LASO2, A set of Fortran IV subroutines for computing a few eigenvalues and eignvectors of a large (sparse) symmetric matrix. Author D. S. Scott. Source available by sending message 'send index' to anl-mcs. ARPA!netlibd.

Google Scholar

[10]

P. de Wilde (ed.), "The Integrated Design Book", Delft University Press (1986) 7.55--7.147. J. A. G. Jess et. al., "A Gate-Array Design System adapted to many technologies", Proc. ICCAD, (1984) 338--343.

Google Scholar

An efficient placement method for large standard-cell and sea-of-gates designs
1. Networks
  1. Network algorithms

Recommendations

An efficient heuristic for standard-cell placement

A new method is presented for optimization of the one and two-dimensional quadratic assignment problem. The method is suitable for placement problems as they appear in sea-of-gates and standard-cell layout styles for VLSI design. The method is based on ...
Consistent placement of macro-blocks using floorplanning and standard-cell placement
ISPD '02: Proceedings of the 2002 international symposium on Physical design

While a number of recent works address large-scale standard-cell placement, they typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. ...
Multilevel generalized force-directed method for circuit placement
ISPD '05: Proceedings of the 2005 international symposium on Physical design

Automatic circuit placement has received renewed interest recently given the rapid increase of circuit complexity, increase of interconnect delay, and potential sub-optimality of existing placement algorithms [13]. In this paper we present a generalized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EURO-DAC '90: Proceedings of the conference on European design automation

March 1990

659 pages

ISBN:0818620242

General Chair:
Gordon Adshead
ICL, Manchester, UK
,
Program Chair:
Jochen Jess
Eindhoven University of Technology, Eindhoven, The Netherlands

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 12 March 1990

Check for updates

Author Tags

Qualifiers

Article

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
113
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Recommendations

An efficient heuristic for standard-cell placement

Consistent placement of macro-blocks using floorplanning and standard-cell placement

Multilevel generalized force-directed method for circuit placement