考慮障礙物之直角史坦納樹快速建造

Abstract

在平面上，考慮障礙物之直角史坦納(Steiner)樹為利用直線或橫線連接所有節點、同時避免穿越障礙物的史坦納樹。在先進的積體電路設計中，繞線的過程必須考慮各種線路、區塊所產生的障礙物，因此這個問題越來越受到重視與關注。除此之外，由於積體電路為多層之製程，這使得在多層繞線平面中，建造考慮障礙物之直角史坦納樹成為一個新的挑戰。然而，考慮障礙物與多層繞線平面大幅增加了問題的難度，所以現存的研究結果都還有進步的空間。在此篇論文中，我們提出一個利用考慮障礙物之連結圖的演算法，它能快速地建造考慮障礙物之直角史坦納樹，而且不同於現存的演算法，我們的演算法在節點數為二以及其他許多情況達到最佳解。而對於在多層繞線平面中的問題，我們也提出許多不同於單層繞線平面的性質，並且適當地延伸單層繞線的演算法來解決此問題。實驗結果顯示，比起當今先進的演算法，我們的演算法能產生線長更短的考慮障礙物之直角史坦納樹。

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins by vertical/horizontal edges, possibly through some additional points (called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Besides, because modern nanometer IC designs are processed layer by layer, it is a new challenge for designers to deal with the multi-layer OARSMT (ML-OARSMT) problem where pins are connected by vertical/horizontal edges within layers and vias between layers. Nevertheless, the presences of obstacles and multi-layers significantly increase the problem complexity, and thus most previous works for the OARSMT problem on a layer suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph (OASG), this thesis presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction on a layer. Unlike previous heuristics, our algorithm guarantees to find an optimal solution for any 2-pin net and many higher-pin nets. Furthermore, we identify key different properties of the ML-OARSMT problem from the single-layer counterpart and present the first algorithm to solve the ML-OARSMT problem. This algorithm can also guarantee an optimal solution for any 2-pin net and many higher-pin nets. Extensive experiments show that our algorithms result in significantly shorter wirelengths than all state-of-the-art works.