通過高效且有效的布林運算將多層之避障直角史坦那樹方法用來解決繞線開路問題

Extending ML-OARSMT to Net Open Locator with Efficient and Effective Boolean Operations

江炳輝(Bing-Hui Jiang)

指導教授 ： 陳宏明

國立交通大學/電機學院/電子工程系所/碩士(2018年)

摘要

近年來,多層之障礙物避障直角史坦那樹 (ML-OARSMT) 問題得到了廣泛的研究。在這項工作中,我們考慮多層之障礙物避障直角史坦那樹問題的變體,並將適用性擴展到開放網路定位器。由於工程變更命令 (ECO) 或路由器的限制可能導致開放網路,我們提出了一個框架來檢測和重新連接現有網路來解決開放網路問題。與先前基於連接圖的方法不同,我們提出一個藉由應用高效的布林運算技術來修復開放網路。我們的方法具有良好的品質與可擴展性,並且是可高度平行化。與 ICCAD2017 競賽的結果相比,我們表明我們提出的演算法與前三名優勝者相比,可以達到最低的成本,並且平均有 4.81 倍的加速。

關鍵字

繞線 ； 實體設計 ； 直角史坦納樹 ； 避障 ； 布林操作

並列摘要

Multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem has been extensively studied in recent years. In this work, we consider a variant of ML- OARSMT problem and extend the applicability to the net open location finder. Since ECO or router limitations may cause the open nets, we come up with a framework to detect and reconnect existing nets to resolve the net opens. Different from prior connection graph based approach, we propose a technique by applying efficient Boolean operations to repair net opens. Our method has good quality and scalability and is highly parallelizable. Compared with the results of ICCAD-2017 contest, we show that our proposed algorithm can achieve the smallest cost with 4.81 speedup in average than the top-3 winners.

並列關鍵字

routing ； physical design ； rectilinear Steiner tree ； obstacle-avoidance ； Boolean operations

參考文獻

[5] M. R. Garey and D. S. Johnson, “The rectilinear steiner tree problem is NP-complete,” SIAM Journal on Applied Mathematics, vol. 32, no. 4, pp. 826–834, 1977. [Online]. Available: https://doi.org/10.1137/0132071

[21] M. Hanan, “On steiner’s problem with rectilinear distance,” SIAM Journal on Applied Mathematics, vol. 14, no. 2, pp. 255–265, 1966. [Online]. Available: https://doi.org/10.1137/0114025

[22] R.-Y. Wang, C.-C. Pai, J.-J. Wang, H.-T. Wen, Y.-C. Pai, Y.-W. Chang, J. C. M. Li, and J.-H. R. Jiang, “Efficient multi-layer obstacle-avoiding region-to-region rectilinear steiner tree construction,” in Proceedings of the 55th Annual Design Automation Conference, 2018, pp. 45:1–45:6. [Online]. Available: http://doi.acm.org/10.1145/3195970.3196040

[23] G.-Q. Fang, Y. Zhong, Y.-H. Cheng, and S.-Y. Fang, “Obstacle-avoiding open-net connector with precise shortest distance estimation,” in Proceedings of the 55th Annual Design Automation Conference, 2018, pp. 46:1–46:6. [Online]. Available: http://doi.acm.org/10.1145/3195970.3196081

[1] K. S. Hu, M. J. Yang, Y. H. Huang, B. Y. Wong, and C. Shen, “ICCAD-2017 CAD contest in net open location finder with obstacles: Invited paper,” in 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Nov 2017, pp. 863–866.