【芯片設(shè)計】從RTL到GDS（九）：布線

倒序瀏覽 · 發(fā)表于 2024-10-28 11:58:00

在前面的文章中，我們已經(jīng)完成了布局和時鐘樹綜合了。既然該擺放的東西都擺好了，我們現(xiàn)在應(yīng)該是把它們連起來。連起來以后各個Cell、Macro Blcok等就可以建立彼此的通訊了。這就是本篇文章將要談?wù)摰闹黝}，布線即Routing。

1、Introduction大家可能會覺得，把該連的接口都連好不就行了。實際中可能沒有這么簡單粗暴，因為芯片的規(guī)模很大，有非常多非常多的門，因此也會有非常多非常多的連線，我們不光要連，還要連好。

我們來考慮兩個東西，首先是幾何復(fù)雜性，在布線過程中，通常使用網(wǎng)格表示法作為基本的出發(fā)點。但是在納米尺度上，幾何規(guī)則變得非常復(fù)雜。此外，集成電路中通常有多個布線層，每個層的“成本”（如制造難度、電阻、電容等）都不同，這增加了布線的復(fù)雜性。
然后是電氣復(fù)雜性：僅僅連接所有電線是不夠的。還必須確保電線中的延遲盡可能小，因為信號在傳輸過程中延遲過大會影響電路的性能。同時，還需要確保電線之間的相互作用（如串擾）不會干擾電路的行為。串擾是指信號在一條電線中傳輸時，無意中影響到另一條相鄰電線上的信號的現(xiàn)象，這可能導(dǎo)致信號失真或錯誤。

我們把Routing這個問題細化一下，其主要包含以下幾個要點。
問題：在給定的芯片布局（placement）和固定的金屬布線層數(shù)的條件下，找到一個有效的水平線和垂直線的模式，以連接網(wǎng)的端點。
輸入：單元位置，網(wǎng)表。單元位置指的是各個標準單元在芯片上的物理位置，網(wǎng)表則列出了所有需要連接的端點組合，即哪些端點屬于同一個網(wǎng)。
輸出：net的幾何布局，即每個net在芯片上的實際布線圖案，連接了各個標準單元。
兩步過程：全局布線（Global routing）和詳細布線（Detailed routing）。全局布線確定電線的大致路徑，而詳細布線則在這些路徑上精確地放置電線。
目標：系統(tǒng)的100%連通性，即所有網(wǎng)都必須正確連接；最小面積，即在滿足布線要求的前提下，占用最小的芯片面積；最短線長，即電線總長度盡可能短，以減少延遲和串擾。
約束條件：布線層數(shù)的限制，設(shè)計規(guī)則（Design rules），時序（延遲），串擾（Crosstalk）和工藝變化（Process variations）。設(shè)計規(guī)則定義了布線時可以采用的路徑和間距等規(guī)則，時序約束要求電線的延遲必須滿足特定的性能要求，串擾約束要求布線時要減小電線之間的相互干擾，工藝變化則要求布線能夠適應(yīng)制造過程中的不確定性。

2、Routing Algorithms在了解了Routing的概念以后，我們來看以下Routing常用的算法，這里主要是從EDA工具的視角看，學習一下EDA工具背后的原理。下面的例子都是非常簡化的版本，但對于我們的學習還是有幫助的。

在處理納米尺度的集成電路布線問題時，盡管實際布線可能非常復(fù)雜，但為了簡化問題，我們首先假設(shè)布線是在一個規(guī)則的網(wǎng)格上進行的。
在這個假設(shè)下，導(dǎo)線只能在網(wǎng)格的垂直和水平方向上走線，形成直角路徑，這種布線方式被稱為曼哈頓布線。網(wǎng)格中的某些單元可能被標記為障礙物，導(dǎo)線必須繞過這些障礙物。這樣的簡化假設(shè)有助于我們更容易地理解和計算布線問題，隨著問題的深入，我們可以逐步引入更多的復(fù)雜性以更接近實際情況。

我們首先看一個算法，Maze Routers，其策略如下：

一次布線一個net。

為當前net找到最佳的布線路徑。

存在的問題是：

