In this thesis, we present the first of its kind early global routing framework after floorplanning of a design is done as per the existing physical design (PD) flow. The intent of this work is to assess early routability of a design, earlier than the existing practices in the present PD flow. The proposed routing framework begins with the identification of a set of monotone staircase routing regions obtained by recursive floorplan bipartitioning, based on a simple floorplan topology graph. For this purpose, a new floorplan bipartitioning framework based on different graph search techniques on the floorplan graph is proposed for faster completion, as compared to the existing maxflow based methods that incur higher runtime overhead. During the proposed early global routing, we aim to address an early version of unconstrained via minimization (UVM) problem, by an improved bipartitioning framework for identifying of a set of minimal bend monotone staircase routing regions, using a greedy and a randomized search technique.

The corresponding routing regions are used to construct a new routing graph model which allows the nets to be strictly routed through these routing regions in a number of routing (metal) layers. Notably, this routing model is fundamentally different from the grid graph model used in the existing global routing methods. Subsequently, we extend this early routing model for undertaking over-the-block early global routing at floorplan level. This hybrid model employs the monotone staircases for routing in lower routing layers, while a suitable floorplan based adaptation of the existing grid graph model is used for upper layers. Unlike the existing grid graph model used in post-placement global routing, both the proposed routing models can potentially address the pin accessibility problem of the nets at floorplan block level by suitable edge definition. Beside early routability assessment, both the models ensure that the congestion in any routing region is restricted to 100% and also adhere to the proposed UVM based early routing topology generation and layer assignment of the nets for minimal via routing. The corresponding routing solutions can be helpful in guiding the subsequent post-placement global/detailed routing as well as performing detailed placement of standard cells while obeying the given floorplan topology. In this regard, a case study on different floorplan instances of an industrial design with the help of a well known industrial physical design (PD) tool has been also conducted.

Finally, the proposed routing framework is explored for design for manufacturability (DFM) aware early routability assessment, by considering an early abstraction model of edge placement errors (EPE) due to the limitation of planar fabrication processes. In this part, we also focus on uniform wire distribution intended for minimizing the surface irregularities due to non-uniform metal density across the layout and different hardness factors of the metal and the dielectric materials during chemical mechanical polishing (CMP) process.