Floorplan Representation, Global Placement, and Routability Analysis for VLSI Layout Design Automation

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