早期布線的net可能會阻擋后來net的路徑。

對一個net的最優(yōu)選擇可能會阻塞其他net。

該算法基本思路包括三個步驟：

Expand（擴展）：從源點到目標點，以四個基本方向（上、下、左、右）擴展，尋找可行路徑。這一過程通常使用廣度優(yōu)先搜索（BFS）或類似的方法來實現(xiàn)。

Backtrace（回溯）：一旦找到目標點，通過標記的路徑回溯到源點，確定最終的布線路徑。

Cleanup（清理）：在確認了布線路徑之后，移除所有為了尋找路徑而設(shè)置的臨時標記，只保留最終的布線路徑。
迷宮布線器的這種逐步擴展和回溯的方法，可以有效地找到從源點到目標點的路徑，但是它可能會遇到早期布線網(wǎng)絡(luò)對后續(xù)網(wǎng)絡(luò)布線的阻礙問題。因此，在實際應(yīng)用中，可能需要結(jié)合其他布線策略和優(yōu)化算法來提高整體布線質(zhì)量和成功率。

迷宮布線中的擴展（Expansion）階段是布線過程的第一步，其目的是從源點開始，逐漸擴展到目標點，尋找所有可能的路徑。這個過程可以描述如下：

從源點開始，尋找所有與源點相鄰的、可達的單元格（即沒有被障礙物占據(jù)的單元格）。

以這些單元格為新的起點，繼續(xù)尋找它們相鄰的可達單元格，如此類推，不斷擴展。

這個過程一直持續(xù)，直到達到目標點。

在擴展過程中，我們可以想象一個“波前”（wavefront）從源點向外擴散，逐漸接近目標點。這個波前代表了布線過程在網(wǎng)格中擴散的邊界。當我們到達目標點時，我們就可以確定從源點到目標點的最短路徑。在這個例子中，我們找到了一條最短路徑，它包含6個單位步驟。這意味著從源點到目標點的路徑長度是6個網(wǎng)格單元。
需要注意的是，迷宮布線算法在擴展過程中可能會找到多條路徑到達目標點，但在回溯階段，我們通常會選擇其中一條最短的路徑作為最終的布線路徑。

在迷宮布線過程中，一旦擴展階段找到了從源點（S）到目標點（T）的路徑，接下來就會進行回溯和清理階段。
回溯階段：

回溯是指從目標點開始，沿著路徑長度遞減的順序反向追蹤。

這樣做可以標記出一條到目標點的最短路徑。

通常情況下，可能存在多條同樣長度的最短路徑，這時可以采用優(yōu)化策略來選擇最佳路徑。例如，可以根據(jù)路徑的直線性、拐角數(shù)量或與其他網(wǎng)絡(luò)的干擾程度來決定。

清理階段：

當?shù)谝粭l網(wǎng)絡(luò)布線完成之后，為了確保未來的網(wǎng)絡(luò)不會嘗試使用同一條路徑，需要將這條從源點到目標點的網(wǎng)絡(luò)路徑標記為障礙物。

這樣，當其他網(wǎng)絡(luò)進行布線時，就不會考慮已經(jīng)占用過的路徑，從而避免了資源沖突。

通過回溯和清理，迷宮布線器為每個網(wǎng)絡(luò)逐一找到并確定了最佳的布線路徑，并為后續(xù)網(wǎng)絡(luò)的布線做好了準備。這個過程需要重復(fù)進行，直到所有的網(wǎng)絡(luò)都完成了布線。

