research-article

Fixed-outline floorplanning: enabling hierarchical design

Authors:

Saurabh N. Adya,

Igor L. MarkovAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 11, Issue 6

Pages 1120 - 1135

https://doi.org/10.1109/TVLSI.2003.817546

Published: 01 December 2003 Publication History

Abstract

Classical floorplanning minimizes a linear combination of area and wirelength. When simulated annealing is used, e.g., with the sequence pair representation, the typical choice of moves is fairly straightforward. In this paper, we study the fixed-outline floorplan formulation that is more relevant to hierarchical design style and is justified for very large ASICs and SoCs. We empirically show that instances of the fixed-outline floorplan problem are significantly harder than related instances of classical floorplan problems. We suggest new objective functions to drive simulated annealing and new types of moves that better guide local search in the new context.Wirelength improvements and optimization of aspect ratios of soft blocks are explicitly addressed by these techniques. Our proposed moves are based on the notion of floorplan slack. The proposed slack computation can be implemented with all existing algorithms to evaluate sequence pairs, of which we use the simplest, yet semantically indistinguishable from the fastest reported [28]. A similar slack computation is possible with many other floorplan representations. In all cases the computation time approximately doubles. Our empirical evaluation is based on a new floorplanner implementation Parquet-1 that can operate in both outline-free and fixed-outline modes. We use Parquet-1 to floorplan a design, with approximately 32000 cells, in 37 min using a top-down, hierarchical paradigm.

References

[1]

S. N. Adya and I. L. Markov, "Consistent placement of macroblocks using floorplanning and standard-cell placement," in Proc. ISPD, 2002, pp. 12-17.

[2]

S. N. Adya and I. L. Markov, "Fixed-outline floorplanning through better local search," in Proc. ICCD, 2001, pp. 328-334.

[3]

A. E. Caldwell, A. B. Kahng, A. A. Kennings, and I. L. Markov, "Hypergraph partitioning for VLSI CAD: Methodology for reporting, and new results," in Proc. DAC , 1999, pp. 349-354.

[4]

A. E. Caldwell, A. B. Kahng, and I. Markov, "Can recursive bisection alone produce routable placements?," in Proc. DAC, 2000, pp. 477-482.

[5]

Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu, "B -trees: A new representation for nonslicing floorplans," in Proc. DAC, 2000, pp. 458-463.

[6]

P. Chen and E. S. Kuh, "Floorplan sizing by linear programming approximation," in Proc. DAC, 2000, pp. 468-471.

[7]

J. Cong, T.Kong, and D. Z. Pan, "Buffer block planning for interconnectdriven floorplanning," in Proc. ICCAD, 1999, pp. 358-363.

[8]

W. Dai, D. Huang, C. Chang, and M. Courtoy, "Silicon virtual prototyping: The new cockpit for nanometer chip design," in Proc. ASP-DAC, 2003, pp. 635-639.

[9]

Y. Feng, D. P. Mehta, and H. Yang, "Constrained "modern" floorplanning," in Proc. ISPD, 2003, pp. 128-134.

[10]

K. Fujuyoshi and H. Murata, "Arbitrary convex and concave rectilinear block packing using sequence pair," in Proc. ISPD 1999, pp. 103-110.

Digital Library

[11]

X. Hong et al., "Corner block list: An effective and efficient topological representation of nonslicing floorplan," in Proc. ICCAD 2000, pp. 8-13.

[12]

A. Jagannathan, S. W. Hur, and J. Lillis, "A fast algorithm for contextaware buffer insertion," ACM Trans. Design Automation Electron. Syst. (TODAES), vol. 7, no. 1, pp. 173-188, January 2002.

Digital Library

[13]

A. B. Kahng, "Classical floorplanning harmful?," in Proc. ISPD 2000, pp. 207-213.

[14]

J. Koehl, D. E. Lackey, and G. Doerre, "IBM's 50 million gate ASICs," in Proc. ASP-DAC 2003, pp. 628-634.

[15]

D. E. Lackey, "Design planning methodology for rapid chip deployment," in Proc. IEEE/DATC Electronic Design ProcessWorkshop, 2001.

[16]

A. Mehrotra, L. V. Ginneken, and Y. Trivedi, "Design flow and methodology for 50M gate ASIC," in ASP-DAC 2003, pp. 640-647.

[17]

J. Lin and Y. Chang, "TCG: A Transitive Closure Graph based representation for nonslicing floorplans," in Proc. DAC 2001, pp. 764-769.

[18]

L. Scheffer, "Data modeling and convergence methodology in integration ensemble," in Proc. IEEE/DATC Electronic Design Process Workshop, 2001.

[19]

T. S. Moh, T. S. Chang, and S. L. Hakimi, "Globally optimal floorplanning for a layout problem," IEEE Trans. Circuits Syst. I, vol. 43, pp. 713-720, Sept. 1996.

[20]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence pair," in Proc. IEEE Trans. CAD, vol. 15, 1996, pp. 1518-1524.

Digital Library

[21]

H. Murata and E. S. Kuh, "Sequence-pair based placement methods for hard/soft/pre-placed modules," in Proc. ISPD 1998, pp. 167-172.

