Article

A fixed-die floorplanning algorithm using an analytical approach

Authors:

Sachin S. SapatnekarAuthors Info & Claims

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Pages 771 - 776

https://doi.org/10.1145/1118299.1118477

Published: 24 January 2006 Publication History

Abstract

Fixed-die floorplanning is an important problem in the modern physical design process. An effective floorplanning algorithm is crucial to improving both the quality and the time-to-market of the design. In this paper, we present an analytical floorplanning algorithm that can be used to efficiently pack soft modules into a fixed die. The locations and sizing of the modules are simultaneously optimized so that a minimum total wire length is achieved. Experiments on the MCNC and GSRC benchmarks show that our algorithm can achieve above a 90% success rate with a 10% white space constraint in the fixed die, and the efficiency is much higher than that of the simulated annealing based algorithms for benchmarks containing a large number of modules.

References

[1]

A. B. Kahng, "Classical Floorplanning Harmful?" Proceedings of the ACM International Symposium on Physical Design, pp. 207--213, Apr. 2000.

Digital Library

[2]

S. N. Adya and I. L. Markov, "Fixed-outline Floorplanning: Enabling Hierarchical Design," IEEE Transactions on VLSI Systems, vol. 11, no. 6, pp. 1120--1135, Dec. 2003.

Digital Library

[3]

C. T. Lin, D. S. Chen, and Y. W. Wang, "Robust Fixed-outline Floorplanning through Evolutionary Search," Proceedings of the IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 42--44, Jan. 2004.

Digital Library

[4]

T. C. Chen and Y. W. Chang, "Modern Floorplanning Based on Fast Simulated Annealing," Proceedings of the ACM International Symposium on Physical Design, pp. 104--112, Apr. 2005.

Digital Library

[5]

S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov, "Unification of Partitioning, Placement, and Floorplanning," Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 550--557, Nov. 2004.

Digital Library

[6]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-Packing-Based Module Placement," Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 472--479, Nov. 1995.

Digital Library

[7]

S. Nakatake, K. Fujiyoshi, H. Mirata, and Y. Kajitani, "Module Packing Based on the BSG-Structure and IC Layout Applications," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 6, pp. 519--530, Jun. 1998.

Digital Library

[8]

P Guo, C. Cheng, and T. Yoshimura, "An O-Tree Representation of Non-Slicing Floorplan and Its Applications," Proceedings of the IEEE/ACM Design Automation Conference, pp. 268--273, Jun. 1999.

Digital Library

[9]

X. Hong, S. Dong, G. Huang, Y. Ma, Y. Cai, C. Cheng, and J. Gu, "A Non-Slicing Floorplanning Algorithm Using Corner Block List Topological Representation," Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems, pp. 833--836, Dec. 2000.

[10]

Y. C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu, "B*-Tree: A New Representation for Non-Slicing Floorplans," Proceedings of the IEEE/ACM Design Automation Conference, pp. 458--463, Jun. 2000.

Digital Library

[11]

J. M. Lin and Y. W. Chang, "TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans," Proceedings of the IEEE/ACM Design Automation Conference, pp. 764--760, Jun. 2001.

Digital Library

[12]

A. Ranjan, K. Bazargan, S. Ogrenci, and M. Sarrafzadeh, "Fast Floorplanning for Effective Prediction and Construction," IEEE Transactions on Very Large Scale Integration (VLSI), vol. 9, no. 2, pp. 341--351, Apr. 2001.

Digital Library

[13]

T. C. Wang and D. F. Wong, "Optimal Floorplan Area Optimization," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 11, no. 8, pp. 992--1001, Aug. 1992.

Digital Library

[14]

F. Y. Young, C. C. N. Chu, W. S. Luk, and Y. C. Wong, "Handling Soft Modules in General Non-Slicing Floorplan using Lagrangian Relaxation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 5, pp. 687--692, May 2001.

Digital Library

[15]

J. Cong, M. Romesis, and J. R. Shinnerl, "Fast Floorplanning by Look-Ahead Enabled Recursive Bipartitioning," Proceedings of the IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 1119--1122, Jan. 2005.

Digital Library

[16]

W. Naylor et al., "Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer," US Patent 6301693, Oct. 2001.

[17]