在迷宮布線中，處理障礙物（blockages）的方法就是簡單地“繞過”它們。具體來說，當布線算法在擴展（Expand）階段遇到障礙物時，它會忽略障礙物占據(jù)的單元格，繼續(xù)在其余可用的單元格中尋找路徑。這樣做可以確保布線不會穿過障礙物，而是圍繞它們進行。
總結(jié)一下處理障礙物的方法：
擴展（Expand）階段：使用廣度優(yōu)先搜索（Breadth-First Search, BFS）來按路徑長度順序找出從源點（S）到目標點（T）的所有路徑。在這個過程中，障礙物被視為不可通過的單元格，布線算法會自動避開它們。
回溯（Backtrace）階段：一旦找到目標點，算法會沿著最短路徑回溯到源點。這個過程會標記出一條避開所有障礙物的最佳路徑。
清理（Cleanup）階段：在確認了布線路徑之后，將這條路徑標記為障礙物，以防止后續(xù)網(wǎng)絡(luò)使用相同的資源。同時，擦除在擴展階段留下的距離標記，為下一次布線做準備。
通過這種方式，迷宮布線算法能夠有效地處理集成電路布線中的障礙物問題，確保每個網(wǎng)絡(luò)都能找到一條合適的路徑，并且不會與其他網(wǎng)絡(luò)發(fā)生干擾。

對于具有多個目標點的網(wǎng)絡(luò)（Multi-Point Nets）進行布線時，處理方式相對直接。以下是解決多目標點網(wǎng)絡(luò)布線的步驟：
初始布線：使用常規(guī)的迷宮布線算法（maze routing algorithm）找到從源點到最近目標點的路徑。在這個階段，我們只關(guān)注一個目標點，并找到到達它的最短路徑。
重新標記：一旦找到了到達第一個目標點的路徑，我們將路徑上所有的單元格重新標記為源點（sources）。為什么可以這么做呢？因為這時候這幾個單元格從電路上來講，是等電位的，我們認為其電氣信息是一樣的。這樣做的目的是為了將已經(jīng)布線的路徑轉(zhuǎn)換為新的布線起點，以便于為其他目標點布線。
重復(fù)布線過程：使用所有新的源點同時作為起點，再次運行迷宮布線器。這一次，布線器會嘗試找到從這些新的源點到剩余目標點的路徑。這個過程可能會重復(fù)多次，直到所有的目標點都通過路徑與源點相連。
通過這種方式，多目標點網(wǎng)絡(luò)的每個目標點都會通過一條獨立的路徑與源點相連，而這些路徑之間不會相互干擾。這種方法確保了每個目標點都能夠有效地連接到源點，同時保持了布線的效率和合理性。

下面是上述方法的一個具體流程，解釋的很清楚。

上述方法找到的并不是最優(yōu)路徑，而是基于啟發(fā)式算法的一個局部最優(yōu)解，全局最優(yōu)路徑有一個名稱叫做Steiner Tree。找到這個路徑是一個NP-hard問題。

我們已經(jīng)討論了單個Layer的布線問題，對于Multi-layer呢？首先我們看幾個Multi-layer的圖片。

怎么解決？此時我們要定義新的擴展方向，up/down。通過通孔去連接。

下圖是涉及到兩層的Source到Target。

對于通孔而言，其電阻相對較高，按理說我們應(yīng)該盡可能的在同一層布線。我們也傾向于使用曼哈頓布線，對于每一層的導(dǎo)線將只沿一個方向布置，比如某一層只進行水平布線，而另一層只進行垂直布線。這種方式有助于減少導(dǎo)線之間的交叉和干擾。在布線過程中，如果需要改變方向，通常需要通過通孔到另一層進行，或者在同一層內(nèi)進行曲折（jog）布線。由于這兩種情況都會增加布線的復(fù)雜性和電阻，因此算法會對此類操作進行懲罰，以鼓勵更直接的布線方式。
基于non uniform grid costs懲罰機制，有助于實現(xiàn)上述的要求。

比如下圖中，對于Metal1，我們只希望水平布線，如果豎直布線成本將是10。而Metal2與之相反，經(jīng)過Via，也會有額外的成本為10的開銷。這樣我們可以基于Non uniform grid cost的方式找到想要的路徑。

實現(xiàn)這樣的布線算法需要高效的算法和數(shù)據(jù)結(jié)構(gòu)。對于如此巨大的網(wǎng)格（例如一個1cm x 1cm的芯片，100納米的軌跡，10個布線層，總共1000億個網(wǎng)格單元），我們需要一種低成本的表現(xiàn)形式來處理這個問題。以下是如何實現(xiàn)這個算法的步驟：

