An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SAT

References

• F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math., Vol. 30, no. 1, pp. 104–14, 1976. doi:10.1137/0130013.
   Web of Science ®Google Scholar
• S. B. Akers, “A modification of lee's path connection algorithm,” IEEE Trans. Electron. Comput., Vol. 16, no. 1, pp. 97–8, 1967. doi:10.1109/PGEC.1967.264620.
   Google Scholar
• F. O. Hadlock, “A shortest path algorithm for grid graphs,” Networks, Vol. 7, no. 4, pp. 323–4, 1977. doi:10.1002/(ISSN)1097-0037.
   Web of Science ®Google Scholar
• F. Rubin, “The lee path connection algorithm,” IEEE Trans. Comput., Vol. 100, no. 9, pp. 907–14, 1974. doi:10.1109/T-C.1974.224054.
   Google Scholar
• D. W. Hightower, “A solution to line routing problems on the continuous plane,” in Papers on Twenty-Five Years of Electronic Design Automation, ACM, 1988, pp. 11–34, Atlantic City, NJ, USA.
   Google Scholar
• K. Mikami and K. Tabuchi, “A computer program for optimal routing of printed circuit conductors,” in IFIP Congress (2), 1968, pp. 1475–1478, Edinburgh, UK.
   Google Scholar
• W.-K. Chow, L. Li, E. F. Y. Young and C.-W. Sham, “Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach,” Integration, Vol. 47, no. 1, pp. 105–14, 2014. doi:10.1016/j.vlsi.2013.08.001.
   Web of Science ®Google Scholar
• Y. Hu, T. Jing, X. Hong, Z. Feng, X. Hu and G. Yan,  “An-oarsman: Obstacle-avoiding routing tree construction with good length performance,” in Proceedings of the 2005 Asia and South Pacific Design Automation Conference, ACM, 2005, pp. 7–12, Shanghai, China.
   Google Scholar
• Z. Shen, C. C. N. Chu and Y.-M. Li, “Efficient rectilinear Steiner tree construction with rectilinear blockages,” in ICCD 2005. Proceedings. 2005 IEEE International Conference on Computer Design: VLSI in Computers and Processors, IEEE, 2005, pp. 38–44, San Jose, CA, USA.
   Google Scholar
• Y. Yang, Q. Zhu, T. Jing, X. L. Hong and Y. Wang, “Rectilinear Steiner minimal tree among obstacles,” in Proceedings of IEEE ASICON, Beijing, China, 2003, pp. 348–351.
   Google Scholar
• Z. Feng, Y. Hu, T. Jing, X. Hu, and G. Yan, “An O(n log n) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane,” in Proceedings of the 2006 International Symposium on Physical Design, ACM, 2006, pp. 48–55, San Jose, CA, USA.
   Google Scholar
• Y. Shi, T. Jing, L. He, Z. Feng and X. Hong, “Cdctree: novel obstacle-avoiding routing tree construction based on current driven circuit model,” in Asia and South Pacific Conference on Design Automation, IEEE, 2006, p. 6, Yokohama, Japan.
   Google Scholar
• Y. Hu, et al. “Forst: A 3-step heuristic for obstacle-avoiding rectilinear Steiner minimal tree construction,” J. Inform. Comput. Sci., Vol. 1, no. 3, pp. 107–16, 2004.
   Google Scholar
• K. Clarkson, S. Kapoor, and P. Vaidya, “Rectilinear shortest paths through polygonal obstacles in time,” in Proceedings of the Third Annual Symposium on Computational Geometry, ACM, 1987, pp. 251–257, Waterloo, Ontario, Canada.
   Google Scholar
• J. L. Ganley and J. P. Cohoon, “Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In IEEE International Symposium on Circuits and Systems, Vol. 1, IEEE, 1994, pp. 113–6, London, UK.
   Google Scholar
• C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang and C.-L. Yang, “Efficient obstacle-avoiding rectilinear Steiner tree construction,” in Proceedings of the 2007 International Symposium on Physical Design, ACM, 2007, pp. 127–34, Austin, TX, USA.
   Google Scholar
• L. Li, Z. Qian and E. F. Y Young, “Generation of optimal obstacle-avoiding rectilinear Steiner minimum tree,” in Proceedings of the 2009 International Conference on Computer-Aided Design, ACM, 2009, pp. 21–5, San Jose, CA, USA.
   Google Scholar
• T. Huang, L. Li and E. F. Y. Young, “On the construction of optimal obstacle-avoiding rectilinear Steiner minimum trees,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 30, no. 5, pp. 718–31, 2011. doi:10.1109/TCAD.2010.2098930.
   Web of Science ®Google Scholar
