Algorithms for Vlsi Physical Design Automation

by Sherwani, Naveed A.

• ISBN13: 9780792383932
• ISBN10: 0792383931
• Edition: 3rd
• Format: Hardcover
• Copyright: 1999-06-01
• Publisher: Kluwer Academic Pub

Summary

Algorithms for VLSI Physical Design Automation, Third Edition covers all aspects of physical design. The book is a core reference for graduate students and CAD professionals. For students, concepts and algorithms are presented in an intuitive manner. For CAD professionals, the material presents a balance of theory and practice. An extensive bibliography is provided which is useful for finding advanced material on a topic. At the end of each chapter, exercises are provided, which range in complexity from simple to research level. Algorithms for VLSI Physical Design Automation, Third Edition provides a comprehensive background in the principles and algorithms of VLSI physical design. The goal of this book is to serve as a basis for the development of introductory-level graduate courses in VLSI physical design automation. It provides self-contained material for teaching and learning algorithms of physical design. All algorithms which are considered basic have been included, and are presented in an intuitive manner. Yet, at the same time, enough detail is provided so that readers can actually implement the algorithms given in the text and use them. The first three chapters provide the background material, while the focus of each chapter of the rest of the book is on each phase of the physical design cycle. In addition, newer topics such as physical design automation of FPGAs and MCMs have been included. The basic purpose of the third edition is to investigate the new challenges presented by interconnect and process innovations. In 1995 when the second edition of this book was prepared, a six-layer process and 15 million transistor microprocessors were in advanced stages of design. In 1998, six metal process and 20 million transistor designs are in production. Two new chapters have been added and new material has been included in almost allother chapters. A new chapter on process innovation and its impact on physical design has been added. Another focus of the third edition is to promote use of the Internet as a resource, so wherever possible URLs have been provided for further investigation. Algorithms for VLSI Physical Design Automation, Third Edition is an important core reference work for professionals as well as an advanced level textbook for students.

Table of Contents

