有效率的方塊式繞線器使用繞線圖形簡化法

Abstract

當製程技術進展到奈米科技的時代，電路信號的延遲和雜訊的最佳化是整個積體電路設計中最關鍵的一環。這些最佳化的問題可以由改變導線尺寸和加大導線的間距來達到。與網格式繞線器相較，方塊式繞線器能夠更有效率的處理導線線寬及線距的問題。為此，這篇論文中我們針對整個晶片的繞線問題建置了一個有效率的方塊式繞線器。另外，我們亦將繞線圖形的簡化法整合到兩階段式的繞線流程之中。第一階段是一個通用的全域繞線器，此全域繞線評估整個晶片繞線資源的分佈情形來決定全域路徑。而此全域路徑導引第二階段的細部繞線器來決定在佈局上的實際路徑。繞線圖形簡化法移除冗贅的方塊及切齊相鄰方塊來減少佈局中方塊碎裂的情形，進而提高了方塊式繞線器的執行效率而且不會因簡化繞線圖形而犧牲繞線品質。此外我們還提出一個區段樹的資料結構來儲存多重端點的接線，此資料結構可以幫助我們更有效率地去處理拔除重繞的程序。實驗結果顯示，我們的方塊式繞線器跟多重層次架構的繞線器比較起來能夠更迅速的完成繞線並且獲得更好的繞線結果。

As technology advances into the nanometer era, the interconnect optimization for the delay and noise issues is the dominant factor to the modern IC design. These optimizations impose the wire sizing and spacing to the interconnections .Gridless router is more applicable to handle the various design rules than grid router. Therefore, we develop an efficient tile-based router for the full chip routing in this thesis. This work integrates the routing graph reduction into the two-stage routing flow. The first stage is a general global router, which estimates the routing resource to decide a rough path for the detailed router. According to the result of global routing, the tile-based router, the second stage, completes the full chip routing net by net. Routing graph reduction involves the removal of redundant tiles and alignment of neighboring tiles to reduce the fragment of the tile plane and accelerate the routing speed of tile-based router. We also propose a segment tree to help the rip-up and reroute procedure work more flexibly and efficiently. Segment tree maintains the Steiner tree of multi-terminal net segment by segment so that the rip-up and reroute procedure just rip-up and reroute the violated segment instead of the entire net. Experiment results show the expeditious routing speed and better routing solution than multilevel framework.