Direction-Constrained Rectangle Escape Routing

Abstract

Given a set of buses with available escape directions inside a chip, a two-phase algorithm is proposed to assign one feasible escape direction onto any bus such that the number of used layers is minimized and to allocate the pin rectangle and the projection rectangle of any escape bus onto the minimized layers in direction-constrained rectangle escape routing. In our proposed algorithm, based on the concept of two-dimensional maximum density inside a chip, the escape directions of the buses can be first assigned to minimize the number of the used layers by iteratively eliminating unnecessary escape directions for any bus inside a chip. Furthermore, based on the construction of the represented intervals and the assignment constraints for the escape buses, a modified left-edge algorithm can be used to allocate all the escape buses onto the minimized layers. Compared with Ma’s integer linear program (ILP)-based algorithm [10] using lp_solve and Gurobi in rectangle escape routing, the experimental results show that our proposed algorithm obtains the same results but reduces CPU time by 94.2% and 35.7% when using lp_solve and Gurobi for 16 tested examples with no direction constraint on average, respectively. Compared with the modified algorithm from Ma's ILP-based algorithm [10] using lp_solve and Gurobi in direction-constrained rectangle escape routing, the experimental results show that our proposed algorithm obtains the same results but reduces CPU time by 94.3% and 37.7% when using lp_solve and Gurobi for 16 tested examples with direction constraints on average, respectively. Besides that, compared with Yan’s iterative algorithm, the experimental results show that our proposed algorithm increases CPU time by 1.0% to reduce the number of used layers 11.1% for 16 tested examples on average.

References

1. C. F. Coombs, editor. 2007. Printed Circuits Handbook (6th ed.). McGraw--Hill, New York, NY.
2. M. M. Ozdal, D. F. Wong, and P. S. Honsinger. 2005. An escape routing framework for dense boards with high-speed design constraints. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 759--766.
3. M. M. Ozdal and D. F. Wong. 2006. A length-matching routing algorithm for high-performance printed circuit boards. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 25, 12 (2006), 2784--2794.
4. M. M. Ozdal and D. F. Wong. 2004. Simultaneous escape routing and layer assignment for dense PCBs. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 822--829.
5. H. Kong, T. Yan, D. F. Wong, and M. M. Ozdal. 2007. Optimal bus sequencing for escape routing in dense PCBs. In Proceedings of the International Conference on Computer-Aided Design. 390--395.
6. H. Kong, T. Yan, and M. D. F. Wong. 2009. Automatic bus planner for dense PCBs. In Proceedings of the Design Automation Conference. 326--331.
7. T. Yan, H. Kong, and D. F. Wong. 2009. Optimal layer assignment for escape routing of buses. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 245--248.
8. J. T. Yan and Z. W. Chen. 2011. New optimal layer assignment for bus-oriented escape routing. In Proceedings of the ACM Great Lakes Symposium on VLSI. 205--210.
9. H. Kong, Q. Ma, T. Yan, and D. F. Wong. 2010. An optimal algorithm for finding disjoint rectangles and its application to PCB routing. In Proceedings of the Design Automation Conference. 212--217.
10. Q. Ma, H. Kong, D. F. Wong, and F. Y. Young. 2011. A provably good approximation algorithm for rectangle escape problem with application to PCB routing. In Proceedings of the Asia and South Pacific Design Automation Conference. 843--848.
11. Q. Ma and D. F. Wong. 2010. NP-completeness and an approximation algorithm for rectangle escape problem with application to PCB routing. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 31, 9 (2012), 1356--1365.
12. J. T. Yan, J. M. Chung, and Z. W. Chen. 2012. Density-reduction-oriented layer assignment for rectangle escape routing. In Proceedings of the ACM Great Lakes Symposium on VLSI. 275--278.
13. J. T. Yan and Z. W. Chen. 2012. Direction-constrained layer assignment for rectangle escape routing. In Proceedings of the International SOC Conference. 254--259.
14. A. Ahmadinejad and H. Zarrabi-Zadeh. 2017. Finding maximum disjoint set of boundary rectangles with application to PCB routing. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 36, 3 (2017), 412--420.
15. M. C. Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY, 1980.
16. A. Hashimoto and J. Stevens. 1971. Wire routing by optimizing channel assignment within large apertures. Proceedings of the 8th Design Automation Workshop. 155--169.
17. lp_solve: an open source linear programming solver. Retrieved from http://sourceforge.net/projects/lpsolve.
18. Gurobi: a state-of-the-art solver engine for optimization problems. Retrieved from http://www.gurobi.com./.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Wire routing