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

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

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

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

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

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

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

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

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

一次布線一個net。

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

存在的問題是：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

清理階段：

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

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

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

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

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

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

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

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

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

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

對于通孔而言，其電阻相對較高，按理說我們應該盡可能的在同一層布線。我們也傾向于使用曼哈頓布線，對于每一層的導線將只沿一個方向布置，比如某一層只進行水平布線，而另一層只進行垂直布線。這種方式有助于減少導線之間的交叉和干擾。在布線過程中，如果需要改變方向，通常需要通過通孔到另一層進行，或者在同一層內(nèi)進行曲折（jog）布線。由于這兩種情況都會增加布線的復雜性和電阻，因此算法會對此類操作進行懲罰，以鼓勵更直接的布線方式。
基于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)被訪問過，以及到達這些單元格的成本和來自哪個方向。這樣可以幫助算法避免重復訪問單元格，并確保找到最便宜的路徑。

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

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

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

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

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

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

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

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

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

保持總線在一起：對于總線（一組并行信號線），全局布線會盡量將它們保持在一起，以便于后續(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都設置好相應的軌道了嗎？我們現(xiàn)在就是確定GBOX內(nèi)部之間，是怎么根據(jù)這個軌道連接的。這個內(nèi)部的Routing，我們也要考慮下面這幾個因素。

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

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

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

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

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

我們直接看兩個例子：

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

系列文章入口——

【芯片設計】SoC 101（一）：緒論

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

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

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

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

【芯片設計】復位那些小事 —— 復位消抖

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

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

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

【芯片設計】從RTL到GDS（一）：Introduction

其他文章鏈接——

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