Congestion driven global routing and cross point assignment

This research work presents a new methodology for congestion driven Global Routing (GR) and Cross Point Assignment (CPA) for use in VLSI designs. Global routing is often used to estimate wire length in many physical design steps and as a guide by DR algorithms to reduce runtime. Many GR algorithms have been published over the last few decades. However, the growth of design sizes and complexity makes these algorithms unsuitable due to longer runtimes. Rectilinear Steiner Trees (RST) are often used as faster alternative to GR. The problem of net ordering has traditionally been addressed using rip-up and re-route iterations, which are usually very time consuming. The proposed algorithm does not use rip-up and re-route. New models and algorithms for congestion estimation, spanning tree construction and RST determination are proposed. The pre-route congestion estimates are used to modify the classical Minimum Spanning Tree (MST) algorithm to account for routing congestion to create Congestion Driven Spanning Tree (CDST) algorithm. This research work also proposes a new RST algorithm that has a fast runtime. The proposed GR & CPA algorithm uses these new components to compute a global routing solution. By utilizing the pre-route congestion estimates, every net is routed with due consideration to other nets. The combined effect of these innovations enables the proposed GR & CPA methodology to achieve high completion rates with fast runtimes. The simultaneous GR & CPA algorithm was tested on the MCNC testcases and a number of other testcases from the VLSI industry. The total GR net length is within 1.97% of the DR wire length, while the total Steiner tree length is within 3.63% of DR wire length. Individual net wire lengths are also compared and it was found that the GR net lengths correlate with DR wire length better than Steiner tree lengths. The runtime of the proposed GR & CPA algorithm is comparable to the Batched-1-Steiner algorithm. The fast runtime (at least 15x faster than a detailed router) and better correlation to the final routing makes the proposed algorithm very useful for early estimation of routing for use in circuit and layout design feasibility analysis and to reduce the detailed routing runtime