An incremental alternation placement algorithm for macrocell array design.

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
http://library.cuhk.edu.hk/record=b5886910
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/)