by H.S. Ng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 91-97). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Neuro-connectionist Network --- p.2 / Chapter 2 --- Related Works --- p.5 / Chapter 2.1 --- Introduction --- p.5 / Chapter 2.1.1 --- Kruskal's Algorithm --- p.5 / Chapter 2.1.2 --- Prim's algorithm --- p.6 / Chapter 2.1.3 --- Sollin's algorithm --- p.7 / Chapter 2.1.4 --- Bellman-Ford algorithm --- p.8 / Chapter 2.1.5 --- Floyd-Warshall algorithm --- p.9 / Chapter 3 --- Binary Relation Inference Network and Path Problems --- p.11 / Chapter 3.1 --- Introduction --- p.11 / Chapter 3.2 --- Topology --- p.12 / Chapter 3.3 --- Network structure --- p.13 / Chapter 3.3.1 --- Single-destination BRIN architecture --- p.14 / Chapter 3.3.2 --- Comparison between all-pair BRIN and single-destination BRIN --- p.18 / Chapter 3.4 --- Path Problems and BRIN Solution --- p.18 / Chapter 3.4.1 --- Minimax path problems --- p.18 / Chapter 3.4.2 --- BRIN solution --- p.19 / Chapter 4 --- Analog and Voltage-mode Approach --- p.22 / Chapter 4.1 --- Introduction --- p.22 / Chapter 4.2 --- Analog implementation --- p.24 / Chapter 4.3 --- Voltage-mode approach --- p.26 / Chapter 4.3.1 --- The site function --- p.26 / Chapter 4.3.2 --- The unit function --- p.28 / Chapter 4.3.3 --- The computational unit --- p.28 / Chapter 4.4 --- Conclusion --- p.29 / Chapter 5 --- Current-mode Approach --- p.32 / Chapter 5.1 --- Introduction --- p.32 / Chapter 5.2 --- Current-mode approach for analog VLSI Implementation --- p.33 / Chapter 5.2.1 --- Site and Unit output function --- p.33 / Chapter 5.2.2 --- Computational unit --- p.34 / Chapter 5.2.3 --- A complete network --- p.35 / Chapter 5.3 --- Conclusion --- p.37 / Chapter 6 --- Neural Network Compensation for Optimization Circuit --- p.40 / Chapter 6.1 --- Introduction --- p.40 / Chapter 6.2 --- A Neuro-connectionist Architecture for error correction --- p.41 / Chapter 6.2.1 --- Linear Relationship --- p.42 / Chapter 6.2.2 --- Output Deviation of Computational Unit --- p.44 / Chapter 6.3 --- Experimental Results --- p.46 / Chapter 6.3.1 --- Training Phase --- p.46 / Chapter 6.3.2 --- Generalization Phase --- p.48 / Chapter 6.4 --- Conclusion --- p.50 / Chapter 7 --- Precision-limited Analog Neural Network Compensation --- p.51 / Chapter 7.1 --- Introduction --- p.51 / Chapter 7.2 --- Analog Neural Network hardware --- p.53 / Chapter 7.3 --- Integration of analog neural network compensation of connectionist net- work for general path problems --- p.54 / Chapter 7.4 --- Experimental Results --- p.55 / Chapter 7.4.1 --- Convergence time --- p.56 / Chapter 7.4.2 --- The accuracy of the system --- p.57 / Chapter 7.5 --- Conclusion --- p.58 / Chapter 8 --- Transitive Closure Problems --- p.60 / Chapter 8.1 --- Introduction --- p.60 / Chapter 8.2 --- Different ways of implementation of BRIN for transitive closure --- p.61 / Chapter 8.2.1 --- Digital Implementation --- p.61 / Chapter 8.2.2 --- Analog Implementation --- p.61 / Chapter 8.3 --- Transitive Closure Problem --- p.63 / Chapter 8.3.1 --- A special case of maximum spanning tree problem --- p.64 / Chapter 8.3.2 --- Analog approach solution for transitive closure problem --- p.65 / Chapter 8.3.3 --- Current-mode approach solution for transitive closure problem --- p.67 / Chapter 8.4 --- Comparisons between the different forms of implementation of BRIN for transitive closure --- p.71 / Chapter 8.4.1 --- Convergence Time --- p.71 / Chapter 8.4.2 --- Circuit complexity --- p.72 / Chapter 8.5 --- Discussion --- p.73 / Chapter 9 --- Critical path problems --- p.74 / Chapter 9.1 --- Introduction --- p.74 / Chapter 9.2 --- Problem statement and single-destination BRIN solution --- p.75 / Chapter 9.3 --- Analog implementation --- p.76 / Chapter 9.3.1 --- Separated building block --- p.78 / Chapter 9.3.2 --- Combined building block --- p.79 / Chapter 9.4 --- Current-mode approach --- p.80 / Chapter 9.4.1 --- "Site function, unit output function and a completed network" --- p.80 / Chapter 9.5 --- Conclusion --- p.83 / Chapter 10 --- Conclusions --- p.85 / Chapter 10.1 --- Summary of Achievements --- p.85 / Chapter 10.2 --- Future development --- p.88 / Chapter 10.2.1 --- Application for financial problems --- p.88 / Chapter 10.2.2 --- Fabrication of VLSI Implementation --- p.88 / Chapter 10.2.3 --- Actual prototyping of Analog Integrated Circuits for critical path and transitive closure problems --- p.89 / Chapter 10.2.4 --- Other implementation platform --- p.89 / Chapter 10.2.5 --- On-line update of routing table inside the router for network com- munication using BRIN --- p.89 / Chapter 10.2.6 --- Other BRIN's applications --- p.90 / Bibliography --- p.91

