Efficient and reliable transient simulators are essential for VLSI designs due to the increasing size and design complexity. In this dissertation, we explore the advanced time integration algorithms for solving the dynamical systems of VLSI circuits. We aim to reveal the numerical performance of our proposed simulation framework with matrix exponential based integration algorithms and illustrate its advantages over the conventional methods.

Pre-2018 CSE ID: CS2000-0662

Pre-2018 CSE ID: CS2002-0706

In the past decades, semiconductor technologies have significantly contributed to the modern society and human welfare, and led entire industries toward more automated systems with advancement of integrated circuits (ICs). Innovations and achievements on physical design (PD) have guided progresses of modern VLSI designs and automation. With the advanced performance of ICs, the overall industry has been profitable, and the global semiconductor market size has shown an upward-climbing trend for the past decades. Consequently, high-performance ICs enable the recent advent of the fourth industrial revolution that evolves almost every industry, e.g., artificial intelligence (AI), the Internet of things (IoT), bio- and nano-technology, autonomous vehicles, robotics, etc.

While “Moore’s Law” and “Dennard Scaling” have shown the correction of the slowing down, designing IC has become much more sophisticated and complicated. IC layout design directly impacts on timing closure, die utilization, routability, and design turnaround time (TAT); these in turn affect the classic design metrics of operating frequency, yield, power consumption and cost. As a result, physical design engineers face many nontrivial challenges, and the overall design cost increases rapidly. The industries look for higher efficiency in design optimization, automation, and innovation for high-performance ICs and design-cost reduction.

This dissertation describes new design methodologies for the advanced IC layout development and design automation. Chapter 2 introduces new three-dimensional (3-D) floorplan representations, corner links, four trees, and partial order, which enhance 3-D IC physical design automation. Our floorplan representations are potentially extendable toward multiple dimensions by adding factors such as time, energy, temperature, security, etc. Chapter 3 describes our constraint-driven and routability-driven global placement engine, RePlAce. RePlAce is a flat, nonlinear analytical global placement engine with electrostatics-based global-smooth density cost function. RePlAce addresses routing congestion as well as classical design goals (such as wirelength, area, etc.) with analogy of charge and electrical potential distribution. Chapter 4 presents a new framework that quickly identifies the design rule-correct routability through well-organized Boolean satisfiability (SAT) formulation. Our routability analysis method is developed on top of the multi-commodity flow theory and SAT-friendly ILP-based (integer linear programming-based) detailed routing formulation.

With the relentless scaling of technology nodes, VLSI design engineers encounter non-trivial challenges, particularly in the physical layout and multiprocessor system-on-chips design. Thus, a holistic exploration, co-optimizing the design/process side of the technology/system architecture, becomes an essential approach to maintaining the power, performance, area, and cost (PPAC) gain. Those co-optimizations require fidelity in terms of the optimality of solutions. However, most of the VLSI application problems are NP-complete so the complexity of derivation is too huge to find an optimal solution. Therefore, many conventional works focus on divide-and-conquer-style and/or heuristic approaches due to the intrinsic scalability limitation of the problem. As a result, outcomes of these approaches are hard to reach the optimal solution due to the intractable search space partitioning and heuristic manner. In this dissertation, we propose logical reasoning techniques and automated frameworks to tackle those challenges for several VLSI applications in the physical design (PD) and network-on-chip (NoC) design. We mainly focus on finding an optimal solution by exact solving of the integrated constraint satisfaction problem (CSP) which enables simultaneous optimization with one-time execution without any iteration. To alleviate the huge complexity of the VLSI application problems, (i) we utilize a matured fast reasoning method: satisfiability modulo theories (SMT) and formulate all our variables/constraints in a Boolean manner, (ii) we simplify our placement-and-routing (P&R) and task mapping/scheduling graphs and apply encoding techniques for further refinement, and (iii) we identify and implement practical constraints to reduce the search space.

In the physical design applications, we propose automated frameworks, which simultaneously solve place and route without deploying any sequential/separate operations for the conventional FinFET and many-tier Vertical Gate-All-Around-FET (VFET) standard cell synthesis and concurrent refinement in the engineering change order (ECO) stage. The proposed standard cell synthesis frameworks utilize the multi-objective optimization feature of SMT to obtain optimal layout results. To achieve practical scalability of the framework, we develop various search-space reduction techniques. Through orchestrating all innovative tactics together, our framework successfully generates a whole 7nm FinFET standard cell library and one to four tiers VFETs. Our ECO automation framework efficiently resolves pin accessibility-induced design rule violations (DRVs) by simultaneously performing detailed placement, detailed routing, and cell replacement. In addition to perturbation-minimized solutions, our proposed SMT-based optimization framework also suggests the adoption of alternative master cells to better achieve DRV-clean layouts. We demonstrate that our framework successfully resolves 58.6% of remaining DRVs on average, across a range of benchmark circuits with various cell architectures.

In NoC application, we propose an SMT-based framework to find optimal contention-free task mappings with minimum application schedule lengths on 2D/3D SMART NoCs with mixed dimension-order routing. We develop efficient search-space reduction techniques to achieve practical scalability. Experiments demonstrate that our SMT framework achieves 10X higher scalability than ILP (Integer Linear Programming) for finding optimum solutions on 2D and 3D SMART NoCs and our 2D and 3D extensions of the SMT framework with mixed dimension-order routing also maintain the improved scalability with the extended and diversified routing paths, resulting in reduced application schedule lengths throughout various application benchmarks.

Transient analysis of large-scale circuits relies on efficient numerical time integration algorithms. In this thesis, we focus on the high-order exponential integration and the explicit formulation for solving large-scale dynamical systems of VLSI designs. First, we demonstrate the advantages of exponential integration for the application to linear systems. To accelerate the computation of matrix exponential and vector product, Krylov subspace method and Arnoldi algorithm with different preconditioned matrices are explored. Second, we integrate the exponential integration based algorithms into a simulator for power network analysis, which is a challenging task for modern VLSI signoff. We verify the capability of adaptive stepping with high accuracy and the model of distributed computation. Comparing with the traditional approach, we observe the speedups up to 14X and 98X without the loss of accuracy by single-core and distributed computation models, respectively. Third, we devise a novel integration framework with the explicit formulation for nonlinear dynamical systems. This framework reduces the number of computationally expensive matrix factorizations required by traditional integration approaches. Furthermore, we demonstrate that the Krylov subspace methods can reduce the complexity of strongly coupled dynamical problems such as post layout analysis.

Pre-2018 CSE ID: CS2003-0759

Pre-2018 CSE ID: CS2006-0874

The design of power distribution networks (PDNs) become increasingly complex and less margin, as the CMOS technology node continues to scale down into 10nm and below and the operating voltage of high-performance (HPm) logic keeps decreasing. As circuit density on a single chip doubles every two to three years, the current density is growing rapidly as well. As the application of machine learning and deep learning are emerging, more and more logic blocks, such as application-specic or heterogeneous integrations are needed on future application processors(APs). All of these requires a better design and analysis of methodology for PDNs.

Pre-2018 CSE ID: CS2003-0758