More Web Proxy on the site http://driver.im/

Article

A study of netlist structure and placement efficiency

Authors:

Malgorzata Marek-SadowskaAuthors Info & Claims

ISPD '04: Proceedings of the 2004 international symposium on Physical design

Pages 198 - 203

https://doi.org/10.1145/981066.981109

Published: 18 April 2004 Publication History

Abstract

In this paper, we study the relationship between netlist structure and the efficiency of placers measured in terms of quality and stability of results. We analyze three types of placers: analytic, simulated-annealing-based and partition-based. We test the placers on industrial and synthetic benchmarks. Based on the observations and analyses of experimental results, we obtain several useful conclusions about relationships between netlist structure and placement efficiency of different types of placers.

References

[1]

S.N.Adya, M.C.Yildiz, I.L.Markov, P.G.Villarrubia, P.N.Parakh and P.H.Madden, "Benchmarking for Large-scale Placement and Beyond", in Proc. Intl. Symp. on Physical Design, pp.95--103, 2003.

Digital Library

[2]

C.J.Alpert, J.H.Huang and A.B.Kahng, "Multi-level Circuit Partitioning", Design Automation Conference, pp.530-533, 1997.

Digital Library

[3]

A.E.Caldwell, A.B.Kahng and I.L.Markov, "Improved Algorithms for Hypergraph Bisection", ASP-DAC, pp.661--666, 2000.

Digital Library

[4]

A.E.Caldwell, A.B.Kahng and I.L.Markov, "Can Recursive Bisection alone Produce Routable Placements", Design Automation Conference, pp.260--263, 2000.

Digital Library

[5]

A.E.Caldwell, A.B.Kahng and I.L.Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", IEEE Transactions on Computer Aided Design, vol.19, no.11, pp.1304--1314, 2000.

Digital Library

[6]

T. F. Chan, J. Cong, T. Kong and J. Shinnerl, "Multilevel Optimization for Large-scale Circuit Placement", Proc. of Int. Conf. on Computer-Aided Design, pp. 171--176, 2000.

Digital Library

[7]

T. F. Chan, J. Cong, J. Shinnerl and K. Sze, "An Enhanced Multilevel Algorithm for Circuit Placement", Proc. of Int. Conf. on Computer-Aided Design, pp. 299--306, November 2003.

Digital Library

[8]

C.C. Chang, J. Cong and M. Xie, "Optimality and Scalability Study of Existing Placement Algorithms", ASP-DAC, pp.621--627, 2003.

Digital Library

[9]

J. Cong, M. Romesis and M. Xie, "Optimality and Scalability Study of Partitioning and Placement Algorithms", In Proc. Intl. Symp. on Physical Design, pp.88--94, Apr 2003.

Digital Library

[10]

H. Eisenmann and F.M. Johannes, "Generic Global Placement and Floorplanning", Design Automation Conference, pp.269--274, 1998.

Digital Library

[11]

C.M. Fiduccia and R.M. Mattheyses, "A Linear Time Heuristic for Improve Network Partitions", Design Automation Conference, pp.175--181, 1982.

Digital Library

[12]

B. Hu and M. Marek-Sadowska, "Fine-granularity Clustering for Large-scale Placement Problems", In Proc. Intl. Symp. on Physical Design, pp.67--74, Apr 2003.

Digital Library

[13]

G. Karypis, R. Aggarwal, V. Kurnar and S. Shekhar, "Multi-level Hypergraph Partition: Applications in VLSI Design", Design Automation Conference, pp.526--529, 1997.

Digital Library

[14]

P. Kudva, A. Sullivan and W. Dougherty, "Metrics for Structural Logic Synthesis", Proc. of Int. Conf. on Computer-Aided Design, pp. 551--556, 2002.

Digital Library

[15]

T. Kutzschebauch and L. Stok, "Congestion Aware Layout Driven Logic Synthesis", Proc. of Int. Conf. on Computer-Aided Design, pp. 216--223, 2001.

Digital Library

[16]

M. Pedram and N. Bhat, "Layout Driven Technology Mapping", In Design Automation Conference, pp. 99--105, 1991.

Digital Library

[17]

M. Pedram and N. Bhat, "Layout Driven Logic Restructure/Decomposition", Proc. of Int. Conf. on Computer-Aided Design, pp. 134--137, 1991.

[18]

M. Sarrafzadeh and M. Wang, "NRG: Global and Detailed Placement". Proc. of Int. Conf. on Computer-Aided Design, pp. 164--169, 1997.

Digital Library

[19]

D. Stroobandt, P. Verplaetse and J. Van Campenhout, "Generating Synthetic Benchmark Circuits for Evaluating CAD Tools", IEEE Transactions on Computer Aided Design,vol.19, no.9, 2000.

Digital Library

[20]

