Cited By
View all- Huang WChen DXu R(2007)A new heuristic algorithm for rectangle packingComputers and Operations Research10.1016/j.cor.2005.12.00534:11(3270-3280)Online publication date: 1-Nov-2007
Stairway Compaction using Corner Block List and Its Applications with Rectilinear Blocks
Abstract
Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room of improvement for our purpose. This paper proposes a compact algorithm for placement based on corner block list. By introducing the dummy blocks in CBL, our algorithm can intellective employ dummy blocks in the packing to represent the placement including empty rooms, which corner block list cannot represent. Our algorithm can obtain the fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.
References
[1]
{1} Hiroshi Murata, Kunihiro Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Block Placement Based on Rectangle-Packing by the Sequence Pair" in IEEE Trans. on CAD, vol. 15, NO. 15, pp. 1518-1524, 1996.
[2]
{2} S. Nakatake, H. Murata, K. Fujiyoshi and Y. Kajitani, "Block Placement on BSG-structure and IC layout application" in Proc. of International Conference on Computer Aided Design, pp. 484-490, 1996.
[3]
{3} P. N. Guo, and C, K, Cheng, "An O-tree representation of nonslicing floorplan and its applications", in ACM/IEEE Design Automation Conference, 1999.
[4]
{4} Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, and Shu-Wei Wu. "B*-Trees: A New Representation for Non-Slicing Floorplans" in ACM/IEEE DAC, pp. 458-464, 2000.
[5]
{5} Hong Xianlong, Huang Gang et al. "Corner Block List: An Effective and Efficient Topological Representation of Nonslicing Floorplan" ICCAD'2000.
[6]
{6} D. F. Wong, C. L. Liu, "A new algorithm for floorplan design", in Proc. of 23rd ACM/IEEE DAC, pp. 101-107, 1986.
[7]
{7} Jin Xu, Pei-Ning Guo, Chung-Kuan Cheng, "Cluster Refinement for Block Placement", in DAC'97.
[8]
{8} Shuo Zhou, Sheqin Dong, Xianlong Hong, Yici Cai, Chung-Kuan Cheng, Jun Gu "ECBL: An Extended Corner Block List with O(n) complexity and solution space including optimum placement", ISPD' 2001.
[9]
{9} Yuchun Ma, Sheqin Dong, Xianlong Hong, Yici Cai, Chung-Kuan Cheng, Jun Gu "VLSI Floorplanning with Boundary Constraints Based on Corner Block List" ASPDAC'2001.
[10]
{10} Yuchun Ma, Xianlong Hong, Sheqin Dong, Yici Cai, Chung-Kuan Cheng, Jun Gu "Floorplanning with Abutment Constraints and L-shaped/T-shaped Blocks Based on Corner Block List", DAC 2001, pp. 770-776.
[11]
{11} Yingxin Pang, Chung-Kuan Cheng, Koen Lampaert, Weize Xie" Rectilinear Block Packing Using O-tree Representation", ISPD 2001.
[12]
{12} M. Kang, W. W. M. Dai," General Floorplanning with L-shaped, T-shaped and Soft Block Based on Bounded Slicing Grid Structure", ASPDAC'1997, pp. 265-270, 1997.
[13]
{13} Kunihiro Fujiyoshi, Hiroshi Murata, "Arbitrary Convex and Concave Rectilinear Block Packing using Sequence-pair", ISPD'1999.
[14]
{14} M. Kang, W. W. M. Dai, "Arbitrary Rectilinear Block Packing Based on Sequence Pair" ICCAD'1998.
[15]
{15} J. Xu, P. N. Guo, C. K. Cheng: "Rectilinear Block Placement Using Sequence-Pair" ISPD'1998.
[16]
{16} F. Y. Young, Hannah H. Yang, D. F. Wong: "On extending slicing floorplans to handle L/T-shaped blocks and abutment constraints", WCC'2000.
[17]
{17} Jai-Ming Lin and Yao-Wen Chang: "TCG: A Transitive Closure Graph-Based Representation for Non-slcing Floorplans", in DAC'2001, pp. 764-769.
Recommendations
Stairway compaction using corner block list and its applications with rectilinear blocks
Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room for improvement for our purpose. This article proposes a compact ...
Corner block list: an effective and efficient topological representation of non-slicing floorplan
ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided designIn this paper, a corner block list -- a new efficient topological representation for non-slicing floorplan is proposed with applications to VLSI floorplan and building block placement. Given a corner block list, it takes only linear time to construct ...
General floorplans with L/T-shaped blocks using corner block list
With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List (CBL), we propose a new method of handling ...
Comments
Information & Contributors
Information
Published In
January 2002
753 pages
ISBN:0769514413
Copyright © Copyright (c) 2002 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Sponsors
Publisher
IEEE Computer Society
United States
Publication History
Published: 07 January 2002
Check for updates
Qualifiers
- Article
Conference
ASPDAC/VLSI02
Sponsor:
Acceptance Rates
Overall Acceptance Rate 466 of 1,454 submissions, 32%
Upcoming Conference
ASPDAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 92Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
Cited By
View all- Huang WChen DXu R(2007)A new heuristic algorithm for rectangle packingComputers and Operations Research10.1016/j.cor.2005.12.00534:11(3270-3280)Online publication date: 1-Nov-2007
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in