低成本的表示法：由于網(wǎng)格巨大，我們不能存儲每一個網(wǎng)格單元的詳細信息。相反，我們只存儲波前，即當前正在處理的邊界區(qū)域。這樣可以大大減少內(nèi)存的使用。

記錄已到達的單元格：我們需要記錄哪些單元格已經(jīng)被訪問過，以及到達這些單元格的成本和來自哪個方向。這樣可以幫助算法避免重復(fù)訪問單元格，并確保找到最便宜的路徑。

使用Dijkstra算法：Dijkstra算法是一種圖搜索算法，用于找到從起點到其他所有點的最短路徑。在這個場景中，我們可以使用Dijkstra算法來找到成本最低的單元格。

數(shù)據(jù)存儲在堆中：堆是一種特殊的數(shù)據(jù)結(jié)構(gòu)，可以有效地找到最小元素。在這個算法中，我們可以使用最小堆來存儲和檢索到達每個單元格的成本，以便我們可以快速找到下一個成本最低的單元格。
[/ol]

具體實現(xiàn)步驟如下：

初始化一個最小堆，用來存儲所有可訪問的單元格及其對應(yīng)的成本。

將起點添加到堆中，其成本為0。

當堆不為空時，執(zhí)行以下步驟：

從堆中移除成本最低的單元格。

對于該單元格的每個鄰居，計算到達該鄰居的成本。

如果鄰居未被訪問過，或者找到了一條更cheap的路徑，則更新該鄰居的成本和方向，并將其添加到堆中。

當算法到達終點時，回溯已記錄的方向，以找到從起點到終點的最優(yōu)路徑。
在實際的EDA布線中，還需要考慮其他因素，如布線層的方向性限制、通孔的成本、布線層的容量限制等。這些因素需要在算法的成本計算和決策過程中被考慮進去。

對于大芯片，常常采用分治策略，先Global Routing再Detailed Routing。我們將一個芯片分成一個個的大格子，這個大格子我們叫做GBOX。Global Routing基于大格子先粗略確定每個格子到每個格子的入口和出口。其內(nèi)部的細節(jié)先不管。

完成以后再對格子內(nèi)部的連線確定細節(jié)，這一步叫做Detailed Routing。

就比如我們有了第一個Box內(nèi)部的source和target。我們的Detailed Routing就是確定這個一個個Box內(nèi)部的連線。

3、Routing in Practice在上面的介紹中，我們用了很EDA的視角去看布線，接下來我們從更加電路的視角去看布線。

我們可以看到隨著工藝節(jié)點的提升，Layer的層數(shù)也在增加。對于早期的工藝，我們可以看到其盡管有很多層，但是每一層都是一樣的，因此DRC規(guī)則中，最小間距和最小寬度將會保持一致。
隨著工藝的推進，我們需要厚度更加厚的金屬層，從而減少RC值并提高更好的電源布線。較低的金屬層主要用于局部互連，中間層可能用于時鐘或者更長的全局布線，頂層主要用于電源連接。
右邊是兩個實際的例子，我們可以看到UMC的六層金屬堆疊和英特爾的8層金屬堆疊明顯不一樣�？梢钥吹�8層金屬堆疊明顯有幾種不同厚度的metal layer，不同厚度的metal layer用于做不同的事情。

我們接著探討一下EDA工具內(nèi)部的實際路由過程是如何進行的。正是由于上述的金屬層變化的問題，會讓我們的布線問題變得更加困難。文章上面講過的布線算法也會變得復(fù)雜起來。
我們從全局布線開始考慮，全局布線將整個芯片的布局劃分為多個GCell（Global Cell），每個GCell代表了芯片上的一塊區(qū)域。全局布線的目標是為芯片上的各個連接提供初步的路徑，這些路徑將在后續(xù)的詳細布線（Detailed Routing）階段被細化。以下是全局布線的一些關(guān)鍵特點：
將floorplan劃分為GCells：全局布線首先將芯片的布局（floorplan）劃分為一系列的GCell。每個GCell包含了一定數(shù)量的布線資源，如導(dǎo)線軌道。在每個布線層上，每個GCell大約包含10個導(dǎo)線軌道。這些軌道用于連接芯片上的不同模塊。軌道有Minimum Width和Minimum Spacing屬性，具體的可以看圖。這個是用于滿足DRC約束的。
全局布線的目的是執(zhí)行快速的網(wǎng)格布線：全局布線使用一種快速的網(wǎng)格布線方法，這種方法在GCell網(wǎng)格上為信號提供路徑。

