Contents

Preface    
In the Classroom    
Acknowledgments    
Contributors    
About the Editors    
CHAPTER 1    Introduction
1.1    Overview of electronic design automation
    1.1.1 Historical perspective
    1.1.2 VLSI design flow and typical EDA flow
    1.1.3 Tvpical EDA implementation examples
    1.1.4 Problems and challenges
1.2    Logic design automation
    1.2.1 Modeling
    1.2.2 Design verification
    1.2.3 Logic synthesis
1.3    Test automation
    1.3.1 Fault models
    1.3.2 Design for testability
    1.3.3 Fault simulation and test generation
    1.3.4 Manufacturing test
1.4    Physical design automation
    1.4.1 Floorplanning
    1.4.2 Placement
    1.4.3 Routing
    1.4.4 Synthesis of clock and power/ground networks
1.5    Concluding remarks
1.6    Exercises
Acknowledgments    
References    
CHAPTER 2    Fundamentals of CMOS design
2.1    Introduction
2.2    Integrated circuit technology
    2.2.1 MOS transistor
    2.2.2 Transistor equivalency
    2.2.3 Wire and interconnect
    2.2.4 Noise margin
2.3    CMOS logic
    2.3.1 CMOS inverter and analysis
    2.3.2 Design of CMOS logic gates and circuit blocks
    2.3.3 Design of latches and flip-flops.
    2.3.4 Optimization techniques for high performance
2.4    Integrated circuit design techniques
    2.4.1 Transmission-gate/pass-transistor logic
    2.4.2 Differential CMOS logic
    2.4.3 Dynamic pre-charge logic
    2.4.4 Domino logic
    2.4.5 No-race logic
    2.4.6 Single-phase logic
2.5    CMOS physical design
    2.5.1 Layout design rules
    2.5.2 Stick diagram
    2.5.3 Layout design
2.6    Low-power circuit design techniques
    2.6.1 Clock-gating
    2.6.2 Power-gating
    2.6.3 Substrate biasing
    2.6.4 Dynamic voltage and frequency scaling
    2.6.5 Low-power cache memory design
2.7    Concluding remarks
2.8    Exercises
Acknowledgments
References    
CHAPTER 3 Design for testability
3.1    Introduction
3.2    Testability analysis
    3.2.1    SCOAP testability analysis
    3.2.2    Probability-based testability analysis
    3.2.3    Simulation-based testability analysis
3.3    Scan design
    3.3.1 Scan architectures
    3.3.2 At-speed testing
3.4    Logic built-in self-test
    3.4.1    Test pattern generation
    3.4.2    Output response analysis
    3.4.3    Logic BIST architectures
    3.4.4    Industry practices
3.5    Test Compression
    3.5.1    Circuits for test stimulus compression
    3.5.2    Circuits for test response compaction
    3.5.3    Industry practices
3.6    Concluding remarks
3.7    Exercises
Acknowledgments
References
CHAPTER 4 Fundamentals of algorithms
4.1    Introduction
4.2    Computational complexity
    4.2.1    Asymptotic notations
    4.2.2    Complexity classes
4.3    Graph algorithms
    4.3.1    Terminology
    4.3.2    Data structures lor representations of graphs
    4.3.3    Breadth-first search and depth-first search
    4.3.4    Topological sort
    4.3 5    Strongly connected component
    4.3.6    Shortest and longest path algorithms
    4.3.7    Minimum spanning tree
    4.3.8    Maximum flow and minimum cut
4.4    Heuristic algorithms
    4.4.1    Greedy algorithm
    4.4.2    Dynamic programming
    4.4.3    Branch-and-bound
    4.4.4    Simulated annealing
    4.4.5    Genetic algorithms
4.5    Mathematical programming
    4.5.1    Categories of mathematical programming problems
    4.5.2    Linear programming (LP) problem
    4.5.3    Integer linear programming (ILP) problem
    4.5.4    Convex optimization problem
4.6    Concluding remarks
4.7    Exercises
Acknowledgments
References
CHAPTER 5 Electronic system-level design and high-level synthesis
5.1    Introduction
    5.1.1    ESL design methodology
    5.1.2    Function-based ESL methodology
    5.1.3    Architecture-based ESL methodology
    5.1.4    Function architecture codesign methodology
    5.1.5    High-level synthesis within an ESL design methodology
5.2    Fundamentals of High-level synthesis.
    5.2.1    TinyC as an example for behavioral descriptions
    5.2.2    Intermediate representation in TinylR
    5.2.3    RTL representation in TinyRTL
    5.2.4    Structured hardware description in FSMD
    5.2.5    Quality metrics
