Traditional VLSI design flow is composed of serialized stages with different abstractions of the final design. The serialization helps reduce complexity of the overall design process, but at the same time leads to "optimization disconnect" between these stages. In other words, the optimizations performed in one stage do not necessarily correlate well with the objectives in subsequent phases. This is due to the fact that not all the information is available at all stages. Moreover, in traditional setup, the decisions made in the preceding stages are binding on the subsequent ones. So as a result, as the design picture gets clearer with each stage, the degree of freedom or flexibility is reduced. This thesis investigates one such optimization disconnect in physical design phase at the boundary between placement and routing stages.

Classical approach to handle routing related issues, such as routability, have concentrated on prediction, either empirical or based on Rent's rule. Another different approach has been to embed a fast router inside the placement optimization engine, so that every placement perturbation is followed by routing changes to keep the routing information consistent.

As a part of this thesis, We show that the prediction models, upon which some routability optimization engines are based, do not exhibit sufficient "fidelity" in identifying congested regions. Moreover, we propose an alternative way to encode routing information based on a technique called trunk decomposition. In this framework, routing structures are represented as horizontal trunks and vertical segments. The main advantage of this framework is that the elementary perturbations on the routing topology of a net are very simple, complete and have well defined effect. This framework also allows for simultaneous placement and routing perturbation, since we can view vertical segments as placeable objects. Moreover, the optimization engines based on this framework can handle very flexible cost objective for optimization.

We shall develop and evaluate a set of robust optimization engines based on basic trunk decomposition strategy. The outcome of the thesis will be a unified multi-level combinatorial framework in which different engines optimize various objectives by performing simultaneous placement and routing optimizations.