Digital Library

[22]

S. Nag and K. Chaudhary, "Post-placement residual-overlap removal with minimal movement," DATE '99, pp. 581-586.

[23]

Y. Pang, C. K. Cheng, and T. Yoshimura, "An enhanced perturbing algorithm for floorplan design using the O-tree representation," in Proc. ISPD 2000, pp. 168-173.

Digital Library

[24]

Y. Pang, F. Balasa, K. Lampaert, and C. K. Chang, "Block placement with symmetry constraint based on the O-tree nonslicing representation," in Proc. DAC 2000, pp. 464-468.

[25]

F. Remond, "Monterey usage at STMicroelectronics," DAC 02.

[26]

N. Sherwani, Algorithms For VLSI Design Automation, 3rd ed. Norwell, MA: Kluwer, 1999.

[27]

X. Tang, R. Tian, and D. F. Wong, "Fast evaluation of sequence pair in block placement by longest common subsequence computation," in Proc. DATE 2000, pp. 106-111.

[28]

X. Tang and D. F. Wong, "FAST-SP: A fast algorithm for block placement based on sequence pair," in Proc. ASPDAC 2001.

[29]

F. Y. Young, C. C. N. Chu, W. S. Luk, and Y. C. Wong, "Floorplan area minimization using Lagrangian relaxation," in Proc. ISPD 2000, pp. 174-179.

Digital Library

Cited By

Yu SCensor YLuo G(2025)Floorplanning With I/O Assignment via Feasibility-Seeking and Superiorization MethodsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340810644:1(317-330)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TCAD.2024.3408106
Yao WLin YLi L(2025)Learning placement order for constructive floorplanningIntegration, the VLSI Journal10.1016/j.vlsi.2024.102293100:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.vlsi.2024.102293
Markov I(2024)Reevaluating Google’s Reinforcement Learning for IC Macro PlacementCommunications of the ACM10.1145/367684567:11(60-71)Online publication date: 23-Oct-2024
https://dl.acm.org/doi/10.1145/3676845
Show More Cited By

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 ...
Multi-bend bus-driven floorplanning considering fixed-outline constraints

The rapid rate of technological advances makes it necessary for very large scale integration (VLSI) floorplanning to consider not only interconnect constraints, but also fixed-outline constraints. In this paper, we propose a new approach to address the ...
Fast floorplanning by look-ahead enabled recursive bipartitioning

A new paradigm is introduced for floorplanning any combination of fixed-shape and variable-shape blocks under tight fixed-outline area constraints and a wirelength objective. Dramatic improvement over traditional floorplanning methods is achieved by the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 11, Issue 6

December 2003

213 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 2003.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 December 2003

Revised: 28 March 2003

Received: 31 May 2002

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

115
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu SCensor YLuo G(2025)Floorplanning With I/O Assignment via Feasibility-Seeking and Superiorization MethodsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.340810644:1(317-330)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TCAD.2024.3408106
Yao WLin YLi L(2025)Learning placement order for constructive floorplanningIntegration, the VLSI Journal10.1016/j.vlsi.2024.102293100:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.vlsi.2024.102293
Markov I(2024)Reevaluating Google’s Reinforcement Learning for IC Macro PlacementCommunications of the ACM10.1145/367684567:11(60-71)Online publication date: 23-Oct-2024
https://dl.acm.org/doi/10.1145/3676845
Shi YXue KSong LQian COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Macro placement by wire-mask-guided black-box optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666421(6825-6843)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666421
Kahng AVaradarajan RWang Z(2023)Hier-RTLMP: A Hierarchical Automatic Macro Placer for Large-Scale Complex IP BlocksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334628443:5(1552-1565)Online publication date: 22-Dec-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3346284
Li XPeng KHuang FZhu W(2023)PeF: Poisson’s Equation-Based Large-Scale Fixed-Outline FloorplanningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321360942:6(2002-2015)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TCAD.2022.3213609
Kahng AVaradarajan RWang ZBehjat LYang S(2022)RTL-MPProceedings of the 2022 International Symposium on Physical Design10.1145/3505170.3506731(3-11)Online publication date: 13-Apr-2022
https://dl.acm.org/doi/10.1145/3505170.3506731
Kashi SPatooghy ARahmati DFazeli M(2022)A multi-application approach for synthesizing custom network-on-chipsThe Journal of Supercomputing10.1007/s11227-022-04444-078:13(15358-15380)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04444-0
Prakash ALal R(2021)Floorplanning for Area Optimization Using Parallel Particle Swarm Optimization and Sequence PairWireless Personal Communications: An International Journal10.1007/s11277-020-08015-5118:1(323-342)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s11277-020-08015-5
Shunmugathammal MChristopher Columbus CAnand S(2020)A Novel B*tree Crossover-Based Simulated Annealing Algorithm for Combinatorial Optimization in VLSI Fixed-Outline FloorplansCircuits, Systems, and Signal Processing10.1007/s00034-019-01054-939:2(900-918)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s00034-019-01054-9
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents