跳到主要內容

臺灣博碩士論文加值系統

(54.161.24.9) 您好!臺灣時間:2022/01/17 12:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林家民
研究生(外文):Jai-Ming Lin
論文名稱:利用遞移封閉圖表示法處理超大型積體電路之平面規劃
論文名稱(外文):Transitive Closure Graph Based Representations for VLSI Floorplan Design
指導教授:莊仁輝張耀文張耀文引用關係
指導教授(外文):Jen-Hui ChuangYao-Wen Chang
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:149
中文關鍵詞:遞移封閉圖表示法平面規劃
外文關鍵詞:transitive closure graphrepresentationfloorplan
相關次數:
  • 被引用被引用:0
  • 點閱點閱:261
  • 評分評分:
  • 下載下載:21
  • 收藏至我的研究室書目清單書目收藏:0
隨著製程技術進步,設計越來越複雜。為了處理如此複雜的線路,階層式設計和IP模組被廣泛應用於超大型積體電路設計以加速設計收斂的速度,這使得平面規劃(floorplanning)這個問題越來越重要。平面規劃和擺置(Floorplanning/placement) 最主要的目的是分配模組的位置來最佳化一些既定的目標例如面積、效能、或者是繞線成功率。要實現模組平面規劃和擺置,首先必須有一個表示法來描述模組之間相對的位置。因為表示法對於平面規劃設計的可行性和複雜度具有決定性的影響,所以發展一個有效、快速而且有彈性的表示法 變得非常重要。在這本博士論文當中,我們首先提出P*-admissible 表示法的概念,接著又提出了兩個圖形表示法分別稱為Transitive Closure Graph (TCG) 和Transitive Closure Graph-Sequence (TCG-S),因為我們很容易從此兩種表示法觀察模組之間的相對位置,並且利用其對應的動作 (operations) 來改變模組間的相對位置,所以 TCG 和 TCG-S 非常容易處理各種形狀的模組和各式各樣的擺置問題,例如有些模組必須放在晶片的邊界,或者是有些模組已經事先被擺好了,所以其它的模組只能放在剩餘的區域,而在類比設計中,模組必須對稱放置。不像過去所提出的方法,以遞移封閉圖 (transitive closure graph) 為基礎的方法在處理這些問題的時候,不僅可以保證每次在擾動的時候皆可得到合理的解答,而且我們的方法非常簡單容易被實行。

As technology advances, the circuit size in modern VLSI design increases dramatically. To handle the increasing design complexity, hierarchical designs and IP modules are widely used for design convergence, which makes floorplaning more important than ever. The major objective of floorplanning/placement is to allocate the modules of a circuit into a chip to optimize a predefined cost metric such as area, timing, routability, etc. The realization of floorplanning/placement relies on a representation which describes geometric relations among modules. The representation has a great impact on the feasibility and complexity of floorplan designs. Thus, it is of particular significance to develop an efficient, effective, and flexible representation for floorplan/placement designs. In this dissertation, we first propose the concept of the P*-admissible representation, and then present two graph based representations, namely Transitive Closure Graph (TCG) and Transitive Closure Graph-Sequence (TCG-S) representations for general floorplans. Since the geometric relations of modules are transparent to the two representations and their operations, we can easily use TCG and TCG-S to deal with arbitrarily shaped modules and various placement constraints, such as the boundary constraint, the pre-placed constraint, and the symmetry constraint. Unlike most of previous works, our approaches can guarantee the feasibility in each perturbation in handling these problems. Also, the methods are very simple and can be implemented easily.

Chapter 1. Introduction
1.1 What is Floorplanning/Placement?
1.2 Existing Representations
1.3 Overiew of the Thesis
Chapter 2. Transitive Closure Graph (TCG)
2.1 Introduction
2.2 Problem Definition
2.3 Transitive Closure Graph(TCG)
2.4 Floorplanning Algorithm
2.5 Experiemntal Results
Chapter 3. Arbitrarily Shaped Rectilinear Module Placement Using TCG
3.1 Introduction
3.2 Preliminaries
3.3 TCG for Sliceasble Rectilinear Moudles
3.4 Algorithm
3.5 TCG for Non-Sliceable Rectilinear Modules
3.6 Experimental Results
Chapter 4. Orthogonal Coupling of TCG and SP
4.1 Introduction
4.2 P*-admissible Representations
4.3 The TCG-S Representation
4.4 Floorplanning Algorithm
4.5 Placement with Constraints
4.6 Experimental Results
Chapter 5. Symmetry Module Placement Using TCG-S
5.1 Introduction
5.2 Preliminaries
5.3 TCG-S for the Symmetry Constraint
5.4 Algorithm
5.5 Experimental Results
Chapter 6. Concluding Remarks and Future Works
6.1 Transitive Closure Graph (TCG)
6.2 Arbitrarily Shaped Rectilinear Module Placement Using TCG
6.3 Orthogonal Coupling of TCG and SP
6.4 Symmetry Module Placement Using TCG-S
6.5 Future Work

