by Sau-yuen Wong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 77-82). / Acknowledgement --- p.i / Abstract --- p.ii / List of Tables --- p.ii / List of Figures --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Review of Previous Work --- p.4 / Chapter 2.1 --- Optimization of Delay and Layout Design --- p.4 / Chapter 2.2 --- Simulated Annealing --- p.8 / Chapter 3 --- Definition of Circuit Model --- p.12 / Chapter 4 --- Evaluation of Delay --- p.16 / Chapter 4.1 --- RC-tree and Elmore Delay --- p.16 / Chapter 4.2 --- Exponential Decayed Polynomial Function --- p.17 / Chapter 4.3 --- Two-pole Approximation --- p.18 / Chapter 4.4 --- AWE and Adopted Delay Model --- p.19 / Chapter 5 --- Delay Minimization by Simulated Annealing --- p.28 / Chapter 5.1 --- Cost Function --- p.28 / Chapter 5.2 --- Neighbor Moves --- p.30 / Chapter 5.2.1 --- Logical models --- p.31 / Chapter 5.2.2 --- Discretization of Solution Space --- p.32 / Chapter 5.2.3 --- Valid Configurations --- p.35 / Chapter 5.2.4 --- Valid Moves --- p.39 / Chapter 5.2.5 --- Modification to the Newly Generated Graph --- p.41 / Chapter 5.2.6 --- Access to Neighbor configuration --- p.43 / Chapter 5.2.7 --- Reduction of Solution Space --- p.45 / Chapter 5.2.8 --- Correctness of the Algorithm --- p.48 / Chapter 5.2.9 --- Completeness of the Algorithm --- p.49 / Chapter 6 --- Experimental result --- p.56 / Chapter 6.1 --- Optimization of Overall Performance --- p.58 / Chapter 6.2 --- Optimization on Individual Delay --- p.70 / Chapter 7 --- Conclusion --- p.74 / A --- p.76 / Bibliography

by Eva Yuk-Wah Pang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 88-89). / ACKNOWLEDGEMETS / ABSTRACT / LIST OF FIGURES / LIST OF TABLES / Chapter CHAPTER1 --- INTRODUCTION / Chapter 1.1 --- Motivation --- p.1-1 / Chapter 1.1.1 --- Problems with Synchronous Systems --- p.1-1 / Chapter 1.1.2 --- The Advantages of Self-timed Systems --- p.1-2 / Chapter 1.1.3 --- Self-Timed Cell Library --- p.1-3 / Chapter 1.2 --- Overview of the Thesis --- p.1-5 / Chapter CHAPTER2 --- BACKGROUND / Chapter 2.1 --- Introduction --- p.2-1 / Chapter 2.2 --- Models for Asynchronous System --- p.2-2 / Chapter 2.2.1 --- Huffman model --- p.2-2 / Chapter 2.2.2 --- Muller model --- p.2-4 / Chapter 2.3 --- Self-timed System --- p.2-5 / Chapter 2.3.1 --- Definitions and Assumptions --- p.2-6 / Chapter 2.4 --- Design Methodologies --- p.2-8 / Chapter 2.4.1 --- Differential Logic Structure Design Methodology --- p.2-9 / Chapter 2.4.1.1 --- Data Path --- p.2-9 / Chapter 2.4.1.2 --- Control Path --- p.2-10 / Chapter 2.4.2 --- Micropipeline Design Methodology --- p.2-12 / Chapter 2.4.2.1 --- Data Path --- p.2-12 / Chapter 2.4.2.2 --- Control Path --- p.2-13 / Chapter CHAPTER3 --- SELF-TIMED CELL LIBRARY / Chapter 3.1 --- Introduction --- p.3-1 / Chapter 3.2 --- Muller C element --- p.3-1 / Chapter 3.3 --- Differential Cascode Voltage Switch Logic Circuits --- p.3-6 / Chapter 3.3.1 --- INVERTER --- p.3-8 / Chapter 3.3.2 --- "AND, OR, NAND, NOR" --- p.3-8 / Chapter 3.3.3 --- "XOR, XNOR" --- p.3-10 / Chapter 3.4 --- Latches --- p.3-11 / Chapter 3.4.1 --- Precharged Latch --- p.3-12 / Chapter 3.4.2 --- Capture and Pass Latch --- p.3-12 / Chapter 3.5 --- Delay Elements --- p.3-13 / Chapter 3.6 --- Discussion --- p.3-15 / Chapter CHAPTER4 --- THE CHARACTERISTICS OF SELF-TIMED CELL LIBRARY / Chapter 4.1 --- Introduction --- p.4-1 / Chapter 4.2 --- The Simulation Characteristics --- p.4-2 / Chapter 4.2.1 --- HSPICE program --- p.4-2 / Chapter 4.2.2 --- Characterization Information and Datasheet terms --- p.4-5 / Chapter 4.2.3 --- Characterization values --- p.4-6 / Chapter 4.3 --- The Experimental Analysis --- p.4-6 / Chapter 4.4 --- Experimental Result and Discussion --- p.4-9 / Chapter 4.4.1 --- Experimental Result --- p.4-9 / Chapter 4.4.2 --- Comparison of the characteristics of C-elements --- p.4-12 / Chapter 4.4.3 --- Comparison of simulation with experimental results --- p.4-13 / Chapter 4.4.4 --- Properties of DCVSL gate --- p.4-14 / Chapter 4.4.5 --- The Characteristics of Delay elements --- p.4-15 / Chapter 4.5 --- CAD Features on Cadence --- p.4-16 / Chapter CHAPTER5 --- DESIGN EXAMPLE: SELF-TIMED MATRIX MULTIPLIER / Chapter 5.1 --- Introduction --- p.5-1 / Chapter 5.2 --- A Matrix Multiplier using DCVSL structure --- p.5-2 / Chapter 5.2.1 --- Structure --- p.5-2 / Chapter 5.2.2 --- Handshaking Control Circuit --- p.5-3 / Chapter 5.2.2.1 --- Handshaking Control Circuit of Pipeline --- p.5-4 / Chapter 5.2.2.2 --- Handshaking Control Circuit of Feedback Path --- p.5-8 / Chapter 5.3 --- A Matrix Multiplier using Micropipeline Structure --- p.5-10 / Chapter 5.3.1 --- Structure --- p.5-10 / Chapter 5.3.2 --- Control Circuit --- p.5-12 / Chapter 5.4 --- Experimental Result --- p.5-13 / Chapter 5.4.1 --- The Matrix Multiplier using DCVSL structure --- p.5-13 / Chapter 5.4.2 --- The Matrix Multiplier using Micropipeline structure --- p.5-16 / Chapter 5.5 --- Comparison of DCVSL structure and Micropipeline structure --- p.5-18 / Chapter CHAPTER6 --- CONCLUSION / Chapter 6.1 --- Achievement --- p.6-1 / Chapter 6.1.1 --- Self-timed Cell Library --- p.6-1 / Chapter 6.1.2 --- Self-timed System Design simplification --- p.6-2 / Chapter 6.1.3 --- Area and Speed --- p.6-3 / Chapter 6.1.4 --- Applications --- p.6-4 / Chapter 6.2 --- Future work --- p.6-6 / Chapter 6.2.1 --- Interface with synthesis tools --- p.6-6 / Chapter 6.2.2 --- Mixed Circuit Design --- p.6-6 / REFERENCES / APPENDICES

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