by Tsz Shing Cheung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1990. / Includes bibliographical references. / Chapter Section 1 --- Introduction --- p.2 / Chapter 1.1 --- The Affinity Clustering Phase --- p.2 / Chapter 1.2 --- The Alteration Phase --- p.3 / Chapter 1.3 --- Floorplan of Macrocell Array --- p.3 / Chapter 1.4 --- Chip Model --- p.4 / Chapter 1.4.1 --- Location Representation --- p.4 / Chapter 1.4.2 --- Interconnection Length Estimation --- p.6 / Chapter 1.5 --- Cost Function Evaluation --- p.6 / Chapter 1.5.1 --- Net-length Calculation --- p.6 / Chapter 1.5.2 --- Net-length Estimated by Half of the Perimeter of Bounding Box --- p.7 / Chapter 1.6 --- Thesis Layout --- p.8 / Chapter Section 2 --- Reviews of Partitioning and Placement Methods --- p.9 / Chapter 2.1 --- Partitioning Methods --- p.9 / Chapter 2.1.1 --- Direct Method --- p.10 / Chapter 2.1.2 --- Group Migration Method --- p.10 / Chapter 2.1.3 --- Metric Allocation Methods --- p.10 / Chapter 2.1.4 --- Simulated Annealing --- p.11 / Chapter 2.2 --- Placement Methods --- p.12 / Chapter 2.2.1 --- Min-cut Methods --- p.13 / Chapter 2.2.2 --- Affinity Clustering Methods --- p.13 / Chapter 2.2.3 --- Other Placement Methods --- p.16 / Chapter Section 3 --- Algorithm --- p.17 / Chapter 3.1 --- The Affinity Clustering Phase --- p.18 / Chapter 3.1.1 --- Construction of Connection Lists --- p.18 / Chapter 3.1.2 --- Primary Grouping --- p.21 / Chapter 3.1.3 --- Element Appendage to Existing Groups --- p.23 / Chapter 3.1.4 --- Loose Appendage of Ungrouped Elements --- p.25 / Chapter 3.1.5 --- Single Element Groups Formation --- p.26 / Chapter 3.2 --- The Alteration Phase --- p.27 / Chapter 3.2.1 --- Element Assignment to a Group --- p.29 / Chapter 3.2.2 --- Empty Space Searching --- p.30 / Chapter 3.2.3 --- Determination of Direction of Element Allocation --- p.31 / Chapter 3.2.3.1 --- Cross-cut Direction of Allocation --- p.32 / Chapter 3.2.3.2 --- Dynamic Determination of Path Based on Size Functions --- p.34 / Chapter 3.2.3.2.1 --- Segmentation of Cross-cut --- p.35 / Chapter 3.2.3.2.2 --- Partial Optimization of Segments --- p.36 / Chapter 3.2.3.2.3 --- Dynamic Linking of Segments --- p.38 / Chapter 3.2.4 --- Element Allocation --- p.39 / Chapter Section 4 --- Implementation --- p.41 / Chapter 4.1 --- The System Row --- p.41 / Chapter 4.1.1 --- The Affinity Clustering Phase --- p.43 / Chapter 4.1.2 --- The Alteration Phase --- p.44 / Chapter 4.2 --- Data Structures --- p.47 / Chapter 4.2.1 --- Insertion of Elements to a Linked List --- p.54 / Chapter 4.2.2 --- Dynamic Linking of Segments --- p.56 / Chapter 4.2.3 --- Advantages of the Dynamic Data Structure --- p.59 / Chapter 4.3 --- Data Manipulation and File Management --- p.60 / Chapter 4.3.1 --- The Connection Lists and the Group List --- p.60 / Chapter 4.3.2 --- Description on Programs and Data Files --- p.62 / Chapter 4.3.2.1 --- The Affinity Clustering Phase --- p.63 / Chapter 4.3.2.2 --- The Alteration Phase --- p.64 / Chapter Section 5 --- Results --- p.70 / Chapter 5.1 --- Results on Affinity Clustering Phase --- p.84 / Chapter 5.2 --- Details of Affinity Clustering Procedure on Ckt. 2 and Ckt. 5 --- p.92 / Chapter 5.3 --- Results on Alteration Phase --- p.97 / Chapter 5.4 --- Details of Alteration Procedure on Ckt. 2 and Ckt. 5 --- p.101 / Chapter Section 6 --- Discussion --- p.107 / Chapter 6.1 --- Computation Time of the Algorithm --- p.107 / Chapter 6.2 --- Alternative Methods on the Determination of Propagation Path --- p.110 / Chapter 6.2.1 --- Method 1 --- p.110 / Chapter 6.2.2 --- Method 2 --- p.111 / Chapter 6.2.3 --- Method 3 --- p.114 / Chapter 6.2.4 --- Comparison on Execution Time of the Four Methods --- p.117 / Chapter 6.3 --- Wiring Optimization --- p.118 / Chapter 6.3.1 --- Data Structure --- p.119 / Chapter 6.3.2 --- Overlapping and Separate Bounding Boxes --- p.120 / Chapter 6.4 --- Generalization of the Data Structure --- p.122 / Chapter 6.4.1 --- Cell Types --- p.123 / Chapter 6.4.2 --- Adhesive Attributes --- p.124 / Chapter 6.4.3 --- Blocks Representation --- p.124 / Chapter 6.4.4 --- Critical Path Adjustment --- p.125 / Chapter 6.4.5 --- Total Interconnection Length Estimation --- p.129 / Chapter 6.5 --- A New Placement Algorithm --- p.130 / Chapter 6.6 --- An Alternative Method on Element Allocation --- p.132 / Chapter Section 7 --- Conclusion --- p.136 / Chapter Section 8 --- References --- p.138 / Chapter Section 9 --- Appendix I --- p.142 / Chapter 9.1 --- Definition of the Problem --- p.142 / Chapter 9.2 --- The Simulated Annealing Algorithm --- p.142 / Chapter 9.3 --- Example Circuit --- p.143 / Chapter 9.4 --- Performance Indices and Energy Value --- p.144 / Chapter 9.4.1 --- Total Interconnection Length --- p.144 / Chapter 9.4.2 --- Delay on Critical Paths --- p.144 / Chapter 9.4.3 --- Skew in Input-to-Output Delays --- p.146 / Chapter 9.4.4 --- Energy Value --- p.146 / Chapter 9.5 --- The Simulation Program --- p.146 / Chapter 9.5.1 --- "The ""function"" Subroutines" --- p.147 / Chapter 9.5.1.1 --- alise --- p.147 / Chapter 9.5.1.2 --- max delay --- p.147 / Chapter 9.5.1.3 --- replace --- p.147 / Chapter 9.5.1.4 --- total length --- p.147 / Chapter 9.5.2 --- "The ""procedure"" Subroutines" --- p.148 / Chapter 9.5.2.1 --- init_weight --- p.148 / Chapter 9.5.2.2 --- inverse --- p.148 / Chapter 9.5.2.3 --- initial --- p.148 / Chapter 9.5.2.4 --- shuffle --- p.148 / Chapter 9.5.3 --- The Main Program --- p.148 / Chapter 9.6 --- Results and Discussion --- p.149 / Chapter 9.7 --- Summary --- p.156 / Chapter 9.8 --- References --- p.156 / Chapter Section 10 --- Appendix II --- p.157
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_318812 |
| Date | January 1990 |
| Contributors | Cheung, Tsz Shing., Chinese University of Hong Kong Graduate School. Division of Electronic Engineering. |
| Publisher | Chinese University of Hong Kong |
| Source Sets | The Chinese University of Hong Kong |
| Language | English |
| Detected Language | English |
| Type | Text, bibliography |
| Format | print, 160 leaves : ill. ; 30 cm. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0035 seconds