# Minimizing wire length in floorplanning 譯文

# ABSTRACT
現有的布局規劃以左下角為基準進行壓縮。可以最佳化使用面積，但並不是和其他目的，如最小化總線長度。本文首先表明該問題通過線性規劃來表達的方式。再進而提出一種有效的、基於最小成本流(minimum-cost flow-based)的方案來解決問題，而不是使用常見但效率一般的線性規劃。該方案能夠在多項式時間內取得最小總線長度，同時保證了最小的面積需求。此外，該方案能夠輕易地擴展以處理如fixed area、IO pins、preplaced blocks、boundary blocks、range placement、alignment and abutment、rectilinear blocks、soft blocks，one-dimensional cluster placement和bounded net delay，且不損失最佳性。該算法的效率非常高，以北卡羅萊納州微電子中心 (MCNC) 的放置基準測試為例，它能夠在 0.4 秒内完成所有運算。而實驗結果表明，布線長度的優化最大可達 4.2%。

# INTRODUCTION
布局規劃是依據目標來決定芯片上電路、模塊的擺置位置，它是物理設計的早期部分，決定了芯片整體的性能。由於超大型積體電路的高度複雜性和continuous scaling down of technology (看不懂)，導致電路設計須採用多層方案以減少運行時常並提高品質。布局規劃已經被研究多年，而在平面上可以分為兩種：slicing 和 nonslicing

圖 1-a：最小化面積布局
圖 1-b：保持布局面積不變的情況下，改變了空白分布，優化導線總長
大多數布局規劃使用模擬退火算法來最佳化布局，而該方法的實現依賴於平面圖，而在本文中，則是使用序列對來呈現該方法，原因是它更簡單且被廣泛使用，但我們的方案並不限於序列對，對於其他表示的平面圖，可以推導出一約束圖，從而應用該方案。
而本文簡要安排如下：
Ch2 敘述了序列對和約束圖構造
Ch3 闡述最小化總導線長度問題，並提出最小成本流解決方案
Ch4 討論處理各種約束的能力
Ch5 實驗結果呈現
Ch6 提出總結

# PRELIMINARY
序列對是表示 n 個blocks的 n 個元素的一對序列。
以下述兩個序列對為例，它表達了兩個元素的幾何關係。
{[... bi ... bj ...], [... bi ... bj ...]} ⇒ bi 在 bj 的左側
{[... bi ... bj ...], [... bi ... bj ...]} ⇒ bi 在 bj 下方
序列對可以表達为網格（如上圖）。提出序列對的原始論文提出了通過兩個圖 Gh 和 Gv 將序列對轉換成布局的算法。 Gh 和 Gv 都有 n + 2 個頂點，代表 n 個blocks加上source和sink
如果 bi 在 bj 的左側，則 Gh 添加一個有向邊 (bi, bj )。
如果 bi 在 bj 的下方，則 Gv 添加一個有向邊 (bi, bj )。
對於任何一組[ bi, bj ]，Gh 或 Gv 中存在一個邊連接 bi, bj。 Gh 和 Gv 都是頂點權重、有向、非循環圖。此時定義block的座標為該block的左下角座標， Gh中的權重表示block的寬度，Gv中的權重表示block的高度。如圖1中指定放置的序列對是(b3b1b2，b1b2b3)，轉換為網格後如圖2所示。

# PROBLEM AND SOLUTION
一個序列對表法可以特定畫每個block之間的拓樸關係。在以前的演算法中，我們會利用給定一個序列對表將其block緊湊地擠壓至左下角以最小化面積。
儘管是同樣的面積，也存在著不同的放置方式能夠滿足序列對表的拓樸關係。這種方法簡單來說，就是將其為放置block的區域縮至最小以及最小整體導線長度並滿足其拓樸關係。
第一個問題:我們先給m個marco block分別為Wi X hi的尺寸以及n個net去連接每一個block以滿足他們相互的拓樸關係
並使此式最小化，W(Ni)為每一個net的導線長度，λi為其權重。

