隨著VLSI技術的進步，在一顆IC上的電晶體數目也越來越多，在standard cell設計裡，是由一些等高的cell所組成的，如何把這些 cell置放並考慮到連接的長度是非常困難的，置放的優劣也會影響到IC的面積、可繞性及性能。置放有數種方法被提出，本篇論文當中，我們使用多層次技術的置放方法，hMetis 是基於此方法的一套軟體對巨大的超邊來作分割，此軟體提供了高品質的線路分割，全子集是一個包含巨大圖形的完全子圖形，全子集通常用來把超邊轉換成邊，也把超圖形轉換成圖形，我們把線路轉換成圖形分成有使用全子集模型及沒有使用全子集模型，發現在較大的分割數時，由hMetis得知使用全子集模型比沒有用全子集模型有較小的分割點數及減少了15%的外部度數，我們發展了一個基於超邊全子集模型的線路分割的全域置放器，根據實驗結果，使用全子集模型比沒有用全子集模型減少了10%的連線長度。

As VLSI technology advances, more transistors will be on a chip. In standard cell designs, transistors are grouped into cells of the same height to perform some basic logic function. There will be more than a million cells in a VLSI design. Placement of these cells on a chip is increasingly difficult, but bearing the responsibility of deciding the length of interconnects. It will certainly affect chip area, routability, performance, etc.
Several placement algorithms have been proposed in the past. We choose the multi-level hierarchical technique for placement. hMetis is a software package for partitioning a large hypergraph based on multi-level hypergraph partitioning. This program provides high quality partition for VLSI designs. This program is fast than the other widely used partitioning algorithms. Clique is a complete subgraph contained in a larger graph. Clique is often used to convert a hyperedge into edges such that a hypergraph can be transformed into a graph. It has been found that clique modeling of hyperedges in circuit partitioning could lead to a cut size as small as that obtained by hMetis without using clique modeling and up to 15% reduction in external degree if a circuit is partitioned into a large number of parts. A placer is designed to place the results obtained from the partitioning of graphs with clique modeling. Global placement by circuit partitioning with hyperedge clique could obtained small wirelength than non-clique model by our experiments. The results shown up to 10% improve in the wirelength with clique model than non-clique model.

Table of Contents
List of Figures iii
List of Tables v
Symbol Definitions vi
Chapter 1. Introduction 1
1.1 Background and Motivation 1
1.2 Scope of the Work 4
1.3 Thesis Organization 4
Chapter 2. Related Work 5
2.1 Clique Model 5
2.1.1 Weight Assignment Problem and Methods 6
2.1.2 Weight Assignment Methods 7
2.2 hMetis 12
Chapter 3. Placer Implementation 15
3.1 Circuit Representation 15
3.1.1 Hypergraph 15
3.1.2 Clique modeling of hyperedges 16
3.1.3 Cell weight 16
3.1.4 Cell and hyperedges weighted of hyperedge graph 17
3.2 Global Placer Implementation 18
3.3 Detailed Placer 29
Chapter 4. Experimental Results 32
Chapter 5. Conclusion 37
5.1 Contribution 37
5.2 Future Work 37
References 38
Appendix A. 40


List of Figures
Figure 1.1 The recursive bipartitioning of a circuit leading to a min-cut placement 2
Figure 1.2 Placement by clustering 3
Figure 2.1 (a). A 3-vertex hyperedge, (b). partitioned into two parts, (c). partitioned into three parts. 7
Figure 2.2 (a). a 5-vertex hyperedge, (b). transformed into a 5-vertex clique, (c). an instance of bi-partitioning, (d). another instance of bi-partitioning. 7
Figure 2.3 Multilevel hypergraph bisection 12
Figure 2.4 Edge coarsening merge schemes 13
Figure 3.1 Hypergraph of a sample circuit 15
Figure 3.2 Clique modeling of hyperedges 16
Figure 3.3 (a) a hyperedge graph. (b) corresponding file 17
Figure 3.4 (a) cell and hyperedges weighted. (b) corresponding file 18
Figure 3.5 Flowchart for our implementation 19
Figure 3.6 Example of nine parts in chip 21
Figure 3.7 Example of eight parts in chip 21
Figure 3.8 Example parts file for ibm01.part.924 25
Figure 3.9 Algorithm of Global Placer 28
Figure 3.10 Regions assign in DEF file 29
Figure 3.11 Script file for QPlacer 30
Figure 3.12 Before detailed placement 31
Figure 3.13 After detailed placement by QPlacer 31
Figure A.1 Global placed result for ibm02-95 circuit with non-clique model 40
Figure A.2 Global placed result for ibm02-95 circuit with MAX clique model 40
Figure A.3 Global placed result for ibm02-95 circuit with DON clique model 41
Figure A.4 Global placed result for ibm02-95 circuit with F&K clique model 41
Figure A.5 Global placed result for ibm02-95 circuit with S&C clique model 42
Figure A.6 Global placed result for ibm02-95 circuit with A&K clique model 42
Figure A.7 Detailed placed result for ibm02-95 circuit with non clique model 43
Figure A.8 Detailed placed result for ibm02-95 circuit with MAX clique model 43
Figure A.9 Detailed placed result for ibm02-95 circuit with DON clique model 44
Figure A.10 Detailed placed result for ibm02-95 circuit with F&K clique model 44
Figure A.11 Detailed placed result for ibm02-95 circuit with S&C clique model 45
Figure A.12 Detailed placed result for ibm02-95 circuit with A&K clique model 45