F. Balasa and K. Lampaert,
"Symmetry within the Sequence-Pair Representation in
the Context of Placement for Analog Design,"
{\it IEEE TCAD}, vol. 19, no. 7, pp. 721--731, July 2000.
F. Balasa, "Modeling Non-Slicing Floorplans with Binary Trees,"
{\it Proc. ICCAD}, pp. 13--16, 2000.
Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu,
``B*-trees: A New Representation for Non-Slicing Floorplans,''
{\it Proc. DAC}, pp. 458--463, June 2000.
J. Cohn, D. Garrod, R. Rutenbar, and L. Carley,
``KOAN/ANAGRAMII: New Tools for Device-Level Analog Layout,"
{\it IEEE J. Solid-State Circuits,}
vol 26., PP. 330-342, Mar. 1991.
T. Cormen, C. Leiserson, and R. Rivest,
{\em Introduction to Algorithms},
McGraw-Hill Book Company, 1990.
K. Fujiyoshi and H. Murata, ``Arbitrary Convex and Concave Rectilinear Block Packing
Using Sequence-Pair,''
{\it IEEE TCAD}, vol. 19, no. 2, pp. 224--233, Feb. 2000.
P.-N. Guo, C.-K. Cheng, and T. Yoshimura,
``An O-Tree Representation of Non-Slicing Floorplan and its Applications,''
{\it Proc. DAC\/}, pp. 268--273, June 1999.
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 Non-Slicing Floorplan,''
{\it Proc. ICCAD}, pp. 8--12, Nov. 2000.
D. W. Jepsen and C. D. Gellat Jr., ``Macro Placement by Monte Carlo Annealing,"
{\it Proc. ICCD\/}, pp. 495-485, Nov. 1983.
M. Kang and W. Dai., ``General Floorplanning with L-shaped, T-shaped and Soft
Blocks Based on Bounded Slicing Grid Structure,''
{\it Proc. ASP-DAC}, pp. 265--270, 1997.
M. Z. Kang and W. W.-M Dai.,
``Arbitrary Rectilinear Block Packing Based on Sequence Pair,''
{\it Proc. ICCAD\/}, pp. 259--266, 1998.
M. Z. Kang and W. W.-M. Dai, ``Topology Constrained Rectilinear Block
Packing for Layout Reuse,''
{\it Proc. ISPD\/}, pp. 179--186, 1998.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi,
``Optimization by Simulated Annealing,''
{\it Science}, vol. 220, no. 4598, pp.671--680, May 1983.
J.-B. Lai, M.-S Lin, T.-C Wang, and Li-C Wang,
``Module Placement with Boundary Constraints Using the Sequence-Pair,''
{\it Proc. ASP-DAC\/}, pp.515--520, 2001.
K. Lampaert, G. Gielen, and W. Sansen,
``A Performance-Driven Placement Tool for Analog Integrated Circuits,''
{\it IEEE J. Solid-State Circuits,}
vol. 30, pp. 773-780, July 1995.
E. Lawler,
{\em Combinatorial Optimization: Networks and Matroids\/},
Holt, Rinehart, and Winston, 1976.
T. C. Lee, ``An Bounded 2D Contour Searching Algorithm for
Floorplan Design with Arbitrarily Shaped Rectilinear and Soft Modules,''
{\it Proc. DAC\/}, pp. 525--530, 1993.
J.-M. Lin and Y.-W Chang,
``TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,''
{\it Proc. DAC\/}, pp. 764--769, June 2001.
J.-M. Lin, H.-L Cheng and Y.-W. Chang,
``Arbitrary Convex and Concave Rectilinear Module Packing Using TCG,''
{\it Proc. DATE\/}, pp. 69--75, March 2002.
J.-M. Lin and Y.-W. Chang,
``TCG-S: Orthogonal Coupling of P-admissible Representations for Non-slicing Floorplans,''
{\it Proc. DAC\/}, pp. 842--847, June 2002.
Y. Ma, Xianlong Hong, Sheqin Dong, Yici Cai, Chung-Kuan Cheng, and Jun Gu,
``Floorplanning with Abutment Constraints and L-shaped/T-shaped Blocks based
on Corner Block List,''
{\it Proc. DAC\/}, pp. 770-775, 2001.
Y. Ma, S. Dong, X. Hong, Y. Cai, C.k. Chang, and J. Gu
``VLSI Floorplanning with Boundary Constraints Based on Corner Block List,''
{\it Proc. ASP-DAC\/}, pp. 509--514, 2001.
E. Malavasi, E. Charbon, E. Felt, and A. Sangiovanni-Vincentelli,
``Automation of IC Layout with Analog Constraints,''
{\it IEEE TCAD}, vol. 15 no. 8, pp. 923-942, Aug. 1996.
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani,
``Rectangle-Packing Based Module Placement,''
{\it Proc. ICCAD\/}, pp. 472--479, Nov.~1995.
H. Murata, K. Fujiyoshi, and M. Kaneko,
``VLSI/PCB Placement with Obstacles
Based on Sequence Pair,'' {\it Proc. ISPD\/}, pp. 26--31, 1997.
S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani,
``Module Placement on BSG-Structure and IC Layout Applications,''
{\it Proc. ICCAD\/}, pp. 484--491, Nov.~1996.
S. Nakatake, M. Furuya, and Y. Kajitani,
``Module Placement on BSG-Structure with Pre-Placed Modules and Rectilinear Modules,''
{\it Proc. ASP-DAC}, pp. 571--576, 1998.
T. Ohtsuki, N. Suzigama, and H. Hawanishi, `
`An Optimization Technique for Intergrated Circuit Layout Design,''
{\it Proc. ICCST}, pp. 67--68, 1970.
H. Onodera, Y. Taniquchi, and K. Tamaru,
``Branch-and-Bound Placement for Building Block Layout,''
{\it Proc. DAC}, pp. 433--439, 1991.
R.H.J.M. Otten, ``Automatic Floorplan Design,''
{\it Proc. DAC}, pp.261--267, June 1982.
P. Pan and C.-L. Liu, ``Area Minimization for Floorplans,''
{\it IEEE TCAD}, Vol. 14 no. 1 , pp. 123 -132, Jan. 1995
Y.-Pang, C.-K. Cheng, and T. Yoshimura,
``An Enhanced Perturbing Algorithm for Floorplan Design Using the
O-tree Representation,''
{\it Proc. ISPD}, pp. 168-173, April 2000.
Y. Pang, F. Balasa, K. Lamaert, and C.-K Cheng,
``Block Placement with Symmetry Constraints Based on thee O-tree Non-Slicing
Representation,''
{\it Proc. DAC}, pp. 464-467, 2000.
Y. Pang, C.-K. Cheng, K. Lampasert, and W. Xie,
``Rectilinear Block Packing Using O-tree Representation,''
{\it Proc. ISPD}, pp. 156-161, 2001.
J. Rijmenants, J. B. Litsios, T. R. Schwarz, and M. Degrauwe,
``ILAC: An Automated Layout Tool for Analog CMOS Circuits,''
{\it IEEE J. Solid-State Circuits,} vol. SC-24, no. 2, pp. 417-425, Apr. 1989.
S. M. Sait and H. Youssef, {\it VLSI Physical Design Automation\/,}
IEEE Press, 1995.
K. Sakanushi and Y. Kajitani,
``The Quarter-State Sequence (Q-sequence) to Represent the Floorplan and Applications to Layout
Optimization,''
{\it Proc. Asia Pacific Conf. Circuits and Systems}, pp. 829--832, 2000.
T. Takahashi,
``A New Encoding Scheme for Rectangle Packing Problem,''
{\it Proc. ASP-DAC}, Jan.~2000.
X. Tang and D. F. Wong,
``FAST-SP: A Fast Algorithm for Block Placement Based on Sequence Pair,''
{\it Proc ASP-DAC}, pp. 521--526, 2001.
T.-C. Wang, and D. F. Wong,
``An Optimal Algorithm for Floorplan and Area Optimization,''
{\it Proc. DAC}, pp. 180--186, June 1990.
D. F. Wong, and C.-L. Liu,
``A New Algorithm for Floorplan Design,''
{\it Proc. DAC}, pp. 101--107, June 1986.
G.-M. Wu, Y.-C. Chang, and Y.-W. Chang,
``Rectilinear Block Placement Using B*-Trees,''
{\it Proc. ICCD}, pp. 351--356, 2000.
J. Xu, P.-N. Guo, and C.-K. Cheng,
``Rectilinear Block Placement Using Sequence-Pair,''
{\it Proc. ISPD\/}, pp. 173--178, 1998.
J. Xu, P.-N. Guo, and C.-K. Cheng,
``Sequence-Pair Approach for Rectilinear Module Placement,''
{\it IEEE TCAD\/},
Vol. 18 no. 4, pp. 484 -493, April 1999.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top