by Lam Shiu-chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 107-113). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Task Scheduling Problem and Lower Bound --- p.3 / Chapter 1.3 --- Organization of the Thesis --- p.4 / Chapter 2 --- Teamwork-Task Scheduling Problem --- p.5 / Chapter 2.1 --- Problem Statement and Notations --- p.5 / Chapter 2.2 --- Classification of Scheduling --- p.7 / Chapter 2.3 --- Computational Complexity --- p.9 / Chapter 2.4 --- Literature Review --- p.12 / Chapter 2.4.1 --- Unrelated Machines Scheduling Environment --- p.12 / Chapter 2.4.2 --- Multiprocessors Scheduling Problem --- p.13 / Chapter 2.4.3 --- Search Algorithms --- p.14 / Chapter 2.4.4 --- Lower Bounds --- p.15 / Chapter 2.5 --- Summary --- p.17 / Chapter 3 --- Fundamentals of Genetic Algorithms --- p.18 / Chapter 3.1 --- Initial Inspiration --- p.18 / Chapter 3.2 --- An Elementary Genetic Algorithm --- p.20 / Chapter 3.2.1 --- "Genes, Chromosomes and Representations" --- p.20 / Chapter 3.2.2 --- Population Pool --- p.22 / Chapter 3.2.3 --- Evaluation Module --- p.22 / Chapter 3.2.4 --- Reproduction Module --- p.22 / Chapter 3.2.5 --- Genetic Operators: Crossover and Mutation --- p.23 / Chapter 3.2.6 --- Parameters --- p.24 / Chapter 3.3 --- A Brief Note to the Background Theory --- p.25 / Chapter 3.4 --- Key Factors for the Success --- p.27 / Chapter 4 --- Tasks Scheduling using Genetic Algorithms --- p.28 / Chapter 4.1 --- Details of Scheduling Problem --- p.28 / Chapter 4.2 --- Chromosome Coding --- p.32 / Chapter 4.2.1 --- Job Priority Sequence --- p.33 / Chapter 4.2.2 --- Engineer Priority Sequence --- p.33 / Chapter 4.2.3 --- An Example Chromosome Interpretation --- p.34 / Chapter 4.3 --- Fitness Evaluation --- p.37 / Chapter 4.4 --- Parent Selection --- p.38 / Chapter 4.5 --- Genetic Operators and Reproduction --- p.40 / Chapter 4.5.1 --- Job Priority Crossover (JOB-CRX) --- p.40 / Chapter 4.5.2 --- Job Priority Mutation (JOB-MUT) --- p.40 / Chapter 4.5.3 --- Engineer Priority Mutation (ENG-MUT) --- p.42 / Chapter 4.5.4 --- Reproduction: New Population --- p.42 / Chapter 4.6 --- Replacement Strategy --- p.43 / Chapter 4.7 --- The Complete Genetic Algorithm --- p.44 / Chapter 5 --- Lower Bound on Optimal Makespan --- p.46 / Chapter 5.1 --- Introduction --- p.46 / Chapter 5.2 --- Definitions and Assumptions --- p.48 / Chapter 5.2.1 --- Task Graph --- p.48 / Chapter 5.2.2 --- Graph Partitioning --- p.49 / Chapter 5.2.3 --- Activity and Load Density --- p.51 / Chapter 5.2.4 --- Assumptions --- p.52 / Chapter 5.3 --- Concepts of Lower Bound on the Minimal Time (LBMT) --- p.53 / Chapter 5.3.1 --- Previous Bound (LBMTF) --- p.53 / Chapter 5.3.2 --- Bound in other form --- p.54 / Chapter 5.3.3 --- Improved Bound (LBMTJR） --- p.56 / Chapter 5.4 --- Lower bound: Task graph reconstruction + LBMTJR --- p.59 / Chapter 5.4.1 --- Problem reduction and Assumptions --- p.60 / Chapter 5.4.2 --- Scenario I --- p.61 / Chapter 5.4.3 --- Scenario II --- p.63 / Chapter 5.4.4 --- An Example --- p.67 / Chapter 6 --- Computational Results and Discussions --- p.73 / Chapter 6.1 --- Parameterization of the GA --- p.73 / Chapter 6.2 --- Computational Results --- p.75 / Chapter 6.3 --- Performance Evaluation --- p.81 / Chapter 6.3.1 --- Solution Quality --- p.81 / Chapter 6.3.2 --- Computational Complexity --- p.86 / Chapter 6.4 --- Effects of Machines Eligibility --- p.88 / Chapter 6.5 --- Future Direction --- p.90 / Chapter 7 --- Conclusion --- p.92 / Chapter A --- Tasks data of problem sets in section 6.2 --- p.94 / Chapter A.l --- Problem 1: 19 tasks --- p.95 / Chapter A.2 --- Problem 2: 21 tasks --- p.97 / Chapter A.3 --- Problem 3: 19 tasks --- p.99 / Chapter A.4 --- Problem 4: 23 tasks --- p.101 / Chapter A.5 --- Problem 5: 27 tasks --- p.104 / Bibliography --- p.107

Lee Chi-wai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 191-196). / Abstracts in English and Chinese. / Abstract of this thesis entitled: --- p.i / 摘要 --- p.iii / Acknowledgements --- p.v / Table of Contents --- p.vii / List of Tables --- p.x / List of Figures --- p.xi / Chapter Chapter1 --- Introduction --- p.1 / Chapter 1.1 --- Synchronous Design --- p.1 / Chapter 1.2 --- Asynchronous Design --- p.2 / Chapter 1.3 --- Discrete Cosine Transform --- p.4 / Chapter 1.4 --- Motivation --- p.5 / Chapter 1.5 --- Organization of the Thesis --- p.6 / Chapter Chapter2 --- Asynchronous Design Methodology --- p.7 / Chapter 2.1 --- Overview --- p.7 / Chapter 2.2 --- Background --- p.8 / Chapter 2.3 --- Past Designs --- p.10 / Chapter 2.4 --- Micropipeline --- p.12 / Chapter 2.5 --- New Asynchronous Architecture --- p.15 / Chapter Chapter3 --- DCT/IDCT Processor Design Methodology --- p.24 / Chapter 3.1 --- Overview --- p.24 / Chapter 3.2 --- Hardware Architecture --- p.25 / Chapter 3.3 --- DCT Algorithm --- p.26 / Chapter 3.4 --- Used Architecture and DCT Algorithm --- p.30 / Chapter 3.4.1 --- Implementation on Programmable DSP Processor --- p.31 / Chapter 3.4.2 --- Implementation on Dedicated Processor --- p.33 / Chapter Chapter4 --- New Techniques for Operating Dynamic Logic in Low Frequency --- p.36 / Chapter 4.1 --- Overview --- p.36 / Chapter 4.2 --- Background --- p.37 / Chapter 4.3 --- Traditional Technique --- p.39 / Chapter 4.4 --- New Technique - Refresh Control Circuit --- p.40 / Chapter 4.4.1 --- Principle --- p.41 / Chapter 4.4.2 --- Voltage Sensor --- p.42 / Chapter 4.4.3 --- Ring Oscillator --- p.43 / Chapter 4.4.4 --- "Counter, Latch and Comparator" --- p.46 / Chapter 4.4.5 --- Recalibrate Circuit --- p.47 / Chapter 4.4.6 --- Operation Monitoring Circuit --- p.48 / Chapter 4.4.7 --- Overall Circuit --- p.48 / Chapter Chapter5 --- DCT Implementation on Programmable DSP Processor --- p.51 / Chapter 5.1 --- Overview --- p.51 / Chapter 5.2 --- Processor Architecture --- p.52 / Chapter 5.2.1 --- Arithmetic Unit --- p.53 / Chapter 5.2.2 --- Switching Network --- p.56 / Chapter 5.2.3 --- FIFO Memory --- p.59 / Chapter 5.2.4 --- Instruction Memory --- p.60 / Chapter 5.3 --- Programming --- p.62 / Chapter 5.4 --- DCT Implementation --- p.63 / Chapter Chapter6 --- DCT Implementation on Dedicated DCT Processor --- p.66 / Chapter 6.1 --- Overview --- p.66 / Chapter 6.2 --- DCT Chip Architecture --- p.67 / Chapter 6.2.1 --- ID DCT Core --- p.68 / Chapter 6.2.1.1 --- Core Architecture --- p.74 / Chapter 6.2.1.2 --- Flow of Operation --- p.76 / Chapter 6.2.1.3 --- Data Replicator --- p.79 / Chapter 6.2.1.4 --- DCT Coefficients Memory --- p.80 / Chapter 6.2.2 --- Combination of IDCT to 1D DCT core --- p.82 / Chapter 6.2.3 --- Accuracy --- p.85 / Chapter 6.3 --- Transpose Memory --- p.87 / Chapter 6.3.1 --- Architecture --- p.89 / Chapter 6.3.2 --- Address Generator --- p.91 / Chapter 6.3.3 --- RAM Block --- p.94 / Chapter Chapter7 --- Results and Discussions --- p.97 / Chapter 7.1 --- Overview --- p.97 / Chapter 7.2 --- Refresh Control Circuit --- p.97 / Chapter 7.2.1 --- Implementation Results and Performance --- p.97 / Chapter 7.2.2 --- Discussion --- p.100 / Chapter 7.3 --- Programmable DSP Processor --- p.102 / Chapter 7.3.1 --- Implementation Results and Performance --- p.102 / Chapter 7.3.2 --- Discussion --- p.104 / Chapter 7.4 --- ID DCT/IDCT Core --- p.107 / Chapter 7.4.1 --- Simulation Results --- p.107 / Chapter 7.4.2 --- Measurement Results --- p.109 / Chapter 7.4.3 --- Discussion --- p.113 / Chapter 7.5 --- Transpose Memory --- p.122 / Chapter 7.5.1 --- Simulated Results --- p.122 / Chapter 7.5.2 --- Measurement Results --- p.123 / Chapter 7.5.3 --- Discussion --- p.126 / Chapter Chapter8 --- Conclusions --- p.130 / Appendix --- p.133 / Operations of switches in DCT implementation of programmable DSP processor --- p.133 / C Program for evaluating the error in DCT/IDCT core --- p.135 / Pin Assignments of the Programmable DSP Processor Chip --- p.142 / Pin Assignments of the 1D DCT/IDCT Core Chip --- p.144 / Pin Assignments of the Transpose Memory Chip --- p.147 / Chip microphotograph of the 1D DCT/IDCT core --- p.150 / Chip Microphotograph of the Transpose Memory --- p.151 / Measured Waveforms of 1D DCT/IDCT Chip --- p.152 / Measured Waveforms of Transpose Memory Chip --- p.156 / Schematics of Refresh Control Circuit --- p.158 / Schematics of Programmable DSP Processor --- p.164 / Schematics of 1D DCT/IDCT Core --- p.180 / Schematics of Transpose Memory --- p.187 / References --- p.191 / Design Libraries - CD-ROM --- p.197

