【芯片設(shè)計(jì)】從RTL到GDS（七）：布局

倒序?yàn)g覽 · 發(fā)表于 2024-10-9 12:02:00

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

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

1、Introduction

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

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

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

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

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

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

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

2、Random Placement

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

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

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

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

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

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

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

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

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

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

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

3、Analytic Placement基于模擬退火算法的優(yōu)化思路比較古老了，目前比較先進(jìn)的方案是基于解析模型（Analytic model）進(jìn)行數(shù)值求解的。因?yàn)榻馕瞿Ｐ涂梢裕海?）很清晰地把問題建模評估與擴(kuò)展；（2）可以更好地跳出局部最優(yōu)點(diǎn)；（3）可以充分利用數(shù)值求解工具的強(qiáng)大并行化計(jì)算能力，提高求解速度。

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

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

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

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

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

可以看到x和y是沒有互相運(yùn)算的。我們分開計(jì)算。

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

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

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

直接看個(gè)例子：

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

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

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

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

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

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

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

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

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

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

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

系列文章入口——

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

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

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

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

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

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

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

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

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

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

其他文章鏈接——

【芯片驗(yàn)證】sva_assertion: 15道助力飛升的斷言練習(xí)