5.3    High-level synthesis algorithm overview
5.4    Scheduling
    5.4.1    Dependency test
    5.4.2    Unconstrained scheduling
    5.4.3    Resource-constrained scheduling
5.5    Register binding
    5.5.1    Liveness analysis
    5.5.2    Register binding by coloring
5.6    Functional unit binding
5.7    Concluding remarks
5.8    Exercises
Acknowledgments
References
CHAPTER 6 Logic synthesis in a nutshell
6.1    Introduction
6.2    Data Structures for Boolean representation and reasoning
    6.2.1    Quantifier-free and quantified Boolean formulas
    6.2.2    Boolean function manipulation
    6.2.3    Boolean function representation
    6.2.4    Boolean representation conversion
    6.2.5    Isomorphism between sets and characteristic functions
    6.2.6    Boolean reasoning engines
6.3    Combinational logic minimization
    6.3.1    Two-level logic minimization
    6.3.2    SOP minimization
    6.3.3    Multilevel logic minimization
    6.3.4    Combinational complete flexibility
    6.3.5 Advanced subjects
6.4    Technology mapping
    6.4.1    Technology libraries
    6.4.2    Graph covering
    6.4.3    Choice of atomic pattern set
    6.4.4    Tree covering approximation
    6.4.5    Optimal tree covering
    6.4.6    Improvement by inverter-pair insertion
    6.4.7    Extension to non-tree patterns
    6.4.8    Advanced subjects
6.5    Timing analysis
    6.5.1    Topological timing analysis
    6.5.2    Functional timing analysis
    6.5.3    Advanced subjects
6.6    Timing optimization
    6.6.1    Technology-independent timing optimization
    6.6.2    Timing-driven technology mapping
    6.6.3    Advanced subjects
6.7    Concluding remarks
6.8    Exercises
Acknowledgments
References
CHAPTER 7 Test synthesis
7.1    Introduction
7.2    Scan design
    7.2.1    Scan design rules
    7.2.2    Scan design flow
7.3    Logic built-in self-test (BIST) design
    7.3.1    BIST design rules
    7.3.2    BIST design example
7.4    RTL Design for testability
    7.4.1    RTL scan design rule checking and repair
    7.4.2    RTL scan synthesis
    7.4.3    RTL scan extraction and scan verification
7.5    Concluding remarks
7.6    Exercises
Acknowledgments
References
CHAPTER 8 Logic and circuit simulation
8.1    Introduction
    8.1.1    Logic simulation
    8.1.2    Hardware-accelerated logic simulation
    8.1.3    Circuit simulation
8.2    Logic simulation models
    8.2.1    Logic symbols and operations
    8.2.2    Timing models
8.3    Logic simulation techniques
    8.3.1    Compiled-code simulation
    8.3.2    Event-driven simulation
8.4    Hardware-accelerated logic simulation
    8.4.1    Types of hardware acceleration
    8.4.2    Reconfigurable computing units
    8.4.3    Interconnection architectures
    8.4.4    Timing issues
8.5    Circuit simulation models
    8.5.1    Ideal voltage and current sources
    8.5.2    Resistors, capacitors, and inductors
    8.5.3    KirchhofFs voltage and current laws
    8.5.4    Modified nodal analysis
8.6    Numerical methods ft)r transient analysis
8.6.1    Approximation methods and numerical integration
8.6.2    Initial value problems
8.7    Simulation of VLSI interconnects
8.7.1    Wire resistance
8.7.2    Wire capacitance
8.7.3    Wire inductance
8.7.4    Lumped and distributed models
8.7.5    Simulation procedure for interconnects
8.8    Simulation of nonlinear devices
8.8.1    The diode
8.8.2    The field-effect transistor
8.8.3    Simulation procedure for nonlinear devices
8.9    Concluding remarks
8.10 Exercises
Acknowledgments
References
CHAPTER 9 Functional verification
9.1    Introduction
9.2    Verification hierarchy
    9.2.1    Designer-level verification
    9.2.2    Unit-level verification
    9.2.3    Core-level verification
    9.2.4    Chip-level verification
    9.2.5    System-/board4evel verification
9.3    Measuring verification quality
    9.3.1    Random testing
    9.3.2    Coverage-driven verification
    9.3.3    Structural coverage metrics
    9.3.4    Functional coverage metrics
9.4    Simulation-based approach
    9.4.1    Testbench and simulation environment development
    9.4.2    Methods of observation points
    9.4.3    Assertion-based verification
