Article

Twin binary sequences: a non-redundant representation for general non-slicing floorplan

Authors:

Evangeline F. Y. Young,

Chris C. N. Chu,

Cien ShenAuthors Info & Claims

ISPD '02: Proceedings of the 2002 international symposium on Physical design

Pages 196 - 201

https://doi.org/10.1145/505388.505435

Published: 07 April 2002 Publication History

Get Access

Abstract

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Non-slicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and non-redundant topological representation for non-slicing structure. In this paper, we will propose the first representation of this kind. Like some previous work [9], we have also made used of mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules, our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan in such a way that every non-slicing floorplan can be obtained by this method uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!2³ⁿ/n^1.5) but every non-slicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.

References

[1]

Y.C. Chang, Y.W. Chang, G.M. Wu, and S.W. Wu. B*-Trees: A New Representation for Non-Slicing Floorplans. Proceedings of the 37th ACM/IEEE Design Automation Conference, 2000.

Digital Library

Google Scholar

[2]

S. Dulucq and O. Guibert. Baxter Permutations. Discrete Mathematics, 180:143--156, 1998.

Digital Library

Google Scholar

[3]

Pei-Ning Guo, Chung-Kuan Cheng, and Takeshi Yoshimura. An O-Tree Representation of Non-Slicing Floorplan and Its Applications. Proceedings of the 36th ACM/IEEE Design Automation Conference, pages 268--273, 1999.

Digital Library

Google Scholar

[4]

Xianlong Hong, Gang Huang, Yici Cai, Jiangchun Gu, Sheqin Dong, Chung-Kuan Cheng, and Jun Gu. Corner Block List: An Effective and Efficient Topological Representation of Non-Slicing Floorplan. Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 8--12, 2000.

Digital Library

Google Scholar

[5]

H. Murata, K. Fujiyoushi, S. Nakatake, and Y. Kajitani. Rectangle-Packing-Based Module Placement. Proceedings IEEE International Conference on Computer-Aided Design, pages 472--479, 1995.

Digital Library

Google Scholar

[6]

S. Nakatake, K. Fujiyoushi, H. Murata, and Y. Kajitani. Module Placement on BSG-Structure and IC Layout Applications. Proceedings IEEE International Conference on Computer-Aided Design, pages 484--491, 1996.

Digital Library

Google Scholar

[7]

D.F. Wong and C.L. Liu. A New Algorithm for Floorplan Design. Proceedings of the 23rd ACM/IEEE Design Automation Conference, pages 101--107, 1986.

Digital Library

Google Scholar

[8]

B. Yao, H. Chen, C.K. Cheng, and R. Graham. Revisiting Floorplan Representations. Proceedings of International Symposium on Physical Design, pages 138--143, 2001.

Digital Library

Google Scholar

[9]

S. Zhou, S. Dong, X. Hong, Y. Cai, and C.-K. Cheng. ECBL: An Extended Corner Block List with Solution Space Including Optimum Placement. Proceedings of International Symposium on Physical Design, pages 156--161, 2001.

Digital Library

Google Scholar

Cited By

View all

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
Banerjee SRatna ARoy S(2016)Satisfiability modulo theory based methodology for floorplanning in VLSI circuits2016 Sixth International Symposium on Embedded Computing and System Design (ISED)10.1109/ISED.2016.7977061(91-95)Online publication date: Dec-2016
https://doi.org/10.1109/ISED.2016.7977061
Tang XTian RWong MTang T(2005)Optimal redistribution of white space for wire length minimizationProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120900(412-417)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120900
Show More Cited By

Index Terms

Twin binary sequences: a non-redundant representation for general non-slicing floorplan
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning

Recommendations

Twin binary sequences: a nonredundant representation for general nonslicing floorplan

The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area ...
Handling routability in floorplan design with twin binary trees

As technology moves into the deep-submicron era, the complexities of VLSI circuits grow rapidly. Interconnect optimization has become an important concern. Most routability-driven floorplanners [H.M. Chen, H. Zhou, F.Y. Young, D.F. Wong, H.H. Yang, N. ...
Modeling non-slicing floorplans with binary trees
ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design

Several novel topological representations of non-slicing floor-plans [2] have been more recently proposed, providing new ideas and techniques for solving block placement problems and other related layout applications. Among these topological ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '02: Proceedings of the 2002 international symposium on Physical design

April 2002

216 pages

ISBN:1581134606

DOI:10.1145/505388

General Chair:
Sachin Sapatnekar
University of Minnesota
,
Program Chair:
Massoud Pedram
USC

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: 07 April 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISPD02

Sponsor:

SIGDA

ISPD02: International Symposium on Physical Design

April 7 - 10, 2002

CA, San Diego, 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

9
Total Citations
View Citations
302
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Banerjee SRatna ARoy S(2016)Satisfiability modulo theory based methodology for floorplanning in VLSI circuits2016 Sixth International Symposium on Embedded Computing and System Design (ISED)10.1109/ISED.2016.7977061(91-95)Online publication date: Dec-2016
https://doi.org/10.1109/ISED.2016.7977061
Tang XTian RWong MTang T(2005)Optimal redistribution of white space for wire length minimizationProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120900(412-417)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120900
Xiaoping Tang Ruiqi Tian Wong M(2005)Optimal redistribution of white space for wire length minimizationProceedings of the ASP-DAC 2005. Asia and South Pacific Design Automation Conference, 2005.10.1109/ASPDAC.2005.1466198(412-417)Online publication date: 2005
https://doi.org/10.1109/ASPDAC.2005.1466198
Shen ZChu CImai M(2004)Accurate and efficient flow based congestion estimation in floorplanningProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015273(671-676)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015273
Tang XWong MImai M(2004)On handling arbitrary rectilinear shape constraintProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015101(38-41)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015101
Gao KMehta D(2004)Floorplan classification algorithmsProceedings. 17th International Conference on VLSI Design10.1109/ICVD.2004.1261057(975-980)Online publication date: 2004
https://doi.org/10.1109/ICVD.2004.1261057
Tang XWong M(2004)On handling arbitrary rectilinear shape constraintASP-DAC 2004: Asia and South Pacific Design Automation Conference 2004 (IEEE Cat. No.04EX753)10.1109/ASPDAC.2004.1337536(38-41)Online publication date: 2004
https://doi.org/10.1109/ASPDAC.2004.1337536
Lai SYoung EChu C(2003)A New and Efficient Congestion Evaluation Model in FloorplanningProceedings of the conference on Design, Automation and Test in Europe - Volume 110.5555/789083.1022831Online publication date: 3-Mar-2003
https://dl.acm.org/doi/10.5555/789083.1022831

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

Twin binary sequences: a nonredundant representation for general nonslicing floorplan

Handling routability in floorplan design with twin binary trees

Modeling non-slicing floorplans with binary trees