Abstract
本篇論文探討了一個新的繞線演算法，可以用來解決非常大的Channel 繞線問題。它包括了三個步驟：(1) 區域繞線；(2) 區域的重新切割；(3) 繞線後最佳化處理。在區域繞線中，我們首先將一個大的channel 繞線區域由左至右的切割，直到每一個子區域的大小都在SILK的繞線能力範圍之內。每一次的切割位置，均選擇局部密度 (local density)較小的地方，如此可使得每一個子區域的可繞度較高。在切割完成後，我們根據三個因素來估計每一個子區域的可繞度，然後選出可繞度最低的子區域；在完成此子區域的繞線後，再以此子區域為基底，往左右兩邊擴展繞線，直到整個 channel的繞線完成為止。在完成每個子區域的繞線之前，必須固定每一個子區域左右兩邊上 net的位置。首先必須決定這些net 在左右邊界的上下順序關係，我們建立一個切割線垂直限制圖(CutLine Vertical Constraint Graph) ，然後用演算法將此有向圖(digraph) 變成沒有圓(cycle) 的有向圖，以得到他們上下順序的關係；接著我們用整數線性規劃來決定這些net 的確實位置。在區域的重新切割步驟裡，其目的是要改進在區域繞線中，一些沒有分配好位置的n-et的繞線。作法是針對每個子區域，選擇其中間的一行當作新的切割線，然後再對每個新形成的子區域，用SILK作繞線處理。最後，我們在繞線後最佳化處理中，整體地改進一些繞線品質不好的 net。我們一次拔掉一個 net，然後再重新繞線，在所有的 net都處理過後，若結果有整體地改進，則一直重覆此步驟，直到結果無法再改進為止。實驗結果證實，成功地用19個軌道(track) 繞出Deutsch difficult example ，而且繞線品質也都優於大部份已發表過的論文。