但隨著實用性，假如λi是小數，我們會使的每一個λi放大為整數，接下來我們利用一個例子來了解，假設每一個pin皆位於block中間，但事實上，我們的作法其實是不受這假設所限制。通常，用作網絡線長度估算的是net的包圍框的半周長。我們考慮一個連接Z個block的net和用(Li, Bi)表示左下角包圍框和(Ri，Ti)表示右上角的包圍框，並滿足
右邊的參數皆為每一個block的中心，若為非中心則改為實際座標。又幾何限制得滿足以下

因此，我們可以將問題簡化為

又考慮到x、y分別分析，可分別分析此兩式。
分開處理的原因是這樣可以使算法更快。正如我們所看到的，所有三個問題都是線性規劃問題。然而，它們所有約束都是差異約束。因此，它們的對偶問題是一個最小成本流問題，因為在對偶問題的約束矩陣中，每一列都只有一個"1"和"-1"。正如我們所知，線性規劃比最小成本流算法更一般，但要慢得多。我們可以構建一個水平網絡圖GH =（VH，EH），如下所示。

(1) VH = {s, t, x1, x2,...,xm, L1, R1, L2, R2,...,Ln, Rn}，s是來源節點，t是決策節點，xi就是每一個block的x座標，Li和Ri是表示包圍框的左便和右邊。

(2)EH = {(s, Ri)i = 1, 2,...,n}∪{(xi, xj )區塊bi在區塊bj的右邊}∪{(Ri, xj ),(xj , Li) 網絡Ni連接區塊bj}∪{(Li, t) i = 1, 2,...,n}，其中（s，Ri）是從源到包圍框的右邊界的邊緣，（xi，xj ）是由序列對所施加的邊緣，如約束（7）所示，(Ri,xj)是由網絡連接所施加的邊緣，如約束(4)所示。(xj,Li)是由網絡連接所施加的邊緣，如約束(3)所示。(Li,t)是從包圍框的左邊界到決策節點的邊緣。

(3)邊的容量：UH(s, Ri) = UH(Li, t) = λi，對於所有i ∈ {1, 2,…
,n}；對於EH中的任何其他邊e，UH(e)是無限的。

(4)成本函數：CH(s, Ri)=0，CH(Li, t)=0，CH(xi, xj )=-wj，CH(Ri, xj )=-wj/2，CH(xj , Li)=wj/2。

子圖包含由序列對施加的邊緣（xi, xj）的頂點xi（i = 1, 2,...m）類似於[14]中提到的水平約束圖。不同在於邊緣的方向相反，並且邊的成本為負值。因此，在[14]中，使用最長路徑算法來計算區塊的位置。而在此論文中，我們將使用最短路徑的最小成本流算法。

因此，我們在圖GH上計算了總量為∑n i=1 λi的最小成本流，這解決了雙重問題。根據約束計算區塊的位置並最小化總線長度（原始問題），這可以通過以下方式完成。首先，我們從最小成本流中得到了剩餘圖。然後，在剩餘圖上應用最短路徑算法將給出所有區塊的位置。如果需要，可以向剩餘圖添加一個連接到所有其他節點的共同源節點以進行最短路徑計算。
同樣地，我們可以構建另一個網絡圖，並使用最小成本流方法來解決。該圖稱為垂直網絡圖，表示為GV =（VV，EV）。 我們使用示例來說明這個方法。問題的輸入是一個序列對（b3b1b2，b1b2b3），其中包含三個區塊，網絡N1 = {b1，b2}的權重為λ1 = 2，網絡N2 = {b2，b3}的權重為λ2 = 1。然後，最小化x的線長度可以表示為
min {2(R1 − L1)+(R2 − L2)}
並以此為條件
接著這可以轉化最小成本流問題GH、GV，如此圖

整個算法步驟如下:
1.建構GH、GV
2.在GH、GV使用最小成本流法
3.得到GH和GV的剩餘圖
4.在剩餘圖中使用最短路徑法