最小化線長：全局布線試圖找到連接各個模塊的最短線路，以減少信號的延遲和功耗。

平衡擁堵：布線時需要考慮不同區(qū)域布線資源的利用率，避免某些區(qū)域過度擁堵，而其他區(qū)域則空閑。

時序驅(qū)動：全局布線考慮信號的時序要求，確保信號能夠在規(guī)定的時間內(nèi)到達目的地。

噪聲/信號完整性驅(qū)動：布線時還需要考慮信號完整性和噪聲的影響，避免由于布線不當導(dǎo)致的信號退化。

保持總線在一起：對于總線（一組并行信號線），全局布線會盡量將它們保持在一起，以便于后續(xù)的詳細布線和信號完整性分析。

全局布線完成后，將生成一個布線圖，該圖顯示了芯片上各個連接的大致路徑。這些路徑將在詳細布線階段被進一步優(yōu)化和實現(xiàn)，以滿足電路的性能和制造要求。
比如在下圖的右上角，我們在完成Global Routing以后，就可以知道哪些地方是Congested Area了。

通常在完成全局布線的時候，我們將使用congestion map展示較高擁塞的區(qū)域。然后就要進行布局規(guī)劃的迭代過程，針對這些區(qū)域進行修正。如果存在這些大規(guī)模的擁塞區(qū)域，最好不要繼續(xù)進行detailed routing，而是返回去修正布局規(guī)劃，否則對后續(xù)的布線非常困難。

完成了全局布線的迭代以后，就可以進行Detailed Routing。我們將逐個的處理Gbox。之前的Global Routing是非常粗略的GBOX和GBOX之間的連接。

我們不是已經(jīng)對每個GBOX都設(shè)置好相應(yīng)的軌道了嗎？我們現(xiàn)在就是確定GBOX內(nèi)部之間，是怎么根據(jù)這個軌道連接的。這個內(nèi)部的Routing，我們也要考慮下面這幾個因素。

我們再來看看時間驅(qū)動布線，這是什么意思呢。其主要是嘗試對關(guān)鍵路徑進行優(yōu)化，如果系統(tǒng)仍然存在時序問題，通過布線的方式可以進行一定的優(yōu)化，對關(guān)鍵路徑采用最短的路徑，以減少延遲。
我們需要采用權(quán)重的方式，給不同的Net分配不同的權(quán)重，比如說這個Net比其它Net更加重要，工具要有限對其進行布線，盡可能不要經(jīng)過Via，不要拐彎。

我們接著看看信號完整性問題。布線之所以會導(dǎo)致信號完整性問題，主要是串擾問題。一個信號的切換可能會影響附近的net，導(dǎo)致其上出現(xiàn)毛刺或其它信號問題。我們稱切換信號的net為Aggressor，被影響的net為Victim。
有兩個主要的影響，當攻擊者上升的時候，Victim正在下降，這個串擾問題導(dǎo)致其下降變緩慢了，我們看圖可以看出來，它又重新升了一會，才下降。這導(dǎo)致了信號變化的Slow Down，與之類似的還有信號變化的Speed Up。
這實際上是由互耦電容引起的，我們要保證電容值不會過大，以避免串擾引起的毛刺或其它問題。

