由於特徵尺寸不斷縮小，集成電路在生產過程中的工藝偏差在運行環境中溫度和電壓等參數的波動以及在使用過程中的老化等效應越來越嚴重，導致芯片的時序行為出現很大的不確定性。多數情況下，芯片的關鍵路徑會不時出現時序錯誤。加入更多的時序餘量不是一種很好的解決方案，因為這種保守的設計方法會抵消工藝進步帶來的性能上的好處。這就為設計一個時序可靠的系統提出了極大的挑戰，其中的一些關鍵問題包括：(一)如何有效地分配有限的功率預算去優化那些正爆炸式增加的關鍵路徑的時序性能；(二)如何產生能夠捕捉準確的最壞情況時延的高品質測試向量；(三)為了能夠取得更好的功耗和性能上的平衡，我們將不得不允許芯片在使用過程中出現一些頻率很低的時序錯誤。隨之而來的問題是如何做到在線的檢錯和糾錯。 / 為了解決上述問題，我們首先發明了一種新的技術用於識別所謂的虛假路徑，該方法使我們能夠發現比傳統方法更多的虛假路徑。當將所提取的虛假路徑集成到靜態時序分析工具里以後，我們可以得到更為準確的時序分析結果，同時也能節省本來用於優化這些路徑的成本。接著，考慮到現有的延時自動向量生成(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

by Yuen-Pat Lau. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 127-[129]). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- VLSI Interconnects in Circuits --- p.1 / Chapter 1.2 --- Propagating Waves on Interconnects --- p.4 / Chapter 2 --- Theory: FDTD --- p.6 / Chapter 2.1 --- Modelling Microstrips in FDTD Mesh Space --- p.6 / Chapter 2.2 --- FDTD Implementation of a Unit Cell --- p.8 / Chapter 2.3 --- FDTD Implementation of a Lumped Element --- p.12 / Chapter 2.4 --- FDTD Implementation of a Circuit --- p.14 / Chapter 3 --- Theory: TDMS --- p.20 / Chapter 3.1 --- FDTD Circuit Simulation --- p.20 / Chapter 3.2 --- TDMS: Microstrip Characterization --- p.22 / Chapter 3.3 --- TDMS: Parameter Extraction --- p.23 / Chapter 3.4 --- TDMS: Circuit Simulation --- p.26 / Chapter 4 --- TDMS Simulations --- p.30 / Chapter 4.1 --- Example One: Loaded Diode --- p.30 / Chapter 4.2 --- Example Two: Unbalanced Mixer --- p.38 / Chapter 5 --- TDR Experiments --- p.54 / Chapter 5.1 --- Example Three: Uniform Microstrip --- p.54 / Chapter 5.2 --- Example Four: Coupled Microstrip --- p.61 / Chapter 5.3 --- Example Five: Change-in-width Microstrip --- p.67 / Chapter 6 --- Conclusion --- p.78 / Chapter 7 --- Program Listing --- p.80 / Chapter 7.1 --- Example Two: Unbalanced Mixer --- p.80 / Chapter 7.2 --- Example Five: Change-in-width Microstrip --- p.110 / Bibliography --- p.127

