以性能和擁擠為導向的多階層繞線方法

Abstract

本論文研製之多階層繞線器可降低擁擠區域、得到較好的性能以及繞線完成 度。藉由最小距離生成樹演算法以及最短改善方法可以對所有的網路建構出一個 滿足時序限制以及較少線段長度的繞線拓撲結構。之後將網路分成critical 以及 non-critical 部分並分別對其做繞線，而且結合了機率及實際的繞線擁擠程度以獲 得更精確的擁擠程度估算值。在實驗結果中，可以看出我們提出的多階層繞線器 比先前的繞線器得到更令人注目的結果。對於所有的測試電路，我們可以百分之 百繞線完成，然而以前提出的多階層繞線器對任一個測試電路都沒有辦法完全的 成功繞出結果。

In this thesis, we present a novel framework of multilevel routing to decrease the congestion and achieve better performance as well as routability. By performing the minimum distance spanning tree (MDST) algorithm and the shortest modification heuristic to construct the performance-driven topology of all nets, we can obtain a better routing topology which satisfies the timing constraint and has less total wire length. After constructing the routing topology, we classify the nets into critical and non-critical nets, route them at different stages, and integrate the probabilistic congestion model with the current routing congestion to improve the accuracy of congestion estimation. The experimental results show that our proposed method achieves significantly better solution than the existing methods. Our approach can achieve 100% routing completion rate for all benchmarks and none of them can be completely routed by prior multilevel routers.