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

research-article

Quantifying academic placer performance on custom designs

Authors:

Samuel I. Ward,

Charles J. Alpert,

Earl SwartzlanderAuthors Info & Claims

ISPD '11: Proceedings of the 2011 international symposium on Physical design

Pages 91 - 98

https://doi.org/10.1145/1960397.1960420

Published: 27 March 2011 Publication History

Abstract

There have been significant prior efforts to quantify performance of academic placement algorithms, primarily by creating artificial test cases that attempt to mimic real designs, such as the PEKO benchmark containing known optimas [5]. The idea was to create benchmarks with a known optimal solution and then measure how far existing placers were from the known optimal. Since the benchmarks do not necessarily correspond to properties of real VLSI netlists, the conclusions were met with some skepticism. This work presents two custom constructed datapath designs that perform common logic functions with hand-designed layouts for each. The new generation of academic placers is then compared against them to see how the placers performed for these design styles. Experiments show that all academic placers have wirelengths significantly greater then the manual solution; solutions range from 1.75 to 4.88 times greater wirelengths. These testcases will be released publically to stimulate research into automatically solving structured datapath placement problems.

References

[1]

S. N. Adya and I. L. Markov, "Consistent Placement of Macro-blocks Using Floorplanning and Standard-Cell Placement'"" ISPD 2002, pp. 12--17.

Digital Library

[2]

P.W. Bosshart and Q.D. An. Shifter circuit for an arithmetic logic unit in a microprocessor. US. patent 5896305, 1999.

[3]

T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie. mPL6: Enhanced multilevel mixed-size placement. In Proc. ISPD, pp 212--214, 2006.

Digital Library

[4]

T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, In Proc. ICCAD, 2006.

Digital Library

[5]

Chin-Chih Chang, Jason Cong, Michail Romesis, and Min Xie; Optimality and Scalability Study of Existing Placement Algorithms; IEEE Transactions on Computer-aided Design Vol.23, pp. 537--549 2004

Digital Library

[6]

R.L. Davis. Uniform shift networks. Computer, 7:327--334, September 1974.

[7]

Lars W. Hagen, Dennis J.-H. Huang, Andrew B. Kahng; Quantified Suboptimality of VLSI Layout Heuristics Design Automation, DAC pp 216--221, 1995.

Digital Library

[8]

J.L. Hennessy and D.A. Patterson. Computer Architecture: A Quantitative Approach. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 2nd edition, 1996.

Digital Library

[9]

Hillebrand, M.A.; Schurger, T.; Seidel, P.-M.; How to half wire lengths in the layout of cyclic shifters, Fourteenth International Conference on VLSI Design, 2001, pp. 339--344.

Digital Library

[10]

A. B. Kahng, S. Reda, and Q. Wang. Architecture and details of a high quality, large-scale analytical placer. In Proc. ICCAD, pp 890--897, 2005.

Digital Library

[11]

Koren. Computer Arithmetic Algorithms. Englewood Cliffs, NJ: Prentice-Hall Inc., 1993.

Digital Library

[12]

T. Machida. Bidirectional barrel shift circuit. US. Patent 4665538, 1987.

[13]

S.M. Mueller and W.J. Paul. Computer Architecture: Complexity and Correctness. Springer Verlat, 2000.

Digital Library

[14]

G.-J. Nam, "ISPD 2006 Placement Contest: Benchmark Suite and Results," ISPD 2006, p. 167.

Digital Library

[15]

G.-J. Nam, C. J. Alpert, P. G. Villarrubia, B. B. Winter, M. C. Yildiz "The ISPD2005 Placement Contest and Benchmark Suite," ISPD 2005, pp. 216--220.

Digital Library

[16]

J. A. Roy, S. N. Adya, D. A. Papa, and I. L. Markov. Min-cut floor placement. IEEE Transactions on Computer-Aided Design, Vol. 25, pp. 1313--1326, July 2006.

Digital Library

[17]

P.-M. Seidel. On the Design of IEEIT Compliant Floating-point Units and Their Quantitative Analysis. PhD thesis, University of Saarland, December 1999.

[18]

L. Sigal et al. Circuit design techniques for the high-performance CMOS IBM S/390 Parallel Enterprise Server G4 microprocessor. IBM Journal of Research and Development, Vol. 41, pp. 489--503, 1997.

Digital Library

[19]

Wern-Jieh Sun and Carl Sechen, Efficient and Effective Placement for Very Large Circuits, IEEE Transactions on Computer-Aided Design, Vol 14, pp. 349--359, 1995

Digital Library

[20]

Natarajan Viswanathan and Chris Chong-Nuen Chu, FastPlace: Efficient Analytical Placement Using Cell Shifting, Iterative Local Refinement, and a Hybrid Net Model IEEE Transactions on Computer-Aided Design, VOL. 24, pp. 722--733 2005

Digital Library

[21]

M. Wang, X. Yang, and M. Sarrafzadeh, Dragon2000: Standard-cell placement tool for large industry circuits, in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, 2000, pp. 260--263.

Digital Library

Cited By

