Pre-2018 CSE ID: CS2002-0706

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.

Recent work has shown that by considering an optimization perspective of the eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, we present efficient methods for solving general quadratic programs with nonconvex constraints in the context of very-large-scale integration (VLSI) computer-aided design (CAD) and graph-based semi-supervised learning problems.

We propose a general framework for matrix quadratic programming with nonconvex constraints, which is motivated by classic algorithms for solving trust-region subproblems. We introduce approximate and iterative methods with derived convergence guarantees.

We demonstrate the effectiveness of our framework on large-scale numerical test cases, specifically real-world benchmarks. By leveraging analytical VLSI and PCB layout engines, we show that effective initialization using our method consistently improves a variety of pre- and post-detailed placement metrics. Additionally, we introduce a graph semi-supervised learning algorithm based on this framework, which yields strong results across a wide spectrum of label rates.

Pre-2018 CSE ID: CS2003-0758

Pre-2018 CSE ID: CS2003-0759

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.

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: CS2006-0874

Pre-2018 CSE ID: CS2000-0662

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.