【芯片設計】從RTL到GDS（七）：布局

倒序瀏覽 · 發(fā)表于 2024-10-9 12:02:00

本篇文章將繼續(xù)討論芯片的Physical Domain，在完成Floorplanning以后，我們需要將視野放在Placement上。
接下來正式進入課程內(nèi)容：

本節(jié)課的課程大綱如下所示：

1、Introduction

我們之前就已經(jīng)完成了邏輯綜合，在邏輯綜合之后，我們有了映射在具體工藝上的網(wǎng)表即netlist。

在Floorplanning之后，大概確定了各個大的Block放在哪里，芯片大致的布局。

我們的Placement實際上就是在Floorplanning的地基之上更進一步的布局，把我們剩下的Standard Cell全部擺放好。

在開始進行Placement之前，我們先考慮一下芯片的大小問題。比如說一個1億門的芯片到底有多大？在實際的芯片設計中，small cells才真正占據(jù)面積的主導。對于大的hard macro，我們將其視為很多很多的小門。
因此通常我們將芯片的大小看成等效的門數(shù)量，并且是最簡單的二輸入與非門的大小。也就是可以簡單認為絕對面積/與非門的面積=門的數(shù)量。這里還需要搞清楚Gates和Instances兩個不同的概念。Instances是實際被Placed的東西，包括但不限于1-bit加法器，D-flip flop，稍微復雜一點的門，最基本的門等等。Instances的數(shù)量大概是Gates數(shù)量除以4到除以5這個范圍區(qū)間。

通過下圖，我們可以看到Placement的輸入輸出，以及其想達到的目標。其本質(zhì)就是在不違例，盡可能優(yōu)化的情況下，給gate找個地方放下來！聽上去很簡單，實際上很難。不好的Placement會導致有非常多的連線，連線過多會導致阻塞問題，寄生參數(shù)問題，芯片面積問題，時序問題等等。布局不好的話會讓下一步的時鐘樹綜合以及布線也非常困難。所以布局作為承上啟下的一個階段，其非常重要。

通常來說，大部分EDA工具會將Placement任務劃分為兩個階段：Global Placement這個階段的目的是快速地將設計中的所有單元分配到芯片上的各個區(qū)域或“箱子”中，目標是盡量減少不同區(qū)域之間的連接數(shù)量，同時考慮到整體的布局密度和平衡；全局布局通常不會關注每個單元的精確位置，而是關注于整體布局的框架和結構；這個過程中，主要的元器件的位置是“浮動”的，可以“平滑”地在版圖上移動；Detailed Placement在全局布局的基礎上，詳細布局的任務是為每個單元實例提供一個合法的位置；這個階段會盡量減少連線長度，優(yōu)化電路的性能，如減少信號延遲和功耗；同時，詳細布局還會嘗試確保布局后的設計不會出現(xiàn)過度的擁擠，即避免出現(xiàn)布線擁塞問題，這會影響最終的布線質(zhì)量和信號完整性。根據(jù)下圖我們可以看到一個好的Placement和一個不好的Placement的差別有多大。其互連線長度差距非常大。

為什么我們需要在Placement階段重點關注wire的長度呢？這就有點像綜合重點會關注時序，明明后續(xù)有靜態(tài)時序分析工具。布局也是類似的，其需要為后續(xù)的router服務，其一般內(nèi)部有一個簡化版的router估計工具，其目的最核心的在于沒有違反電路規(guī)則的情況下，最小化互連線的長度。這也是Placer最核心的出發(fā)點，其基于這個出發(fā)點進行布局。并且這種涉及方法學和邏輯綜合的靜態(tài)時序分析方法一樣，都是將一個復雜的電路玄學問題，轉(zhuǎn)換為有跡可循的數(shù)學優(yōu)化問題，通過合理的抽象，我們能把非常難分析的問題變成相對容易解決的數(shù)學問題。這也是很多EDA工具的核心理念。

2、Random Placement

隨機布局（Random Placement）是一種在芯片設計中進行初始布局的簡單方法。在這種方法中，設計中的各個單元（如標準單元、宏單元等）被隨機地放置在芯片的可用區(qū)域上，而不考慮它們之間的任何特定關系或連接。在此基礎上進行隨機的交換，從而最小化wire長度。