Sze, Chin Ngai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 80-84) and index. / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / Curriculum Vitae --- p.iv / List of Figures --- p.ix / List of Tables --- p.xii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Aims --- p.1 / Chapter 1.2 --- Contribution --- p.8 / Chapter 1.3 --- Organization of Dissertation --- p.10 / Chapter 2 --- Definitions and Notations --- p.11 / Chapter 3 --- Literature Review --- p.15 / Chapter 3.1 --- Logic Reconstruction --- p.15 / Chapter 3.1.1 --- SIS: A System for Sequential and Combinational Logic Synthesis --- p.16 / Chapter 3.2 --- ATPG-based Alternative Wiring --- p.17 / Chapter 3.2.1 --- Redundancy Addition and Removal for Logic Optimization --- p.18 / Chapter 3.2.2 --- Perturb and Simplify Logic Optimization --- p.18 / Chapter 3.2.3 --- REWIRE --- p.21 / Chapter 3.2.4 --- Implication-tree Based Alternative Wiring Logic Trans- formation --- p.22 / Chapter 3.3 --- Graph-based Alternative Wiring --- p.24 / Chapter 4 --- Implication Based Alternative Wiring Logic Transformation --- p.25 / Chapter 4.1 --- Source Node Implication --- p.25 / Chapter 4.1.1 --- Introduction --- p.25 / Chapter 4.1.2 --- Implication Relationship and Implication-tree --- p.25 / Chapter 4.1.3 --- Selection of Alternative Wire Based on Implication-tree --- p.29 / Chapter 4.1.4 --- Implication-tree Based Logic Transformation --- p.32 / Chapter 4.2 --- Destination Node Implication --- p.35 / Chapter 4.2.1 --- Introduction --- p.35 / Chapter 4.2.2 --- Destination Node Relationship --- p.35 / Chapter 4.2.3 --- Destination Node Implication-tree --- p.39 / Chapter 4.2.4 --- Selection of Alternative Wire --- p.41 / Chapter 4.3 --- The Algorithm --- p.43 / Chapter 4.3.1 --- IB AW Implementation --- p.43 / Chapter 4.3.2 --- Experimental Results --- p.43 / Chapter 4.4 --- Conclusion --- p.45 / Chapter 5 --- Graph Based Alternative Wiring Logic Transformation --- p.47 / Chapter 5.1 --- Introduction --- p.47 / Chapter 5.2 --- Notations and Definitions --- p.48 / Chapter 5.3 --- Alternative Wire Patterns --- p.50 / Chapter 5.4 --- Construction of Minimal Patterns --- p.54 / Chapter 5.4.1 --- Minimality of Patterns --- p.54 / Chapter 5.4.2 --- Minimal Pattern Formation --- p.56 / Chapter 5.4.3 --- Pattern Extraction --- p.61 / Chapter 5.5 --- Experimental Results --- p.63 / Chapter 5.6 --- Conclusion --- p.63 / Chapter 6 --- Logic Optimization by GBAW --- p.66 / Chapter 6.1 --- Introduction --- p.66 / Chapter 6.2 --- Logic Simplification --- p.67 / Chapter 6.2.1 --- Single-Addition-Multiple-Removal by Pattern Feature . . --- p.67 / Chapter 6.2.2 --- Single-Addition-Multiple-Removal by Combination of Pat- terns --- p.68 / Chapter 6.2.3 --- Single-Addition-Single-Removal --- p.70 / Chapter 6.3 --- Incremental Perturbation Heuristic --- p.71 / Chapter 6.4 --- GBAW Optimization Algorithm --- p.73 / Chapter 6.5 --- Experimental Results --- p.73 / Chapter 6.6 --- Conclusion --- p.76 / Chapter 7 --- Conclusion --- p.78 / Bibliography --- p.80 / Chapter A --- VLSI Design Cycle --- p.85 / Chapter B --- Alternative Wire Patterns in [WLFOO] --- p.87 / Chapter B.1 --- 0-local Pattern --- p.87 / Chapter B.2 --- 1-local Pattern --- p.88 / Chapter B.3 --- 2-local Pattern --- p.89 / Chapter B.4 --- Fanout-reconvergent Pattern --- p.90 / Chapter C --- New Alternative Wire Patterns --- p.91 / Chapter C.1 --- Pattern Cluster C1 --- p.91 / Chapter C.1.1 --- NAND-NAND-AND/NAND;AND/NAND --- p.91 / Chapter C.1.2 --- NOR-NOR-OR/NOR;AND/NAND --- p.92 / Chapter C.1.3 --- AND-NOR-OR/NOR;OR/NOR --- p.95 / Chapter C.1.4 --- OR-NAND-AND/NAND;AND/NAND --- p.95 / Chapter C.2 --- Pattern Cluster C2 --- p.98 / Chapter C.3 --- Pattern Cluster C3 --- p.99 / Chapter C.4 --- Pattern Cluster C4 --- p.104 / Chapter C.5 --- Pattern Cluster C5 --- p.105 / Glossary --- p.106 / Index --- p.108