Sham Chiu Wing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 107-113). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.1 / Chapter 1.2 --- Progress on the Problem --- p.2 / Chapter 1.3 --- Our Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.5 / Chapter 2 --- Preliminaries --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.1.1 --- The Role of Floorplanning --- p.6 / Chapter 2.1.2 --- Wirelength Estimation --- p.7 / Chapter 2.1.3 --- Different Types of Floorplan --- p.8 / Chapter 2.2 --- Representations of Floorplan --- p.10 / Chapter 2.2.1 --- Polish Expressions --- p.10 / Chapter 2.2.2 --- Sequence Pair --- p.11 / Chapter 2.2.3 --- Bounded-Sliceline Grid (BSG) Structure --- p.13 / Chapter 2.2.4 --- O-Tree --- p.14 / Chapter 2.2.5 --- B*-Tree --- p.16 / Chapter 2.2.6 --- Corner Block List --- p.18 / Chapter 2.2.7 --- Twin Binary Tree --- p.19 / Chapter 2.2.8 --- Comparisons between Different Representations --- p.20 / Chapter 2.3 --- Algorithms of Floorplan Design --- p.20 / Chapter 2.3.1 --- Constraint Based Floorplanning --- p.21 / Chapter 2.3.2 --- Integer Programming Based Floorplanning --- p.21 / Chapter 2.3.3 --- Neural Learning Based Floorplanning --- p.22 / Chapter 2.3.4 --- Rectangular Dualization --- p.22 / Chapter 2.3.5 --- Simulated Annealing --- p.23 / Chapter 2.3.6 --- Genetic Algorithm --- p.23 / Chapter 2.4 --- Summary --- p.24 / Chapter 3 --- Literature Review on Interconnect-Driven Floorplanning --- p.25 / Chapter 3.1 --- Introduction --- p.25 / Chapter 3.2 --- Simulated Annealing Approach --- p.25 / Chapter 3.2.1 --- """Pepper - A Timing Driven Early Floorplanner""" --- p.25 / Chapter 3.2.2 --- """A Timing Driven Block Placer Based on Sequence Pair Model""" --- p.26 / Chapter 3.2.3 --- """Integrated Floorplanning and Interconnect Planning""" --- p.27 / Chapter 3.2.4 --- """Interconnect Driven Floorplanning with Fast Global Wiring Planning and Optimization""" --- p.27 / Chapter 3.3 --- Genetic Algorithm Approach --- p.28 / Chapter 3.3.1 --- "“Timing Influenced General-cell Genetic Floorplanning""" --- p.28 / Chapter 3.4 --- Force Directed Approach --- p.29 / Chapter 3.4.1 --- """Timing Influenced Force Directed Floorplanning""" --- p.29 / Chapter 3.5 --- Congestion Planning --- p.30 / Chapter 3.5.1 --- """On the Behavior of Congestion Minimization During Placement""" --- p.30 / Chapter 3.5.2 --- """Congestion Minimization During Placement""" --- p.31 / Chapter 3.5.3 --- "“Estimating Routing Congestion Using Probabilistic Anal- ysis""" --- p.31 / Chapter 3.6 --- Buffer Planning --- p.32 / Chapter 3.6.1 --- """Buffer Block Planning for Interconnect Driven Floor- planning""" --- p.32 / Chapter 3.6.2 --- """Routability Driven Repeater Block Planning for Interconnect- centric Floorplanning""" --- p.33 / Chapter 3.6.3 --- """Provably Good Global Buffering Using an Available Block Plan""" --- p.34 / Chapter 3.6.4 --- "“Planning Buffer Locations by Network Flows""" --- p.34 / Chapter 3.6.5 --- """A Practical Methodology for Early Buffer and Wire Re- source Allocation""" --- p.35 / Chapter 3.7 --- Summary --- p.36 / Chapter 4 --- Floorplanner with Fixed Buffer Planning [34] --- p.37 / Chapter 4.1 --- Introduction --- p.37 / Chapter 4.2 --- Overview of the Floorplanner --- p.38 / Chapter 4.3 --- Congestion Model --- p.38 / Chapter 4.3.1 --- Construction of Grid Structure --- p.39 / Chapter 4.3.2 --- Counting the Number of Routes at a Grid --- p.40 / Chapter 4.3.3 --- Buffer Location Computation --- p.41 / Chapter 4.3.4 --- Counting Routes with Blocked Grids --- p.42 / Chapter 4.3.5 --- Computing the Probability of Net Crossing --- p.43 / Chapter 4.4 --- Time Complexity --- p.44 / Chapter 4.5 --- Simulated Annealing --- p.45 / Chapter 4.6 --- Wirelength Estimation --- p.46 / Chapter 4.6.1 --- Center-to-center Estimation --- p.47 / Chapter 4.6.2 --- Corner-to-corner Estimation --- p.47 / Chapter 4.6.3 --- Intersection-to-intersection Estimation --- p.48 / Chapter 4.7 --- Multi-pin Nets Handling --- p.49 / Chapter 4.8 --- Experimental Results --- p.50 / Chapter 4.9 --- Summary --- p.51 / Chapter 5 --- Floorplanner with Flexible Buffer Planning [35] --- p.53 / Chapter 5.1 --- Introduction --- p.53 / Chapter 5.2 --- Overview of the Floorplanner --- p.54 / Chapter 5.3 --- Congestion Model --- p.55 / Chapter 5.3.1 --- Probabilistic Model with Variable Interval Buffer Inser- tion Constraint --- p.57 / Chapter 5.3.2 --- Time Complexity --- p.61 / Chapter 5.4 --- Buffer Planning --- p.62 / Chapter 5.4.1 --- Estimation of Buffer Usage --- p.62 / Chapter 5.4.2 --- Estimation of Buffer Resources --- p.69 / Chapter 5.5 --- Two-phases Simulated Annealing --- p.70 / Chapter 5.6 --- Wirelength Estimation --- p.72 / Chapter 5.7 --- Multi-pin Nets Handling --- p.73 / Chapter 5.8 --- Experimental Results --- p.73 / Chapter 5.9 --- Remarks --- p.76 / Chapter 5.10 --- Summary --- p.76 / Chapter 6 --- Global Router --- p.77 / Chapter 6.1 --- Introduction --- p.77 / Chapter 6.2 --- Overview of the Global Router --- p.77 / Chapter 6.3 --- Buffer Insertion Constraint and Congestion Constraint --- p.78 / Chapter 6.4 --- Multi-pin Nets Handling --- p.79 / Chapter 6.5 --- Routing Methodology --- p.79 / Chapter 6.6 --- Implementation --- p.80 / Chapter 6.7 --- Summary --- p.86 / Chapter 7 --- Interconnect-Driven Floorplanning by Alternative Packings --- p.87 / Chapter 7.1 --- Introduction --- p.87 / Chapter 7.2 --- Overview of the Method --- p.87 / Chapter 7.3 --- Searching Alternative Packings --- p.89 / Chapter 7.3.1 --- Rectangular Supermodules in Sequence Pair --- p.89 / Chapter 7.3.2 --- Finding rearrangable module sets --- p.90 / Chapter 7.3.3 --- Alternative Sequence Pairs --- p.94 / Chapter 7.4 --- Implementation --- p.97 / Chapter 7.4.1 --- Re-calculation of Interconnect Cost --- p.98 / Chapter 7.4.2 --- Cost Function --- p.101 / Chapter 7.4.3 --- Time Complexity --- p.101 / Chapter 7.5 --- Experimental Results --- p.101 / Chapter 7.6 --- Summary --- p.103 / Chapter 8 --- Conclusion --- p.105 / Bibliography --- p.107

