COALA: Concurrently Assigning Wire Segments to Layers for 2-D Global Routing

Two-dimensional (2-D) global routing followed by layer assignment is a common and popular strategy to obtain a good tradeoff between runtime and routing performance. Yet, the huge gap between 2-D routing patterns and the final 3-D routing paths often results in inevitable overflow after layer assignment. State-of-the-art (SOTA) studies on layer assignment usually adopt dynamic programming-based approaches to sequentially find an optimal solution for each net in terms of overflow or/and the number of vias. However, a fixed assignment ordering severely restricts the solution space, and the distributed overflows can hardly be resolved with any existing refinement approach. This article proposes a novel layer assignment framework that concurrently considers all the wire segments of nets and iteratively assigns them from the lowest available layer to the highest one. The concurrent scheme facilitates the maximal utilization of routing resource on each layer, contributing to an effective rerouting procedure that greatly reduces inevitable overflows. Based on the proposed framework, we further propose an obstacle-aware strategy that can mitigate obstacle-induced inevitable overflows in the original framework. Experimental results show that compared to an implemented sequential layer assignment approach based on SOTA techniques and refined by the well-known overflow/congestion reduction rip up and rerouting procedure, the proposed concurrent layer assignment framework (COALA) brings great improvements in the overflow reduction and runtime efficiency, which shows the significant advantage of the concurrent layer assignment scheme over sequential methods. The improvement is also verified in detailed routing, where the proposed COALA framework contributes to sparser routing results with fewer vias and design rule violations (DRVs).