Algorithms for VLSI Physical Design Automation

Algorithms for VLSI Physical Design Automation, Second Edition is a core reference text for graduate students and CAD professionals. Based on the very successful First Edition, it provides a comprehensive treatment of the principles and algorithms of VLSI physical design, presenting the concepts and algorithms in an intuitive manner. Each chapter contains 3-4 algorithms that are discussed in detail. Additional algorithms are presented in a somewhat shorter format. References to advanced algorithms are presented at the end of each chapter.
Algorithms for VLSI Physical Design Automation covers all aspects of physical design. In 1992, when the First Edition was published, the largest available microprocessor had one million transistors and was fabricated using three metal layers. Now we process with six metal layers, fabricating 15 million transistors on a chip. Designs are moving to the 500-700 MHz frequency goal. These stunning developments have significantly altered the VLSI field: over-the-cell routing and early floorplanning have come to occupy a central place in the physical design flow.
This Second Edition introduces a realistic picture to the reader, exposing the concerns facing the VLSI industry, while maintaining the theoretical flavor of the First Edition. New material has been added to all chapters, new sections have been added to most chapters, and a few chapters have been completely rewritten. The textual material is supplemented and clarified by many helpful figures.
Audience: An invaluable reference for professionals in layout, design automation and physical design.

1 VLSI Physical Design Automation.- 1.1 VLSI Design Cycle.- 1.2 New Trends in VLSI Design Cycle.- 1.3 Physical Design Cycle.- 1.4 New Trends in Physical Design Cycle.- 1.5 Design Styles.- 1.6 System Packaging Styles.- 1.7 Historical Perspectives.- 1.8 Existing Design Tools.- 1.9 Summary.- 2 Design and Fabrication of VLSI Devices.- 2.1 Fabrication Materials.- 2.2 Transistor Fundamentals.- 2.3 Fabrication of VLSI Circuits.- 2.4 Design Rules.- 2.5 Layout of Basic Devices.- 2.6 Additional Fabrication Factors.- 2.7 Summary.- 2.8 Exercises.- 3 Data Structures and Basic Algorithms.- 3.1 Basic Terminology.- 3.2 Complexity Issues and NP-hardness.- 3.3 Basic Algorithms.- 3.4 Basic Data Structures.- 3.5 Graph Algorithms for Physical design.- 3.6 Summary.- 3.7 Exercises.- 4 Partitioning.- 4.1 Problem Formulation.- 4.2 Classification of Partitioning Algorithms.- 4.3 Group Migration Algorithms.- 4.4 Simulated Annealing and Evolution.- 4.5 Other Partitioning Algorithms.- 4.6 Performance Driven Partitioning.- 4.7 Summary.- 4.8 Exercises.- 5 Placement, Floorplanning and Pin Assignment.- 5.1 Placement.- 5.2 Floorplanning.- 5.3 Pin Assignment.- 5.4 Integrated Approach.- 5.5 Summary.- 5.6 Exercises.- 6 Global Routing.- 6.1 Problem Formulation.- 6.2 Classification of Global Routing Algorithms.- 6.3 Maze Routing Algorithms.- 6.4 Line-Probe Algorithms.- 6.5 Shortest Path Based Algorithms.- 6.6 Steiner Tree based Algorithms.- 6.7 Integer Programming Based Approach.- 6.8 Summary.- 6.9 Exercises.- 7 Detailed Routing.- 7.1 Problem Formulation.- 7.2 Classification of Routing Algorithms.- 7.3 Single-Layer Routing Algorithms.- 7.4 Two-Layer Channel Routing Algorithms.- 7.5 Three-Layer Channel Routing Algorithms.- 7.6 Multi-Layer Channel Routing Algorithms.- 7.7 Switchbox Routing Algorithms.- 7.8 Summary.- 7.9 Exercises.- 8 Over-the-Cell Routing and Via Minimization.- 8.1 Over-the-cell Routing.- 8.2 Via Minimization.- 8.3 Summary.- 8.4 Exercises.- 9 Specialized Routing.- 9.1 Clock Routing.- 9.2 Power and Ground Routing.- 9.3 Summary.- 9.4 Exercises.- 10 Compaction.- 10.1 Problem Formulation.- 10.2 Classification of Compaction Algorithms.- 10.3 One-Dimensional Compaction.- 10.4 l -Dimensional Compaction.- 10.5 Two-Dimensional Compaction.- 10.6 Hierarchical Compaction.- 10.7 Summary.- 10.8 Exercises.- 11 Physical Design Automation of FPGAs.- 11.1 FPGA Technologies.- 11.2 Physical Design Cycle for FPGAs.- 11.3 Partitioning.- 11.4 Routing.- 11.5 Summary.- 11.6 Exercises.- 12 Physical Design Automation of MCMs.- 12.1 MCM Technologies.- 12.2 MCM Physical Design Cycle.- 12.3 Partitioning.- 12.4 Placement.- 12.5 Routing.- 12.6 Summary.- 12.7 Exercises.- Author Index.