Wong Wai-Chiu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 94-101). / Abstracts in English and Chinese. / Abstract --- p.iii / Abstract in Chinese --- p.v / Acknowledgements --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.2 / Chapter 1.2 --- Progress on Interconnect-driven Floorplanning --- p.4 / Chapter 1.2.1 --- Congestion Optimization --- p.4 / Chapter 1.2.2 --- Buffer Insertion --- p.5 / Chapter 1.3 --- Contributions --- p.6 / Chapter 1.4 --- Organization of this Thesis --- p.7 / Chapter 2 --- "VLSI Circuit Design, Physical Design Cycle and Floorplanning" --- p.8 / Chapter 2.1 --- VLSI Circuit Design Cycle --- p.9 / Chapter 2.2 --- Physical Design Cycle --- p.10 / Chapter 2.2.1 --- Circuit Partitioning --- p.10 / Chapter 2.2.2 --- Floorplanning and Placement --- p.11 / Chapter 2.2.3 --- Routing --- p.12 / Chapter 2.2.4 --- Compaction --- p.12 / Chapter 2.3 --- Introduction to Floorplanning --- p.13 / Chapter 2.4 --- Types of Floorplan --- p.14 / Chapter 2.5 --- Simulated Annealing --- p.15 / Chapter 2.6 --- Floorplan Representation --- p.16 / Chapter 2.6.1 --- Polish Expression --- p.17 / Chapter 2.6.2 --- Sequence Pair --- p.18 / Chapter 2.6.3 --- Twin Binary Tree --- p.20 / Chapter 2.6.4 --- Comparisons between Different Floorplan Representations --- p.21 / Chapter 2.7 --- Chapter Summary --- p.22 / Chapter 3 --- Interconnect Optimization in Floorplanning --- p.24 / Chapter 3.1 --- Routing Congestion Optimization --- p.25 / Chapter 3.2 --- Buffer Planning --- p.26 / Chapter 3.3 --- Wire Sizing --- p.28 / Chapter 3.4 --- Simultaneous Wire Sizing and Buffer Planning --- p.30 / Chapter 3.5 --- Literature Review on Interconnect-driven Floorplanning --- p.31 / Chapter 3.5.1 --- Congestion Optimization --- p.31 / Chapter 3.5.2 --- Buffer Insertion --- p.36 / Chapter 3.6 --- Chapter Summary --- p.40 / Chapter 4 --- Floorplanning with Congestion Optimization and Buffer Block Planning --- p.41 / Chapter 4.1 --- Floorplanner Overview --- p.42 / Chapter 4.1.1 --- Grid Structure and Blocked Grids --- p.44 / Chapter 4.1.2 --- Buffer Block Planning --- p.44 / Chapter 4.2 --- Elmore Delay Model --- p.46 / Chapter 4.2.1 --- Wire Sizing --- p.47 / Chapter 4.2.2 --- Buffer Insertion --- p.48 / Chapter 4.2.3 --- Simultaneous Buffer Insertion and Wire Sizing --- p.49 / Chapter 4.3 --- Dynamic Programming Approach for Buffer Planning and Wire Sizing --- p.49 / Chapter 4.4 --- Implementation of the Dynamic Programming Approach --- p.51 / Chapter 4.5 --- Lookup Table Construction --- p.53 / Chapter 4.6 --- Congestion Model --- p.55 / Chapter 4.7 --- Cost Function --- p.56 / Chapter 4.8 --- Algorithm --- p.56 / Chapter 4.9 --- Experimental Results --- p.57 / Chapter 4.9.1 --- Experimental Results on Simultaneous Buffer Insertion and Wire Sizing --- p.57 / Chapter 4.9.2 --- Experimental Results of using the Table Lookup Approach --- p.58 / Chapter 4.10 --- Chapter Summary --- p.60 / Chapter 5 --- Floorplanning with Flexible Buffer Planning and Routability Op- timization --- p.63 / Chapter 5.1 --- Floorplanner Overview --- p.64 / Chapter 5.1.1 --- Constraints in Buffer Locations --- p.64 / Chapter 5.2 --- Congestion Estimation --- p.66 / Chapter 5.3 --- Buffer Location Computation --- p.67 / Chapter 5.3.1 --- Feasible Locations for Buffer Insertion --- p.67 / Chapter 5.3.2 --- Cost of Grids for Buffer Insertion --- p.69 / Chapter 5.3.3 --- Dynamic Programming Approach for Selecting Buffer Lo- cation of a Net --- p.70 / Chapter 5.3.4 --- An Example --- p.70 / Chapter 5.4 --- Congestion Model --- p.72 / Chapter 5.4.1 --- Net-count Congestion Model --- p.72 / Chapter 5.4.2 --- Grid-count Congestion Model --- p.74 / Chapter 5.5 --- Buffer Location Bounds --- p.75 / Chapter 5.6 --- Net Grouping --- p.77 / Chapter 5.7 --- Cost Function --- p.79 / Chapter 5.8 --- Algorithm . --- p.79 / Chapter 5.9 --- Experimental Results --- p.79 / Chapter 5.9.1 --- Net Grouping Factor --- p.80 / Chapter 5.9.2 --- Experimental Results of our Floorplanner --- p.80 / Chapter 5.9.3 --- Comparison on Different Congestion Models --- p.82 / Chapter 5.10 --- Chapter Summary --- p.83 / Chapter 6 --- Conclusion --- p.86 / Chapter 6.1 --- Discussion --- p.87 / Chapter 6.2 --- Improvements --- p.88 / Chapter 6.2.1 --- Net Grouping and Ordering --- p.88 / Chapter 6.2.2 --- Congestion Modelling --- p.89 / Appendix --- p.90 / Chapter A --- Overview on VLSI Technology --- p.91 / Chapter A.l --- Moore's Law and Trends in VLSI --- p.91 / Chapter A.2 --- Scaling --- p.93 / Bibliography --- p.101