• T. Huang and E. F. Y. Young, “Obsteiner: An exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 32, no. 6, pp. 882–93, 2013. doi:10.1109/TCAD.2013.2238291.
   Web of Science ®Google Scholar
• G. Ajwani, C. Chu and W.-K. Mak, “Foars: Flute based obstacle-avoiding rectilinear Steiner tree construction,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 30, no. 2, pp. 194–204, 2011. doi:10.1109/TCAD.2010.2096571.
   Web of Science ®Google Scholar
• J. Long, H. Zhou and S. O. Memik, “Eboarst: An efficient edge-based obstacle-avoiding rectilinear Steiner tree construction algorithm,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 27, no. 12, pp. 2169–82, 2008. doi:10.1109/TCAD.2008.2006098.
   Web of Science ®Google Scholar
• C.-H. Liu, C.-X. Lin, I.-C. Chen, D. T. Lee and T.-C. Wang, “Efficient multilayer obstacle-avoiding rectilinear Steiner tree construction based on geometric reduction,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 33, no. 12, pp. 1928–41, 2014. doi:10.1109/TCAD.2014.2363390.
   Web of Science ®Google Scholar
• R.-Y. Wang, et al. “Efficient multi-layer obstacle-avoiding region-to-region rectilinear Steiner tree construction,” in Proceedings of the 55th Annual Design Automation Conference, 2018, pp. 1–6, San Francisco, CA, USA.
   Google Scholar
• S. Mukherjee and S. Roy, “Nearly-2-sat solutions for segmented-channel routing,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 35, no. 1, pp. 128–40, 2016. doi:10.1109/TCAD.2015.2446950.
   Web of Science ®Google Scholar
• G.-J. Nam, F. Aloul, K. A. Sakallah and R. A. Rutenbar, “A comparative study of two boolean formulations of FPGA detailed routing constraints,” IEEE Trans. Comput., Vol. 53, no. 6, pp. 688–96, 2004. doi:10.1109/TC.2004.1.
   Web of Science ®Google Scholar
• S. Kundu, S. Roy and S. Mukherjee, “Sat based rectilinear Steiner tree construction,” in 2016 2nd International Conference on Applied and Theoretical Computing and Communication Technology, IEEE, 2016, pp. 623–27, Bangalore, India.
   Google Scholar
• S. Kundu, S. Roy and S. Mukherjee, “K-nearest neighbour (KNN) approach using sat based technique for rectilinear Steiner tree construction,” in 2017 7th International Symposium on Embedded Computing and System Design, IEEE, 2017, pp. 1–5, Durgapur, India.
   Google Scholar
• A. Biere, A. Cimatti, E. M. Clarke, M. Fujita and Y. Zhu, “Symbolic Model Checking using Sat Procedures Instead of BDDS,” in Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, ACM, 1999, pp. 317–20, New Orleans, LA, USA.
   Google Scholar
• S. Roy, P. P. Chakrabarti and P. Dasgupta, “Event propagation for accurate circuit delay calculation using sat,” ACM Trans. Design Autom. Electron. Syst., Vol. 12, no. 3, pp. 36, 2007. doi:10.1145/1255456.1255473.
   Web of Science ®Google Scholar
• A. Ramani, F. A. Aloul, I. L. Markov and K. A. Sakallah, “Breaking instance-independent symmetries in exact graph coloring,” in Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings, Vol. 1, IEEE, 2004, pp. 324–9, Paris, France.
   Google Scholar
• F. A. Aloul, A. Ramani, I. L. Markov and K. A. Sakallah, “Generic ilp versus specialized 0-1 ilp: An update,” in Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design, ACM, 2002, pp. 450–457, San Jose, CA, USA.
   Google Scholar
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed., The MIT Press, 2001.
   Google Scholar
• E. Niklas and S. Niklas, “Minisat+,” 2006.
   Google Scholar
• C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang and C.-L. Yang, “Obstacle-avoiding rectilinear Steiner tree construction based on spanning graphs,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., Vol. 27, no. 4, pp. 643–53, 2008. doi:10.1109/TCAD.2008.917583.
   Web of Science ®Google Scholar
• L. Li and E. F. Y. Young, “Obstacle-avoiding rectilinear Steiner tree construction,” in Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, IEEE Press, 2008, pp. 523–8, San Jose, CA, USA.
   Google Scholar
• C.-H. Liu, S.-Y. Yuan, S.-Y. Kuo, and Y.-H. Chou, “An O(n log n) path-based obstacle-avoiding algorithm for rectilinear Steiner tree construction,” in Proceedings of the 46th Annual Design Automation Conference, ACM, 2009, pp. 314–9, San Francisco, CA, USA.
   Google Scholar