Han Wei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 60-61). / Abstracts in English and Chinese. / Abstract --- p.i / 摘要 --- p.ii / Acknowledgements --- p.iii / Contents --- p.iv / List of Figures --- p.vi / List of Tables --- p.vii / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1. --- Speech Recognition --- p.1 / Chapter 1.2. --- ASIC Design with HDLs --- p.3 / Chapter Chapter 2 --- Theory of HMM-Based Speech Recognition --- p.6 / Chapter 2.1. --- Speaker-Dependent and Speaker-Independent --- p.6 / Chapter 2.2. --- Frame and Feature Vector --- p.6 / Chapter 2.3. --- Hidden Markov Model --- p.7 / Chapter 2.3.1. --- Markov Model --- p.8 / Chapter 2.3.2. --- Hidden Markov Model --- p.9 / Chapter 2.3.3. --- Elements of an HMM --- p.10 / Chapter 2.3.4. --- Types of HMMs --- p.11 / Chapter 2.3.5. --- Continuous Observation Densities in HMMs --- p.13 / Chapter 2.3.6. --- Three Basic Problems for HMMs --- p.15 / Chapter 2.4. --- Probability Evaluation --- p.16 / Chapter 2.4.1. --- The Viterbi Algorithm --- p.17 / Chapter 2.4.2. --- Alternative Viterbi Implementation --- p.19 / Chapter Chapter 3 --- HMM-based Isolated Word Recognizer Design Methodology …… --- p.20 / Chapter 3.1. --- Speech Recognition Based On Single Mixture --- p.23 / Chapter 3.2. --- Speech Recognition Based On Double Mixtures --- p.25 / Chapter Chapter 4 --- VLSI Implementation of the Speech Recognizer --- p.29 / Chapter 4.1. --- The System Requirements --- p.29 / Chapter 4.2. --- Implementation of a Speech Recognizer with a Single-Mixture HMM --- p.30 / Chapter 4.3. --- Implementation of a Speech Recognizer with a Double-Mixture HMM --- p.39 / Chapter 4.4. --- Extend Usage in High Order Mixtures HMM --- p.46 / Chapter 4.5. --- Pipelining and the System Timing --- p.50 / Chapter Chapter 5 --- Simulation and IC Testing --- p.53 / Chapter 5.1. --- Simulation Result --- p.53 / Chapter 5.2. --- Testing --- p.55 / Chapter Chapter 6 --- Discussion and Conclusion --- p.58 / Reference --- p.60 / Appendix I Verilog Code of the Double-Mixture HMM Based Speech Recognition IC (RTL Level) --- p.62 / Subtracter --- p.62 / Multiplier --- p.63 / Core_Adder --- p.65 / Register for X --- p.66 / Subtractor and Comparator --- p.67 / Shifter --- p.68 / Look-Up Table --- p.71 / Register for Constants --- p.79 / Register for Scores --- p.80 / Final Score Register --- p.84 / Controller --- p.86 / Top --- p.97 / Appendix II Chip Microphotograph --- p.103 / Appendix III Pin Assignment of the Speech Recognition IC --- p.104 / Appendix IV The Testing Board of the IC --- p.108

