published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

This thesis addresses the problem of constructing a flawless subarray from a defective VLSI/WSI array consists of identical cells such as memory cells or processors. In contrast to the redundancy approach in which some cells are dedicated as spares, all the cells in the degradation approach are treated in a uniform way. Each cell can be either fault-free or defective and a subarray which contains no faulty cell is derived under constraints of switching and routing mechanisms. Although extensive literatures exist concerning spare allocation and reconfiguration in arrays with redundancy, little research has been published on optimal reconfiguration in a degradable array. A systematic method based on graph theoretic models is developed to deal with the problem. The complexities of reconfiguration are analyzed for schemes using different switching mechanisms. Efficient heuristic algorithms are presented to determine a target subarray from the defective host array.

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

Yuen Wing-seung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves [116]-[122]). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / List of Figures --- p.viii / List of Tables --- p.xii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations and Aims --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Dissertation Overview --- p.4 / Chapter 2 --- Physical Design and Floorplanning in VLSI Circuits --- p.6 / Chapter 2.1 --- VLSI Design Flow --- p.6 / Chapter 2.2 --- Floorplan Design --- p.8 / Chapter 2.2.1 --- Problem Formulation --- p.9 / Chapter 2.2.2 --- Types of Floorplan --- p.10 / Chapter 3 --- Floorplanning Representations --- p.12 / Chapter 3.1 --- Polish Expression(PE) [WL86] --- p.12 / Chapter 3.2 --- Bounded-Sliceline-Grid(BSG) [NFMK96] --- p.14 / Chapter 3.3 --- Sequence Pair(SP) [MFNK95] --- p.17 / Chapter 3.4 --- O-tree(OT) [GCY99] --- p.19 / Chapter 3.5 --- B*-tree(BT) [CCWW00] --- p.21 / Chapter 3.6 --- Corner Block List(CBL) [HHC+00] --- p.22 / Chapter 4 --- Optimization Technique in Floorplan Design --- p.27 / Chapter 4.1 --- General Optimization Methods --- p.27 / Chapter 4.1.1 --- Simulated Annealing --- p.27 / Chapter 4.1.2 --- Genetic Algorithm --- p.29 / Chapter 4.1.3 --- Integer Programming Method --- p.31 / Chapter 4.2 --- Shape Optimization --- p.33 / Chapter 4.2.1 --- Shape Curve --- p.33 / Chapter 4.2.2 --- Lagrangian Relaxation --- p.34 / Chapter 5 --- Literature Review on Interconnect Driven Floorplanning --- p.37 / Chapter 5.1 --- Placement Constraint in Floorplan Design --- p.37 / Chapter 5.1.1 --- Boundary Constraints --- p.37 / Chapter 5.1.2 --- Pre-placed Constraints --- p.39 / Chapter 5.1.3 --- Range Constraints --- p.41 / Chapter 5.1.4 --- Symmetry Constraints --- p.42 / Chapter 5.2 --- Timing Analysis Method --- p.43 / Chapter 5.3 --- Buffer Block Planning and Congestion Control --- p.45 / Chapter 5.3.1 --- Buffer Block Planning --- p.45 / Chapter 5.3.2 --- Congestion Control --- p.50 / Chapter 6 --- Clustering Constraint in Floorplan Design --- p.53 / Chapter 6.1 --- Problem Definition --- p.53 / Chapter 6.2 --- Overview --- p.54 / Chapter 6.3 --- Locating Neighboring Modules --- p.56 / Chapter 6.4 --- Constraint Satisfaction --- p.62 / Chapter 6.5 --- Multi-clustering Extension --- p.64 / Chapter 6.6 --- Cost Function --- p.64 / Chapter 6.7 --- Experimental Results --- p.65 / Chapter 7 --- Interconnect Driven Multilevel Floorplanning Approach --- p.69 / Chapter 7.1 --- Multilevel Partitioning --- p.69 / Chapter 7.1.1 --- Coarsening Phase --- p.70 / Chapter 7.1.2 --- Refinement Phase --- p.70 / Chapter 7.2 --- Overview of Multilevel Floorplanner --- p.72 / Chapter 7.3 --- Clustering Phase --- p.73 / Chapter 7.3.1 --- Clustering Methods --- p.73 / Chapter 7.3.2 --- Area Ratio Constraints --- p.75 / Chapter 7.3.3 --- Clustering Velocity --- p.76 / Chapter 7.4 --- Refinement Phase --- p.77 / Chapter 7.4.1 --- Temperature Control --- p.79 / Chapter 7.4.2 --- Cost Function --- p.80 / Chapter 7.4.3 --- Handling Shape Flexibility --- p.80 / Chapter 7.5 --- Experimental Results --- p.81 / Chapter 7.5.1 --- Data Set Generation --- p.82 / Chapter 7.5.2 --- Temperature Control --- p.82 / Chapter 7.5.3 --- Packing Results --- p.83 / Chapter 8 --- Study of Non-slicing Floorplan Representations --- p.89 / Chapter 8.1 --- Analysis of Different Floorplan Representations --- p.89 / Chapter 8.1.1 --- Complexity --- p.90 / Chapter 8.1.2 --- Types of Floorplans --- p.92 / Chapter 8.2 --- T-junction Orientation Property --- p.97 / Chapter 8.3 --- Twin Binary Tree Representation for Mosaic Floorplan --- p.103 / Chapter 8.3.1 --- Previous work --- p.103 / Chapter 8.3.2 --- Twin Binary Tree Construction --- p.105 / Chapter 8.3.3 --- Floorplan Construction --- p.109 / Chapter 9 --- Conclusion --- p.114 / Chapter 9.1 --- Summary --- p.114 / Bibliography --- p.116 / Chapter A --- Clustering Constraint Data Set --- p.123 / Chapter A.1 --- ami33 --- p.123 / Chapter A.1.1 --- One cluster --- p.123 / Chapter A.1.2 --- Multi-cluster --- p.123 / Chapter A.2 --- ami49 --- p.124 / Chapter A.2.1 --- One cluster --- p.124 / Chapter A.2.2 --- Multi-cluster --- p.124 / Chapter A.3 --- playout --- p.124 / Chapter A.3.1 --- One cluster --- p.124 / Chapter A.3.2 --- Multi-cluster --- p.125 / Chapter B --- Multilevel Data Set --- p.126 / Chapter B.l --- data_100 --- p.126 / Chapter B.2 --- data_200 --- p.127 / Chapter B.3 --- data_300 --- p.129 / Chapter B.4 --- data_400 --- p.131 / Chapter B.5 --- data_500 --- p.133