Ching Lap Sze. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 69-71). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Shuttle Mask --- p.2 / Chapter 1.2 --- Voltage Island --- p.6 / Chapter 1.3 --- Structure of the Thesis --- p.8 / Chapter 2 --- Literature Review on Shuttle Mask Floorplanning --- p.9 / Chapter 2.1 --- Introduction --- p.9 / Chapter 2.1.1 --- Problem formulation --- p.10 / Chapter 2.2 --- Slicing Floorplan --- p.10 / Chapter 2.3 --- General Floorplan --- p.11 / Chapter 2.3.1 --- Conflict Graph Approaches --- p.11 / Chapter 2.3.2 --- Integer Linear Programming Approaches --- p.14 / Chapter 2.4 --- Grid Packing --- p.15 / Chapter 2.4.1 --- "(α,β,γ)-restricted Grid Approach" --- p.15 / Chapter 2.4.2 --- Branch and Bound Searching Approach --- p.17 / Chapter 3 --- Shuttle Mask Floorplanning --- p.18 / Chapter 3.1 --- Problem Description --- p.18 / Chapter 3.2 --- An Overview --- p.20 / Chapter 3.3 --- Modified α-Restricted Grid --- p.21 / Chapter 3.4 --- Branch and Bound Algorithm --- p.23 / Chapter 3.4.1 --- Feasibility Check --- p.25 / Chapter 3.5 --- Dicing Plan --- p.30 / Chapter 3.6 --- Experimental Result --- p.30 / Chapter 4 --- Literature Review on Voltage Island Partitioning --- p.36 / Chapter 4.1 --- Introduction --- p.36 / Chapter 4.1.1 --- Problem Definition --- p.36 / Chapter 4.2 --- Dynamic Programming --- p.38 / Chapter 4.2.1 --- Problem Definition --- p.38 / Chapter 4.2.2 --- Algorithm Overview --- p.38 / Chapter 4.2.3 --- Size Reduction --- p.39 / Chapter 4.2.4 --- Approximate Voltage-Partitioning --- p.40 / Chapter 4.3 --- Quad-tree Approach --- p.41 / Chapter 5 --- Voltage Island Partitioning --- p.44 / Chapter 5.1 --- Introduction --- p.44 / Chapter 5.2 --- Problem Formulation --- p.45 / Chapter 5.3 --- Methodology --- p.46 / Chapter 5.3.1 --- Coarsening and Graph Construction --- p.47 / Chapter 5.3.2 --- Tree Construction --- p.49 / Chapter 5.3.3 --- Optimal Tree Partitioning --- p.50 / Chapter 5.3.4 --- Tree Refinement --- p.52 / Chapter 5.3.5 --- Solution Legalization --- p.53 / Chapter 5.3.6 --- Time Complexity --- p.54 / Chapter 5.4 --- Direct Method --- p.55 / Chapter 5.4.1 --- Dual Grid-partitioning Problem (DGPP) --- p.56 / Chapter 5.4.2 --- Time Complexity --- p.58 / Chapter 5.5 --- Experimental Results --- p.59 / Chapter 6 --- Conclusion --- p.66 / Bibliography --- p.69