我們在這展示了如何得到最短導線長度的方法。在下一個部分我們將討論如何得到最短導線長度以及同時獲得最小面積(在固定面積限制下)。其餘的邊包括由網絡連接引入的邊以及從源到匯的邊。從源頭到匯點的邊數是 O(n)。圖中由網絡連接引入的邊的數量與所有網絡中的引腳數成比例。通常情況下，在實踐中，我們可以假設網絡中引腳的數量平均是恆定的。因此，由網絡連接引入的邊的數量通常為 O(n)。總之，邊的數量是 O(m log m + n)。因此，如果我們採用Orlin 算法來計算最小成本流，Min-wire 算法的時間複雜度通常為 O (|E| log |V | (|E| + |V | log |V |)) = O((m log m + n) log(m + n)(m log m + n + (m + n) log(m + n))) = O((m log m + n)(m + n) log2(m + n))。在實際應用中，我們可以假設網絡權重 λi 是 O(1)（例如，1-10），這在大多數應用中是真實的。我們觀察到，在實際應用中不需要非常大的權重。當網絡權重超出某個閾值時，它在最小化線路長度方面的行為是相同的。然后，我們可以應用連續最短路徑增廣算法來計算最小成本流，這種情況下更快。因此，複雜度為 O(nS(m, n))，其中 S(m, n) 表示解決最短路徑問題所需的時間。我們可以將每個節點 i 與距離標籤 d(i) 關聯起來。然後，對於邊 (i, j) 的“減少”成本定義為 C(i, j) = C(i, j) + d(i) - d(j)。在最短路徑計算中，始終成立 d(j) ≤ d(i) + C(i, j)，因此如果我們通過最短路徑計算獲得距離標籤 d(i)，則 C(i, j) ≥ 0。因此，具有“減少”成本邊的圖形沒有負成本邊。我們可以使用 Bellman-Ford 算法獲取初始 d(i)。之后，我們可以將 Dijkstra 算法應用到具有“減少”成本的圖形上，因為“減少”成本 C(i, j) ≥ 0。請注意，Dijkstra 算法速度較快，但無法處理負成本。因此，S(m, n) 是 Dijkstra 算法的複雜度。最后，複雜度為 O(n(|E| + |V | log |V |)) = O(n(m log m + n + (m+n) log(m + n))) = O(n(m + n) log(m + n))。

# DISCUSSION OF CAPABILITIES
在應用中，平面規劃能處理約束是實用且重要的[25]。正如我們所見，這種方法能夠處理各種約束，並且維持最優解。

## A. 固定框架
在某些應用中，平面規劃受限於給定的框架 W × H，其中 W 和 H 分別表示寬度和高度。此外，如果我們仍然希望在最小化線長的同時保持最小面積，我們可以使用最小面積的框架來解決問題。當考慮框架時，我們如下修改圖表。對於水平網絡圖 GH，添加了兩個節點 fL 和 fR，其中 fL 和 fR 分別表示框架的左邊界和右邊界。我們有 xᵢ + wᵢ ≤ fR，xᵢ ≥ fL 和 fR - fL ≤ W。相應地，圖上添加了a set of edges：(fR, xᵢ)，成本為 -wᵢ，容量無限；(xᵢ, fL)，成本為 0，容量無限；i = 1, 2,...,m 和 (fL, fR)，成本為 W，容量無限。同樣，可以省略 (fR, xᵢ) 和 (xᵢ, fL) 中的transitive edges。同樣，對於vertical network graph GV，添加了兩個節點 fB 和 fT，分別表示框架的底邊界和頂邊界，以及相應的邊。圖 7 為兩個上述示例的修改後的圖表。框架是 6×6（最小面積）。因此，Min-wire 算法仍然可以應用於最小化總線長並將塊放置在給定的框架內。節點 fR（fT）將在計算 GH（GV）中的最短路徑時充當source node以獲得塊的位置。在計算中，我們設定 fR = W 和 fT = H。圖 1(b) 其實給出了在框架內的最優放置。

圖 7：未處理固定框架而修改的圖表，框架大小為6×6。
圖 7-a：水平網絡圖
圖 7-b：垂直網絡圖