來看一個非常簡單的例子，通過這個例子我們大概了解Placement到底在做什么。假設我們有一個非常簡單的網(wǎng)格。所有的gate大小都相同，網(wǎng)格的每個格子可以放一個gate。實際的布局沒有這么簡單，但這個簡化的例子有助于我們理解布局。

在具體布線（Routing）之前，我們在布局階段就需要評估布線時的走線長度或者時序質(zhì)量的。因此我們需要有這些指標的高效估計模型（總不能更新一下布局又完全重跑一次布線吧）。對于線長這個問題，我們需要分成兩步驟進行分析：（1）首先，我們要猜這個線可能長什么樣子；（2）然后，我們要可以在我們的問題模型中，數(shù)值化地反映出這個線長。我們先假設，所有的電路中的網(wǎng)線（net）都是只有一個驅(qū)動引腳，但可以有多個被驅(qū)動的fanout引腳，當然每個引腳有其所屬的電路實例。其次有個前提，在VLSI中，走線都必須是XY兩個方向的，也就是不能像散落的繩子一樣，隨意拐彎。這里還需要說明一下，Net到底是什么，在layout中，我們把線叫做net，這些線是netlist的一部分。netlist就是映射在具體工藝上的gates+wires。我們根據(jù)這些net連接了多少個東西，稱其為“x-point net”。比如下圖中的2-point net和4-point net。

針對第一個步驟，即猜線長什么樣子。在布局中，我們會用一些布線模式去近似實際布線器的走線。如下圖所示，同樣是4-point net。其形式可以多種多樣。

常見的近似布線模式有：半周線長（half-perimeter wirelength ，HPWL)，也叫做Bouding Box(BBOX)。HPWL只關心最上下左右的邊長，主要特點是簡單、評估快、和實際布線長度誤差10%左右。其核心思想在于找一個最小的矩形框，把所有的point給包住，基于這個矩形框，我們就可以評估相應的net長度了。

我們看一下怎么通過HPWL參數(shù)估計wire length。第一個例子中總共只有兩個gate，它們的△X=2，△Y=3。則HPWL等于2+3=5。同理，在右下角這個4個gate例子中，我們找最遠的△X和△Y。則相應的HPWL為3+4=7。

有一點需要提一下，HPWL是實際Wire length的下界，也就是我們至少要按照這個長度去估計。畢竟我們根據(jù)上面的圖就可以看出來，你找不出比這個更加理想的連接方式了（只能沿著X和Y擴展，HPWL沒有走任何多余的路）。

好了，我們已經(jīng)有了基本的連線了，如何基于這個基礎去優(yōu)化呢？這就問的好了，我們先考慮一個簡單的算法，隨機的去優(yōu)化。下圖中的算法很簡單，這里就不詳細講了。簡單來說我們就是不斷的更換Gate，使得整個的L變少。

我們來看一個具體的例子，兩個Gate是怎么交換的。圖片這里不是水平或者豎直方向的其實不太合理，大家簡單理會其意思即可。

這種方法有什么缺點呢？我們可以看到其很容易陷入局部最優(yōu)解。除非使用全局遍歷的方法，但這樣開銷成本又太大，有什么好方法呢？

我們可以使用模擬退火算法（Simulated Annealing）優(yōu)化上述過程，基于模擬退火算法，不斷隨機的更換gate的位置。有關模擬退火算法的細節(jié)，大家可以去找相關資料，這里就不講了。

3、Analytic Placement基于模擬退火算法的優(yōu)化思路比較古老了，目前比較先進的方案是基于解析模型（Analytic model）進行數(shù)值求解的。因為解析模型可以：（1）很清晰地把問題建模評估與擴展；（2）可以更好地跳出局部最優(yōu)點；（3）可以充分利用數(shù)值求解工具的強大并行化計算能力，提高求解速度。

基于解析的布局方法具體思路如下所示。現(xiàn)代的布局器都是基于解析布局方法的。我們需要以數(shù)學上友好的方式寫出成本函數(shù)，然后我們可以對其求導并令其等于0，從而找到最小值。簡而言之，解析布局方法是將布局問題轉(zhuǎn)化為一個數(shù)學優(yōu)化問題，通過求解成本函數(shù)的最小值來確定電路元件的最佳位置。這種方法的關鍵在于將成本函數(shù)表達為電路元件坐標的函數(shù)，并利用數(shù)學工具（如微積分）來找到這個最小值。

