# BOB-Router: A New Buffering-Aware Global Router with Over-the-Block Routing Resources

## Abstract
在本文中，我們提出了一種新的全域繞線器(global router)，BOB-Router，具備利用區塊內繞線資源的能力，以及傳統繞線(router)概念中透過count和overflow最小化線長。在過去的全域繞線制定中，IP塊內的繞線資源要麼被視為導致顯著浪費的繞線障礙(routing blockages)，要麼簡單地被視為區塊外的繞線資源；違反了延遲約束(slew constraints)並因此導致緩衝失敗。利用區塊內的繞線資源可以顯著改善繞線結果，但需要特別注意，因為延遲受不同金屬層上的不同電阻電容影響，必須受到緩衝限制，並且很容易被違反。此外，即使所有網路都確認延遲合法，繞線解決方案仍可能遭受嚴重的擁塞問題。BOB-Router首次嘗試通過同時最小化overflow、線長和途徑數量，且不違反延遲約束來解決區塊內全域繞線問題。BOB-Router生成一個延遲合法的初始解，然後進行基於拉格朗日乘子的定價(pricing)階段和基於RC約束的A* search，以幫助在所有金屬層上探索新的緩衝感知拓撲。我們的實驗結果表明，BOB-Router完全滿足延遲約束，並且在線長、途徑數量(via count)和overflow方面明顯優於避障全域繞線器。

## Introduction
隨著半導體技術不斷深入次微米級別，互連延遲對於芯片性能的影響變得更加關鍵。在芯片互連性能方面，繞線即是其中最重要的階段之一。由CEDA贊助的ISPDs [2] 和 [3]全球繞線競賽吸引了數十學術和工業參與者的關注。受到這些競賽的啟發，許多高性能的全域繞線器問世，包括但不限於FastRoute 3.0 [22], FastRoute 4.0 [20], BoxRouter 2.0 [7], NTUgr [6], NTHU-Route [10], NTHU-Route 2.0 [5], GRIP [19], FGR [18], MaizeRouter [16], Archer [17] and NCTU-GR [9].
這些全域繞線器大致可以分為兩類：順序和並行算法。順序算法[22]、[20]、[6]、[10]、[5]、[16]、[17]、[9]使用啟發式(heuristics)撕裂和reroute（RNR）技術進行繞線，通常運行2D全域繞線，然後進行層分配。另一方面，像[19]和[18]直接通過運行完整的3D全域繞線來解決問題。
同時，現今廣泛使用IP區塊以縮短交付時間(turnaround time)，將SOC設計與IP區塊或macro進行打包(pack)。為了避免在這些區塊(blocks)上進行繞線，避障直交式Steiner最小樹(obstacle-avoiding rectilinear Steiner minimum tree/ OA-RSMT)也是近年熱門研究主題（例如[4]、[12]至[14]）。然而，完全避免這些繞線區域將導致高層金屬層的利用顯著低落，而其為節省功率並實現時序關閉(close timeing)的關鍵。為了應對這個問題，在考慮緩衝感知的前提下，[21]和[11]提出了智能利用部分而不是完全避免區塊內繞線資源的新思路，並將其作為BOB-RSMT [21]問題進行研究，同時也作為[15]中的風景約束(scenic constraints)進行研究。
由於兩個ISPD全球繞線競賽的指導相似，大多數發表的現代繞線器都針對同一問題：透過途徑數量最小化線長，以及緩解擁塞。然而，考慮線長、途徑(vias)和overflow，並適當地使用區塊內繞線資源的全局繞線問題從未被討論。研究這個新問題至關重要；它不僅可以縮短設計周期，還可以提高芯片品質。如果將區塊內繞線資源與區塊外繞線資源一視同仁，則在區塊上的長途網絡將無法進行緩衝，導致額外的手動(manual)工作；而如果完全不使用區塊內繞線資源，則更少的剩餘繞線資源將嚴重損害繞線的品質。

