考慮可繞度和效能之多階層繞線器

Abstract

在這碩士論文中，我們提出一個可以同時考慮可繞度以及效能的多階層(multilevel)繞線器的架構。此架構包含兩個主要步驟：粗糙化(coarsening)及反粗糙化(uncoarsening)。與之前多階層繞線器架構不同的地方是，我們將全域繞線(global routing)、細部繞線(detailed routing)以及資源評估(resource estimation)整合在多階層繞線器的架構的每一個階段(level)，使得在粗糙化階段的資源評估更為正確，同時在反粗糙化階段也可以加速結果的改善。並且由於每一階段皆得到正確繞線資訊，讓我們的架構更具彈性，並且能去處理不同繞線的要求(例如減少雜訊，能量的消耗等)。實驗結果證明，我們的架構比其他方法具有較好的繞線完成度。例如在11個常用的標準電路中，我們的方法對所有電路皆達到了100%的繞線完成度，反之以前的方法，包括多階層繞線架構、三階段式繞線(three-level routing)以及階層式繞線(hierarchical routing)分別只完成了3, 0, 3個電路。另外我們的繞線器也可使用比較少的繞線層數來達成100%完成度。我們同時提出了依效能為導向的繞線器，也得到了不錯的成果。

We propose in this thesis a novel framework for multilevel routing considering both routability and performance. The two-stage multilevel framework consists of coarsening followed by uncoarsening. Unlike the previous multilevel routing, we integrate global routing, detailed routing, and resource estimation together into each level of the framework, leading to more accurate routing resource estimation during coarsening and thus facilitating the solution refinement during uncoarsening. Further, the exact routing information obtained at each level makes our framework more flexible in dealing with various routing objectives (such as crosstalk, power, etc). Experimental results show that our approach obtains significantly better routing solutions than all previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100\% routing completion for all circuits while the previous multilevel routing, the three-level routing, and the hierarchical routing can complete routing for only 3, 0, 3 circuits, respectively. In particular, the number of routing layers used by our router is even smaller. We also have performed experiments on timing-driven routing. The results are also very promising.