article

Slicible rectangular graphs and their optimal floorplans

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 6, Issue 4

Pages 447 - 470

Published: 01 October 2001 Publication History

Abstract

Rectangular dualization method of floorplanning usually involves topology generation followed by sizing. Slicible topologies are often preferred for their simplicity and efficiency. While slicible topologies can be obtained efficiently, existing linear-time algorithms for topology generation from a given rectangular graph does not guarantee slicible topologies even if one exists. Moreover, the class of rectangular graphs, known as inherently nonslicible graphs, do not have any slicible topologies. In this article, new tighter sufficiency conditions for slicibility of rectangular graphs are postulated and utilized in the generation of area-optimal floorplans. These graph-theoretic conditions not only capture a larger class of slicible rectangular graphs but also help in reducing the total effort for topology generation, and in solving problems of larger size.

References

[1]

BHASKER,J.,AND SAHNI, S. 1986. A linear algorithm to find a rectangular dual of a planar triangulated graph. In Proceedings of the 23rd Annual ACM/IEEE Design Automation Conference (DAC) (June). ACM, New York, pp. 108-114.

Crossref

Google Scholar

[2]

CAI,Y.,AND WONG, D. F. 1990. A channel/switchbox definition algorithm for building-block layout. In Proceedings of the 27th Annual ACM/IEEE Design Automation Conference (June). ACM, New York, pp. 638-641.

Crossref

Google Scholar

[3]