我們的主要貢獻包括：
1) 我們首次研究了區塊內(over-the-block)全域繞線問題，提供了同時考慮overflow、線長、count和緩衝感知的全域繞線解決方案。
2) 我們通過解決BOB-RSMT算法 [21] 的兩個限制來改進它，然後應用修改後的BOB-RSMT算法來生成我們的合法初始inside-tree。
3) 對於任何具有overflow的區塊，在每次迭代中，我們從該區塊inside-tree中產生新的拓撲，其擁塞、線長和途徑數量的成本較低。
4) 我們進行基於拉格朗日乘子的成本函數，以反映所有生成的拓撲的加權影響。結果表明，成本較低的拓撲將對決定覆蓋邊緣(covered edges)的成本產生更大的影響。
5) 我們提出了一種RC約束的A* search方法，以幫助逐步發展成本最低的新拓撲，同時滿足延遲約束。

論文的其餘部分結構如下。我們首先在第二節介紹inside-tree、延遲模型和問題概述的基本概念。我們的區塊內繞線算法將在第三節中呈現，該節包括三個小節。
第三節A部分討論如何修改BOB-RSMT以生成初始合法內部拓撲。第三節B部分說明了根據拉格朗日乘子的成本函數和RC約束A* search逐步發展新拓撲的過程。實驗結果在第四節中展示和分析，最後在第五節得出結論。

## II. Preliminary
### A.基本區塊內概念
圖1. 由分為3*3全域繞線區域的三個金屬層組成的3D網格圖G

在全域繞線中，芯片被劃分為矩形的全局繞線區域，其中使用一個3D網格圖G =（V，E）來建模多層設計。如圖1(a)和圖1(b)所示，每個全局繞線區域都是一個頂點v ∈ V。同一層上相鄰的兩個全域繞線區域之間的邊界被建模為一條邊e ∈ E，其容量ce反映了單元格之間的最大繞線資源。
在放置後，芯片被放置了(is packed with)佔用低層金屬層並禁止在IP區塊上插入緩衝器的IP區塊或macro。在我們的定式中，我們將B = \{b1，b2，...，bm}設置為區塊集合。每個區塊都在3D網格圖G中由一個方塊(box)建模，如圖1中的陰影部分所示。
我們需要在3D圖G中連接一組多終端網絡N = \{n1，n2，...，nk}。每個網絡ni的樹拓撲將進入並離開圖中的區塊，這將整個樹拓撲分為一組outside trees TOi和一組inside trees TIi。
對於任何inside trees t，t的葉節點位於一個區塊的邊界上。在所有葉節點中，必須有一個輸出信號，其他則為接收信號。我們將這些接收信號的葉節點稱為逃逸點（escaping points, E），對於t，逃逸點的集合是EPt = \{EPt1，EPt2，...，EPt|EPt|}。
我們使用與[21]相同的模型來檢查是否有任何inside tree滿足延遲約束。在我們的定式中，每個內部樹都被強制為合法的（即滿足延遲約束）。

### B.問題定式
我們使用包括線長、途徑成本和總overflow（TOF）的矩陣來評估我們的繞線解決方案。 TOF最好為零，因為即使只有些微overflow的全域繞線仍然會使詳細繞線變得更加困難。
我們提出的具有緩衝感知的全域繞線器將連接N中的每個網絡，以最小化總線長並減少TOF。區塊內樹必須滿足延遲約束，以確保每個拓撲都有可行的緩衝解決方案。

## III. BOB-ROUTER ALGORITHMS

BOB-Router 方法的整體流程如圖2所示。“Main loop”框架中的過程包含內部樹的路由算法，而其餘部分則由初始合法的RSMT生成以及外部樹的routing組成。

在BOB-Router問題的公式化過程中，任何內部樹都必須滿足為了緩衝而設的slew約束。由於這個額外要求，內部樹的routing比外部樹的routing更具挑戰性。我們的BOB-Router將優先routing內部樹，因為我們在算法上強調內部樹的routing，它更偏好於在外部樹routing成本上帶來最小的負面影響甚至改善。

