Article

NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs

Authors:

Tung-Chieh Chen,

Tien-Chang Hsu,

Zhe-Wei Jiang,

Yao-Wen ChangAuthors Info & Claims

ISPD '05: Proceedings of the 2005 international symposium on Physical design

Pages 236 - 238

https://doi.org/10.1145/1055137.1055188

Published: 03 April 2005 Publication History

Get Access

Abstract

In this paper, we present a hierarchical ratio partitioning based placement algorithm for large-scale mixed-size designs. The placement algorithm consists of three steps: global placement, legalization,and detailed placement; it works in a hierarchical manner and integrates net-weighting partitioning, whitespace management, look-ahead bipartitioning, and fast legalization to handle the large-scale mixed-size placement problems. Unlike the traditional partitioning-based technique that is based on balanced partitioning, we apply ratio partitioning in each level. Further, applying the look-ahead bipartitioning technique in each level, we can evaluate the feasibility of the placement for sub-partitions more accurately. Therefore, we can find better ratios for the partitions, leading to easier legalization for the global placement result and finally a better detailed placement solution. Experimental results show the efficiency and effectiveness of our algorithm.

References

[1]

Placement Utilities, http://vlsicad.eecs.umich.edu/BK/PlaceUtils/.

Google Scholar

[2]

S. N. Adya, I. L. Markov, and P. G. Villarrubia. On whitespace and stability in mixed-size placement and physical synthesis. Proc. of ICCAD, pages 311--318, 2003.

Digital Library

Google Scholar

[3]

A. Agnihotri, M.C. YILDIZ, A. Khatkhate, A. Mathur, S. Ono, and P. H. Madden. Fractional cut: Improved recursive bisection placement. Proc. of ICCAD, pages 307--310, 2003.

Digital Library

Google Scholar

[4]

A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection alone produce routable standard-cell layout. Proc.of DAC, pages 477--482, 2000.

Digital Library

Google Scholar

[5]

C.-C. Chang, J. Cong, and X. Yuan. Multi-level placement for large-scale mixed-size ic designs. Proc. of ASPDAC, 2003.

Digital Library

Google Scholar

[6]

J. Cong and J. R. Shinnerl. Multielevel Optimization in VLSI/CAD. Kluwer Academic Publisher, 2003.

Google Scholar

[7]

J. Cong and J. Xu. Fast floorplanning by look-ahead enable recursive bipartitioning. Proc. of ASPDAC, 2005.

Digital Library

Google Scholar

[8]

H. Eisenmann and F. M. Johannes. Multielevel optimization in vlsi/cad. Proc.of DAC, pages 269--274, 1998.

Digital Library

Google Scholar

[9]

A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. Proc. of ISPD, pages 18--25, 2003.

Digital Library

Google Scholar

[10]

A. B. Kahng and Q. Wang. An analytic placer for mixed-size placement and timing-driven placement. Proc. of ICCAD, pages 565--572, 2004.

Digital Library

Google Scholar

[11]

A. Khatkhate, C. Li, A.R. Agnihotri, M.C. Yildiz, S. Ono, C.-K. Koh, and P. H. Madden. Recursive bisection based mixed block placement. Proc. of ISPD, pages 84--89, 2004.

Digital Library

Google Scholar

Cited By

View all

Zhang ZChen G(2024)Incremental Placement Technology Based on Front-End DesignElectronics10.3390/electronics1314274513:14(2745)Online publication date: 12-Jul-2024
https://doi.org/10.3390/electronics13142745
Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Qi YGan ZDing JFu ZGong MYu W(2024)Track Assignment Using Gradient Indication and Simulated Annealing2024 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS58744.2024.10557940(1-5)Online publication date: 19-May-2024
https://doi.org/10.1109/ISCAS58744.2024.10557940
Show More Cited By

Index Terms

NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '05: Proceedings of the 2005 international symposium on Physical design

April 2005

258 pages

ISBN:1595930213

DOI:10.1145/1055137

General Chair:
Patrick Groeneveld
Eindhoven University
,
Program Chair:
Lou Scheffer
Cadence

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 April 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD05

Sponsor:

ISPD05: International Symposium on Physical Design 2005

April 3 - 6, 2005

California, San Francisco, 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

54
Total Citations
View Citations
589
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)7

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang ZChen G(2024)Incremental Placement Technology Based on Front-End DesignElectronics10.3390/electronics1314274513:14(2745)Online publication date: 12-Jul-2024
https://doi.org/10.3390/electronics13142745
Hou YYe HZhang YXu SSong GBaeza-Yates RBonchi F(2024)RoutePlacer: An End-to-End Routability-Aware Placer with Graph Neural NetworkProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671895(1085-1095)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671895
Qi YGan ZDing JFu ZGong MYu W(2024)Track Assignment Using Gradient Indication and Simulated Annealing2024 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS58744.2024.10557940(1-5)Online publication date: 19-May-2024
https://doi.org/10.1109/ISCAS58744.2024.10557940
Zheng SZou LXu PLiu SYu BWong M(2023)Lay-Net: Grafting Netlist Knowledge on Layout-Based Congestion Prediction2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323800(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323800
Zheng SZou LLiu SLin YYu BWong M(2023)Mitigating Distribution Shift for Congestion Optimization in Global Placement2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247660(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247660
Guo ZLiu MGu JZhang SPan DLin YOshana R(2022)A timing engine inspired graph neural network model for pre-routing slack predictionProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530597(1207-1212)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530597
Liu SSun QLiao PLin YYu B(2021)Global Placement with Deep Learning-Enabled Explicit Routability Optimization2021 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE51398.2021.9473959(1821-1824)Online publication date: 1-Feb-2021
https://doi.org/10.23919/DATE51398.2021.9473959
Rasheed FHefenbrock MBishnoi RBeigl MAghassi-Hagmann JTahoori M(2020)Crossover-aware Placement and Routing for Inkjet Printed CircuitsACM Journal on Emerging Technologies in Computing Systems10.1145/337546116:2(1-22)Online publication date: 30-Jan-2020
https://dl.acm.org/doi/10.1145/3375461
Lin YLi WGu JRen HKhailany BPan D(2020)ABCDPlace: Accelerated Batch-based Concurrent Detailed Placement on Multi-threaded CPUs and GPUsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.2971531(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.2971531
Kranas GKouskouras TDimitriadis VDossis MOikonomou PDadaliaris A(2020)A Novel Genetic Algorithm for I/O Pad Planning Retaining Former Cell Positions2020 5th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM)10.1109/SEEDA-CECNSM49515.2020.9221794(1-5)Online publication date: Sep-2020
https://doi.org/10.1109/SEEDA-CECNSM49515.2020.9221794
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.

Cited By

Index Terms

Recommendations

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

Routability-driven placement for hierarchical mixed-size circuit designs

Routability-Driven Blockage-Aware Macro Placement