Table of Contents
I Preliminaries
1 Introduction to Design Methodologies
1.1 The VLSI Design Problem
1.2 The Design Domains
1.3 Design Actions
1.4 Design Methods and Technologies
1.5 Bibliographic Notes
2 A Quick Tour of VLSI Design Automation Tools
2.1 Algorithmic and System Design
2.2 Structural and Logic Design
2.3 Transistor-level Design
2.4 Layout Design
2.5 Verification Methods
2.6 Design Management Tools
2.7 Bibliographic Notes
3 Algorithmic Graph Theory and Computational Complexity
3.1 Terminology
3.2 Data Structures for the Representation of Graphs
3.3 Computational Complexity
3.4 Examples of Graph Algorithms
3.4.1 Depth-first Search
3.4.2 Breadth-first Search
3.4.3 Dijkstra's Shortest-path Algorithm
3.4.4 Prim's Algorithm for Minimum Spanning Trees
3.5 Bibliographic Notes
3.6 Exercises
4 Tractable and Intractable Problems
4.1 Combinatorial Optimization Problems
4.2 Decision Problems
4.3 Complexity Classes
4.4 NP-completeness and NP-hardness
4.5 Consequences
4.6 Bibliographic Notes
4.7 Exercises
5 General-purpose Methods for Combinatorial Optimization
5.1 The Unit-size Placement Problem
5.2 Backtracking and Branch-and-bound
5.2.1 Backtracking
5.2.2 Branch-and-bound
5.3 Dynamic Programming
5.4 Integer Linear Programming
5.4.1 Linear Programming
5.4.2 Integer Linear Programming
5.5 Local Search
5.6 Simulated Annealing
5.7 Tabu Search
5.8 Genetic Algorithms
5.9 A Few Final Remarks on General-purpose Methods
5.10 Bibliographic Notes
II Selected Design Problems and Algorithms
6 Layout Compaction
6.1 Design Rules
6.2 Symbolic Layout
6.3 Problem Formulation
6.3.1 Applications of Compaction
6.3.2 Informal Problem Formulation
6.3.3 Graph-theoretical Formulation
6.3.4 Maximum-distance Constraints
6.4 Algorithms for Constraint-graph Compaction
6.4.1 A Longest-path Algorithm for DAGs
6.4.2 The Longest Path in Graphs with Cycles
6.4.3 The Liao- Wong Algorithm
6.4.4 The Bellman-Ford Algorithm
6.4.5 Discussion: Shortest Paths, Longest Paths and Time Complexity
6.5 Other Issues
6.6 Bibliographic Notes
6.7 Exercises
7 Placement and Partitioning
7.1 Circuit Representation
7.2 Wire-length Estimation
7.3 Types of Placement Problem
7.4 Placement Algorithms
7.4.1 Constructive Placement
7.4.2 Iterative Improvement
7.5 Partitioning
7.5.1 The Kernighan-Lin Partitioning Algorithm
7.6 Bibliographic Notes
7.7 Exercises
8 Floorplanning
8.1 Floorplanning Concepts
8.1.1 Terminology and Floorplan Representation
8.1.2 Optimization Problems in Floorplanning
8.2 Shape Functions and Floorplan Sizing
8.3 Bibliographic Notes
8.4 Exercises
9 Routing
9.1 Types of Local Routing Problems
9.2 Area Routing
9.3 Channel Routing
9.3.1 Channel Routing Models
9.3.2 The Vertical Constraint Graph
9.3.3 Horizontal Constraints and the Left-edge Algorithm
9.3.4 Channel Routing Algorithms
9.4 Introduction to Global Routing
9.4.1 Standard-cell Layout
9.4.2 Building-block Layout and Channel Ordering
9.5 Algorithms for Global Routing
9.5.1 Problem Definition and Discussion
9.5.2 Efficient Rectilinear Steiner-tree Construction
9.5.3 Local Transformations for Global Routing
9.6 Bibliographic Notes
9.7 Exercises
10 Simulation
10.1 General Remarks on VLSI Simulation
10.2 Gate-level Modeling and Simulation
10.2.1 Signal Modeling
10.2.2 Gate Modeling
10.2.3 Delay Modeling
10.2.4 Connectivity Modeling
10.2.5 Compiler-driven Simulation
10.2.6 Event-driven Simulation
10.3 Switch-level Modeling and Simulation
10.3.1 Connectivity and Signal Modeling
10.3.2 Simulation Mechanisms
10.4 Bibliographic Notes
10.5 Exercises
11 Logic Synthesis and Verification
11.1 Introduction to Combinational Logic Synthesis
11.1.1 Basic Issues and Terminology
11.1.2 A Practical Example
11.2 Binary-decision Diagrams
11.2.1 ROBDD Principles
11.2.2 ROBDD Implementation and Construction
11.2.3 ROBDD Manipulation
11.2.4 Variable Ordering
11.2.5 Applications to Verification
11.2.6 Applications to Combinatorial Optimization
11.3 Two-level Logic Synthesis
11.3.1 Problem Definition and Analysis
11.3.2 A Heuristic Based on ROBDDs
11.4 Bibliographic Notes
11.5 Exercises
12 High-level Synthesis
12.1 Hardware Models for High-level Synthesis
12.1.1 Hardware for Computations, Data Storage, and Interconnection
12.1.2 Data, Control, and Clocks
12.2 Internal Representation of the Input Algorithm
12.2.1 Simple Data Flow
12.2.2 Conditional Data Flow
12.2.3 Iterative Data Flow
12.2.4 Data-flow Graph Representation
12.3 Allocation, Assignment and Scheduling
12.3.1 Goals and Terminology
12.3.2 A Detailed Example
12.3.3 Optimization Issues
12.4 Some Scheduling Algorithms
12.4.1 ASAP Scheduling
12.4.2 Mobility-based Scheduling
12.4.3 Force-directed Scheduling
12.4.4 List Scheduling
12.5 Some Aspects of the Assignment Problem
12.5.1 Optimization Issues
12.5.2 Graph Theoretical Problem Formulation
12.5.3 Assignment by Interval and Circular-arc Graph Coloring
12.5.4 Assignment by Clique Partitioning
12.6 High-level Transformations
12.7 Bibliographic Notes
12.8 Exercises
III Appendices
A CMOS Technology
A.1 The MOS Transistor and CMOS Logic Design
A.2 Transistor Layout in CMOS and Related Issues
A.3 Bibliographic Notes
B About the Pseudo-code Notation
B.1 Data Structures and Declarations
B.2 C-language Constructs
B.3 Pseudo-code Constructs
B.4 Bibliographic Notes
C List of Acronyms
References
Index