DASGUPTA,P.S.,SUR-KOLAY,S.,AND BHATTACHARYA, B. B. 1995a. VLSI Floorplan generation and area optimization using AND-OR graph search. In Proceedings of the 8th International Conference on VLSI Design (Jan.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 370- 375.

Crossref

Google Scholar

[4]

DASGUPTA,P.S.,SUR-KOLAY,S.,AND BHATTACHARYA, B. B. 1995b. A unified approach to topology generation and area optimization of general floorplans. In Proceedings of the IEEE/ACM International Conference on Computer Aided Design (ICCAD). (San Jose, Calif., Nov. 5-9). ACM, New York, pp. 712-715.

Crossref

Google Scholar

[5]

DASGUPTA,P.S.,SUR-KOLAY,S.,AND BHATTACHARYA, B. B. 1998. A unified approach to topology generation and optimal sizing of floorplans. IEEE Trans. CAD 17, 2. (Feb.), 126-145.

Crossref

Google Scholar

[6]

KOZMINSKI, K., AND KINNEN, K. 1985. Rectangular dual of planar graphs. Networks 15, 2, 145- 157.

Google Scholar

[7]

LAI,Y.T.,AND LEINWAND, S. M. 1988. Algorithms for floorplan design via rectangular dualization. IEEE Trans. CAD 7, 12 (Dec.), 1278-1289.

Google Scholar

[8]

OTTEN, R. 1983. Efficient floorplan optimization. In Proceedings of the IEEE International Conference on Computer Design (ICCD). IEEE Computer Society Press, Los Alamitos, Calif., pp. 499- 502.

Google Scholar

[9]

PAN, P., SHI,W.,AND LIU, C. L. 1996. Area minimization for hierarchical Floorplans. Algorithmica 15,6.

Google Scholar

[10]

REBAUDENGO, M., AND REORDA, M. S. 1996. GALLO: A genetic algorithm for floorplan area optimization. IEEE Trans. CAD 15, 8, (Aug.), 943-951.

Crossref

Google Scholar

[11]

SUR-KOLAY,S.,AND BHATTACHARYA, B. B. 1988. Inherent nonslicibility of rectangular duals in VLSI floorplanning. In Proceedings of the 8th Conference on Foundations of Software Technology and Theoretical Computer Science (Pune, India, Dec. 21-23). Lecture Notes in Computer Science, vol. 338. Springer-Verlag, Berlin, Germany, pp. 88-107.

Crossref

Google Scholar

[12]

SUR-KOLAY,S.,AND BHATTACHARYA, B. B. 1991. On the family of inherently nonslicible floorplans in VLSI layout design. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS) (Singapore, Jun.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 2850- 2853.

Google Scholar

[13]

SHERWANI, N. 1993. Algorithms for VLSI physical design automation. Kluwer Academic Publishers.

Crossref

Google Scholar

[14]

STOCKMEYER, L. 1983. Optimal orientation of cells in slicing floorplan designs. Inf. Control 57, 91-101.

Crossref

Google Scholar

[15]

WIMER, S., KOREN, I., AND CEDERBAUM, I. 1989. Optimal aspect ratios of building blocks in VLSI. IEEE Trans. CAD 8, 2 (Feb.), 139-145.

Google Scholar

[16]

WANG,T.C.,AND WONG, D. F. 1992. Optimal floorplan area optimization. IEEE Trans. CAD 11, 992-1002.

Google Scholar

[17]

YEAP,K.H.,AND SARRAFZADEH, M. 1993. A unified approach to floorplan sizing and enumeration. IEEE Trans. CAD 12, 12, 1858-1867.

Google Scholar

[18]

YEAP,K.H.,AND SARRAFZADEH, M. 1995. Sliceable floorplanning by graph dualization. SIAM J. Disc. Math. 8, 2 (May), 258-280.

Crossref

Google Scholar

Cited By

View all

Felsner SNathenson ATóth C(2022)Aspect Ratio Universal Rectangular LayoutsWALCOM: Algorithms and Computation10.1007/978-3-030-96731-4_7(73-84)Online publication date: 24-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-96731-4_7
Das SDas D(2018)Floorplanning in Graphene Nanoribbon (GNR) Based Circuits2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2018.00061(293-298)Online publication date: Jul-2018
https://doi.org/10.1109/ISVLSI.2018.00061
Felsner S(2016)Shifting Segments to OptimalityGems of Combinatorial Optimization and Graph Algorithms10.1007/978-3-319-24971-1_1(1-12)Online publication date: 12-Jan-2016
https://doi.org/10.1007/978-3-319-24971-1_1
Show More Cited By

Recommendations

Slicibility of rectangular graphs and floorplan optimization
ISPD '97: Proceedings of the 1997 international symposium on Physical design
Floorplanning by graph dualization: L-shaped modules

We propose a novel technique for constructing a floorplan from an adjacency requirement -- represented by a graphG. The algorithm finds a geometric dual ofG involving both rectangular and L-shaped modules. This is the first dualization technique which ...
Sliceable Floorplanning by Graph Dualization

Previous algorithms on rectangular dual graph floorplanning generate general floorplans which include the class of nonsliceable floorplans. We examine the framework of generating sliceable floorplans using the rectangular dual graph approach and ...

Reviews

Reviewer: Lyudmila A. Zinchenko

In order to generate an effective floorplan, the interconnection between different modules may be represented by an adjacency graph. Rectangular graphs are the subset of adjacency graphs that this article focuses on. In the rectangular approach, there are inherently nonslicible (INS) graphs, having unknown properties. Advantages of proposed method are that it solves problems of large sizes for floorplan optimization, and applies to a large class of slicible graphs. As a result, the proposed approach makes is possible to create polynomial-time algorithms that can find a slicible floorplan for a rectangular graph. In all sections, the mathematics of the proposed algorithms are clearly explained, although most proofs require advanced mathematical knowledge. This paper represents extensive experimental results on benchmarks as well. Comparison with a previous method [1] gave good results. The paper could have been more useful if it had included a comparison with approaches proposed by other authors. This paper is intended not only for those working in graph theory but also for engineers who want to improve computer-aided design tools by means of effective algorithms, as well as for those working in the field of search algorithms using graphs. The paper is well organized, and represents a small step forward in the improvement of VLSI physical design. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 6, Issue 4

October 2001

198 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/502175

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 October 2001

Published in TODAES Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
612
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Felsner SNathenson ATóth C(2022)Aspect Ratio Universal Rectangular LayoutsWALCOM: Algorithms and Computation10.1007/978-3-030-96731-4_7(73-84)Online publication date: 24-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-96731-4_7
Das SDas D(2018)Floorplanning in Graphene Nanoribbon (GNR) Based Circuits2018 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2018.00061(293-298)Online publication date: Jul-2018
https://doi.org/10.1109/ISVLSI.2018.00061
Felsner S(2016)Shifting Segments to OptimalityGems of Combinatorial Optimization and Graph Algorithms10.1007/978-3-319-24971-1_1(1-12)Online publication date: 12-Jan-2016
https://doi.org/10.1007/978-3-319-24971-1_1
Lu H(2014)Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of BitsSIAM Journal on Computing10.1137/12087914243:2(477-496)Online publication date: Jan-2014
https://doi.org/10.1137/120879142
Liu HYang YAlhalawani SMitra N(2013)Constraint-aware interior layout exploration for pre-cast concrete-based buildingsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-013-0825-129:6-8(663-673)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00371-013-0825-1
Eppstein DMumford ESpeckmann BVerbeek K(2012)Area-Universal and Constrained Rectangular LayoutsSIAM Journal on Computing10.1137/11083403241:3(537-564)Online publication date: Jan-2012
https://doi.org/10.1137/110834032
Thakur MKumari MDas M(2010)Architectural layout planning using genetic algorithms2010 3rd International Conference on Computer Science and Information Technology10.1109/ICCSIT.2010.5565165(5-11)Online publication date: Jul-2010
https://doi.org/10.1109/ICCSIT.2010.5565165
Eppstein DMumford ESpeckmann BVerbeek KHershberger JFogel E(2009)Area-universal rectangular layoutsProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542411(267-276)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542411
Yang GSong XYang HXie F(2005)A Theoretical Upper Bound for IP-Based FloorplanningProceedings of the 11th Annual International Conference on Computing and Combinatorics - Volume 359510.5555/2958119.2958232(411-419)Online publication date: 16-Aug-2005
https://dl.acm.org/doi/10.5555/2958119.2958232
Yang GSong XYang HXie F(2005)A Theoretical Upper Bound for IP-Based FloorplanningComputing and Combinatorics10.1007/11533719_42(411-419)Online publication date: 2005
https://doi.org/10.1007/11533719_42

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

Slicibility of rectangular graphs and floorplan optimization

Floorplanning by graph dualization: L-shaped modules

Sliceable Floorplanning by Graph Dualization

Reviews

Access critical reviews of Computing literature here