470 Pages
by
CRC Press
The rapid growth of the electronic products market has created an increasing need for affordable, reliable, high-speed and high-density multi-layer printed circuit boards (PCBs). This book presents the technologies, algorithms, and methodologies for engineers and others developing the next generation of electronic products.
A vision of the future in advanced electronics
Advanced Routing of Electronic Modules provides both fundamental theory and advanced technologies for improving routing. Beginning chapters discuss approaches to approximate a minimum rectilinear Steiner tree from a minimum spanning tree and introduce ways to avoid obstacles for routing simple multi-terminal nets sequentially in a workspace. Timing delay, clock skew, and noise control requirements in signal integrity are described as well as computer-aided approaches to managing these requirements in high-speed PCB/MCM routing.
Later chapters present the two-layer wiring problem, rip-up and reroute approaches, and parallel routing, including global routing, boundary crossing placement, and detailed maze routing in hardware acceleration. Data structures, data management, and algorithms for parallel routing in a multiple-processor hardware systems are also covered.
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
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
Biography
Michael Pecht, Yeun Tsun Wong