為了避免在內部樹routing問題中同時處理線長、通孔數、過載和slew約束，我們通過先使所有拓撲合法化來解耦slew約束，並確保在整個內部樹routing過程中的每一步都不會違反slew約束。這個解耦過程包括兩個步驟。首先，由於初始的內部樹可能違反slew約束，我們應用基於EP運動的合法化程序（修改自[21]）來合法化任何非法的內部拓撲，並盡量減少線長的懲罰。其次，在內部樹routing中的“演化新拓撲”步驟（如圖2所示），我們使用受RC約束的A*搜索來確保每次新拓撲演化過程中的操作都不會打破slew約束。
### A.生成合法的初始拓撲
我們修改了 \[21\] 中的 BOB-RSMT 算法，以生成合法的初始內部樹。首先，我們將簡要回顧 BOB-RSMT 方法，然後研究 BOB-RSMT 的兩個不足之處。最後，我們將提出改進後的 BOB-RSMT（BOB-RSMT-m），以提供升級的初始合法內部樹。

在 BOB-RSMT 中，通過 FLUTE \[8\] 為每個網絡生成初始 RSMT。然而，對於任何生成的 RSMT，它可能會違反漸變約束並變得非法。首先，為了合法化非法 RSMT 中的任何非法內部樹 t，我們將根據其漸變違反情況對 t 的所有非法逃逸點（EP）進行排序。接下來，在每次迭代中，將合法化排序中漸變違反最嚴重的第一個非法逃逸點 EPt1。為了合法化 EPt1 的漸變，來自 {EPt1, EPt2,...EPt|EPt|} 的每個逃逸點可能會通過採取一組初始解滑動到不同的位置，同時更新內部Steiner nodes。這些初始化包括平行滑動（移動連接的分支）、垂直滑動（拉伸連接的分支）和與相鄰 EP 合併。使用 ILP 選擇每個 EP 最終的位置。最後，固定 EPt1 的位置，並啟動下一次迭代以合法化下一個非法逃逸點 EPt2。此過程將迭代進行，直到所有逃逸點滿足漸變約束為止。

#### 改進 BOB-RSMT 演算法

BOB-RSMT 方法有效生成滿足slew constraints的拓撲，但它有兩個限制。首先，內部樹的driver移動沒有被考慮。其次，當driver兩端的兩個分支同時移動時，可能會低估slew improvement。為了解決這兩個限制，我們保留優化初始解，但用greedy algorithm取代 ILP。取而代之的是，我們評估所有 EP 和driver的每個單位移動，並選擇最佳移動。例如，圖 3(a) 顯示了一個非法內部樹，而圖 3(b)、圖 3(c) 和圖 3(d) 分別展示了假設選擇driver、EP1 和 EP2 最佳移動的結果拓撲。為了直接顯示圖 3 中的slew improvement，我們設置單位 R 和單位 C 為 1，同時在我們的slew model中設置緩衝輸出電阻、緩衝輸入電容和輸出漸變為 0。如我們所見，最佳的slew improvement發生在圖 3(b) 中，driver通過單位移動減少了 19.88 個slew unit。然而，在 BOB-RSMT 中，這個解決方案無法找到，因為沒有考慮driver的移動。

#### 改進的 BOB-RSMT-m 的其他優點

改進後的 BOB-RSMT-m 還具有準確捕捉driver兩端多個分支同時移動時的slew difference的優點。在這種罕見情況下，BOB-RSMT 方法可能會忽視來自天線清除的slew improvement並高估分支滑動的slew improvement。如圖 4 所示，將 EP1 向右移動一個單位（圖 4(b)）可以改進 9.89 個漸變單位，而以相同方式移動 EP2（圖 4(c)）將改進 3.30 個漸變單位。如果在 BOB-RSMT 中應用 ILP 選擇這兩個滑動，總改進將被錯誤地加總為 13.19 個漸變單位。實際改進如圖 4(e) 所示為 11.98 個漸變單位，包括將 EP1 向右移動一個單位和移除 4(d) 中圈出的天線段。

