A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> d: LAYER ASSIGNMENT <s> In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-layer global routing solution and aim to find a layer assignment result for each net such that the via cost is minimized while the given congestion constraints are satisfied. To solve the problem, we propose a polynomial-time algorithm which first generates a net order and then performs layer assignment one net at a time according to the order using dynamic programming. Our algorithm is guaranteed to generate a layer assignment solution satisfying the given congestion constraints. We used the six-layer benchmarks released from the ISPD'07 global routing contest to test our algorithm. The experimental results show that our algorithm was able to improve the contest results of the top three winners MaizeRouter, BoxRouter, and FGR on each benchmark. As compared to BoxRouter 2.0 and FGR 1.1, which are newer versions of BoxRouter and FGR, our algorithm respectively produced smaller via costs on all benchmarks and half the benchmarks. Our algorithm can also be adapted to refine a given multilayer global routing solution in a net-by-net manner, and the experimental results show that this refinement approach improved the via costs on all benchmarks for FGR 1.1. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> d: LAYER ASSIGNMENT <s> In this article, we present BoxRouter 2.0, and discuss its architecture and implementation. As high-performance VLSI design becomes more interconnect-dominant, efficient congestion elimination in global routing is in greater demand. Hence, we propose a global router which has a strong ability to improve routability and minimize the number of vias with blockages, while minimizing wirelength. BoxRouter 2.0 is extended from BoxRouter 1.0, but can perform multi-layer routing with 2D global routing and layer assignment. Our 2D global routing is equipped with two ideas: node shifting for congestion-aware Steiner tree and robust negotiation-based A* search for routing stability. After 2D global routing, 2D-to-3D mapping is done by the layer assignment which is powered by progressive via/blockage-aware integer linear programming. Experimental results show that BoxRouter 2.0 has better routability with comparable wirelength than other routers on ISPD07 benchmark, and it can complete (no overflow) the widely used ISPD98 benchmark for the first time in the literature with the shortest wirelength. We further generate a set of harder ISPD98 benchmarks to push the limit of BoxRouter 2.0, and propose the hardened ISPD98 benchmarks to map state-of-the-art solutions for future routing research. <s> BIB002
For multi-layer global routing, layer assignment maps a 2-D global routing result back to the original multi-layer solution space. Dynamic programming BIB001 , Integer Linear Programming (ILP) BIB002 , etc. are often used on this problem. Its main research focus is on minimizing the number of vias.