단순 격자 상에서 효과적인 이동 연산을 이용한 평면계획 알고리즘

다국어 초록 (Multilingual Abstract)

Most existing floorplan techniques use variable models to represent the topology of modules and suggest appropriate algorithms for floorplan on the models. This paper uses a grid model, which is much simpler than any other models, and suggests very effective move operations in the solution space in the simulated annealing frame. The key idea of the suggested effective move operations can be summarized as follows. On the compacted floorplan, it searches floorplan and determines where white (or dead) spaces are. Then, it selects one or two modules around those white spaces and move it to other location in order to change the shape of the white space. Experimental results prove that the suggested technique is comparable with the state-of-the-art techniques.

참고문헌 (Reference)

1 H. Murata, "VLSI module placement based on rectangular-packing by the sequence-pair" 15 (15): 1518-1524, 1996

2 E. F. Y. Young, "Twin Binary Sequence: A Nonredundant Representation for General Nonslicing Floorplan" 22 (22): 457-469, 2003

3 Jai-Ming Lin, "TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans"

4 j. -M. Lin, "TCG-S: Orthogonal Coupling of P*-admissible Representati ons for General Floorplans" 842-847, 2002

5 H. Murata, "Sequence-Pair Based Placement Method for Hard/Soft/Pre-placed Modules" 167-172, 1998

6 허성우, "O-tree 기반 효과적인 평면계획 알고리즘" 한국정보기술학회 8 (8): 21-27, 2010

7 S. Nakatake, "Module Placement on BSG-structure and IC Layout Application" 484-490, 1996

8 T. C. Chen, "Modern Floorplanning Based on Fast Simulated Annealing" 104-112, 2005

9 Jia Wang, "Linear Constraint Graph for Floorplan Optimization with Soft Blocks" 9-15, 2008

10 S. Zhou, "ECBL: An Extended Corner Block List with Solution Space including Optimum Placement" 150-155, 2001

11 J. Z. Yan, "DeFer: Deferred Decision Making Enabled Fixed-Outline Floorplann er" 161-166, 2008

12 X. Hong, "Corner Block List: An Effective and Efficient Topological Representation of Non-slicing Floorplan"

13 Yun-Chih Chang, "B*-Trees: A New Representation for Non Slicing Floorplans" 2001

14 H. H. Chan, "Are Floorplan Representations Important in Digital Design?" 129-136, 2005

15 P. -N. Guo, "An O-tree Representation of Non-slicing Floorplan and Its Applications" 268-273, 1999

16 C. Zhuang, "An Enhanced Q-Sequence Augmented with Empty-Room-Insertion and Parenthesis Trees" 61-68, 2002

17 Y. Pang, "An Enhanced Perturbing algorithm for Floorplan Design Using the O-tree Representation" 168-173, 2000

18 H. Zhou, "ACG-Adjacent Constraint Graph for General Floorplans"