UC San Diego

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.