Heading towards the era of Internet-of-things (IoT) means both opportunity and challenge for the circuit-design community. In a system where billions of devices are equipped with the ability to sense, compute, communicate with each other and perform tasks in a coordinated manner, security and power management are among the most critical challenges. Physically unclonable function (PUF) emerges as an important security primitive in hardware-security applications; it provides an object-specific physical identifier hidden within the intrinsic device variations, which is hard to expose and reproduce by adversaries. Yet, designing a compact PUF robust to noise, temperature and voltage remains a challenge. This thesis presents a novel PUF design approach based on a pair of ultra-compact analog circuits whose output is proportional to absolute temperature. The proposed approach is demonstrated through two works: (1) an ultra-compact and robust PUF based on voltage-compensated proportional-to-absolute-temperature voltage generators that occupies 8.3× less area than the previous work with the similar robustness and twice the robustness of the previously most compact PUF design and (2) a technique to transform a 6T-SRAM array into a robust analog PUF with minimal overhead. In this work, similar circuit topology is used to transform a preexisting on-chip SRAM into a PUF, which further reduces the area in (1) with no robustness penalty. In this thesis, we also explore techniques for power management circuit design. Energy harvesting is an essential functionality in an IoT sensor node, where battery replacement is cost-prohibitive or impractical. Yet, existing energy-harvesting power management units (EH PMU) suffer from efficiency loss in the two-step voltage conversion: harvester-to-battery and battery-to-load. We propose an EH PMU architecture with hybrid energy storage, where a capacitor is introduced in addition to the battery to serve as an intermediate energy buffer to minimize the battery involvement in the system energy flow. Test-case measurements show as much as a 2.2× improvement in the end-to-end energy efficiency. In contrast, with the drastically reduced power consumption of IoT nodes that operates in the sub-threshold regime, adaptive dynamic voltage scaling (DVS) for supply-voltage margin removal, fully on-chip integration and high power conversion efficiency (PCE) are required in PMU designs. We present a PMU–load co-design based on a fully integrated switched-capacitor DC-DC converter (SC-DC) and hybrid error/replica-based regulation for a fully digital PMU control. The PMU is integrated with a neural spike processor (NSP) that achieves a record-low power consumption of 0.61 µW for 96 channels. A tunable replica circuit is added to assist the error regulation and prevent loss of regulation. With automatic energy-robustness co-optimization, the PMU can set the SC-DC’s optimal conversion ratio and switching frequency. The PMU achieves a PCE of 77.7% (72.2%) at VIN = 0.6 V (1 V) and at the NSP’s margin-free operating point.

Law Hoi Ying. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 101-106). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- VLSI Design Cycle --- p.2 / Chapter 1.2 --- Physical Design Cycle --- p.6 / Chapter 1.3 --- Floorplanning --- p.10 / Chapter 1.3.1 --- Floorplanning Objectives --- p.11 / Chapter 1.3.2 --- Common Approaches --- p.12 / Chapter 1.3.3 --- Interconnect-Driven Floorplanning --- p.14 / Chapter 1.4 --- Motivations and Contributions --- p.15 / Chapter 1.5 --- Organization of the Thesis --- p.17 / Chapter 2 --- Literature Review on 2D Floorplan Representations --- p.18 / Chapter 2.1 --- Types of Floorplans --- p.18 / Chapter 2.2 --- Floorplan Representations --- p.20 / Chapter 2.2.1 --- Slicing Floorplan --- p.21 / Chapter 2.2.2 --- Non-slicing Floorplan --- p.22 / Chapter 2.2.3 --- Mosaic Floorplan --- p.30 / Chapter 2.3 --- Summary --- p.35 / Chapter 3 --- Literature Review on 3D Floorplan Representations --- p.37 / Chapter 3.1 --- Introduction --- p.37 / Chapter 3.2 --- Problem Formulation --- p.38 / Chapter 3.3 --- Previous Work --- p.38 / Chapter 3.4 --- Summary --- p.42 / Chapter 4 --- Literature Review on Bus-Driven Floorplanning --- p.44 / Chapter 4.1 --- Problem Formulation --- p.44 / Chapter 4.2 --- Previous Work --- p.45 / Chapter 4.2.1 --- Abutment Constraint --- p.45 / Chapter 4.2.2 --- Alignment Constraint --- p.49 / Chapter 4.2.3 --- Bus-Driven Floorplanning --- p.52 / Chapter 4.3 --- Summary --- p.53 / Chapter 5 --- Multi-Bend Bus-Driven Floorplanning --- p.55 / Chapter 5.1 --- Introduction --- p.55 / Chapter 5.2 --- Problem Formulation --- p.56 / Chapter 5.3 --- Methodology --- p.57 / Chapter 5.3.1 --- Shape Validation --- p.58 / Chapter 5.3.2 --- Bus Ordering --- p.65 / Chapter 5.3.3 --- Floorplan Realization --- p.72 / Chapter 5.3.4 --- Simulated Annealing --- p.73 / Chapter 5.3.5 --- Soft Block Adjustment --- p.75 / Chapter 5.4 --- Experimental Results --- p.75 / Chapter 5.5 --- Summary --- p.77 / Chapter 6 --- Bus-Driven Floorplanning for 3D Chips --- p.80 / Chapter 6.1 --- Introduction --- p.80 / Chapter 6.2 --- Problem Formulation --- p.81 / Chapter 6.3 --- The Representation --- p.82 / Chapter 6.3.1 --- Overview --- p.82 / Chapter 6.3.2 --- Review of TCG --- p.83 / Chapter 6.3.3 --- Layered Transitive Closure Graph (LTCG) --- p.84 / Chapter 6.3.4 --- Aligning Blocks --- p.85 / Chapter 6.3.5 --- Solution Perturbation --- p.87 / Chapter 6.4 --- Simulated Annealing --- p.92 / Chapter 6.5 --- Soft Block Adjustment --- p.92 / Chapter 6.6 --- Experimental Results --- p.93 / Chapter 6.7 --- Summary --- p.94 / Chapter 6.8 --- Acknowledgement --- p.95 / Chapter 7 --- Conclusion --- p.99 / Bibliography --- p.101

