Broadening the Scope of Multi-Objective Optimizations in Physical Synthesis of Integrated Circuits

In modern VLSI design, physical synthesis tools are primarily responsible for satisfying chip-performance and power constraints by invoking a broad range of circuit optimizations, such as buffer insertion, logic restructuring, gate sizing and relocation. This process is known as timing closure. Our research seeks more powerful and more efficient optimizations to improve the state of the art in modern chip design. In particular, we integrate timing-driven placement, retiming, logic cloning, buffer insertion and gate sizing in novel ways to create powerful circuit transformations that help timing-critical paths satisfy setup-time constraints.

State-of-the-art physical synthesis optimizations are typically applied at two scales: i) global algorithms that affect the entire netlist and ii) local transformations that focus on a single gate or interconnection. The scale of modern chip designs dictates that only near linear-time optimization algorithms can be applied at the global scope—typically limited to wirelength-driven placement and legalization. The converse is also true: localized transformations can rely on more time-consuming optimizations, e.g., those involving accurate delay models. Few techniques bridge the gap between fully-global and localized optimizations, and this state of affairs complicates timing closure by limiting the effectiveness of logic restructuring. We aim to broaden the scope of physical synthesis optimization to include accurate transformations operating between the global and local scales.

This dissertation describes a suite of interrelated algorithmic techniques. Each transformation combines multiple physical-synthesis optimizations, and together they impact nearly every aspect of a typical physical synthesis flow. These new techniques are designed to bridge the gap between global and local physical synthesis operations and ensure graceful timing-closure process. Our techniques have been deployed in EDA tools used at IBM for physical synthesis of high-performance CPU and ASIC designs, where they significantly improved chip performance.