List of Tables
Table 2.1 Normalized average cut size (µ) and its standard deviation (σ) 11
Table 2.2 Normalized average external degree (µ) and its standard variation (σ) 11
Table 2.3 Probability of having best cut size (left column) and external degree (right column) 11
Table 3.1 Number of parts of ibm01-85% circuit 22
Table 3.2 Number of parts of all IBM Placer2 benchmark circuit 23
Table 4.1 ISPD98 IBM Placer2 benchmark circuit 32
Table 4.2 number of partition of benchmark circuit 33
Table 4.3 HPWL results of our global placer 34
Table 4.4 HPWL results of detailed place by QPlacer 35
Table 4.5 HPWL results by QPlacer only and our global placer 36

[1]. Sabih, Algorithms for VLSI Design Automation, John Wiley & Sons, New York, 1999.
[2]. A. Caldwell, A. Kahng and I. Markov, “Can Recursive Bisection Produce Routable Placements?” Proc. Design Automation Conference, pp. 477-482, 2000.
[3]. C. M. Fiduccia and R. M. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions,” DAC ‘82, pp. 175-181.
[4]. C. Sechen and A. Sangiovanni-Vincentelli, “The Timberwolf Placement and Routing Package,” IEEE Journal of of Solid-state Circuits, Vol. 20 No. 2, pp. 432-439, 1985.
[5]. G. Karypis, B. Aggarwal, V. Kumar and S. Shekhar, “Multi-level hypergraph partitioning: Application in VLSI domain,” IEEE Trans. VLSI Syst, vol. 7, pp. 69-79, 1999.
[6]. J. Cong, M. Romesis and M. Xie, "Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms," Proceedings of the International Symposium on Physical Design, Monterey, California, pp. 88 - 94, April 2003.
[7]. hMETIS hypergraph partitioning package available via the World Wide Web at URL: http://www.cs.umn.edu/˜metis.
[8]. D. G. Schweikert, B. W. Kernighan, “A proper model for the partitioning of electrical circuits,” in Proceedings of the 9th workshop on Design automation, Dallas, TX, pp.57-62, June 1972.
[9]. K. R. Stevens and W. M. vanCleemput, “Global via minimization in generalized routing environment,” IEEE Trans. on Circuits and Systems, pp.789-692, 1979.
[10]. X. M. Xiong and E. S. Kuh, “A unified approach to the via minimization problem,” IEEE Trans. on Circuits and Systems, Vol. 36, No. 2, pp. 190-204, Feb. 1989.
[11]. A. Vannelli and S. W. Hadley, “A Gomory-Hu cut tree representation of a netlist partitioning problem,” IEEE Trans. on Circuits and Systems, Vol. 37, No. 9, pp. 1133-11394, Sept. 1990.
[12]. C. J. Alpert, A. B. Kahng, “Geometric embeddings for faster and better multi-way netlist partitioning,” Proceedings of the 30th international conference on Design automation, July 1993.
[13]. Rung-Bin Lin, “A Study on Clique Modeling of Hyperedges for Circuit partitioning,” unpublished, 2004.
[14]. C.M. Fiduccia and R.M. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions,” Proc. Design Automation Conf., pp. 175-181, 1982.
[15]. C. J. Alpert, “The ISPD98 Circuit Benchmark Suite,” International Symposium on Physical Design, pp. 18-25, April 1998.