由於特徵尺寸不斷縮小，集成電路在生產過程中的工藝偏差在運行環境中溫度和電壓等參數的波動以及在使用過程中的老化等效應越來越嚴重，導致芯片的時序行為出現很大的不確定性。多數情況下，芯片的關鍵路徑會不時出現時序錯誤。加入更多的時序餘量不是一種很好的解決方案，因為這種保守的設計方法會抵消工藝進步帶來的性能上的好處。這就為設計一個時序可靠的系統提出了極大的挑戰，其中的一些關鍵問題包括：(一)如何有效地分配有限的功率預算去優化那些正爆炸式增加的關鍵路徑的時序性能；(二)如何產生能夠捕捉準確的最壞情況時延的高品質測試向量；(三)為了能夠取得更好的功耗和性能上的平衡，我們將不得不允許芯片在使用過程中出現一些頻率很低的時序錯誤。隨之而來的問題是如何做到在線的檢錯和糾錯。 / 為了解決上述問題，我們首先發明了一種新的技術用於識別所謂的虛假路徑，該方法使我們能夠發現比傳統方法更多的虛假路徑。當將所提取的虛假路徑集成到靜態時序分析工具里以後，我們可以得到更為準確的時序分析結果，同時也能節省本來用於優化這些路徑的成本。接著，考慮到現有的延時自動向量生成(ATPG) 方法會產生功能模式下無法出現的測試向量，這種向量可能會造成測試過程中在被激活的路徑周圍出現過多(或過少)的電源噪聲(PSN) ，從而導致測試過度或者測試不足情況。為此，我們提出了一種新的偽功能ATPG工具。通過同時考慮功能約束以及電路的物理佈局信息，我們使用類似ATPG 的算法產生狀態跳變使其能最大化已激活的路徑周圍的PSN影響。最後，基於近似電路的原理，我們提出了一種新的在線原位校正技術，即InTimeFix，用於糾正時序錯誤。由於實現近似電路的綜合僅需要簡單的電路結構分析，因此該技術能夠很容易的擴展到大型電路設計上去。 / With technology scaling, integrated circuits (ICs) suffer from increasing process, voltage, and temperature (PVT) variations and aging effects. In most cases, these reliability threats manifest themselves as timing errors on speed-paths (i.e., critical or near-critical paths) of the circuit. Embedding a large design guard band to prevent timing errors to occur is not an attractive solution, since this conservative design methodology diminishes the benefit of technology scaling. This creates several challenges on build a reliable systems, and the key problems include (i) how to optimize circuit’s timing performance with limited power budget for explosively increased potential speed-paths; (ii) how to generate high quality delay test pattern to capture ICs’ accurate worst-case delay; (iii) to have better power and performance tradeoff, we have to accept some infrequent timing errors in circuit’s the usage phase. Therefore, the question is how to achieve online timing error resilience. / To address the above issues, we first develop a novel technique to identify so-called false paths, which facilitate us to find much more false paths than conventional methods. By integrating our identified false paths into static timing analysis tool, we are able to achieve more accurate timing information and also save the cost used to optimize false paths. Then, due to the fact that existing delay automated test pattern generation (ATPG) methods may generate test patterns that are functionally-unreachable, and such patterns may incur excessive (or limited) power supply noise (PSN) on sensitized paths in test mode, thus leading to over-testing or under-testing of the circuits, we propose a novel pseudo-functional ATPG tool. By taking both circuit layout information and functional constrains into account, we use ATPG like algorithm to justify transitions that pose the maximized functional PSN effects on sensitized critical paths. Finally, we propose a novel in-situ correction technique to mask timing errors, namely InTimeFix, by introducing redundant approximation circuit with more timing slack for speed-paths into the design. The synthesis of the approximation circuit relies on simple structural analysis of the original circuit, which is easily scalable to large IC designs. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Yuan, Feng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 88-100). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Challenges to Solve Timing Uncertainty Problem --- p.2 / Chapter 1.2 --- Contributions and Thesis Outline --- p.5 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Sources of Timing Uncertainty --- p.7 / Chapter 2.1.1 --- Process Variation --- p.7 / Chapter 2.1.2 --- Runtime Environment Fluctuation --- p.9 / Chapter 2.1.3 --- Aging Effect --- p.10 / Chapter 2.2 --- Technical Flow to Solve Timing Uncertainty Problem --- p.10 / Chapter 2.3 --- False Path --- p.12 / Chapter 2.3.1 --- Path Sensitization Criteria --- p.12 / Chapter 2.3.2 --- False Path Aware Timing Analysis --- p.13 / Chapter 2.4 --- Manufacturing Testing --- p.14 / Chapter 2.4.1 --- Functional Testing vs. Structural Testing --- p.14 / Chapter 2.4.2 --- Scan-Based DfT --- p.15 / Chapter 2.4.3 --- Pseudo-Functional Testing --- p.17 / Chapter 2.5 --- Timing Error Tolerance --- p.19 / Chapter 2.5.1 --- Timing Error Detection --- p.19 / Chapter 2.5.2 --- Timing Error Recover --- p.20 / Chapter 3 --- Timing-Independent False Path Identification --- p.23 / Chapter 3.1 --- Introduction --- p.23 / Chapter 3.2 --- Preliminaries and Motivation --- p.26 / Chapter 3.2.1 --- Motivation --- p.27 / Chapter 3.3 --- False Path Examination Considering Illegal States --- p.28 / Chapter 3.3.1 --- Path Sensitization Criterion --- p.28 / Chapter 3.3.2 --- Path-Aware Illegal State Identification --- p.30 / Chapter 3.3.3 --- Proposed Examination Procedure --- p.31 / Chapter 3.4 --- False Path Identification --- p.32 / Chapter 3.4.1 --- Overall Flow --- p.34 / Chapter 3.4.2 --- Static Implication Learning --- p.35 / Chapter 3.4.3 --- Suspicious Node Extraction --- p.36 / Chapter 3.4.4 --- S-Frontier Propagation --- p.37 / Chapter 3.5 --- Experimental Results --- p.38 / Chapter 3.6 --- Conclusion and Future Work --- p.42 / Chapter 4 --- PSN Aware Pseudo-Functional Delay Testing --- p.43 / Chapter 4.1 --- Introduction --- p.43 / Chapter 4.2 --- Preliminaries and Motivation --- p.45 / Chapter 4.2.1 --- Motivation --- p.46 / Chapter 4.3 --- Proposed Methodology --- p.48 / Chapter 4.4 --- Maximizing PSN Effects under Functional Constraints --- p.50 / Chapter 4.4.1 --- Pseudo-Functional Relevant Transitions Generation --- p.51 / Chapter 4.5 --- Experimental Results --- p.59 / Chapter 4.5.1 --- Experimental Setup --- p.59 / Chapter 4.5.2 --- Results and Discussion --- p.60 / Chapter 4.6 --- Conclusion --- p.64 / Chapter 5 --- In-Situ Timing Error Masking in Logic Circuits --- p.65 / Chapter 5.1 --- Introduction --- p.65 / Chapter 5.2 --- Prior Work and Motivation --- p.67 / Chapter 5.3 --- In-Situ Timing Error Masking with Approximate Logic --- p.69 / Chapter 5.3.1 --- Equivalent Circuit Construction with Approximate Logic --- p.70 / Chapter 5.3.2 --- Timing Error Masking with Approximate Logic --- p.72 / Chapter 5.4 --- Cost-Efficient Synthesis for InTimeFix --- p.75 / Chapter 5.4.1 --- Overall Flow --- p.76 / Chapter 5.4.2 --- Prime Critical Segment Extraction --- p.77 / Chapter 5.4.3 --- Prime Critical Segment Merging --- p.79 / Chapter 5.5 --- Experimental Results --- p.81 / Chapter 5.5.1 --- Experimental Setup --- p.81 / Chapter 5.5.2 --- Results and Discussion --- p.82 / Chapter 5.6 --- Conclusion --- p.85 / Chapter 6 --- Conclusion and Future Work --- p.86 / Bibliography --- p.100