由于HPWL的數(shù)學表達式是不可導的，在數(shù)學求解器里面，不可導通常是不利于求解的，因此我們需要用可導函數(shù)去近似這個真正的HPWL。比較典型的是二次（Quadratic）近似。對于兩個point的“net"，非常容易計算。

但是當point大于2呢？此時將使用clique model。這種模式下實現(xiàn)了一對一的連接。最后一點假設是，假設門電路是沒有維度的點。

此外為了補償這種模型的偏差，我們可以通過將每個新網(wǎng)絡的權重設為1/(k-1)來進行調(diào)整。

我們來看一個簡單的例子。每個gate的坐標未知，每個net（線）有具體的權重，邊緣PAD的位置固定。

可以看到x和y是沒有互相運算的。我們分開計算。

如下圖所示，我們利用導數(shù)，求得相應的局部最優(yōu)解。

我們可以得到一個很直觀的結果，使用二次線長模型進行布局時，電路元件（點）會被放置在一條直線上，這樣的布局可以最小化彈簧權重，即權重較大的連接會有較短的線長。這種方法可以有效地減少總體的線長，從而優(yōu)化電路的性能。

我們基于下面的說明，構建解析網(wǎng)絡：

直接看個例子：

上述的方法其實存在一個問題，什么問題？所有的門電路都想要放在同一個地方！這種現(xiàn)象英文叫做Gate Clustering。上述現(xiàn)象這是很自然而然能看出來的，我們?nèi)绾谓鉀Q這個問題？通過遞歸Partitioning！遞歸Partitioning是一種層次化的布局方法，它將整個電路分成多個子部分，然后對每個子部分進行單獨布局。這些子部分可以進一步劃分，直到每個子部分的大小和復雜性適合進行有效的布局。這種方法可以避免所有門電路聚集在一起的問題，并且可以在不同的層次上優(yōu)化布局，以減少總體的線長和提高電路的性能。

遞歸Partitioning思路如下所示，大家直接看圖就行。更加細節(jié)的東西需要自己搜索相關資料，這里大家搞懂基本概念就行。

我們再討論一下合法化的概念，在實際的布局中，我們需要各類實例都映射到實際板子上的離散的位置上。比如某個實例Q的XY坐標是(1.3, 5.2)，它就需要被映射/對齊到如(1，5)這些離散位置。在ASIC上，可能只有某個維度需要進行對齊，如對齊到行（Row）只需要變成（1.3,5）坐標就好了。

4、Placement in Practice之前我們討論的都是基于wire-length最小化優(yōu)化目標。布局實際上還要考慮時需優(yōu)化和阻塞最小化。以及后續(xù)的時鐘樹和功耗優(yōu)化。

我們看一下基于時間驅(qū)動的布局，其嘗試將關鍵路徑相關的Cell放的很久，從而減少相關的RC參數(shù)，其減少了，需要的充放電時間也會得到改善，可以優(yōu)化時序。這里還涉及虛擬布線的概念，大家感興趣的可以搜索相關資料。

我們看一下其前后的變化：

我們再把視角放回Congestion，中文一般叫做阻塞問題或者擁塞問題。之所以會出現(xiàn)這個問題，簡單理解就是路徑不夠用了！因為某些實例它的連線太多太密集了，如果在它旁邊擺滿其他人，就沒位置走線了。這就像一些舊城區(qū)改造，小樓太多了，中間馬路穿來穿去經(jīng)常堵車，因此通常就是拆遷，擴大樓距和路寬。

對于基于Congestion驅(qū)動的Placement，會盡可能減少wire length通道數(shù)的密度，比如下圖中的例子，其交換了A和D兩個Cell。這樣交織的線就變少了（Wire length Channel Density從3變成了2）。但是整體的長度增加了，因此這也是一個需要權衡的問題。

我們來看一些修理Congestion的方法。

我們看一下Innovus工具中，怎么進行Placement，可以看到其非常人性化。很多時候我們不需要了解細節(jié)，也可以完成工作，這就是抽象的力量。

下篇文章講時鐘樹綜合。最近同時也在看EDA相關的資料，這個系列的文章可能整體會再補充的更加詳細。

系列文章入口——

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

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

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

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

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

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

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

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

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

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

其他文章鏈接——

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