Ma, Qiang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 78-80). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Floorplanning --- p.2 / Chapter 1.3 --- Motivations --- p.4 / Chapter 1.4 --- Design Implementation of Voltage Islands --- p.5 / Chapter 1.5 --- Problem Formulation --- p.8 / Chapter 1.6 --- Progress on the Problem --- p.10 / Chapter 1.7 --- Contributions --- p.12 / Chapter 1.8 --- Thesis Organization --- p.14 / Chapter 2 --- Literature Review on MSV --- p.15 / Chapter 2.1 --- Introduction --- p.15 / Chapter 2.2 --- MSV at Post-floorplan/Post Placement Stage --- p.16 / Chapter 2.2.1 --- """Post-Placement Voltage Island Generation under Performance Requirement""" --- p.16 / Chapter 2.2.2 --- """Post-Placement Voltage Island Generation""" --- p.18 / Chapter 2.2.3 --- """Timing-Constrained and Voltage-Island-Aware Voltage Assignment""" --- p.19 / Chapter 2.2.4 --- """Voltage Island Generation under Performance Requirement for SoC Designs""" --- p.20 / Chapter 2.2.5 --- """An ILP Algorithm for Post-Floorplanning Voltage-Island Generation Considering Power-Network Planning""" --- p.21 / Chapter 2.3 --- MSV at Floorplan/Placement Stage --- p.22 / Chapter 2.3.1 --- """Architecting Voltage Islands in Core-based System-on-a- Chip Designs""" --- p.22 / Chapter 2.3.2 --- """Voltage Island Aware Floorplanning for Power and Timing Optimization""" --- p.23 / Chapter 2.4 --- Summary --- p.27 / Chapter 3 --- MSV Driven Floorplanning --- p.29 / Chapter 3.1 --- Introduction --- p.29 / Chapter 3.2 --- Problem Formulation --- p.32 / Chapter 3.3 --- Algorithm Overview --- p.33 / Chapter 3.4 --- Optimal Island Partitioning and Voltage Assignment --- p.33 / Chapter 3.4.1 --- Voltage Islands in Non-subtrees --- p.35 / Chapter 3.4.2 --- Proof of Optimality --- p.36 / Chapter 3.4.3 --- Handling Island with Power Down Mode --- p.37 / Chapter 3.4.4 --- Speedup in Implementation and Complexity --- p.38 / Chapter 3.4.5 --- Varying Background Chip-level Voltage --- p.39 / Chapter 3.5 --- Simulated Annealing --- p.39 / Chapter 3.5.1 --- Moves --- p.39 / Chapter 3.5.2 --- Cost Function --- p.40 / Chapter 3.6 --- Experimental Results --- p.40 / Chapter 3.6.1 --- Extension to Minimize Level Shifters --- p.45 / Chapter 3.6.2 --- Extension to Consider Power Network Routing --- p.46 / Chapter 3.7 --- Summary --- p.46 / Chapter 4 --- MSV Driven Floorplanning with Timing --- p.49 / Chapter 4.1 --- Introduction --- p.49 / Chapter 4.2 --- Problem Formulation --- p.52 / Chapter 4.3 --- Algorithm Overview --- p.56 / Chapter 4.4 --- Voltage Assignment Problem --- p.56 / Chapter 4.4.1 --- Lagrangian Relaxation --- p.58 / Chapter 4.4.2 --- Transformation into the Primal Minimum Cost Flow Problem --- p.60 / Chapter 4.4.3 --- Cost-Scaling Algorithm --- p.64 / Chapter 4.4.4 --- Solution Transformation --- p.66 / Chapter 4.5 --- Simulated Annealing --- p.69 / Chapter 4.5.1 --- Moves --- p.69 / Chapter 4.5.2 --- Speeding up heuristic --- p.69 / Chapter 4.5.3 --- Cost Function --- p.70 / Chapter 4.5.4 --- Annealing Schedule --- p.71 / Chapter 4.6 --- Experimental Results --- p.71 / Chapter 4.7 --- Summary --- p.72 / Chapter 5 --- Conclusion --- p.76 / Bibliography --- p.80

Leung, Chi Kwan. / Thesis submitted in: December 2007. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 66-68). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Literature Review on Fixed-outline Floorplanning --- p.5 / Chapter 2.1 --- General Floorplanning --- p.5 / Chapter 2.1.1 --- Simulated Annealing --- p.6 / Example - Normalized Polish Expression --- p.9 / Example - Sequence Pair Representation --- p.15 / Example - Corner Block List --- p.19 / Chapter 2.1.2 --- Genetic Algorithm --- p.24 / Chapter 2.1.3 --- Mixed Integer Linear Programming --- p.25 / Chapter 2.1.4 --- Geometric Programming --- p.25 / Chapter 2.1.5 --- Discussion --- p.26 / Advantages of using Simulated Annealing --- p.26 / Disadvantages of using Simulated Annealing --- p.27 / Chapter 2.2 --- Fixed-outline Floorplanning --- p.28 / Chapter 2.2.1 --- Motivation --- p.28 / Chapter 2.2.2 --- Dimension Based Cost Function --- p.30 / Chapter 2.2.3 --- Aspect Ratio Based Cost Function --- p.32 / Chapter 2.2.4 --- Evolutionary Search --- p.33 / Chapter 2.2.5 --- Instance Augmentation --- p.35 / Chapter 3 --- Predictive Rating with Fixed Outline Constraints --- p.39 / Chapter 3.1 --- Introduction --- p.39 / Chapter 3.2 --- Motivation --- p.40 / Chapter 3.3 --- Predictive Rating Scheme --- p.44 / Chapter 3.3.1 --- Area --- p.45 / Chapter 3.3.2 --- Dimensions --- p.46 / Chapter 3.3.3 --- Aspect Ratio --- p.47 / Chapter 3.3.4 --- Overall Equation for Predictive Rating --- p.48 / Chapter 3.4 --- Integration into the Floorplanner --- p.49 / Chapter 3.5 --- Experimental Results --- p.50 / Chapter 3.5.1 --- Accuracy of Predictive Rating --- p.50 / Chapter 3.5.2 --- Test One --- p.52 / Chapter 3.5.3 --- Test Two --- p.57 / Chapter 3.6 --- Conclusion --- p.61 / Chapter 4 --- Conclusion --- p.64 / Bibliography --- p.66

