Intro
Preface
Acknowledgments
Contents
About the Authors
1 Introduction
1.1 Precursors of VLSI
1.2 The rise of VLSI
1.3 Outline of book
2 Graph fundamentals
2.1 Graph categories
2.1.1 Hypergraph
2.1.2 Graphs with parallel edges
2.1.3 Graphs without parallel edges
2.1.4 Weighted graph
2.1.5 Directed graph
2.2 Inter-graph relationships
2.3 Graph exploration
2.4 Bipartite graph
2.5 Directed acyclic graph
2.6 Tree
2.7 Common problems in graph theory
2.7.1 Pathfinding
2.7.1.1 Depth-first search
2.7.1.2 Breadth-first search

2.7.1.3 Dijkstra's algorithm
2.7.1.4 Bellman-Ford
2.7.1.5 A* (A-star) algorithm
2.7.2 Spanning tree
2.7.2.1 Borůvka's algorithm
2.7.2.2 Prim's algorithm
2.7.2.3 Kruskal's algorithm
2.7.2.4 Advanced MST Algorithms
2.7.2.5 Steiner tree
2.7.3 Graph coloring
2.7.4 Topological sorting
2.8 Summary
3 Graphs in VLSI circuits and systems
3.1 Graphs as a VLSI abstraction tool
3.2 Register transfer level
3.2.1 Register allocation
3.2.2 Task scheduling
3.2.3 Synchronization
3.3 Gate layer
3.3.1 Ordered binary decision diagram

3.3.2 And-inverter graph
3.4 Circuit layer
3.4.1 Laplacian matrix of a circuit graph
3.5 Physical layer
3.5.1 Partitioning
3.5.2 Floorplanning
3.5.3 Placement
3.5.4 Routing
3.6 Summary
4 Synchronization in VLSI
4.1 Graph-based timing analysis
4.1.1 Timing constraints in synchronous systems
4.1.1.1 Local timing constraints
4.1.1.2 Global timing constraints
Serial data path.
Reconvergent (parallel) paths.
Cyclic data paths.
4.1.1.3 Constraint graph
4.2 Clock skew scheduling
4.2.1 Robustness
4.2.2 Performance
4.2.2.1 Wave pipelining

4.2.3 Power
4.3 Clock tree synthesis
4.3.1 Clock tree topology
4.3.2 Clock tree embedding
4.3.3 Method of means and medians
4.3.4 Deferred merge embedding
4.3.5 Elmore delay
4.3.6 Bounded skew tree
4.3.7 Useful skew tree
4.4 Summary
5 Circuit analysis
5.1 Modified nodal analysis
5.2 Iterative numerical methods
5.2.1 Domain decomposition
5.2.2 ps: [/EMC pdfmark [/Subtype /Span /ActualText (script upper H) /StPNE pdfmark [/StBMC pdfmarkHps: [/EMC pdfmark [/StPop pdfmark [/StBMC pdfmark-matrix
5.2.3 Multigrid methods
5.3 Non-MNA techniques

5.3.1 Scattering parameters
5.3.2 Random walks
5.3.3 Lattice graph
5.4 Summary
6 Effective resistance of truncated infinite mesh structures
6.1 Historical perspective
6.2 Electric potential in an infinite mesh
6.3 Electric potential within a truncated infinite mesh
6.3.1 Modeling truncation with image
6.3.1.1 Half-plane mesh
6.3.1.2 Quarter-plane mesh
6.3.2 Integral expressions for effective resistance
6.4 Closed-form approximation
6.5 Model evaluation
6.5.1 Accuracy evaluation
6.5.2 Computational speed
6.6 Conclusions