Singh AMishra VAkhter S(2023)Investigating Machine Learning Applications for FDSOI MOS-Based Computer-Aided Design2023 9th International Conference on Signal Processing and Communication (ICSC)10.1109/ICSC60394.2023.10441540(708-713)Online publication date: 21-Dec-2023
https://doi.org/10.1109/ICSC60394.2023.10441540
Amuru DZahra AVudumula HCherupally PGurram SAhmad AAbbas Z(2023)AI/ML algorithms and applications in VLSI design and technologyIntegration, the VLSI Journal10.1016/j.vlsi.2023.06.00293:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.vlsi.2023.06.002
Lin JDeng YLi SYu BChang LPeng T(2019)Regularity-Aware Routability-Driven Macro Placement Methodology for Mixed-Size Circuits With ObstaclesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2018.286783327:1(57-68)Online publication date: Jan-2019
https://doi.org/10.1109/TVLSI.2018.2867833
Show More Cited By

Index Terms

Quantifying academic placer performance on custom designs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

An efficient placement method for large standard-cell and sea-of-gates designs
EURO-DAC '90: Proceedings of the conference on European design automation

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 ...
Placement Flow Study and Detailed Placement for Hybrid-Row-Height Designs
At the 3 nm node, a hybrid-row-height design paradigm has emerged for better power efficiency and performance optimization. A diverse cell library that includes multiple variants of a cell with different fin counts is available. Instead of using cells ...
Implementation and extensibility of an analytic placer

Automated cell placement is a critical problem in very large scale integration (VLSI) physical design. New analytical placement methods that simultaneously spread cells and optimize wirelength have recently received much attention from both academia and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '11: Proceedings of the 2011 international symposium on Physical design

March 2011

192 pages

ISBN:9781450305501

DOI:10.1145/1960397

General Chair:
Yao-Wen Chang
National Taiwan University
,
Program Chair:
Jiang Hu
Texas A&M University

Copyright © 2011 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

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISPD'11

Sponsor:

SIGDA

ISPD'11: International Symposium on Physical Design

March 27 - 30, 2011

CA, Santa Barbara, 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

17
Total Citations
View Citations
227
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh AMishra VAkhter S(2023)Investigating Machine Learning Applications for FDSOI MOS-Based Computer-Aided Design2023 9th International Conference on Signal Processing and Communication (ICSC)10.1109/ICSC60394.2023.10441540(708-713)Online publication date: 21-Dec-2023
https://doi.org/10.1109/ICSC60394.2023.10441540
Amuru DZahra AVudumula HCherupally PGurram SAhmad AAbbas Z(2023)AI/ML algorithms and applications in VLSI design and technologyIntegration, the VLSI Journal10.1016/j.vlsi.2023.06.00293:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.vlsi.2023.06.002
Lin JDeng YLi SYu BChang LPeng T(2019)Regularity-Aware Routability-Driven Macro Placement Methodology for Mixed-Size Circuits With ObstaclesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2018.286783327:1(57-68)Online publication date: Jan-2019
https://doi.org/10.1109/TVLSI.2018.2867833
Wang YYeo DShin H(2019)Effective datapath logic extraction techniques using connection vectorsIET Circuits, Devices & Systems10.1049/iet-cds.2018.508313:6(741-747)Online publication date: 31-Jul-2019
https://doi.org/10.1049/iet-cds.2018.5083
Lin YPan D(2019)Machine Learning in Physical Verification, Mask Synthesis, and Physical DesignMachine Learning in VLSI Computer-Aided Design10.1007/978-3-030-04666-8_4(95-115)Online publication date: 16-Mar-2019
https://doi.org/10.1007/978-3-030-04666-8_4
Lin JYu BChang L(2017)Regularity-aware routability-driven placement prototyping algorithm for hierarchical mixed-size circuits2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2017.7858362(438-443)Online publication date: Jan-2017
https://doi.org/10.1109/ASPDAC.2017.7858362
Wang YShin H(2017)Effective regularity extraction and placement techniques for datapath‐intensive circuitsIET Circuits, Devices & Systems10.1049/iet-cds.2016.024911:5(512-519)Online publication date: 31-Jul-2017
https://doi.org/10.1049/iet-cds.2016.0249
Bae SKim HChoi JPark JDavoodi AYoung E(2015)Coarse-grained Structural Placement for a Synthesized Parallel MultiplierProceedings of the 2015 Symposium on International Symposium on Physical Design10.1145/2717764.2717775(17-24)Online publication date: 29-Mar-2015
https://dl.acm.org/doi/10.1145/2717764.2717775
Chatterjee SSaun VArunachalam A(2015)A Methodology for Placement of Regular and Structured Circuits2015 28th International Conference on VLSI Design10.1109/VLSID.2015.90(499-504)Online publication date: Jan-2015
https://doi.org/10.1109/VLSID.2015.90
Yu BPan DMatsunawa TZeng X(2015)Machine learning and pattern matching in physical designThe 20th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2015.7059020(286-293)Online publication date: Jan-2015
https://doi.org/10.1109/ASPDAC.2015.7059020
Show More Cited By

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