Jiang, Yan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 87-92). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Physical Design --- p.2 / Chapter 1.2 --- Floorplanning --- p.6 / Chapter 1.2.1 --- Floorplanning Objectives --- p.7 / Chapter 1.2.2 --- Common Approaches --- p.8 / Chapter 1.3 --- Motivations and Contributions --- p.14 / Chapter 1.4 --- Organization of the Thesis --- p.15 / Chapter 2 --- Literature Review on BDF --- p.17 / Chapter 2.1 --- Zero-Bend BDF --- p.17 / Chapter 2.1.1 --- BDF Using the Sequence-Pair Representation --- p.17 / Chapter 2.1.2 --- Using B*-Tree and Fast SA --- p.20 / Chapter 2.2 --- Two-Bend BDF --- p.22 / Chapter 2.3 --- TCG-Based Multi-Bend BDF --- p.25 / Chapter 2.3.1 --- Placement Constraints for Bus --- p.26 / Chapter 2.3.2 --- Bus Ordering --- p.28 / Chapter 2.4 --- Bus-Pin-Aware BDF --- p.30 / Chapter 2.5 --- Summary --- p.33 / Chapter 3 --- Fixed-Outline BDF --- p.35 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.2 --- Problem Formulation --- p.36 / Chapter 3.3 --- The Overview of Our Approach --- p.36 / Chapter 3.4 --- Partitioning --- p.37 / Chapter 3.4.1. --- The Overview of Partitioning --- p.38 / Chapter 3.4.2 --- Building a Hypergraph G --- p.39 / Chapter 3.5 --- Floorplaiining with Bus Routing --- p.43 / Chapter 3.5.1 --- Find Bus Routes --- p.43 / Chapter 3.5.2 --- Realization of Bus Routes --- p.48 / Chapter 3.5.3 --- Details of the Annealing Process --- p.50 / Chapter 3.6 --- Handle Fixed-Outline Constraints --- p.52 / Chapter 3.7 --- Bus Layout --- p.52 / Chapter 3.8 --- Experimental Results --- p.56 / Chapter 3.9 --- Summary --- p.61 / Chapter 4 --- Fixed-Outline BDF with L-shape bus --- p.63 / Chapter 4.1 --- Introduction --- p.63 / Chapter 4.2 --- Problem Formulation --- p.64 / Chapter 4.3 --- Our Approach --- p.65 / Chapter 4.3.1 --- Bus Routability Checking --- p.67 / Chapter 4.3.2 --- Details of the Annealing Process --- p.79 / Chapter 4.4 --- Experimental Results --- p.79 / Chapter 4.5 --- Summary --- p.82 / Chapter 5 --- Conclusion --- p.85 / Bibliography --- p.92

