以區域為基礎的整數線性規劃軌道繞線

Abstract

軌道繞線是一個位於全域繞線和細部繞線的中間步驟，這個步驟非常適合考慮deep submicron 相關的議題，例如: 雜訊(crosstalk)，臨界區域(critical area), 和金屬密度(metal density)，我們在這裡提出了一個軌道繞線的線性整數規劃的模型，軌道繞線包含n層指派和軌道指派，在n層指派法方面上，我們提出了的方法可以達到平均密度，避開障礙物和保證可繞性。在軌道指派上，藉由更動花費表格(cost table),我們可以盡量減少線段長度(wire length)和 考慮deep submicron 相關的議題，在最後我們提出一個平行化的繞線演算法，這個平行化的方式能夠大量的降低運算時間。實驗結果上我們以金屬密度作為我們方法的驗證，我們的實驗結果顯示可以降低9.5%的Maximal Density 區域和密度的標準差減少了3.5%，最後，我們的用8顆 Cpu做平行化減少了約80%的執行時間.

Track routing is an intermediate step between global routing and detailed routing. It is an ideal stage to consider deep submicron (DSM) issues, such as crosstalk, critical area, and density distribution. This paper provides a track routing model via Integer Linear programming (ILP). The proposed layer assignment optimizes routability, balances density distribution and avoids obstacles. In track assignment stage, we adopt extensive cost table to minimize cost for DSM issues and local wire length based on wire segment assignment results. For speeding up, the parallelism algorithm is provided to simultaneously route nets of each panel. Experimental results indicate that the proposed track routing algorithm improves maximal density by 9.5% and density deviation by 3.5% to using detailed router only. In addition, the proposed parallelism algorithm reduces 80% routing time in 8 core processer compared with 1 core system.