Wong Sze Hon. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 88-91). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Preliminaries --- p.1 / Chapter 1.2 --- Motivations --- p.1 / Chapter 1.3 --- Contributions --- p.3 / Chapter 1.4 --- Organization of the Thesis --- p.4 / Chapter 2 --- VLSI Physical Design Automation --- p.5 / Chapter 2.1 --- Preliminaries --- p.5 / Chapter 2.2 --- VLSI Design Cycle [1] --- p.6 / Chapter 2.2.1 --- System Specification --- p.6 / Chapter 2.2.2 --- Architectural Design --- p.6 / Chapter 2.2.3 --- Functional Design --- p.6 / Chapter 2.2.4 --- Logic Design --- p.8 / Chapter 2.2.5 --- Circuit Design --- p.8 / Chapter 2.2.6 --- Physical Design --- p.8 / Chapter 2.2.7 --- Fabrication --- p.8 / Chapter 2.2.8 --- Packaging and Testing --- p.9 / Chapter 2.3 --- Physical Design Cycle [1] --- p.9 / Chapter 2.3.1 --- Partitioning --- p.9 / Chapter 2.3.2 --- Floorplanning and Placement --- p.11 / Chapter 2.3.3 --- Routing --- p.11 / Chapter 2.3.4 --- Compaction --- p.12 / Chapter 2.3.5 --- Extraction and Verification --- p.12 / Chapter 2.4 --- Chapter Summary --- p.12 / Chapter 3 --- Recent Approaches on Circuit Partitioning --- p.14 / Chapter 3.1 --- Preliminaries --- p.14 / Chapter 3.2 --- Circuit Representation --- p.15 / Chapter 3.3 --- Delay Modelling --- p.16 / Chapter 3.4 --- Partitioning Objectives --- p.19 / Chapter 3.4.1 --- Interconnections between Partitions --- p.19 / Chapter 3.4.2 --- Delay Minimization --- p.19 / Chapter 3.4.3 --- Area and Number of Partitions --- p.20 / Chapter 3.5 --- Partitioning Algorithms --- p.20 / Chapter 3.5.1 --- Cut-size Driven Partitioning Algorithm --- p.21 / Chapter 3.5.2 --- Delay Driven Partitioning Algorithm --- p.32 / Chapter 3.5.3 --- Acyclic Circuit Partitioning Algorithm --- p.33 / Chapter 4 --- Clustering Based Acyclic Multi-way Partitioning --- p.38 / Chapter 4.1 --- Preliminaries --- p.38 / Chapter 4.2 --- Previous Works on Clustering Based Partitioning --- p.39 / Chapter 4.2.1 --- Multilevel Circuit Partitioning [2] --- p.40 / Chapter 4.2.2 --- Cluster-Oriented Iterative-Improvement Partitioner [3] --- p.42 / Chapter 4.2.3 --- Section Summary --- p.44 / Chapter 4.3 --- Problem Formulation --- p.45 / Chapter 4.4 --- Clustering Based Acyclic Multi-Way Partitioning --- p.46 / Chapter 4.5 --- Modified Fan-out Free Cone Decomposition --- p.47 / Chapter 4.6 --- Clustering Phase --- p.48 / Chapter 4.7 --- Partitioning Phase --- p.51 / Chapter 4.8 --- The Acyclic Constraint --- p.52 / Chapter 4.9 --- Experimental Results --- p.57 / Chapter 4.10 --- Chapter Summary --- p.58 / Chapter 5 --- Network Flow Based Multi-way Partitioning --- p.61 / Chapter 5.1 --- Preliminaries --- p.61 / Chapter 5.2 --- Notations and Definitions --- p.62 / Chapter 5.3 --- Net Modelling --- p.63 / Chapter 5.4 --- Previous Works on Network Flow Based Partitioning --- p.64 / Chapter 5.4.1 --- Network Flow Based Min-Cut Balanced Partitioning [4] --- p.65 / Chapter 5.4.2 --- Network Flow Based Circuit Partitioning for Time-multiplexed FPGAs [5] --- p.66 / Chapter 5.5 --- Proposed Net Modelling --- p.70 / Chapter 5.6 --- Partitioning Properties Based on the Proposed Net Modelling --- p.73 / Chapter 5.7 --- Partitioning Step --- p.75 / Chapter 5.8 --- Constrained FM Post Processing Step --- p.79 / Chapter 5.9 --- Experiment Results --- p.81 / Chapter 6 --- Conclusion --- p.86 / Bibliography --- p.88

