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

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

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

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

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

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

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

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

8、821低溫退火一、該算法的效果取決于一套退火方案, 即一系列參數(shù)的設(shè)定：布局的初始溫度、每個溫度下執(zhí)行多少次交換、選擇交換對象的范圍、如何改變溫度以及退火終止的條件。二、設(shè)定初始溫度的原則是: 一個導(dǎo)致現(xiàn)有布局方案質(zhì)量下降0.1%的交換仍有0.1%的可能被接受。由于導(dǎo)致布局質(zhì)量變差的交換被接受的概率是 所以初始溫度為：其中C是當前布局方案下目標函數(shù)的值。2022/9/1822實驗結(jié)果2022/9/1824實驗結(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)總長度為評價指標, 對于大多數(shù)例子, 本文提出的算法在布局質(zhì)量上與VPR相仿, 而與此同時其所耗費的時間相較于VPR而言大大減少. 當電路規(guī)模特別小時, 本文提出的算法在速度上的優(yōu)勢并不