Graph Algorithms for VLSI Power and Clock Networks

Rassul Bairamkulov

Supervised by Professor Eby Friedman

Computer Studies Building Room 426

Join Zoom Link:
https://rochester.zoom.us/j/97272800091

The exponential growth in the computational capabilities of humankind cannot be sustained without innovative design methodologies to manage the immense complexity of VLSI systems. To facilitate cooperation across diverse disciplines, the IC design process is composed of multiple abstraction layers. Decomposition of the VLSI process into discrete components enables the automation of manually intractable circuit design tasks. Graph theory plays an important role in electronic design automation (EDA) by providing powerful and versatile algorithms to tackle a variety of VLSI system design issues at each layer of abstraction. In this dissertation, a diverse spectrum of applications of graph theory in the design of VLSI circuits is discussed, ranging from coloring-based register allocation at the register transfer layer to tree-based floor planning at the physical layer.

Graph-based synthesis of VLSI power and clock distribution networks is emphasized in this dissertation. By exploiting the duality between a random walk within a graph and resistive electrical networks, an efficient algorithm for analyzing arbitrarily large power grids is proposed. Based on this model, a set of voltage regulators are efficiently distributed within a power grid, drastically improving the power integrity of a synthesized integrated system.

To facilitate the development of power distribution networks at early stages of the system design process, the Smart Power ROUTing (SPROUT) tool for power delivery exploration and prototyping at the board level is proposed. By converting the physical layout of the power network into a graph, prototypical physical layouts of a power network are efficiently created. From an analysis of these prototypes, the power network characteristics can be accurately predicted during early stages of the design process.

Finally, graph theory is applied to synthesize clock distribution network for super- conductive single flux quantum (SFQ) integrated circuits. A clock skew scheduling algorithm, originally developed for CMOS circuits, is adapted to synchronize SFQ circuits. Based on a schedule of clock arrival times produced for SFQ systems, a clock tree topology is determined. Using the proposed proxy graph technique, a clock tree layout based on the clock tree topology is synthesized.