### B. Evolving Legal Congestion-Aware Min-Cost Topologies (最小成本拓撲)
最初的內部樹合法化保證每個內部樹都能有一個合法化的拓撲結構。然而，將這些合法的拓撲結構同時放置在各自的區塊中可能會引發擁塞問題。為了解決這個問題，我們的方法使用生成的合法拓撲作為種子，進一步產生更多合法的、具有擁塞感知的拓撲結構，這些新拓撲的成本比當前的拓撲更低。最後，會為每個內部樹選擇一個拓撲結構，以實現最小的溢出和成本。

我們將拓撲結構保持在斯坦納樹（Steiner Tree）結構中，而不是將它們分解成兩針網（2-pin nets），原因如下：(1) 斯坦納樹結構具有更多靈活性，因為未固定的斯坦納點，而兩針網必須連接指定的端點；(2) 斯坦納樹結構允許在整個樹上進行非線性延遲計算的跟蹤，而這對分解的兩針網來說是不可能的。

在常規的全局繞線問題中，如何設計出具有最小成本的擁塞感知斯坦納樹拓撲結構是一個非簡單的問題。然而，我們對內部樹所需的斯坦納樹拓撲結構必須滿足額外的延遲約束。

#### B.1\) 公式：
首先，我們建立一個整數線性規劃（ILP）公式來描述每個區塊中的繞線問題。ILP公式中不包含延遲約束，因為ILP公式中所呈現的每個拓撲結構都是合法的。
T I = {T1, T2, ..., Tn} 是區塊 b 中的內部樹集合，公式中的 ζi 是 Ti 的所有拓撲結構的集合。對於每個斯坦納樹拓撲 t ∈ ζi，參數 Wit 代表該拓撲結構的總成本，包括線長和過孔。變量 Si 表示 Ti 的可繞性；如果 Si 為正數，則表示內部樹 Ti 無法使用可用的斯坦納樹拓撲進行繞線。公式中的表示每個邊 e 上所需的繞線資源數量，這需要保持在邊容量向量 Ce 之下。

為了最小化溢出，在目標函數中使用 MSi 來懲罰任何不可繞線的內部樹 Ti。參數 M 是一個預定義的較大數值，超過晶片中任何可能的斯坦納樹的線長。求解 ILP 公式（1）保證無內部溢出並最大限度地減少總成本和最大數量的可繞線內部樹。

在我們的方法中，ILP 公式有以下兩個目的：i) 選擇每個內部樹的一個拓撲，以檢查在每次迭代結束時是否可以實現無溢出解；ii) 鬆弛的 LP 雙重問題可以提供每個邊的成本。

#### B.2\) 邊的定價：
在求解 ILP 並固定當前迭代中的拓撲之前，我們需要更多的斯坦納樹拓撲，而不僅僅是最初的拓撲，以實現最小溢出和成本的繞線解決方案。我們使用對邊容量約束的敏感性分析來對每條邊進行定價，這為從當前拓撲演變出新的斯坦納樹拓撲提供了指導。
不同層上的不同邊在繞線中有不同的價值，因為其中一些位於擁擠區域，而一些則不是。我們計算價格來描述每條邊的潛在溢出。為了獲得邊的價格，我們首先通過放鬆二元變量 {Xij}，將 ILP 公式（1）放鬆為 LP 公式。

對二元變量 {Xij} 的放鬆將為每個內部樹選擇唯一拓撲的約束分解為一組分數，表示幾個潛在的首選拓撲。避免擁擠區域並且線長和過孔成本較低的拓撲將更受青睞，並被賦予正的 Xij，這取決於拓撲的質量。
每條邊的價格來自這個 LP 公式的對偶形式，如公式 (2) 所示。變量 λi 是與拓撲選擇約束 (1a) 相關的拉格朗日乘數，ρe 是與邊 e 的容量約束 (1b) 相關的拉格朗日乘數。根據互補鬆弛定理，對於最佳原始變量 X∗i，i ∈ {1, 2, ..., n} 和最佳對偶變量 ρ∗e，存在 ρ∗e ∗ (∑i=1n ∑t∈ζi Xite − Ce) = 0。