在比較舊的工藝中，會采用無限噪聲窗的方式分析這個互耦電容產(chǎn)生的影響。但隨著工藝的提升，導(dǎo)線之間的間距日益縮小，交叉覆蓋面積增大，側(cè)壁電容增加，導(dǎo)致了極端情況的出現(xiàn)。比如Net B在考慮最大延遲的時候顯著減速，最小延遲的時候顯著加速。（其實到這里我就看不懂了，有懂的大佬可以詳細解釋一下）
為此一種新型時序分析方法被提出并被整合進了EDA工具，稱為傳播噪聲分析。傳播噪聲分析是一種更為精確的方法，它考慮了實際信號波形的變化。在這種分析中，會使用設(shè)計中的最小和最大信號向量來模擬干擾源和受害線之間的相互作用。通過這些向量，可以為每個干擾源相對于受害線創(chuàng)建一個時間上的過渡窗口。這個窗口代表了干擾源可能對受害線產(chǎn)生影響的時刻。噪聲只在干擾源的過渡窗口和受害線的敏感窗口重疊時才被考慮，這樣可以更準確地確定由多個干擾源引起的最壞情況下的噪聲尖峰。

我們看一下怎么解決信號完整性問題，防止串擾的首要措施是限制平行net的長度，如果由兩條net平行，通常應(yīng)該增大它們之間的間距。還要考慮屏蔽特殊net，如果有特殊net，可以在中間放置一個屏蔽層，這樣可以大大減少net之間的交叉耦合。對于Victim，可以擴大其Size，這樣平均下來交叉耦合效應(yīng)的影響就會降低。
我們看幾個例子，下面的四個例子分別采用了增加空間，調(diào)換順序，添加屏蔽層，重新排序形成隔離屏障的方式優(yōu)化串擾問題。

另一個問題就是所謂的可制造型涉及，即DFM問題。我們通過添加額外的方法以提高良率，降低特定芯片出現(xiàn)缺陷的風險。方法包括但不限于：
Via reduction：目的：減少過孔（Via）的數(shù)量可以降低制造復(fù)雜性，減少潛在的缺陷點，提高良率。方法：通過優(yōu)化布線策略，比如使用更有效的層間連接方式，或者合并多個相鄰的過孔，來減少過孔的總數(shù)。
Redundant via insertion：目的：插入冗余過孔可以提高電路的可靠性，因為在制造過程中某些過孔可能會失敗。方法：在關(guān)鍵信號線上添加額外的過孔，確保即使某些過孔出現(xiàn)問題，信號仍然可以通過其他過孔正常傳輸。
Wire straightening：目的：直線的布線可以提高制造的準確性，減少布線錯誤，降低信號完整性問題。方法：盡可能使用直線的布線方式，減少不必要的彎曲，這樣可以降低布線的電阻和電容，提高信號質(zhì)量。
Wire spreading：目的：線展開可以減少布線之間的相互干擾，降低串擾，提高信號完整性。方法：在布線時，盡量增加線與線之間的距離，特別是在高速信號線上，這樣可以減少電磁干擾，提高電路的性能。
我們看下面這個圖，Wire straightening把本來是拐彎了幾次的線給他拉直了。另外一個例子是，我們有一個晶體管，有兩個彼此對稱的接觸點，但不是完全對稱，這可能導(dǎo)致較高的制造缺陷風險。通過增加兩個額外的接觸點，讓其變得更加對稱。

我們直接看兩個例子：

我們看一下Innovus中Routing怎么做（Encounter就是之前的名字，現(xiàn)在已經(jīng)改名Innovus了）�？梢钥吹绞褂霉ぞ弑戎拦ぞ呒毠�(jié)簡單的多，這就是抽象的力量。

系列文章入口——

【芯片設(shè)計】SoC 101（一）：緒論

【芯片設(shè)計】FIFO漫談（零）從無處不在的FIFO開始說起

【芯片設(shè)計】計算機體系結(jié)構(gòu)（一）虛擬內(nèi)存

【芯片設(shè)計】深入理解AMBA總線（零）緒論

【芯片設(shè)計】握手協(xié)議的介紹與時序說明

【芯片設(shè)計】復(fù)位那些小事 —— 復(fù)位消抖

【芯片設(shè)計】快速入門數(shù)字芯片設(shè)計（一）Introduction

【芯片驗證】UVM源碼計劃（零）下定決心讀源碼前的自測環(huán)節(jié)

【芯片設(shè)計】異步電路碎碎念（一）到底什么是異步電路

【芯片設(shè)計】從RTL到GDS（一）：Introduction

其他文章鏈接——

【芯片驗證】sva_assertion: 15道助力飛升的斷言練習