Rassul Bairamkulov - Graphs in VLSI

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Advances in semiconductor fabrication technology have produced explosive growth in the number of transistors within an integrated circuit (IC). Modern devices consist of dozens of components, thousands of modules, millions of registers, and many billions of transistors. Despite the capacity to fabricate exorbitant quantities of nanoscale devices, converting these transistors into functional products is a complex multifaceted challenge. Synchronization, power integrity, logic synthesis, and physical layout represent only a small portion of the many issues encountered during the very large scale integration (VLSI) design and analysis process. These issues are only expected to grow in complexity as microelectronic systems evolve due to three-dimensional integration, shrinking transistor dimensions, and emerging, beyond CMOS technologies.

Since every integrated system is fundamentally a network, solutions to many of the challenges inherent to VLSI can be resolved using graph theory. Many forms of graphs naturally occur at each level of the VLSI system design hierarchy. At the architectural level, register allocation is often viewed from a graph coloring perspective. Synchronization of the sequential logic is achieved by optimizing timing graphs. The electrical characteristics of a VLSI system are determined from the analysis of circuit graphs. Graph-based partitioning, floorplanning, placement, and routing are integral parts of the multi-tiered VLSI physical layout process.

The quality and complexity of ICs have been greatly enhanced by graph theoretic techniques and algorithms. In return, novel practical VLSI applications have revitalized certain subfields of graph theory. Classic graph theoretic problems, such as Steiner minimal trees, pathfinding, and graph partitioning, have been extensively studied and applied, in no small part, due to the practical effectiveness of graph theory to the design and analysis of VLSI systems. A virtuous cycle of theory and application has greatly advanced both graph theory and ever more powerful VLSI systems.

These observations are reflected in the organization of this book. The first half of the book is focused on existing applications of graph theory and algorithms to the design of integrated systems. After a brief description of the fundamental concepts of graph theory, common applications of graph theory at different levels of abstraction within the VLSI system design process are discussed. Individual chapters are dedicated to synchronization and circuit analysis, two particularly important issues in the VLSI design process which are deeply affected by graph theory.

The second half of the book is focused on three novel unorthodox applications of graph theory. The first application is the Infinity Mirror Technique (IMT) a constant time mesh analysis algorithm accelerating the IR drop analysis process in practical on-chip power networks by several orders of magnitude. An IMT-based computationally efficient algorithm for on-chip voltage regulator distribution is also described. The second application is related to the exploration of system-level power delivery. The SPROUT Smart Power ROUTing algorithm is presented to efficiently produce a prototype of a board-level power network, enabling efficient analysis with high-level architectural tradeoffs, such as the number of layers within the board or the position of discrete components. The second half of the book is completed with QuCTS single flux Quantum Clock Tree Synthesis algorithm, which describes a graph-based algorithm to satisfy the stringent requirements for clock distribution networks in superconductive electronics.

Due to the focus on the VLSI design process, this book is expected to become a useful addition to the library of engineers, researchers, and students working in the areas of VLSI system design and computer science. For professionals working in the design of VLSI systems (typically electrical and computer engineers and computer scientists), this book provides a deeper insight into the theory behind many established design techniques based on graph theory, such as clock skew scheduling, system partitioning, circuit analysis and optimization, and interconnect routing. For mathematicians and computer scientists, the book elucidates the link between graph theory and the design and analysis of VLSI circuits and systems.