Rectilinear Steiner minimum tree (RSMT) problem asks for a shortest tree spanning a set of given terminals using only horizontal and vertical lines. Construction of RSMTs is an important problem in VLSI physical design. It is useful for both the detailed and global routing steps, and it is important for congestion, wire length and timing estimations during the floorplanning or placement step. The original RSMT problem assumes no obstacle in the routing region. However, in today’s designs, there can be many routing blockages, like macro cells, IP blocks and pre-routed nets. Therefore, the RSMT problem with blockages has become an important problem in practice and has received a lot of research attentions in the recent years. The RSMT problem has been shown to be NP-complete, and the introduction of obstacles has made this problem even more complicated. / In the first part of this thesis, we propose an exact algorithm, called ObSteiner, for the construction of obstacle-avoiding RSMT (OARSMT) in the presence of complex rectilinear obstacles. Our work is developed based on the GeoSteiner approach in which full Steiner trees (FSTs) are first constructed and then combined into a RSMT. We modify and extend the algorithm to allow rectilinear obstacles in the routing region. We prove that by adding virtual terminals to each routing obstacle, the FSTs in the presence of obstacles will follow some very simple structures. A two-phase approach is then developed for the construction of OARSMTs. In the first phase, we generate a set of FSTs. In the second phase, the FSTs generated in the first phase are used to construct an OARSMT. Experimental results show that ObSteiner is able to handle problems with hundreds of terminals in the presence of up to two thousand obstacles, generating an optimal solution in a reasonable amount of time. / In the second part of this thesis, we propose the OARSMT problem with slew constraints over obstacles. In modern VLSI designs, obstacles usually block a fraction of metal layers only making it possible to route over the obstacles. However, since buffers cannot be place on top of any obstacle, we should avoid routing long wires over obstacles. Therefore, we impose the slew constraints for the interconnects that are routed over obstacles. To deal with this problem, we analyze the optimal solutions and prove that the internal trees with signal direction over an obstacle will follow some simple structures. Based on this observation, we propose an exact algorithm, called ObSteiner with slew constraints, that is able to find an optimal solution in the extended Hanan grid. Experimental results show that the proposed algorithm is able to reduce nearly 5% routing resources on average in comparison with the OARSMT algorithm and is also very much faster. / Huang, Tao. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves [137]-144). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- The rectilinear Steiner minimum tree problem --- p.1 / Chapter 1.2 --- Applications --- p.3 / Chapter 1.3 --- Obstacle consideration --- p.5 / Chapter 1.4 --- Thesis outline --- p.6 / Chapter 1.5 --- Thesis contributions --- p.8 / Chapter 2 --- Background --- p.11 / Chapter 2.1 --- RSMT algorithms --- p.11 / Chapter 2.1.1 --- Heuristics --- p.11 / Chapter 2.1.2 --- Exact algorithms --- p.20 / Chapter 2.2 --- OARSMT algorithms --- p.30 / Chapter 2.2.1 --- Heuristics --- p.30 / Chapter 2.2.2 --- Exact algorithms --- p.33 / Chapter 3 --- ObSteiner - an exact OARSMT algorithm --- p.37 / Chapter 3.1 --- Introduction --- p.38 / Chapter 3.2 --- Preliminaries --- p.39 / Chapter 3.2.1 --- OARSMT problem formulation --- p.39 / Chapter 3.2.2 --- An exact RSMT algorithm --- p.40 / Chapter 3.3 --- OARSMT decomposition --- p.42 / Chapter 3.3.1 --- Full Steiner trees among complex obstacles --- p.42 / Chapter 3.3.2 --- More Theoretical results --- p.59 / Chapter 3.4 --- OARSMT construction --- p.62 / Chapter 3.4.1 --- FST generation --- p.62 / Chapter 3.4.2 --- Pruning of FSTs --- p.66 / Chapter 3.4.3 --- FST concatenation --- p.71 / Chapter 3.5 --- Incremental construction --- p.82 / Chapter 3.6 --- Experiments --- p.83 / Chapter 4 --- ObSteiner with slew constraints --- p.97 / Chapter 4.1 --- Introduction --- p.97 / Chapter 4.2 --- Problem Formulation --- p.100 / Chapter 4.3 --- Overview of our approach --- p.103 / Chapter 4.4 --- Internal tree structures in an optimal solution --- p.103 / Chapter 4.5 --- Algorithm --- p.126 / Chapter 4.5.1 --- EFST and SCIFST generation --- p.127 / Chapter 4.5.2 --- Concatenation --- p.129 / Chapter 4.5.3 --- Incremental construction --- p.131 / Chapter 4.6 --- Experiments --- p.131 / Chapter 5 --- Conclusion --- p.135 / Bibliography --- p.137