A gridless router based on hierarchical PB corner stitching structure

A multi-layer gridless area router is given in this paper. Based on corner stitching, this router adopts tile expansion to explore path for each net. A heuristic method that penalizes nodes deviating from the destination is devised to accelerate the algorithm. Besides, an enhanced interval tree is used to manage the intermediate data structure. In order to eliminate the effect that the routing order has on final results, a new gridless rip-up and rerouting algorithm is proposed. Test results indicate that the completion rate is improved after the rip-up and reroute process and the speed of this algorithm is satisfactory.