| REFINEMENT APPROACHES FOR RECTILINEAR STEINER TREE CONSTRUCTION, T.-H. Chao and Y.-C. Hsu | |
| Existing Approaches | |
| Local and Global Refinement | |
| Weight of Edges | |
| Refined Steiner Tree and Modified Tree | |
| Local Refinement | |
| Global Refinement | |
| Tree Refinement Algorithm | |
| Implementation and Experiments | |
| Root Selection and Node Ordering | |
| The Efficiency of Loop Detection | |
| Useless Steiner Points | |
| Experimental Results | |
| Remarks | |
| References | |
| RECTILINEAR INTERCONNECTIONS IN PRESENCE OF OBSTACLES, J.P. Colhoon and J.L. Ganley | |
| Introduction | |
| Two-Terminal Interconnections | |
| Grid-based Algorithms | |
| Line-based Algorithms | |
| Multiple Net Routing | |
| Multi-Terminal Interconnections | |
| Escape Graph Reduction | |
| Exact Algorithms | |
| Graph-based Heuristics | |
| Other Heuristics | |
| Special Cases | |
| Terminals on Obstacle Perimeters | |
| Switchboxes with Obstacles | |
| Open Problems | |
| Graph Reductions | |
| Computing Optimal OARSTs | |
| Multiple-net Steiner Tree Routing | |
| References | |
| THE GENERAL SOLUTION OF THE RECTILINEAR STEINER'S PROBLEM AND ITS APPLICATIONS, Y.T. Wong and M.G. Pecht | |
| Basic Definitions | |
| Basic Connectives in an NR Edge-set Tree | |
| Cliques | |
| Evolved Cliques | |
| Edge Set and Clique Replacements | |
| The General Solution | |
| Algorithms for the General Solution | |
| Finding an NR Edge-set Tree | |
| Finding a Three-edge-set Clique | |
| Finding an m-Edge-set Clique or a Set of Edge Sets Connecting (m+3)/2 Edge-set Trees | |
| Finding Sets of Edge Set Trees for nT Subsets of Nodes | |
| Finding an Edge-set Tree Tested by Cm | |
| Finding the General Solution | |
| Binary Trees Storing Edge-set Trees | |
| Algorithm Expansions | |
| A Definition for an Algorithm Expansion | |
| Expansion Indices for the Solution of Rectilinear Steiner's Problem | |
| Length Reduction Contributed by Merging Redundant Edges | |
| Linear Algorithms for Special Cases | |
| Linear Algorithm for the General Solution of the Switch-box Problem | |
| Linear Algorithm for MRSTs Connecting Nodes on the Boundary of a Polygon | |
| A Nearly Linear Algorithm Finding an NR Edge-set tree | |
| The Number of Nodes Connected by an NR Edge-set tree Containing a Set of MRSTs | |
| The MRST Routing | |
| Figure of Merit for Wire Congestion | |
| An MRST Routing | |
| Conclusions | |
| References | |
| PERFORMANCE DRIVEN GLOBAL ROUTING AND WIRING RULE GENERATION FOR HIGH SPEED PCBS AND MCMS, P.D. Franzon and S. Mehrotra | |
| Signal Integrity Management | |
| Signal Integrity Requirements | |
| Delay and Noise Basics | |
| High Speed Interconnect Design | |
| CAD Approaches to Controlling Delay and Reflection Noise | |
| Delay Equations | |
| On-Line Simulation Approach | |
| Pre-Characterization | |
| Conclusions | |
| References | |
| ROUTING FOR ANALOG AND MIXED CIRCUIT, E. Malavasi | |
| Overview of Current Approaches | |
| Routers Based on Net Classification | |
| Weight-driven Routers | |
| Constraint-driven Routers | |
| Analog Constraints for Routing | |
| Sensitivity Analysis for Constraint Generation | |
| Limits of the Constraint-generation Solution | |
| Extension sto the Digital Circuits | |
| Analog Area Routing | |
| Analog Channel Routing | |
| Parasitic Models for Interconnections | |
| Special Features | |
| Wire Width Control | |
| Matching | |
| Symmetries | |
| Shields | |
| Building Lateral Shields | |
| Building Vertical Shields | |
| References | |
| SEGMENTED CHANNEL ROUTING, K. Roy | |
| Preliminaries and Definitions | |
| Bounced Search Algorithm | |
| Cost Functions | |
| The Algorithm | |
| Net Ordering Schemes | |
| Fault Tolerance due to Inherent Redundancy | |
| Channel Segmentation | |
| Cross Antifuse Programming and Channel Routing | |
| Channel Architecture Synthesis | |
| Implenentation and Results | |
| Conclusions | |
| References | |
| RESTRICTED ROUTING FOR CMOS GATE ARRAYS, B. Zhu, A. Lu, and X. Wu | |
| Technological Features of CMOS Gate Arrays | |
| Review on Routing | |
| Review on Global Routing | |
| Review on Contact-region Routing | |
| Review on Main-channel Routing | |
| Global Routing Based on the Analysis of Routing Resources | |
| Initial Global Routing | |
| Rerouting | |
| Contact-Region Routing | |
| Approach Aiming at Minimizing Density | |
| Reassigning Pins Evenly by Routing in Contact-region | |
| Main-channel Routing | |
| A Greedy Router with Routability Prediction | |
| Routing Based on Assigning Resources | |
| References | |
| RECENT DEVELOPMENTS IN WIRING AND VIA MINIMIZATION, P. Molitor | |
| Review on Wiring | |
| Two-layer Wirability and Coherent Problems | |
| Two-layer Wirability | |
| Stretching to Ensure 2-layer Wirability | |
| The Constrained Via Minimization Problem | |
| Wiring for Interconnect Delay Minimization | |
| Two Layers with Same Conductivity | |
| Two Layers with Different Conductivities | |
| Hierarchical Wiring | |
| References | |
| LAYOUT COMPACTIONS FOR HIGH-PERFORMANCE/LARGE-SCALE CIRCUITS, H. Shin | |
| Introductory Tutorial | |
| Virtual Grid, Graph-based, and Lp-based Compactions | |
| Branch-and-bound, ILP, Supercompaction , and Zone-defining | |
| Jog-insertion | |
| Performance-oriented Compactors | |
| Minimization sof Stray Resistance and Capacitance on the Timing Critical Path | |
| Local Transformations of Layouts for Performance Optimizations | |
| Data Structure and Algorithms for Rule Checking and Compaction | |
| Compaction for Hierarchical Design | |
| Future Development | |
| References | |
| RIP-UP AND REROUTE STRATEGIES, M. Raith | |
| Basic Concepts and Strategies | |
| Problem Description | |
| Current Approaches | |
| Shove Aside | |
| Reflection | |
| Strong Rip-up | |
| Limitations | |
| Requirements for Future Strategies | |
| Basic Concept and Strategy | |
| The Method of Minimal Rip-up Set | |
| Minimization Problem | |
| The New Strategy | |
| The Algorithm | |
| Example | |
| Conclusion and Open Problems | |
| References | |
| PARALLEL ROUTING, T.W. Cho | |
| Design Guide for Parallel Processing | |
| Hardware Optimals for Parallel Routing | |
| Interconnection Schemes | |
| Special Purpose Hardware | |
| General Purpose Hardware | |
| Hardware Routing | |
| Fast Maze Router | |
| Interative Array Maze Router | |
| Wire-Routing Machines | |
| A Wave Front Machine | |
| A New Routing Algorithm and Its Hardware Implementation | |
| A Hardware Accelerator for Maze Routing | |
| Parallel Routing with Multiprocessors | |
| Shared Memory Router | |
| Parallel Global Router | |
| A Parallel Approach to Switchbox Routing | |
| Parallex Algorithm | |
| Representation of a Route | |
| Data Structures | |
| Conflict Group | |
| Fixed Segments and Re-Routable Segments | |
| Search Lists | |
| Architecture of Parallelex | |
| Overview of Algorithm | |
| Message Passing | |
| Routing on Hypercube Computer | |
| Hypercube Maze Router | |
| Neural Network Approach | |
| Conclusions | |
| References | |
| APPENDIX A: SYMBOLS | |
| APPENDIX B: ACRONYMS | |
| APPENDIX C: GLOSSARY | |
| INDEX |
More info about Taylor & Francis e-books