Ordered Escape Routing via Routability-Driven Pin Assignment

摘要

For board-level routing, ordered escape routing is a key problem. In this paper, based on the optimality of hierarchical bubble sorting, the process of assigning routability-driven pins is done for single-layer routing. Furthermore, an efficient routing approach with the consideration of variable capacity is proposed to solve the ordered escape routing problem. The experimental results show that our proposed approach achieves 100% routability for the tested examples in reasonable CPU time. Compared with the SAT-based approach[6] for the tested examples with the capacity 1, our proposed approach reduces the CPU time by 77.7% on the average. For the tested examples with the capacity 2, our proposed approach can achieve 100% routability in reasonable CPU time.