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

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

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

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

2、Random Placement

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

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

在具體布線（Routing）之前，我們在布局階段就需要評估布線時的走線長度或者時序質(zhì)量的。因此我們需要有這些指標的高效估計模型（總不能更新一下布局又完全重跑一次布線吧）。對于線長這個問題，我們需要分成兩步驟進行分析：（1）首先，我們要猜這個線可能長什么樣子；（2）然后，我們要可以在我們的問題模型中，數(shù)值化地反映出這個線長。我們先假設(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只關(guān)心最上下左右的邊長，主要特點是簡單、評估快、和實際布線長度誤差10%左右。其核心思想在于找一個最小的矩形框，把所有的point給包住，基于這個矩形框，我們就可以評估相應(yīng)的net長度了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

直接看個例子：

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

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

我們再討論一下合法化的概念，在實際的布局中，我們需要各類實例都映射到實際板子上的離散的位置上。比如某個實例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ū)動的布局，其嘗試將關(guān)鍵路徑相關(guān)的Cell放的很久，從而減少相關(guān)的RC參數(shù)，其減少了，需要的充放電時間也會得到改善，可以優(yōu)化時序。這里還涉及虛擬布線的概念，大家感興趣的可以搜索相關(guān)資料。

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

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

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

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

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

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

系列文章入口——

【芯片設(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道助力飛升的斷言練習