Advanced Routing of Electronic Modules: 1st Edition (Hardback) book cover

Advanced Routing of Electronic Modules

1st Edition

By Michael Pecht, Yeun Tsun Wong

CRC Press

480 pages

Purchasing Options:$ = USD
Hardback: 9780849396229
pub: 1995-10-23
$255.00
x

FREE Standard Shipping!

Description

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.

Table of Contents

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

About the Series

Electronic Packaging

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
TEC008000
TECHNOLOGY & ENGINEERING / Electronics / General
TEC009060
TECHNOLOGY & ENGINEERING / Industrial Engineering
TEC009070
TECHNOLOGY & ENGINEERING / Mechanical