Networks are pervasive. Very large scale integrated (VLSI) systems are no different, consisting of dozens of interconnected subsystems, hundreds of modules, and many billions of transistors and wires. Graph theory is crucial for managing and analyzing these systems. In this book, VLSI system design is discussed from the perspective of graph theory. Starting from theoretical foundations, the authors uncover the link connecting pure mathematics with practical product development. This book not only provides a review of established graph theoretic practices, but also discusses the latest advancements in graph theory driving modern VLSI technologies, covering a wide range of design issues such as synchronization, power network models and analysis, and interconnect routing and synthesis.- Provides a practical introduction to graph theory in the context of VLSI systems engineering;
- Reviews comprehensively graph theoretic methods and algorithms commonly used during VLSI product development process;
- Includes a review of novel graph theoretic methods and algorithms for VLSI system design.
Author(s): Rassul Bairamkulov, Eby G. Friedman
Publisher: Springer
Year: 2022
Language: English
Pages: 355
City: Cham
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
7 Effective resistance of finite grids
7.1 Infinity mirror technique
7.1.1 Infinite strip
7.1.2 Semi-infinite strip
7.1.3 Finite mesh
7.1.4 Generalization to higher dimensions
7.2 Simplification of the effective resistance expressions
7.3 Case studies
7.3.1 Mesh reduction based on effective resistance
7.3.2 Resistive noise in capacitive touch screen
7.3.3 Resistive substrate noise
7.4 Conclusions
8 Placement of on-chip distributed voltage regulators
8.1 On-chip voltage regulation
8.2 Model of power network
8.2.1 Fast grid analysis
8.2.2 Limited regulator current
8.3 Load clustering
8.4 Optimization setup
8.5 Case studies
8.5.1 Unrestricted placement – case study one
8.5.2 Restricted placement – case study two
8.5.3 Restricted current – case study three
8.6 Conclusions
9 Exploratory methodology for power delivery
9.1 Optimization framework
9.1.1 Specification of the electrical design requirements
9.1.2 Specification of non-electrical design requirements
9.1.3 Combination of electrical and nonelectrical metrics
9.1.4 Circuit simulation procedure
9.2 Case studies
9.2.1 Single rail system
9.2.1.1 Optimization setup
9.2.1.2 Optimization results
9.2.2 Multiple rail system
9.3 Conclusions
10 SPROUT - Smart Power ROUting Tool for board-level exploration and prototyping
10.1 SPROUT algorithm
10.1.1 Available routing space
10.1.2 Equivalent graph
10.1.3 Seed subgraph
10.1.4 Growth stage
10.1.5 Refinement stage
10.1.6 Subgraph reheating
10.1.7 Back conversion
10.1.8 Algorithm runtime analysis
10.2 Validation of case study
10.2.1 Two rail system
10.2.2 Six rail system
10.2.3 Area/impedance tradeoff
10.3 Conclusions
11 QuCTS – single flux Quantum Clock Tree Synthesis
11.1 Clock skew scheduling
11.1.1 Timing graph
11.1.2 Minimum clock period
11.1.3 Clock skew optimization
11.2 Clock tree synthesis
11.3 Delay equilibration
11.3.1 Coarse routing
11.3.2 Analysis of proxy path delay
11.3.3 Fine routing
11.4 Case study
11.5 Conclusions
12 Conclusions
A Green's function for a truncated grid
B Uniqueness based on boundary conditions
C Multilayer routing algorithm
References
Index
