LMgr: A Low-Memory Global Router with Dynamic Topology Update and Bending-Aware Optimum Path Search

Jingwei Lu1 and Chiu-Wing Sham2
1Department of Computer Science and Engineering, University of California, San Diego, 2Department of Electronic and Information Engineering, The Hong Kong Polytechnic University


Global routing remains a fundamental physical design problem. We observe that large circuits cause high memory cost, and modern routers could not optimize the routing path of each two-pin subnet. In this paper, we develop a dynamic topology update technique to improve routing quality, and a graph coloring technique to improve the memory efficiency with negligible performance overhead. We prove the non-optimality of traditional maze routing algorithm and develop a optimum routing algorithm. We design a flat global router which integrates all the above techniques. The experimental results show that our router can efficiently solve most benchmarks with good solution quality.