Li, Liang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Partitioning --- p.1 / Chapter 1.1.2 --- Floorplanning and Placement --- p.2 / Chapter 1.1.3 --- Routing --- p.2 / Chapter 1.1.4 --- Compaction --- p.3 / Chapter 1.2 --- Motivations --- p.3 / Chapter 1.3 --- Problem Formulation --- p.4 / Chapter 1.3.1 --- Properties of OARSMT --- p.4 / Chapter 1.4 --- Progress on the Problem --- p.4 / Chapter 1.5 --- Contributions --- p.5 / Chapter 1.6 --- Thesis Organization --- p.6 / Chapter 2 --- Literature Review on OARSMT --- p.8 / Chapter 2.1 --- Introduction --- p.8 / Chapter 2.2 --- Previous Methods --- p.9 / Chapter 2.2.1 --- OARSMT --- p.9 / Chapter 2.2.2 --- Shortest Path Problem with Blockages --- p.13 / Chapter 2.2.3 --- OARSMT with Delay Minimization --- p.14 / Chapter 2.2.4 --- OARSMT with Worst Negative Slack Maximization --- p.14 / Chapter 2.3 --- Comparison --- p.15 / Chapter 3 --- Heuristic Method --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.2 --- Our Approach --- p.18 / Chapter 3.2.1 --- Handling of Multi-pin Nets --- p.18 / Chapter 3.2.2 --- Propagation --- p.20 / Chapter 3.2.3 --- Backtrack --- p.23 / Chapter 3.2.4 --- Finding MST --- p.26 / Chapter 3.2.5 --- Local Refinement Scheme --- p.26 / Chapter 3.3 --- Experimental Results --- p.28 / Chapter 3.4 --- Summary --- p.28 / Chapter 4 --- Exact Method --- p.32 / Chapter 4.1 --- Introduction --- p.32 / Chapter 4.2 --- Review on GeoSteiner --- p.33 / Chapter 4.3 --- Overview of our Approach --- p.33 / Chapter 4.4 --- FST with Virtual Pins --- p.34 / Chapter 4.4.1 --- Definition of FST --- p.34 / Chapter 4.4.2 --- Notations --- p.36 / Chapter 4.4.3 --- Properties of FST with Virtual Pins --- p.36 / Chapter 4.5 --- Generation of FST with Virtual Pins --- p.46 / Chapter 4.5.1 --- Generation of FST with Two Pins --- p.46 / Chapter 4.5.2 --- Generation of FST with 3 or More Pins --- p.48 / Chapter 4.6 --- Concatenation of FSTs with Virtual Pins --- p.50 / Chapter 4.7 --- Experimental Results --- p.52 / Chapter 4.8 --- Summary --- p.53 / Chapter 5 --- Conclusion --- p.55 / Bibliography --- p.61

Bibliography: leaves 282-296.

Not available / text

Not available / text

Not available / text