Tian, Haitong. / Chinese abstract is on unnumbered page. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 65-74). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations --- p.1 / Chapter 1.2 --- Our Contributions --- p.2 / Chapter 1.3 --- Organization of the Thesis --- p.3 / Chapter 2 --- Background Study --- p.4 / Chapter 2.1 --- Traditional Clock Routing Problem --- p.4 / Chapter 2.2 --- Tree-Based Clock Routing Algorithms --- p.5 / Chapter 2.2.1 --- Clock Routing Using H-tree --- p.5 / Chapter 2.2.2 --- Method of Means and Medians(MMM) --- p.6 / Chapter 2.2.3 --- Geometric Matching Algorithm (GMA) --- p.8 / Chapter 2.2.4 --- Exact Zero-Skew Algorithm --- p.9 / Chapter 2.2.5 --- Deferred Merge Embedding (DME) --- p.10 / Chapter 2.2.6 --- Boundary Merging and Embedding (BME) Algorithm --- p.14 / Chapter 2.2.7 --- Planar Clock Routing Algorithm --- p.17 / Chapter 2.2.8 --- Useful-skew Tree Algorithm --- p.18 / Chapter 2.3 --- Non-Tree Clock Distribution Networks --- p.19 / Chapter 2.3.1 --- Grid (Mesh) Structure --- p.20 / Chapter 2.3.2 --- Spine Structure --- p.20 / Chapter 2.3.3 --- Hybrid Structure --- p.21 / Chapter 2.4 --- Post-grid Clock Routing Problem --- p.22 / Chapter 2.5 --- Limitations of the Previous Work --- p.24 / Chapter 3 --- Post-Grid Clock Routing Problem --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- Problem Definition --- p.27 / Chapter 3.3 --- Our Approach --- p.30 / Chapter 3.3.1 --- Delay-driven Path Expansion Algorithm --- p.31 / Chapter 3.3.2 --- Pre-processing to Connect Critical ports --- p.34 / Chapter 3.3.3 --- Post-processing to Reduce Capacitance --- p.36 / Chapter 3.4 --- Experimental Results --- p.39 / Chapter 3.4.1 --- Experiment Setup --- p.39 / Chapter 3.4.2 --- Validations of the Delay and Slew Estimation --- p.39 / Chapter 3.4.3 --- Comparisons with the Tree Grow (TG) Approach --- p.41 / Chapter 3.4.4 --- Lowest Achievable Delays --- p.42 / Chapter 3.4.5 --- Simulation Results --- p.42 / Chapter 4 --- Non-tree Based Post-Grid Clock Routing Problem --- p.44 / Chapter 4.1 --- Introduction --- p.44 / Chapter 4.2 --- Handling Ports with Large Load Capacitances --- p.46 / Chapter 4.2.1 --- Problem Ports Identification --- p.47 / Chapter 4.2.2 --- Non-Tree Construction --- p.47 / Chapter 4.2.3 --- Wire Link Selection --- p.48 / Chapter 4.3 --- Path Expansion in Non-tree Algorithm --- p.51 / Chapter 4.4 --- Limitations of the Non-tree Algorithm --- p.51 / Chapter 4.5 --- Experimental Results --- p.51 / Chapter 4.5.1 --- Experiment Setup --- p.51 / Chapter 4.5.2 --- Validations of the Delay and Slew Estimation --- p.52 / Chapter 4.5.3 --- Lowest Achievable Delays --- p.53 / Chapter 4.5.4 --- Results on New Benchmarks --- p.53 / Chapter 4.5.5 --- Simulation Results --- p.55 / Chapter 5 --- Efficient Partitioning-based Extension --- p.57 / Chapter 5.1 --- Introduction --- p.57 / Chapter 5.2 --- Partition-based Extension --- p.58 / Chapter 5.3 --- Experimental Results --- p.61 / Chapter 5.3.1 --- Experiment Setup --- p.61 / Chapter 5.3.2 --- Running Time Improvement with Partitioning Technique --- p.61 / Chapter 6 --- Conclusion --- p.63 / Bibliography --- p.65

Automatic synthesis of digital VLSI layout has been available for many years. It has become a necessary part of the design industry as the window of time from conception to production shrinks with ever increasing competition. However, automatic synthesis of analog VLSI layout remains rare. With digital circuits, there is often room for signal drift. In a digital circuit, a signal can drift within a range before hitting the threshold which triggers a change in logic state. The effect of parasitic capacitances for the most part, hinders the timing margins of the signal, but not its functionality. The logic functionality is protected by the inherent noise immunity of digital circuits. With analog circuits, however, there is little room for drift. Parasitic influence directly affects signal integrity and the functionality of the circuit. The underlying problem automatic VLSI layout programs face is how to minimize this influence. This thesis describes a software tool that was written to show that the minimization of parasitic influence is possible in the case of automatic layout of continuous-time filters using transconductance-capacitor methods.