Article

TCG: a transitive closure graph-based representation for non-slicing floorplans

Authors:

Yao-Wen ChangAuthors Info & Claims

DAC '01: Proceedings of the 38th annual Design Automation Conference

Pages 764 - 769

https://doi.org/10.1145/378239.379062

Published: 22 June 2001 Publication History

Abstract

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

References

[1]

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

Digital Library

[2]

P.-N. Guo, C.-K. Cheng, and T. Yoshimura, "An O-Tree representation of nonslicing floorplan and its applications,"Proc. DAC, pp. 268-273, June 1999.

Digital Library

[3]

X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu, "Corner Block List: An effective and efficient topological representation of nonslicing floorplan," Proc. ICCAD, pp. 8-12, Nov. 2000.

Digital Library

[4]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp.671-680, May, 1983.

[5]

E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976.

[6]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packingbased module placement," Proc. ICCAD, pp. 472-479, Nov. 1995.

Digital Library

[7]

S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, "Module placement on BSG-structure and IC layout applications," Proc. ICCAD, pp. 484-491, Nov. 1996.

Digital Library

[8]

T. Ohtsuki, N. Suzigama, and H. Hawanishi, "An optimization technique for intergrated circuit layout design," Proc. ICCST, Kyoto, pp. 67-68, 1970.

[9]

H. Onodera, Y. Taniquchi, and K. Tamaru, "Branch-and-bound placement for building block layout," Proc. DAC, pp. 433-439, 1991.

Digital Library

[10]

R.H.J.M. Otten, "Automatic floorplan design,"Proc. DAC, pp.261-267, June 1982.

Digital Library

[11]

P. Pan and C.-L. Liu, "Area minimization for floorplans," IEEE TCAD, pp. 123- 132, Jan. 1995.

Digital Library

[12]

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

Digital Library

[13]

S. M. Sait and H. Youssef, VLSI Physical Design Automation, IEEE Press, 1995.

Digital Library

[14]

X. Tang and D. F. Wong, " FAST-SP: A fast algorithm for block placement based on sequence pair," Proc. ASP-DAC, pp. 521-526, Jan. 2001.

Digital Library

[15]

T.-C. Wang, and D. F. Wong, "An optimal algorithm for floorplan and area optimization," Proc. DAC, pp.180-186, June 1990.

Digital Library

[16]

D. F. Wong, and C.-L. Liu, "A new algorithm for floorplan design,c Proc. DAC, pp. 101-107, June 1986.

Digital Library

Cited By

Zhao YLiao PLiu SJiang JLin YYu B(2025)Analytical Heterogeneous Die-to-Die 3-D Placement With MacrosIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344471644:2(402-415)Online publication date: Feb-2025
https://doi.org/10.1109/TCAD.2024.3444716
Murugan KSyelesh PVishnu Vardhan Reddy BSubba Reddy CPraveen Kummar T(2024)Design and Development of Serial Driver Verification and Test Module using Universal Verification Methodology2024 4th International Conference on Pervasive Computing and Social Networking (ICPCSN)10.1109/ICPCSN62568.2024.00126(754-757)Online publication date: 3-May-2024
https://doi.org/10.1109/ICPCSN62568.2024.00126
Chen HChen YXu N(2024)Automatic Placement of PCB Functional Modules Based on Regional Division2024 13th International Conference on Communications, Circuits and Systems (ICCCAS)10.1109/ICCCAS62034.2024.10652680(51-58)Online publication date: 10-May-2024
https://doi.org/10.1109/ICCCAS62034.2024.10652680
Show More Cited By

Index Terms

TCG: a transitive closure graph-based representation for non-slicing floorplans

Recommendations

TCG-S: orthogonal coupling of P*-admissible representations for general floorplans
DAC '02: Proceedings of the 39th annual Design Automation Conference

We extend in this paper the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P*-admissible representations, SP, ...
TCG: a transitive closure graph-based representation for general floorplans