9.5    Formal approaches
    9.5.1    Equivalence checking
    9.5.2    Model checking (property checking)
    9.5.3    Theorem proving
9.6    Advanced research
9.7    Concluding remarks
9.8    Exercises
Acknowledgments
References
CHAPTER 10 Floorplanning
10.1    Introduction
    10.1.1    Floorplanning basics
    10.1.2    Problem statement
    10.1.3    Floorplanning model
    10.1.4    Floorplanning cost
10.2    Simulated annealing approach
    10.2.1    Simulated annealing basics
    10.2.2    Normalized Polish expression for slicing floorplans
    10.2.3    B*-tree for compacted floorplans
    10.2.4    Sequence pair floor general floorplans
    10.2.5    Floorplan representation comparison
10.3    Analytical approach
10.4    Modern floorplanning considerations
    10.4.1    Soft modules
    10.4.2    Fixed-outline constraint
    10.4.3    Floorplanning lor large-scale circuits
    10.4.4    Other considerations and topics
10.5    Concluding remarks
10.6    Exercises
Acknowledgments
References
CHAPTER 11 Placement
11.1    Introduction
11.2    Problem formulations
    11.2.1    Placement for different design styles
    11.2.2    Placement objectives
    11.2.3    A common placement formulation
11.3    Global placement: partitioning-based approach
    11.3.1    Basics for partitioning
    11.3 2    Placement by partitioning
    11.3.3    Practical implementations
11.4    Global placement: simulated annealing approach
    11.4.1    The placement algorithm in TimberWolf
    11.4.2    The Dragon placement algorithm
11.5    Global placement: analytical approach
    11.5.1    An exact formulation
    11.5.2    Quadratic techniques
    11.5.3    Nonquadratic techniques
    11.5.4    Extension to multilevel
11.6    Legalization
11.7    Detailed placement
    11.7.1    The Domino algorithm
    11.7.2    The FastDP algorithm
11.8    Concluding Remarks
11.9    Exercises
Acknowledgments
References
CHAPTER 12 Global and detailed routing
12.1    Introduction
12.2    Problem definition
    12.2.1    Routing model
    12.2.2    Routing constraints
12.3    General-purpose routing
    12.3.1    Maze routing
    12.3.2    Line-search routing
    12.3.3    A*-search routing
12.4    Global routing
    12.4.1    Sequential global routing
    12.4.2    Concurrent global routing
    12.4.3    Steiner trees
12.5    Detailed Routing
    12.5.1    Channel routing
    12.5.2    Full-chip routing
12.6    Modern routing considerations
    12.6.1    Routing for signal integrity
    12.6.2    Routing for manufacturability
    12.6.3    Routing for reliability
12.7    Concluding remarks
12.8    Exercises
Acknowledgments
References
CHAPTER 13 Synthesis of clock and power/ground networks
13.1    Introduction
13.2    Design considerations
    13.2.1    Timing constraints
    13.2.2    Skew and Jitter
    13.2.3    IR drop and L di/dt noise
    13.2.4    Power dissipation
    13.2.5    Electromigration
13.3    Clock Network design
    13.3.1    Typical clock topologies
    13.3.2    Clock network modeling and analysis
    13.3.3    Clock tree synthesis
    13.3.4    Clock tree optimization
13.4    Power/ground network design
    13.4.1    Typical power/ground topologies
    13.4.2    Power/ground network analysis
    13.4.3    Power/ground network synthesis
13.5    Concluding remarks
13.6    Exercises
Acknowledgments
References
CHAPTER 14 Fault Simulation and Test Generation
14.1    Introduction
14.2    Fault Collapsing
    14.2.1    Equivalence fault collapsing
    14.2.2    Dominance fault collapsing
14.3    Fault Simulation
    14.3.1    Serial fault simulation
    14.3 2    Parallel fault simulation
    14.3.3    Concurrent fault simulation
    14.3.4    Differential fault simulation
    14.3 5    Comparison of fault simulation techniques
14.4    Test Generation
    14.4.1    Random test generation.
    14.4.2    Theoretical Background: Boolean difference
    14.4.3    Designing a stuck-at ATPG for combinational circuits
    14.4.4    PODEM.
    14.4.5    FAN.
14.5    Advanced Test Generation
    14.5.1    Sequential ATPG: Time frame expansion
    14.5.2    Delay fault ATPG
    14.5.3    Bridging fault ATPG
14.6    Concluding Remarks
14.7    Exercises
Acknowledgments
References
Index