## B. Composite Cost函數
我們已經討論了固定框架約束，即塊被限制在給定框架內。實際上，該方法是優化面積和線長的複合成本函數的確切算法：
min α(W + H) + ∑ λiWi
現有方法只能最小化面積並使用壓縮塊的位置來計算線長的成本。通過像處理固定框架約束(#上一段)那樣引入 fL、fR、fB 和 fT，我們可以將目標函數轉換為：
min α(fR - fL + fT - fB) + ∑ λi(Ri - Li + Ti - Bi)
注意W 和 H 變成了變數，其中 W = fR - fL，H = fT - fB。我們仍然可以通過修改圖 GH 和 GV 來使用Network-flow-based approach來優化複合成本。
這類似於處理固定框架約束的修改，只是在圖 GH 中沒有邊 (fL, fR)，且在圖 GV 中沒有邊緣 (fB, fT)。相反地，我們在圖 GH 中添加了邊 (s, fR)（成本為 0，容量為 α）和 (fL, t)（成本為 0，容量為 α），並在圖 GV 中添加了邊 (s, fT)（成本為 0，容量為 α）和 (fB, t)（成本為 0，容量為 α）。圖 8 顯示了兩個上面示例中的修改過的圖表，以優化複合成本函數，其中 α = 3。因此，基於最小成本流的算法可以被用來最優地最小化複合成本。應該注意，在這種情況下，the amount of flow 是 α + n∑(i=1) λi。

圖 8：修改圖表以最小化複合成本，其中α = 3。
圖 8-a：水平網絡圖
圖 8-b：垂直網絡圖

## C. 處理 IO 接腳
通常情況下，存在 IO 網，連接到框架邊界上的接腳（IO 接腳或 IO 墊片）。考慮一個連接到位置 (px, py) 的 IO 接腳的網 Ni。因此，Li ≤ px ≤ Ri 且 Bi ≤ py ≤ Ti。假設框架為 W × H。設定 fR = W 和 fT = H。等效地，Li - fR ≤ px - W ≤ Ri - fR 和 Bi - fT ≤ py - H ≤ Ti - fT。因此，我們在圖 GH 中添加了兩個邊 (fR, Li)（成本為 px - W，容量無限）和 (Ri, fR)（成本為 W - px，容量無限），並在圖 GV 中添加了兩個邊 (fT, Bi)（成本為 py - H，容量無限）和 (Ti, fT)（成本為 H - py，容量無限）。因此，Min-wire 算法可以應用。這種方式，可以處理固定接腳，其中接腳位置可能不在框架邊界上。

## D. Preplaced 和 Boundary Blocks
在一些塊必須放置在固定位置或框架邊界上的情況下，我們的演算法可應用於帶有額外邊的圖。例如，塊 bi 放置在位置 (lx, ly)，即 xi = lx 和 yi = ly。因此，xi - fR = lx - W 和 yi - fT = ly - H。同樣地，xi - fR ≤ lx - W，xi - fR ≥ lx - W，yi - fT ≤ ly - H 和 yi - fT ≥ ly - H。這些被轉化為圖 GH 上的邊 (fR, xi) 和 (xi, fR)，以及圖 GV 上的邊 (fT, yi) 和 (yi, fT)。邊界塊可以相似的方式處理，即邊界塊固定在 x 或 y 坐標中的位置。

## E. Range Placement
範圍約束指定某個塊必須放置在特定的範圍內。預置約束是範圍約束的一個特殊情況。同樣地，我們可以向圖 GH 和 GV 添加額外的邊，以強制在 Min-wire 演算法中計算位置，以確保區塊放置在指定的範圍內。

## F. 對齊和鄰接
對齊約束指定一排區塊必須在一個範圍內對齊[19]。它可以轉化為一組差異約束，以保持它們之間的相對位置。因此，我們可以相應地向圖表添加額外的邊。鄰接是對齊的一個特殊情況。

## G. 直角區塊
直角區塊被劃分為一組矩形子區塊。並使用一組約束來保持它們的相對位置，這可以轉化為圖表中的額外邊[7]。

## H. 軟區塊
在佈局規劃中，某些區塊的形狀可能不是固定的。例如，某些區塊的面積是固定的，但它們的寬度/高度比例可以在一定範圍內改變。這些類型的區塊被稱為軟區塊。要處理軟區塊，可以在模擬退火中引入移動（干擾），以改變軟區塊的形狀，就像[9]中的方法一樣。這種方式，移動是隨機的。另一種方式（更聰明），就像[1]、[21]中的方法一樣，每次選擇關鍵路徑上的軟區塊（“關鍵”表示路徑可決定芯片的大小），並優化其形狀。我們的方法可以以這兩種方式都來最小化線長。

## I、Cluster Placement
在應用程式中，將多個區塊彼此靠近放置（Cluster Placement）非常有用。換句話說，任兩個區塊之間的距離不應該太遠。 這可以寫成一組約束，指定任兩個區塊之間的距離界限。 一維簇放置指定 x 或 y 維度中的距離界限，可以將其寫入一組差異約束。 因此，我們可以透過向圖中添加相應的邊來解決問題。
在二維簇放置的一般情況下，距離界限是根據 x 和 y 維度的總和指定的。 我們可以根據壓縮結果或原始區塊放置，使用啟發式方法將二維簇放置按比例分解為 x 和 y 維度上的兩個一維簇放置問題。 另一方面，我們也可以使用拉格朗日鬆弛(Lagrangian relaxation)來解決問題。 我們將簇放置視為「虛擬」網絡，並調整網路的權重（拉格朗日乘數）以使其滿足距離限制。 因此，拉格朗日鬆弛的每次迭代仍然是為了解決最小成本流問題。

## J、Bounded Net Delay
此方法是最小化總線路長度，這不能保證關鍵網路的有限延遲。 為了解決有界網路延遲，我們使用距離的線性函數來估計延遲。 儘管互連延遲在線路長度方面是二次方，但透過適當的緩衝器插入，實際延遲在來源-匯距離方面接近線性。 這樣，我們將有界網路延遲轉換為有界網路線長度。 因此，，我們對網路的邊界框施加約束，從而相應地在圖中產生額外的邊。 對於所有這些約束，我們有以下充分必要條件。 定理 2：當且僅當圖 GH 和 GV 中不存在負循環時，存在滿足所有這些限制的可行佈局。 當圖具有無限容量的負循環時，不存在最小成本流。 我們可以看到，在圖 GH 和 GV 中，除了從來源節點或匯節點入射的邊之外，邊的容量是無限的，並且從來源節點或匯節點入射的邊不能成為任何環的一部分。 因此，任何負循環都將具有無限的容量。 如果不存在負循環，則可以使用 Minwire 演算法來計算滿足所有約束並具有最小導線長度的佈局。
1）對其圖進行進行面積填充，最小化面積和線長度。
2）我們演算法的主要部分是最小成本流。

## K. Applications to Block Placement
儘管我們在問題定義中輸入序列對，但該方法可以應用於任何平面圖/區塊佈局。 給定平面圖/塊佈局，我們可以先提取任何一對塊的拓撲關係並描述為“左邊”/“下面”。 對於具有對角關係的對，我們可以根據x和y維度上的兩個距離中哪一個較長來選擇“左邊”/“下面”之一。
這是因為選擇較長的一個可以讓我們更自由地移動方塊。 例如，在圖1（a）中，我們指定區塊b2在區塊b3下方，而不是區塊b3在區塊b2的左側。 然後，我們可以建構約束圖和網路圖。 此後，我們可以應用此方法來最小化電線長度。
對於由序列對以外的表示指定的佈局規劃
例如切片、BSG、TCG、CBL、Q序列、孿生二元樹、孿生二元序列），我們也可以建構約束圖，等價於表示指定的拓樸。 因此，該方法仍然可以應用。 請注意，該方法不會改變拓撲。
O-tree和B*-tree中的拓樸資訊不完整（僅指定x維關係，並透過打包取得floorplan）。 然而，我們可以從 O 樹和 B* 樹匯出區塊佈局，然後根據佈局建立約束圖。 我們將結果總結如下。
定理 3：最小線演算法對於最小化給定佈局拓樸的總線長度而言是最佳的。 拓撲可以從平面圖/區塊佈局中提取，或由任何平面圖表示指定。

# EXPERIMENTAL RESULTS
我們已經實現了該演算法並與佈局規劃器 FAST-SP 整合[18]。 我們的程式還可以讀取現有的平面圖並重新分配空白區域以優化電線長度。 假設 λi = O(1)，我們在最小成本流計算中使用連續最短路徑增廣演算法。
我們使用兩個平面規劃器 FAST-SP [18] 和 Parquet 3 [1] 測試了該程式作為平面規劃後的步驟。 測試問題源自於區塊放置的 MCNC 基準。 我們首先運行 FAST-SP 或 Parquet 3 以獲得帶有「最小化電線長度」選項的平面圖。 請注意，FAST-SP 和 Parquet 3 緊湊塊均位於左側和底部。 然後，應用Min-wire演算法進一步優化線材長度。 對於所有測試，我們使用區塊的中心作為引腳的位置並施加固定框架約束。
IO 接腳（IO 焊盤）的位置會根據幀邊界按比例調整大小。 表I列出了最小化線長度的實驗結果，其中所有塊都是硬塊。
應該注意的是，我們的程式不會改變平面圖拓撲和麵積。 因此，表中省略了面積。 實驗是在 Pentium 4 Mobile (2.4 Ghz) 筆記型電腦上進行的。 正如我們所看到的，演算法非常高效，所有基準測試所需時間不到 0.4 秒。 它還非常有效，即使是非常緊湊的佈局規劃，它也可以將電線長度平均進一步提高 4.2%。 作為例證，圖9和圖10分別顯示了ami33和ami49在FAST-SP中的原始佈局結果和最佳化後的佈局結果。

# CONCLUSION
在本文中，我們提出了一種在佈局規劃中最小化電線長度的新穎方法。 此方法可在區塊之間最佳化分配空白空間，並保證獲得給定佈局拓撲的最小總導線長度。 這也是最佳化面積和線長複合成本函數的精確演算法：
我們還表明，該方法可以處理各種約束，例如固定框架、IO 引腳、預置塊、邊界塊、範圍放置、對齊和鄰接、直線塊、軟塊、一維簇放置和有界網絡延遲，而無需失去最優性。 實驗結果表明，該方法非常有效率、有效。 因此，它提供了一種優化佈局規劃的理想方法。 未來的工作是擴展該方法，在佈局規劃中考慮佈線擁塞和緩衝區插入，並將其應用於混合單元佈局

## 註

### 啟發式（heuristics）
是一種問題解決方法，通常是一種簡化的、快速的、經驗性的方法，用來找到可能的解決方案或做出決策，特別是當面對複雜問題時。這種方法可能不是最優的，但它們可以在有限的時間內提供一個合理的解決方案或指導，而不需要完全究竟問題的所有細節或考慮所有可能的選項。
假設你正在一個陌生的城市旅行，想找到一家不錯的餐廳用晚餐。你並不知道這個城市的所有餐廳，也沒有時間和精力進行詳細的市場調查。在這種情況下，你可以使用一種簡單的啟發式方法來做決策，例如：
* 啟發式1：問當地人
* 啟發式2：尋找排隊的地方
* 啟發式3：查詢網上評論

在這個例子中，這些啟發式方法都有助於你快速找到一家餐廳，而不需要花費大量時間和精力進行市場調查。然而，這些方法都有其限制，因為它們可能忽略了某些因素，例如個人口味或特定的飲食要求。因此，這些啟發式方法提供了一個合理的解決方案，但不保證是最佳的選擇。

### 拉格朗日鬆弛（Lagrangian relaxation）
是一種優化問題的數學技巧，用於解決具有約束條件的優化問題。它的主要目的是將原始問題轉化為一個更容易求解的形式，同時保留原問題的一些關鍵性質。
優點是可以將一個困難的優化問題分解為多個較容易處理的子問題，並且在某些情況下，它可以提供原問題的近似最優解。
* 讓我們以一個簡單的例子來說明：
假設你要在花不超過100元的情況下買一些水果，並且你知道蘋果的價格是每個5元，香蕉的價格是每個2元，橙子的價格是每個3元。你想知道應該買多少個蘋果、多少個香蕉和多少個橙子，以使你的花費最小化。
這是一個優化問題，我們可以將其表示為：
最小化花費：5x + 2y + 3z
同時，你還有一個約束條件，即總花費不能超過100元：
5x + 2y + 3z <=100