一種新的快速FPGA布局算法課件

1、論 文 報(bào) 告一種新的快速FPGA布局算法報(bào)告人：陳凡 導(dǎo) 師：梁華國 教授2022/9/18 研究背景1 模擬退火算法2 快速FPGA布局算法3總結(jié)與展望 4TSV數(shù)目敏感的三維電路劃分2022/9/182VLSI設(shè)計(jì)流程（回顧）封裝和測試設(shè)計(jì)驗(yàn)證制造物理設(shè)計(jì)電路設(shè)計(jì)功能設(shè)計(jì)邏輯設(shè)計(jì)系統(tǒng)規(guī)范說明圖1-1 VLSI設(shè)計(jì)流程詳細(xì)布線布圖規(guī)劃和布局總體布線物理設(shè)計(jì)劃分芯片制造電路設(shè)計(jì)圖1-2 物理設(shè)計(jì)過程2022/9/183研究背景1 什么是布局問題？2 集成電路的布局問題怎樣描述？2022/9/184布局就是把元件或模塊安置在芯片或印制電路板的適當(dāng)位置上，并使其滿足一定的目標(biāo)要求。布局階段的輸入

2、是一組模塊、模塊上的引線段信息和網(wǎng)表。通常所說的“布局問題”是指待安置的模塊均是硬模塊。當(dāng)模塊中包含有軟模塊時(shí)，此時(shí)的布局問題稱為布圖規(guī)劃（Floorplanning）問題。布局問題2022/9/185集成電路的布局問題描述為：設(shè)B1，B2，.Bn是需要放置在芯片上的單元，每一個(gè)Bi(1in)對(duì)應(yīng)的高度和寬度分別為Hi和Wi。N=N1,N2,.,Nm表示連接不同單元的線網(wǎng)的集合，Q=Q1,Q2,.,Qk表示單元間用于布線的空區(qū)域，Li(1im)表示估計(jì)的線網(wǎng)Ni的長度。布局問題就是為每個(gè)單元尋求一個(gè)矩形區(qū)域R=(R1,R2,.,Rn)使其滿足下列條件：每個(gè)單元都能放置與它相對(duì)應(yīng)的矩形區(qū)域，也就

3、是說，Ri的高度和寬度分別為Hi和Wi任意兩個(gè)矩形不重疊。即布局是可布的。即 所有 和 面積之和最小。所有線網(wǎng)總線長最小，即 最小。2022/9/187宏模塊的意義及作用隨著電路規(guī)模的增大，F(xiàn)PGA規(guī)劃(FPGAFloorplanning)問題 被引入到FPGA宏模塊布局里。 首先，對(duì)于一些有特殊功能的宏模塊，如加法器、乘法器等宏模塊單元，由于對(duì)時(shí)序有特定要求，故可由用戶指定宏模塊，在布局時(shí)不將其打散而作為硬軟模塊進(jìn)行操作；另外，隨著電路規(guī)模的增大，電路單元越來越多，直接對(duì)大量的邏輯單元等較小單元進(jìn)行布局布線非常耗時(shí)，在這種情況下，將單元以宏模塊的方式進(jìn)行布局有助于節(jié)省大量時(shí)間。2022/9/

4、188模擬退火算法闡述模擬退火模仿逐漸冷卻熔化金屬以制造高質(zhì)量金屬材料的退火過程。首次將模擬退火算法用在布局中的是Jepsen和Gelatt?；谀M退火算法的布局器的偽代碼2022/9/1810 研究背景1 模擬退火算法2 快速FPGA布局算法3總結(jié)與展望 4一種快速FPGA布局算法2022/9/1811摘要在模擬退火算法的基礎(chǔ)上,提出了一種快速FPGA布局算法.該算法先用解析模型快速確定所有宏模塊及單個(gè)邏輯模塊的“理想”位置,然后通過局部擴(kuò)散消除模塊之間的重疊, 得到一個(gè)較好的初始布局方案,最后再用低溫的模擬退火進(jìn)一步優(yōu)化, 確定各模塊的最終位置.實(shí)驗(yàn)數(shù)據(jù)表明, 以目前在學(xué)術(shù)界普遍采用的平

