VLSI Physical Design Automation : Theory and Practice

by Sait, Sadiq M.; Youssef, Habib

• ISBN13: 9789810238834
• ISBN10: 9810238835
• Format: Hardcover
• Copyright: 1999-12-01
• Publisher: Textstream

Summary

Discusses VLSI design automation and chip layout. Provides an essential introduction for senior undergraduates, postgraduates and anyone starting work in the field of CAD for VLSI. Deals with all aspects of VLSI physical design. Covers the latest developments of VLSI.

Table of Contents

Foreword	vii
Preface	ix
Introduction	1	(40)
VLSI Design	1	(1)
The VLSI Design Process	2	(7)
Architectural Design	3	(4)
Logic Design	7	(1)
Physical Design	7	(2)
Layout Styles	9	(14)
Full-custom Layout	9	(3)
Gate-array Layout	12	(2)
Standard-cell Layout	14	(3)
Macro-cell Layout	17	(2)
Programmable Logic Arrays	19	(2)
FPGA layout	21	(2)
Difficulties in Physical Design	23	(4)
Problem Subdivision	24	(1)
Computational Complexity of Layout Subproblems	25	(2)
Solution Quality	27	(1)
Definitions and Notation	27	(7)
Nets and Netlists	28	(1)
Connectivity Information	29	(3)
Weighted Nets	32	(1)
Grids, Trees, and Distances	32	(2)
Summary	34	(2)
Organization of the book	36	(5)
Circuit Partitioning	41	(50)
Introduction	41	(2)
Problem Definition	43	(1)
Cost Function and Constraints	44	(2)
Bounded Size Partitions	44	(1)
Minimize External Wiring	45	(1)
Approaches to Partitioning Problem	46	(34)
Kernighan-Lin Algorithm	48	(10)
Variations of Kernighan-Lin Algorithm	58	(1)
Fiduccia Mattheyses Heuristic	59	(11)
Simulated Annealing	70	(10)
Other Approaches and Recent Work	80	(2)
Conclusion	82	(1)
Bibliographic Notes	83	(8)
Floorplanning	91	(70)
Introduction	91	(1)
Problem Definition	92	(9)
Floorplanning Model	92	(2)
Cost Functions	94	(2)
Terminology	96	(5)
Approaches to Floorplanning	101	(48)
Cluster Growth	102	(6)
Simulated Annealing	108	(14)
Analytical Technique	122	(8)
Dual Graph Technique	130	(19)
Other Approaches and Recent Work	149	(2)
Conclusion	151	(1)
Bibliographic Notes	152	(9)
Placement	161	(72)
Introduction	161	(3)
Complexity of Placement	163	(1)
Organization of the Chapter	164	(1)
Problem Definition	164	(1)
Cost Functions and Constraints	165	(11)
Estimation of Wirelength	165	(3)
Minimize Total Wirelength	168	(1)
Minimize Maximum Cut	169	(3)
Minimize Maximum Density	172	(1)
Maximize Performance	173	(2)
Other Constraints	175	(1)
Approaches to Placement	176	(30)
Partition-Based Methods	179	(5)
Limitation of the Min-cut Heuristic	184	(5)
Simulated Annealing	189	(8)
Numerical Techniques	197	(9)
Other Approaches and Recent Work	206	(13)
Artificial Neural Networks	206	(5)
Genetic Algorithm	211	(8)
Conclusion	219	(1)
Bibliographic Notes	220	(13)
Grid Routing	233	(44)
Introduction	233	(1)
Problem Definition	234	(1)
Cost Functions and Constraints	235	(3)
Placement Constraints	237	(1)
Number of Routing Layers	237	(1)
Geometrical Constraints	238	(1)
Maze Routing Algorithms	238	(15)
Lee Algorithm	239	(2)
Limitations of Lee Algorithm for Large Circuits	241	(3)
Connecting Multi-point Nets	244	(2)
Finding More Desirable Paths	246	(4)
Further Speed Improvements	250	(3)
Line Search Algorithms	253	(3)
Other Issues	256	(11)
Multi Layer Routing	257	(3)
Ordering of Nets	260	(5)
Rip-up and Rerouting	265	(1)
Power and Ground Routing	265	(2)
Other Approaches and Recent Work	267	(1)
Conclusions	268	(1)
Bibliographic Notes	269	(8)
Global Routing	277	(50)
Introduction	277	(1)
Cost Functions and Constraints	278	(1)
Routing Regions	279	(13)
Routing Regions Definition	280	(10)
Routing Regions Representation	290	(2)
Sequential Global Routing	292	(10)
The Steiner Tree Problem	293	(3)
Global Routing by Maze Running	296	(6)
Integer Programming	302	(4)
Global Routing by Simulated Annealing	306	(7)
The First Stage	307	(5)
The Second Stage	312	(1)
Hierarchical Global Routing	313	(2)
Other Approaches and Recent Work	315	(3)
Conclusions	318	(1)
Bibliographic Notes	319	(8)
Channel Routing	327	(50)
Introduction	327	(1)
Problem Definition	328	(4)
Constraint Graphs	329	(3)
Cost function and Constraints	332	(1)
Approaches to Channel Routing	333	(31)
The Basic Left-Edge Algorithm	333	(5)
Dogleg Algorithm	338	(3)
Yoshimura and Kuh Algorithm	341	(11)
Greedy Channel Router	352	(7)
Switchbox Routing	359	(5)
Other Approaches and Recent Work	364	(8)
Conclusions	372	(1)
Bibliographic Notes	373	(4)
Layout Generation	377	(56)
Introduction	377	(6)
Behavioral Level	377	(1)
Structural Level	378	(1)
Physical Level	379	(4)
Layout Generation	383	(5)
Standard-cells	385	(1)
Gate-matrix Methodology	386	(1)
Programmable Logic Array	386	(2)
Standard-cell Generation	388	(9)
Optimization of Standard-cell Layout	391	(6)
Optimization of Gate-matrix Layout	397	(8)
Programmable Logic Arrays	405	(17)
PLA Personality	408	(2)
Optimization of PLAs	410	(12)
Other Approaches and Recent Work	422	(4)
Conclusion	426	(1)
Bibliographic Notes	426	(7)
Layout Editors and Compaction	433	(30)
Introduction	433	(8)
Capabilities of Layout Editors	434	(1)
Introduction to Magic Layout System	435	(6)
Layout Compaction	441	(13)
Compaction Algorithms	444	(1)
Horizontal Virtual Grid Compaction	445	(2)
Constraint Graph Compaction	447	(7)
Other Approaches and Recent Work	454	(1)
Conclusion	455	(1)
Bibliographic Notes	456	(7)
Appendix A Graph Theory and Complexity of Algorithms	463	(8)
A.1 Graph Theory	463	(2)
A.2 Complexity of Algorithms	465	(2)
A.2.1 Big-Omega Notation	466	(1)
A.2.2 Big-Oh Notation	466	(1)
A.2.3 Big-Theta Notation	467	(1)
A.3 Hard Problems vs. Easy Problems	467	(4)
A.3.1 NP-complete Problems and Reduction	469	(2)
Index	471