R. Tsai, E.S. Kuh and C. Hsu, "PROUD: A Sea-of-gates Placement Algorithm", IEEE Design&Test of Computers, pp.44--56, 1988.

Digital Library

[21]

M. Wang, X. Yang and M. Sarrafzadeh, "Dragon2000: Standard-cell Placement Tool for Large Industry Circuits", Proc. of Int. Conf. on Computer-Aided Design, pp. 260--264, 2000.

Digital Library

[22]

X. Yang, B.K. Choi and M. Sarrafzadeh, "Routability Driven White Space Allocation for Fixed-Die Standard-Cell Placement", In Proc. Intl. Symp. on Physical Design, pp.42--47, Apr 2002.

Digital Library

[23]

VLSI CAD Bookshelf: http://www.gigascale.org/bookshelf/

[24]

Gnl Version 1.1.1: http://www.elis.ugent.be/~pvrplaet/gnl/

Cited By

Pedram MSze CDavoodi A(2014)Interconnect length estimation in VLSI designsProceedings of the 2014 on International symposium on physical design10.1145/2560519.2568053(127-128)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2568053
Bian HLing AChoong AZhu JCheung PWawrzynek J(2010)Towards scalable placement for FPGAsProceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1723112.1723140(147-156)Online publication date: 21-Feb-2010
https://dl.acm.org/doi/10.1145/1723112.1723140
Li JBehjat LHuang JMadden PPan D(2007)An effective clustering algorithm for mixed-size placementProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232020(111-118)Online publication date: 18-Mar-2007
https://dl.acm.org/doi/10.1145/1231996.1232020
Show More Cited By

Index Terms

A study of netlist structure and placement efficiency
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design

Recommendations

A study of netlist structure and placement efficiency

In this paper, we examine the relationship between netlist structure and the efficiency of placers measured in terms of quality and stability of results. We analyze three types of placers: analytic, simulated-annealing based, and partition based. We ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Routability-driven placement for hierarchical mixed-size circuit designs
DAC '13: Proceedings of the 50th Annual Design Automation Conference

A wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '04: Proceedings of the 2004 international symposium on Physical design

April 2004

226 pages

ISBN:1581138172

DOI:10.1145/981066

General Chair:
Charles J. Alpert,
IBM
,
Program Chair:
Patrick Groeneveld
Eindhoven University

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 April 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD04

Sponsor:

ISPD04: International Symposium on Physical Design 2004

April 18 - 21, 2004

Arizona, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
162
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pedram MSze CDavoodi A(2014)Interconnect length estimation in VLSI designsProceedings of the 2014 on International symposium on physical design10.1145/2560519.2568053(127-128)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2568053
Bian HLing AChoong AZhu JCheung PWawrzynek J(2010)Towards scalable placement for FPGAsProceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1723112.1723140(147-156)Online publication date: 21-Feb-2010
https://dl.acm.org/doi/10.1145/1723112.1723140
Li JBehjat LHuang JMadden PPan D(2007)An effective clustering algorithm for mixed-size placementProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232020(111-118)Online publication date: 18-Mar-2007
https://dl.acm.org/doi/10.1145/1231996.1232020
Wan TChrzanowska-Jeske M(2007)A novel net-degree distribution model and its application to floorplanning benchmark generationIntegration, the VLSI Journal10.1016/j.vlsi.2006.09.00140:4(420-433)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1016/j.vlsi.2006.09.001
Cong JRomesis MShinnerl JSze KXie M(2007)Locality and Utilization in Placement SuboptimalityModern Circuit Placement10.1007/978-0-387-68739-1_2(13-36)Online publication date: 2007
https://doi.org/10.1007/978-0-387-68739-1_2
Kahng AReda S(2006)Zero-Change Netlist Transformations: A New Technique for Placement BenchmarkingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.88247325:12(2806-2819)Online publication date: Dec-2006
https://doi.org/10.1109/TCAD.2006.882473
Liu QMarek-Sadowska M(2006)Semi-individual wire-length prediction with application to logic synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85948725:4(611-624)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.859487
Kahng AReda S(2005)Intrinsic shortest path lengthProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129627(173-180)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129627
Kahng AReda SGroeneveld PScheffer L(2005)Evaluation of placer suboptimality via zero-change netlist transformationsProceedings of the 2005 international symposium on Physical design10.1145/1055137.1055180(208-215)Online publication date: 3-Apr-2005
https://dl.acm.org/doi/10.1145/1055137.1055180
Kahng AReda S(2005)Intrinsic shortest path length: a new, accurate a priori wirelength estimatorICCAD-2005. IEEE/ACM International Conference on Computer-Aided Design, 2005.10.1109/ICCAD.2005.1560059(173-180)Online publication date: 2005
https://doi.org/10.1109/ICCAD.2005.1560059

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents