切割為基礎繞線問題之研究

Study on Partition-Based Routing Problems in Electronic Design Automation

黃信雄(Hsin-Hsiung Huang)

指導教授 ： 謝財明教授

中原大學/工學院/電子工程研究所/博士(2008年)

https://doi.org/10.6840/CYCU.2008.00012

摘要

在論文中，我們將研究切割(partition)方法如何應用在數個電子設計自動化(Electronic Design Automation, EDA)的繞線問題，以最小化最大起點到各端點的延遲(演算法的執行時間)。經由觀察發現以起點為中心(繞線面積中心)，先將繞線面積切割成k部份，再分別針對每個子區域進行繞線，將可改善電路之迂迴繞線(演算法執行效率)。是以本論文將探討切割為基礎的繞線方法，說明將會遇到的問題，並提出有效的方法解決問題。
首先針對曼哈頓架構，對有矩形障礙物限制下的兩個繞線樹構建問題進行探討。針對第一個問題提出效能導向的演算法，除提出分割為基礎繞線以最小化信號源到信號各端點的最大延遲外，並於擴張圖加入節點到節點連線(terminal-to-terminal)，最小化連線總長度。針對第二問題提出基於密度分析導向之繞線樹演算法，不同於傳統採用單一繞線演算法，我們所提方法可視密度分布情況採用不同演算法，同時最佳化連線總長度和演算法執行時間。
接著在X-架構之對角繞線下，針對兩個不同繞線樹構建問題進行研究，並提出有效方法最小化對信號源到信號各端點的最大延遲和連線總長度。針對第一個不含障礙物X-架構繞線問題，提出混合型的處理方法，此方法先將平面依照信號源位置(source)分成k個子區域，再對每分區使用連線導向的方法完成繞線，有效地同時最小化信號源到信號端點的最大延遲和最小化連線總長度。針對第二個X-架構繞線問題，在有矩形和非矩形障礙物限制下進行研究，首先提出虛擬障礙物觀念來處理非矩形障礙物，並引入虛擬節點來進一步最小化連線總長度。該演算法根據信號源位置將繞線區域分成k區域，針對每區分別繞線，在障礙物限制之下同時最小化信號源到信號端點的最大延遲和最小化連線總長度。

關鍵字

切割為基礎的方法 ； 效能導向 ； 繞線樹演算法 ； 超大型積體電路 ； 障礙物

並列摘要

In this thesis, we study how to improve the routing results in the electronic design automation, EDA, by using the partition-based method. We observe the maximum source-to-terminal delay can be improved by the partition-based method, which takes the source position to divide the routing area into k sub-regions and individually constructs each routing tree for each sub-region. In the thesis, we will discuss the partition-based routing by listing the problems and giving the effective solutions.
First, we study two Manhattan-architecture routing problems and propose two effective algorithms to solve them. For the first problem, we propose a timing-driven routing tree construction, which utilizes the partitioning to minimize the maximum source-to-terminal delay and adds the terminal-to-terminal edges in the spanning graph to minimize the total wirelength, makes a balance between the delay and wirelength. For the second problem, we propose a hybrid approach, which analyzes the density distribution by two density functions and partitions the routing area into a set of sub-regions, simultaneously minimizes the total wirelength and runtime. In contrast to the traditional method, our algorithm is more flexible to automatically apply the multiple approaches for each sub-region by two density functions.
Second, we study two X-architecture routing problems and provide two effective algorithms to solve them. For the first problem, a partition-based method, which partitions the routing area into a set of sub-regions and applies the delaunay triangulation algorithm for each sub-region, is to minimize the maximum source-to-terminal delay and the total wirelength. For the second problem, we incorporate two novel concepts, including the virtual obstacles for handling the nonrectangular obstacles and the virtual nodes to minimize the total wirelength. Furthermore, we partition the routing area and apply the above new approach to construct the routing tree with rectangular/nonrectangular obstacles for each sub-region. In contrast to the previous works, our approach can handle the timing-driven routing with the obstacles.

並列關鍵字

obstacles ； timing-driven ； VLSI ； routing tree algorithm ； a partition-based method

參考文獻

[1] C. Albrecht, “Global Routing by New Approximation Algorithms for Multicommodity Flow,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 622-632, 2001.

[2] C.J. Alpert, A.B. Kahng, C.N. Sze and Q. Wang, “Timing-driven Steiner Trees are (Practically) Free,” in Proc. of ACM/IEEE Design Automation Conference, pp. 389-392, 2006.

[3] C. Bartoschek, S. Held, D. Rautenbach and J. Vygen, “Efficient Generation of Short and Fast Repeater Tree Topologies,” in Proc. of ACM International Symposium on Physical Design, pp. 120-127, 2006.

[4] S.H. Batterywala, N. Shenoy, W. Nicholls, and H. Zhou, “Track Assignment: A Desirable Intermediate Step between Global Routing and Detailed Routing,” in Proc. of IEEE International Conference on Computer-Aided Design, pp. 59-66, 2002.

[6] Y.W. Chang, S.P. Lin, “MR: A New Framework for Multilevel Full-Chip Routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.793-800, 2004.