Foreword	xvii
Preface	xix
Acknowledgements	xxvii
VLSI Physical Design Automation	1	(38)
VLSI Design Cycle	3	(4)
New Trends in VLSI Design Cycle	7	(2)
Physical Design Cycle	9	(4)
New Trends in Physical Design Cycle	13	(2)
Design Styles	15	(11)
Full-Custom	17	(1)
Standard Cell	18	(2)
Gate Arrays	20	(2)
Field Programmable Gate Arrays	22	(3)
Sea of Gates	25	(1)
Comparison of Different Design Styles	25	(1)
System Packaging Styles	26	(6)
Die Packaging and Attachment Styles	26	(1)
Die Package Styles	26	(1)
Package and Die Attachment Styles	27	(1)
Printed Circuit Boards	27	(2)
Multichip Modules	29	(2)
Wafer Scale Integration	31	(1)
Comparison of Different Packaging Styles	31	(1)
Historical Perspectives	32	(1)
Existing Design Tools	33	(2)
Summary	35	(4)
Design and Fabrication of VLSI Devices	39	(36)
Fabrication Materials	40	(3)
Transistor Fundamentals	43	(5)
Basic Semiconductor Junction	43	(2)
TTL Transistors	45	(1)
MOS Transistors	46	(2)
Fabrication of VLSI Circuits	48	(10)
nMOS Fabrication Process	51	(2)
CMOS Fabrication Process	53	(1)
Details of Fabrication Processes	53	(5)
Design Rules	58	(4)
Layout of Basic Devices	62	(9)
Inverters	62	(2)
NAND and NOR Gates	64	(2)
Memory Cells	66	(1)
Static Random Access Memory (SRAM)	67	(2)
Dynamic Random Access Memory (DRAM)	69	(2)
Summary	71	(1)
Exercises	71	(4)
Fabrication Process and its Impact on Physical Design	75	(22)
Scaling Methods	76	(1)
Status of Fabrication Process	77	(2)
Comparison of Fabrication Processes	77	(2)
Issues related to the Fabrication Process	79	(6)
Parasitic Effects	79	(1)
Interconnect Delay	80	(1)
Noise and Crosstalk	81	(1)
Interconnect Size and Complexity	82	(1)
Other Issues in Interconnect	82	(1)
Power Dissipation	82	(1)
Yield and Fabrication Costs	83	(2)
Future of Fabrication Process	85	(6)
SIA Roadmap	85	(1)
Advances in Lithography	86	(1)
Innovations in Interconnect	87	(1)
More Layers of Metal	87	(1)
Local Interconnect	87	(1)
Copper Interconnect	87	(1)
Unlanded Vias	88	(1)
Innovations/Issues in Devices	88	(1)
Aggressive Projections for the Process	89	(1)
Other Process Innovations	90	(1)
Silicon On Insulator	90	(1)
Silicon Germaniun	90	(1)
Solutions for Interconnect Issues	91	(2)
Tools for Process Development	93	(1)
Summary	94	(1)
Exercises	94	(3)
Data Structures and Basic Algorithms	97	(60)
Basic Terminology	99	(1)
Complexity Issues and NP-hardness	100	(4)
Algorithms for NP-hard Problems	101	(1)
Exponential Algorithms	102	(1)
Special Case Algorithms	102	(1)
Approximation Algorithms	102	(1)
Heuristic Algorithms	103	(1)
Basic Algorithms	104	(11)
Graph Algorithms	104	(1)
Graph Search Algorithms	104	(2)
Spanning Tree Algorithms	106	(2)
Shortest Path Algorithms	108	(2)
Matching Algorithms	110	(1)
Min-Cut and Max-Cut Algorithms	110	(1)
Steiner Tree Algorithms	111	(4)
Computational Geometry Algorithms	115	(2)
Line Sweep Method	115	(1)
Extended Line Sweep Method	115	(2)
Basic Data Structures	117	(18)
Atomic Operations for Layout Editors	117	(2)
Linked List of Blocks	119	(1)
Bin-Based Method	120	(2)
Neighbor Pointers	122	(1)
Corner Stitching	123	(7)
Multi-layer Operations	130	(1)
Limitations of Existing Data Structures	131	(1)
Layout Specification Languages	131	(4)
Graph Algorithms for Physical design	135	(16)
Classes of Graphs in Physical Design	135	(1)
Graphs Related to a Set of Lines	136	(2)
Graphs Related to Set of Rectangles	138	(1)
Relationship Between Graph Classes	138	(2)
Graph Problems in Physical Design	140	(2)
Algorithms for Interval Graphs	142	(1)
Maximum Independent Set	142	(1)
Maximum Clique and Minimum Coloring	143	(1)
Algorithms for Permutation Graphs	144	(1)
Maximum Independent Set	144	(2)
Maximum k-Independent Set	146	(2)
Algorithms for Circle Graphs	148	(1)
Maximum Independent Set	148	(1)
Maximum k-Independent Set	149	(2)
Maximum Clique	151	(1)
Summary	151	(1)
Exercises	152	(5)
Partitioning	157	(34)
Problem Formulation	163	(5)
Design Style Specific Partitioning Problems	166	(2)
Classification of Partitioning Algorithms	168	(1)
Group Migration Algorithms	169	(8)
Kernighan-Lin Algorithm	170	(1)
Extensions of Kernighan-Lin Algorithm	171	(2)
Fiduccia-Mattheyses Algorithm	173	(1)
Goldberg and Burstein Algorithm	174	(1)
Component Replication	174	(2)
Ratio Cut	176	(1)
Simulated Annealing and Evolution	177	(6)
Simulated Annealing	177	(2)
Simulated Evolution	179	(4)
Other Partitioning Algorithms	183	(2)
Metric Allocation Method	183	(2)
Performance Driven Partitioning	185	(2)
Summary	187	(1)
Exercises	187	(4)
Floorplanning and Pin Assignment	191	(28)
Floorplanning	193	(14)
Problem Formulation	193	(1)
Design Style Specific Floorplanning Problems	194	(1)
Classification of Floorplanning Algorithms	194	(2)
Constraint Based Floorplanning	196	(2)
Integer Programming Based Floorplanning	198	(2)
Rectangular Dualization	200	(1)
Hierarchical Tree Based Methods	201	(2)
Floorplanning Algorithms for Mixed Block and Cell Designs	203	(1)
Simulated Evolution Algorithms	203	(1)
Timing Driven Floorplanning	204	(1)
Theoretical advancements in Floorplanning	205	(1)
Recent Trends	206	(1)
Chip planning	207	(1)
Problem Formulation	207	(1)
Pin Assignment	207	(7)
Problem Formulation	208	(1)
Design Style Specific Pin Assignment Problems	208	(1)
Classification of Pin Assignment Algorithms	209	(1)
General Pin Assignment	210	(1)
Channel Pin Assignment	211	(3)
Integrated Approach	214	(3)
Summary	217	(1)
Exercises	217	(2)
Placement	219	(28)
Problem Formulation	220	(5)
Design Style Specific Placement Problems	223	(2)
Classification of Placement Algorithms	225	(1)
Simulation Based Placement Algorithms	225	(11)
Simulated Annealing	226	(3)
Simulated Evolution	229	(3)
Force Directed Placement	232	(1)
Sequence-Pair Technique	233	(3)
Comparison of Simulation Based Algorithms	236	(1)
Partitioning Based Placement Algorithms	236	(4)
Breuer's Algorithm	236	(3)
Terminal Propagation Algorithm	239	(1)
Other Placement Algorithms	240	(2)
Cluster Growth	240	(1)
Quadratic Assignment	241	(1)
Resistive Network Optimization	241	(1)
Branch-and-Bound Technique	242	(1)
Performance Driven Placement	242	(1)
Recent Trends	243	(1)
Summary	244	(1)
Exercises	244	(3)
Global Routing	247	(44)
Problem Formulation	253	(7)
Design Style Specific Global Routing Problems	257	(3)
Classification of Global Routing Algorithms	260	(1)
Maze Routing Algorithms	261	(8)
Lee's Algorithm	261	(2)
Soukup's Algorithm	263	(1)
Hadlock's Algorithm	264	(3)
Comparison of Maze Routing Algorithms	267	(2)
Line-Probe Algorithms	269	(3)
Shortest Path Based Algorithms	272	(1)
Steiner Tree based Algorithms	273	(9)
Separability Based Algorithm	274	(3)
Non-Rectilinear Steiner Tree Based Algorithm	277	(2)
Steiner Min-Max Tree based Algorithm	279	(2)
Weighted Steiner Tree based Algorithm	281	(1)
Integer Programming Based Approach	282	(4)
Hierarchical Approach	282	(4)
Performance Driven Routing	286	(1)
Summary	287	(1)
Exercises	288	(3)
Detailed Routing	291	(78)
Problem Formulation	293	(10)
Routing Considerations	293	(2)
Routing Models	295	(2)
Channel Routing Problems	297	(5)
Switchbox Routing Problems	302	(1)
Design Style Specific Detailed Routing Problems	302	(1)
Classification of Routing Algorithms	303	(1)
Single-Layer Routing Algorithms	304	(16)
General River Routing Problem	306	(1)
General River Routing Algorithm	306	(5)
Single Row Routing Problem	311	(1)
Origin of Single Row Routing	312	(4)
A Graph Theoretic Approach	316	(1)
Algorithm for Street Congestion Minimization	316	(2)
Algorithm for Minimizing Doglegs	318	(2)
Two-Layer Channel Routing Algorithms	320	(25)
Classification of Two-Layer Algorithms	320	(1)
LEA based Algorithms	321	(1)
Basic Left-Edge Algorithm	321	(2)
Dogleg Router	323	(2)
Symbolic Channel Router: YACR2	325	(4)
Constraint Graph based Routing Algorithms	329	(1)
Net Merge Channel Router	330	(4)
Glitter: A Gridless Channel Router	334	(4)
Greedy Channel Router	338	(2)
Hierarchical Channel Router	340	(5)
Comparison of Two-Layer Channel Routers	345	(1)
Three-Layer Channel Routing Algorithms	345	(7)
Classification of Three-Layer Algorithms	346	(1)
Extended Net Merge Channel Router	346	(2)
HVH Routing from HV Solution	348	(1)
Hybrid HVH-VHV Router	349	(3)
Multi-Layer Channel Routing Algorithms	352	(1)
Switchbox Routing Algorithms	353	(9)
Classification of switchbox routing algorithms	354	(1)
Greedy Router	355	(3)
Rip-up and Re-route Based Router	358	(1)
Computational Geometry Based Router	358	(4)
Comparison of Switchbox Routers	362	(1)
Summary	362	(1)
Exercises	363	(6)
Over-the-Cell Routing and Via Minimization	369	(48)
Over-the-cell Routing	370	(30)
Cell Models	371	(2)
Two-Layer Over-the-Cell Routers	373	(1)
Basic OTC Routing Algorithm	373	(4)
Planar Over-the-Cell Routing	377	(12)
Over-the-Cell Routing Using Vacant Terminals	389	(7)
Three-Layer Over-the-cell Routing	396	(2)
Multilayer OTC Routing	398	(1)
Performance Driven Over-the-cell Routing	398	(2)
Via Minimization	400	(10)
Constrained Via Minimization Problem	401	(2)
Graph Representation of Two-Layer CVM Problem	403	(4)
Unconstrained Via Minimization	407	(1)
Optimal Algorithm for Crossing-Channel TVM Problem	408	(1)
Approximation Result for General k-TVM Problem	409	(1)
Routing Based on Topological Solution	410	(1)
Summary	410	(1)
Exercises	411	(6)
Clock and Power Routing	417	(32)
Clock Routing	418	(22)
Clocking Schemes	419	(3)
Design Considerations for the Clocking System	422	(1)
Delay Calculation for Clock Trees	423	(3)
Problem Formulation	426	(1)
Design Style Specific Problems	427	(1)
Clock Routing Algorithms	427	(1)
H-tree Based Algorithm	428	(1)
The MMM Algorithm	429	(1)
Geometric Matching based Algorithm	430	(2)
Weighted Center Algorithm	432	(1)
Exact Zero Skew Algorithm	433	(3)
DME Algorithm	436	(3)
Skew and Delay Reduction by Pin Assignment	439	(1)
Multiple Clock Routing	439	(1)
Power and Ground Routing	440	(4)
Summary	444	(1)
Exercises	444	(5)
Compaction	449	(30)
Problem Formulation	450	(1)
Design Style Specific Compaction Problem	450	(1)
Classification of Compaction Algorithms	451	(1)
One-Dimensional Compaction	452	(16)
Constraint-Graph Based Compaction	453	(1)
Constraint Graph Generation	454	(6)
Critical Path Analysis	460	(3)
Wire Jogging	463	(1)
Wire Length Minimization	463	(1)
Virtual Grid Based Compaction	463	(1)
Basic Virtual Grid Algorithm	464	(1)
Split Grid Compaction	464	(3)
Most Recent Layer Algorithm	467	(1)
11/2-Dimensional Compaction	468	(2)
Two-Dimensional Compaction	470	(3)
Simulated Annealing based Algorithm	473	(1)
Hierarchical Compaction	473	(1)
Constraint-Graph Based Hierarchical Compaction	473	(1)
Recent trends in compaction	474	(2)
Performance-driven compaction	474	(1)
Compaction techniques for yield enhancement	475	(1)
Summary	476	(1)
Exercises	476	(3)
Physical Design Automation of FPGAs	479	(22)
FPGA Technologies	480	(5)
Physical Design Cycle for FPGAs	485	(1)
Partitioning	485	(4)
Routing	489	(7)
Routing Algorithm for the Non-Segmented Model	490	(2)
Routing Algorithms for the Segmented Model	492	(1)
Basic Algorithm	493	(1)
Routing Algorithm for Staggered Model	494	(2)
Summary	496	(1)
Exercises	497	(4)
Physical Design Automation of MCMs	501	(24)
MCM Technologies	502	(3)
MCM Physical Design Cycle	505	(2)
Partitioning	507	(3)
Placement	510	(3)
Chip Array Based Approach	512	(1)
Full Custom Approach	512	(1)
Routing	513	(8)
Classification of MCM Routing Algorithms	514	(1)
Maze Routing	514	(1)
Multiple Stage Routing	515	(1)
Pin Redistribution Problem	515	(2)
Layer Assignment	517	(1)
Detailed Routing	517	(1)
Topological Routing	517	(2)
Integrated Pin Distribution and Routing	519	(1)
Routing in Programmable Multichip Modules	519	(2)
Summary	521	(1)
Exercises	521	(4)
Bibliography	525	(38)
Author Index	563	(4)
Subject Index	567