5、方線網(wǎng)總長度為目標(biāo)函數(shù),與經(jīng)典的VPR算法相比,新算法大大降低了布局所耗費(fèi)的時(shí)間,而不影響最終布局方案的質(zhì)量.關(guān)鍵詞: 快速布局; 二次規(guī)劃法; 局部擴(kuò)散; 模擬退火2022/9/1812新的布局算法 2022/9/1814算法偽代碼2022/9/18152種轉(zhuǎn)換方法二次規(guī)劃的目標(biāo)函數(shù)為：2022/9/1817初始布局（續(xù)）(1)式中的x、y是電路中各模塊在芯片上的位置坐標(biāo)。Wij 是連接第i個(gè)節(jié)點(diǎn)(xi,yi)和第j個(gè)節(jié)點(diǎn)(xj,yj)邊的權(quán)重。(2)將等號(hào)右邊展開可以發(fā)現(xiàn)F(x,y)表示的是所有模塊間的線網(wǎng)長度的平方和. 由于平方線網(wǎng)長度和真正的線網(wǎng)總長度是正相關(guān)的，而且便于計(jì)算，因此被學(xué)

6、術(shù)界普遍采用作為布局優(yōu)化的目標(biāo)。(1)式可以用矩陣的形式改寫為:其中x、y分別是所有節(jié)點(diǎn)的橫、縱坐標(biāo)組成的向量, Q是一個(gè)對(duì)稱矩陣, dx 和dy 來自于固定的輸入輸出節(jié)點(diǎn), c是一個(gè)常量。由于(2) 式是一個(gè)二次的函數(shù), 因此該問題是二次規(guī)劃問題, 屬于非線性規(guī)劃的一種. 當(dāng) 時(shí), F(x,y)取最小值, 即需要滿足2022/9/1818調(diào)整初始布局方案1 在FPGA中只有特定的位置才可以放置邏輯模塊,且一個(gè)位置只能容納一個(gè)模塊。2 由于在解方程組時(shí)并沒有考慮這些限制條件, 所以求得的模塊坐標(biāo)可能不在基本位置上, 或者多個(gè)模塊占據(jù)了同一個(gè)基本位置而導(dǎo)致重疊。這里提出一種啟發(fā)式(heurist

7、ic)的局部擴(kuò)散算法來調(diào)整初始布局方案。2022/9/1819調(diào)整初始布局方案(續(xù))2022/9/1820調(diào)整初始布局方案(續(xù))1 決定邏輯模塊的位置時(shí), 首先將其二維坐標(biāo)設(shè)定為二次規(guī)劃得到的果，如果是小數(shù)則必須先取整。對(duì)于宏模塊則將坐標(biāo)賦給處于其幾何中心的基本位置。2 當(dāng)宏模塊的長度或?qū)挾炔皇桥紨?shù)時(shí), 其幾何中心沒有基本位置, 這種情況需要在離中心最近的基本位置中取二維坐標(biāo)值最大者作為中心。然后檢查各模塊的位置是否“合法”具體來說，不“合法”的情況有3種:1，該模塊的坐標(biāo)在整個(gè)芯片區(qū)域之外；2，該模塊的坐標(biāo)所在位置的邏輯資源類型與該模塊的類型不符；3，該位置已放置了其他模塊。2022/9/1

8、821低溫退火一、該算法的效果取決于一套退火方案, 即一系列參數(shù)的設(shè)定：布局的初始溫度、每個(gè)溫度下執(zhí)行多少次交換、選擇交換對(duì)象的范圍、如何改變溫度以及退火終止的條件。二、設(shè)定初始溫度的原則是: 一個(gè)導(dǎo)致現(xiàn)有布局方案質(zhì)量下降0.1%的交換仍有0.1%的可能被接受。由于導(dǎo)致布局質(zhì)量變差的交換被接受的概率是 所以初始溫度為：其中C是當(dāng)前布局方案下目標(biāo)函數(shù)的值。2022/9/1822實(shí)驗(yàn)結(jié)果2022/9/1824實(shí)驗(yàn)結(jié)果(續(xù))2022/9/1825 研究背景1 模擬退火算法2 快速FPGA布局算法3總結(jié)與展望 4TSV數(shù)目敏感的三維電路劃分2022/9/1827總結(jié)與展望1）從以上數(shù)據(jù)可以發(fā)現(xiàn), 以學(xué)術(shù)界普遍采用的平方線網(wǎng)總長度為評(píng)價(jià)指標(biāo), 對(duì)于大多數(shù)例子, 本文提出的算法在布局質(zhì)量上與VPR相仿, 而與此同時(shí)其所耗費(fèi)的時(shí)間相較于VPR而言大大減少. 當(dāng)電路規(guī)模特別小時(shí), 本文提出的算法在速度上的優(yōu)勢并不