Graphs in VLSI

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. 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 translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.