當 ρ∗e 為正時，∑i=1n ∑t∈ζi Xite − Ce = 0 成立，這意味著相應的邊 e 的容量沒有剩餘。如果存在最佳原始解，根據強對偶性，最佳對偶變量 ρ∗e 反映了如果邊 e 的容量增加一單位，我們可以在目標值上獲得多少改進。因此，我們使用最佳對偶變量 ρ∗e 作為邊 e 的價格。與其他繞線器中基於歷史的成本相比，我們的價格更全面，因為它考慮了我們擁有的所有拓撲結構，並根據它們的價值進行最佳加權。

#### B.3\) 三層拓撲選擇：
如果我們為每個現有的拓撲演變出新拓撲，拓撲池的規模將顯著增加，而 TOF（溢出總量）的減少速度卻不會相應提高。因此，我們通過只考慮最昂貴的拓撲來控制每次迭代中新演變的拓撲數量。
我們使用動態的三層拓撲選擇方法來確定每次迭代中要演變的特定拓撲。只有當當前階段無法進一步改善 TOF 時，才會啟動下一階段。下一層以更廣泛的方式選擇拓撲，從而進一步減少 TOF。

1. 在找到所有 Si 為正的內部樹後，所有與這些不可繞線的內部樹相關的拓撲將被演變。
2. 如果第一層拓撲的演變無法繼續優化 LP 公式，我們將通過為每個內部樹選擇 Xij 最大的拓撲來組合一個內部樹繞線解決方案。然後可以計算每條邊的溢出量。除了第一層的拓撲之外，任何包含溢出邊的拓撲也將被添加。
3. 如果第二層的拓撲演變無法繼續優化 LP 公式，我們將進一步演變覆蓋具有正價格邊的拓撲。

我們逐步放寬對拓撲演變的要求，通過控制處理的拓撲數量來推動優化。圖5評估了在ADAPTEC1的單個區塊上進行優化迭代過程中的三層拓撲選擇。圖中顯示，第一層的初始迭代會緩慢地增加拓撲數量。一旦在任何迭代過程中優化停止，將啟動下一層以減少TOF。

#### B.4\) RC受限A搜索：
在每次優化迭代中進行定價和拓撲選擇後，我們使用考慮到slew的拆除和重新繞線來演變新的拓撲。昂貴的部分將被拆除，然後應用RC受限的A搜索算法來重新繞線斷開的部分，而不違反slew約束。

對於選定的拓撲 t，我們找到所有價格非零的導線，並按照它們的價格降序排序。排序後，我們依次拆除和重新繞線每條導線。對於 t 上的一條導線 w，從 U 到 V 的信號，我們首先從 t 中移除 w，並將剩餘部分表示為 t\w。然後，我們計算 t\w 中每個點 p 的 RCp 和 Cp。RCp 和 Cp 是連接到點 p 而不違反slew約束的最大允許的 RC 和 C。 t\w 上所有點的最大可能的 RC 和 C 將是：

然後，應用RC受限的A搜索將V重新連接到剩餘部分 t\w。我們只會接受連接到點 p 的連接，其 RC 和 C 分別小於 RCp 和 Cp。在RC受限的A搜索中，任何 RC 超過 RCmax 或 C 超過 Cmax 的搜索路徑將被剪枝。我們在A搜索中每條邊 e 的成本是 e 的價格加一。我們使用的啟發式成本函數是到 t\w 中最近點的3-D曼哈頓距離，這顯然是一個下界。這種RC受限的A搜索保證了在slew約束下的最小成本解。