In this brief, we introduce the concept of the P* -admissible representation and propose a P* -admissible, transitive closure graph-based representation for general floorplans, called transitive closure graph (TCG), and show its superior properties. TCG ...
TCG-S: orthogonal coupling of P^*-admissible representations for general floorplans

In this paper, we extend the concept of the P-admissible floorplan representation to that of the P^*-admissible one. A P^*-admissible representation can model the most general floorplans. Each of the currently existing P^*-admissible representations, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '01: Proceedings of the 38th annual Design Automation Conference

June 2001

863 pages

ISBN:1581132972

DOI:10.1145/378239

Chairman:
Jan Rabaey
Univ. of California

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

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC01

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC01: 38th ACM/IEEE-CAS/ EDAC Design Automation Conference

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

175
Total Citations
View Citations
140
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao YLiao PLiu SJiang JLin YYu B(2025)Analytical Heterogeneous Die-to-Die 3-D Placement With MacrosIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344471644:2(402-415)Online publication date: Feb-2025
https://doi.org/10.1109/TCAD.2024.3444716
Murugan KSyelesh PVishnu Vardhan Reddy BSubba Reddy CPraveen Kummar T(2024)Design and Development of Serial Driver Verification and Test Module using Universal Verification Methodology2024 4th International Conference on Pervasive Computing and Social Networking (ICPCSN)10.1109/ICPCSN62568.2024.00126(754-757)Online publication date: 3-May-2024
https://doi.org/10.1109/ICPCSN62568.2024.00126
Chen HChen YXu N(2024)Automatic Placement of PCB Functional Modules Based on Regional Division2024 13th International Conference on Communications, Circuits and Systems (ICCCAS)10.1109/ICCCAS62034.2024.10652680(51-58)Online publication date: 10-May-2024
https://doi.org/10.1109/ICCCAS62034.2024.10652680
Al Saleh DSafari YAmik FVaisband B(2023)P* Admissible Thermal-Aware Matrix Floorplanner for 3D ICs2023 IEEE 36th International System-on-Chip Conference (SOCC)10.1109/SOCC58585.2023.10256905(1-6)Online publication date: 5-Sep-2023
https://doi.org/10.1109/SOCC58585.2023.10256905
Jeyarohini RBritto KRamkumar M(2023)Optimization and Representation of Non-Slicing VLSI Floorplanning2023 4th International Conference on Smart Electronics and Communication (ICOSEC)10.1109/ICOSEC58147.2023.10276362(26-31)Online publication date: 20-Sep-2023
https://doi.org/10.1109/ICOSEC58147.2023.10276362
Chen YWen ZLiang YLin Y(2023)Stronger Mixed-Size Placement Backbone Considering Second-Order Information2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323700(1-9)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323700
Lee CChang Y(2023)Floorplanning for Embedded Multi-Die Interconnect Bridge Packages2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323609(1-8)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323609
Jiang LOuyang DZhou HTian NZhang L(2023)DPAHMA: a novel dual-population adaptive hybrid memetic algorithm for non-slicing VLSI floorplansThe Journal of Supercomputing10.1007/s11227-023-05277-179:14(15496-15534)Online publication date: 18-Apr-2023
https://doi.org/10.1007/s11227-023-05277-1
Karna NArisankula JMaheshwaram S(2022)Impact on the Performance of North Bridge I/O Peripheral Component Interconnect Express Block in Physical Design Flow Considering Two Different Synthesis Corners at below 10nm Technology Node2022 IEEE International Symposium on Smart Electronic Systems (iSES)10.1109/iSES54909.2022.00102(471-474)Online publication date: Dec-2022
https://doi.org/10.1109/iSES54909.2022.00102
Chang YTing C(2022)Multiple Crossover and Mutation Operators Enabled Genetic Algorithm for Non-slicing VLSI Floorplanning2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870396(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870396
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