A. B. Kahng and Q. Wang, "Implementation and Extensibility of an Analytical Placer," Proceedings of the ACM International Symposium on Physical Design, pp. 18--25, Apr. 2004.

Digital Library

[18]

F. S. Hillier, and G. J. Lieberman, "Introduction to Operations Research," McGraw-Hill, New York, NY, 1995.

Digital Library

[19]

W. H. Press et al., "Numerical Recipes in C++," Cambridge University Press, Cambridge, UK, 2002.

[20]

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, "Computational Geometry," Springer-Verlag, Berlin, Germany, 2000.

[21]

I. Markov, Private communication, 2005.

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: Jan-2025
https://doi.org/10.1109/TCAD.2024.3408106
Yang RDu S(2024)An RSC-Based Genetic Algorithm for Fixed-Outline Soft Module FloorplanningInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S0218001424510200Online publication date: 11-Dec-2024
https://doi.org/10.1142/S0218001424510200
Kahng AVaradarajan RWang Z(2024) Hier-RTLMP : A Hierarchical Automatic Macro Placer for Large-Scale Complex IP Blocks IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334628443:5(1552-1565)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3346284
Show More Cited By

Index Terms

A fixed-die floorplanning algorithm using an analytical approach
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
  2. Hardware validation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

A stable fixed-outline floorplanning method
ISPD '07: Proceedings of the 2007 international symposium on Physical design

In this paper, we propose a stable fixed-outline floorplanning method(IARFP). An elaborated method for perturbing solutions, Insertion after Remove(IAR), is devised for the simulated annealing. The IAR operation uses the technique of enumerating ...
Fast fixed-outline 3-D IC floorplanning with TSV co-placement

Through-silicon vias (TSVs) are used to connect inter-die signals in a 3-D IC. Unlike conventional vias, TSVs occupy device area and are very large compared to logic gates. However, most previous 3-D floorplanners only view TSVs as points. As a result, ...
An analytical approach to placement legalization
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

We present a method to achieve nearly legal placement while optimizing the traditional metrics in an analytical placement framework. A legalization penalty function term is added to the cost function of the placer. The purpose of this term is to remove ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

January 2006

998 pages

ISBN:0780394518

General Chair:
Fumiyasu Hirose
Cadence Design Systems, Japan

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
382
Total Downloads

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

Reflects downloads up to 08 Mar 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: Jan-2025
https://doi.org/10.1109/TCAD.2024.3408106
Yang RDu S(2024)An RSC-Based Genetic Algorithm for Fixed-Outline Soft Module FloorplanningInternational Journal of Pattern Recognition and Artificial Intelligence10.1142/S0218001424510200Online publication date: 11-Dec-2024
https://doi.org/10.1142/S0218001424510200
Kahng AVaradarajan RWang Z(2024) Hier-RTLMP : A Hierarchical Automatic Macro Placer for Large-Scale Complex IP Blocks IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334628443:5(1552-1565)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3346284
Kai SPui CWang FJiang SWang BHuang YHao J(2023)TOFU: A Two-Step Floorplan Refinement Framework for Whitespace Reduction2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137175(1-5)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137175
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: Jun-2023
https://doi.org/10.1109/TCAD.2022.3213609
Yu SCensor YJiang MLuo G(2023)Per-RMAP: Feasibility-Seeking and Superiorization Methods for Floorplanning with I/O Assignment2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218694(286-291)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218694
Li WWang FMoura JBlanton R(2023)Global Floorplanning via Semidefinite Programming2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247967(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247967
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
Balasubramanian SPanchanathan AChokkalingam BPadmanaban SLeonowicz Z(2018)Module Based Floorplanning Methodology to Satisfy Voltage Island and Fixed Outline ConstraintsElectronics10.3390/electronics71103257:11(325)Online publication date: 15-Nov-2018
https://doi.org/10.3390/electronics7110325
Lin JHu CChan K(2015)Routability-driven floorplanning algorithm for mixed-size modules with fixed-outline constraintVLSI Design, Automation and Test(VLSI-DAT)10.1109/VLSI-DAT.2015.7114531(1-4)Online publication date: Apr-2015
https://doi.org/10.1109/VLSI-DAT.2015.7114531
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.

Figures

Tables

Media

View Table of Conten