### C.外部樹routing
在內部樹的拓撲結構確定後，所有區塊內的邊緣容量將設置為零，以避免在進行外部樹routing時遇到阻塞問題。這將由現有的學術router來解決。

## IV. 實驗結果
BOB-Router 已經在 C++ 編程語言中實現。所有實驗都在一台配備 16GB 內存的 Intel Core 3.0GHz Linux 機器上進行。我們使用了 ISPD 2007 和 2008 Global Routing Contests的 3D global routing 基準測試 adaptec1 ∼ 4 和 bigblue1 ∼ 4 進行實驗。global routing contests的基準測試沒有明確標註區塊信息。據我們所知，global routing contests基準測試中的區塊孔隙率信息來自於某些放置基準測試中的固定宏單元。由於相鄰的區塊，從routing基準測試中直接檢索孔隙區域的幾何信息是困難的。因此，我們找到了相應的放置基準測試，從中提取了固定宏單元的幾何信息。此外，我們刪除了包含區塊內引腳的線路，因為這超出了我們的制定範圍。

每個金屬層的線路電阻和電容來自於 ITRS [1]，我們將 70ps 作為我們允許的最大斜率。

我們首先評估每個基準測試的slew違規情況。表二校準了所有內部樹在由FLUTE生成RSMT拓撲結構並應用簡單的層分配啟發式算法後的slew數據。這個啟發式算法會先將所有內部樹分配到最低允許的層對上。
然後，對於所有存在slew違規的內部樹，我們會根據slew違規的程度，將它們提升到更高的金屬層對。從表二可以看出，一些最初沒有slew問題的基準測試，例如bigblue2，可能會遇到slew問題，因為大多數內部樹可能已經被提升到最高的金屬層對。
由於在初始化期間我們消除了所有slew違規並將slew保持在約束範圍內，我們的最終路由解決方案將不會遇到任何slew問題。在圖6中，我們將表二中的內部樹slew分佈與基準測試adaptec1的最終路由解決方案進行比較。起初，我們觀察到內部樹的最壞slew達到1714ps。但是，在經過BOB-Router處理後，沒有任何內部樹的slew超過70ps，這是我們slew約束中允許的最大slew。slew在60ps到70ps之間的內部樹數量顯著增加，因為大多數原本slew違規的網絡都被合法化到略低於70ps。

如果一個router無法正確使用區塊上的routing資源，那麼在不違反邊沿時間約束的情況下，最安全的做法是將區塊上的routing容量設置為零（或設置較大的懲罰），完全避開這些區塊，這樣可能需要手動處理。我們將我們提出的BOB-Router與OA-Router在導線長度、via count和TOF（到達時間）的方面進行比較。我們修改了NTHU-Router 2.0 [5]使其成為OA-Router，並使用它來解決區塊外routing問題，因為它性能優良。結果如表一所示。從表中的最後一行可以看出，BOB-Router平均將約8%的導線長度和6%的via count推送到區塊上的部分。對於大多數基準測試，區塊上routing的TOF為零。通過使用區塊上的routing資源，BOB-Router的TOF僅為OA-Router的約33%，導線長度為88%，via count為78%。我們認為via count比導線長度減少更多，部分原因是BOB-Router在區塊上部分執行了完整的3D routing，而沒有進行層分配。BOB-Router的平均運行時間與OA-Router相同。然而，我們注意到，對於更大更複雜的基準測試，例如adaptec3，BOB-Router花費了更多的時間，因為需要更多的迭代和拓撲結構。

## V. 結論
在過去幾年裡，傳統的全球routing已經得到了廣泛的研究，這使得即使提高性能 1% 也變得困難。我們提出了一個從不同角度出發的全球routing問題的新形式化方法。解決這個新的 BOB-Routing 問題可以不斷縮短設計周期並提高routing質量。使用我們提出的方法，與避免障礙的方法相比，我們可以生成無斜率違規解決方案，其中 TOF 減少了 66%，線長減少了 12%，通孔計數減少了 22%。