A Negotiated Congestion based Router for Simultaneous Escape Routing

Qiang Ma,  Tan Yan,  Martin D. F. Wong
University of Illinois at Urbana-Champaign


The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resource of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compared the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit a complementary behavior: they are able to solve most of the test cases that the other can not solve. Together, they are able to completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.