Quadratic布局算法力模型的建立和一種均勻展開的方法

虞健，董志丹，惠鋒，王新晨，胡凱

（1.無錫中微億芯有限公司，江蘇無錫214072；2.中國電子科技集團(tuán)公司第五十八研究所，江蘇無錫214072）

Quadratic布局算法力模型的建立和一種均勻展開的方法

虞健1，董志丹1，惠鋒1，王新晨2，胡凱2

（1.無錫中微億芯有限公司，江蘇無錫214072；2.中國電子科技集團(tuán)公司第五十八研究所，江蘇無錫214072）

布局是FPGA軟件設(shè)計中一個基本而且非常重要的環(huán)節(jié)。隨著FPGA規(guī)模的不斷擴(kuò)大，在大規(guī)模、復(fù)雜的設(shè)計約束條件下，花費較少時間獲得高質(zhì)量的相關(guān)邏輯單元物理位置是布局算法的關(guān)鍵問題。在二次線性規(guī)劃布局算法的基礎(chǔ)上，以線長為優(yōu)化目標(biāo)，介紹了一種力模型的建立理論和在力模型基礎(chǔ)上的一種均勻展開方法。

布局；力模型；展開

1 引言

布局是指在既定的所有約束條件下，以一種或者幾種參數(shù)（線長、時序、功耗、擁擠度）組合作為優(yōu)化目標(biāo)，確定所有布局網(wǎng)表中邏輯單元的物理位置。一般可以把布局劃分為全局布局和詳細(xì)布局兩個部分。全局布局主要從整個全局網(wǎng)表的角度出發(fā)，一般可以大體確定邏輯單元位置。全局布局的結(jié)果一般可以允許存在一定的不合法條件。詳細(xì)布局主要做布局結(jié)果合法化和局部位置調(diào)整的工作。目前應(yīng)用比較廣泛的全局布局算法有劃分算法、模擬退火算法、二次線性規(guī)劃算法等，這幾種算法各有優(yōu)缺點，很多情況下需要幾類算法相互配合形成最終的全局布局結(jié)果。本文主要以二次線性規(guī)劃算法為基礎(chǔ)，以線長作為優(yōu)化目標(biāo)參數(shù)，介紹全局布局算法中一種力模型的建立和在力模型下的一種均勻展開方式[2，4]。

2 Quadratic算法模型的建立

在布局網(wǎng)表中，可以把所有的布局邏輯單元看作節(jié)點，把所有節(jié)點之間的信號關(guān)系建立成點到點的邊的關(guān)系。如圖1所示，網(wǎng)表中有A、B、C、D、E 5個節(jié)點，信號1從節(jié)點A輸出，到達(dá)節(jié)點B、C、D、E上的4個目的端口。在建模時將信號1轉(zhuǎn)換成圖中邊1、邊2、邊3、邊4，形成點→邊→點模型。這樣，以圖1為例，以線長作為約束條件布局的話，目標(biāo)信號1從源端A到目的端B、C、D、E的線長最短可以等效看作為目標(biāo)邊1、邊2、邊3、邊4的邊長總和最短。那么對整個網(wǎng)表而言，布局優(yōu)化目標(biāo)就是使得網(wǎng)表中所有邊的長度總和最小[3，5]。

圖1 網(wǎng)表轉(zhuǎn)換圖

圖2 邊長等效圖

對目標(biāo)函數(shù)分別在xc、xd上求偏導(dǎo)數(shù)可得：

圖3 布局網(wǎng)表示意圖

還是以圖3所示網(wǎng)表為例，求解可知節(jié)點C的X坐標(biāo)為16，D的X坐標(biāo)為34，那么以C節(jié)點來看，固定點A、B對C在X方向上可以認(rèn)為產(chǎn)生一個向左的拉力。可動點D對C在X方向上可以認(rèn)為產(chǎn)生一個向右的拉力，大小為：fright=Wcd(xd-xc)=1×(34-16)=18。由此可知X方向上，點C處于一個力平衡狀態(tài)，同理可以得出D也處于一個力平衡狀態(tài)。那么以力模型建立網(wǎng)表結(jié)構(gòu)以后，在布局改變可動點位置時，只需要根據(jù)力平衡模型，對目標(biāo)節(jié)點加上一個固定的力就可以達(dá)到目的。

3 根據(jù)力模型的一種均勻展開方法

由于我們根據(jù)二次函數(shù)偏導(dǎo)數(shù)求極值的方法求得的邏輯單元位置會存在很大程度上的單元重疊，而布局合法的前提條件是邏輯單元之間不能存在重疊。因此我們需要對求解出來的結(jié)果進(jìn)行展開，使得重疊不斷降低。

圖4 初始節(jié)點分布圖

圖5 均勻展開方法示意圖

其中min代表整行方格的左邊邊界的x坐標(biāo)，max代表整行方格的右邊邊界x坐標(biāo)，L1代表切割線左邊的方格長度總和，Lr代表切割線右邊的方格長度總和，xori代表節(jié)點原來的x坐標(biāo)值，xnew代表需要求的節(jié)點新坐標(biāo)。通過上述等式，可以求得節(jié)點的目標(biāo)位置，如果以向右方向代表正方向，那么可以得出節(jié)點需要向右移動的距離xnew-xori。

圖6 加力模型示意圖

4 結(jié)果與討論

通過在實際應(yīng)用中使用上文論述的均勻展開方法，可以在較好地保持模塊間相對關(guān)系的基礎(chǔ)上均勻快速地對布局重疊進(jìn)行展開。圖7、圖8、圖9、圖10、圖11、圖12、圖13、圖14所示為一個實際設(shè)計用例在布局流程中迭代展開過程中的布局效果，當(dāng)?shù)?00次以后，重疊部分已經(jīng)完全展開。

圖7 初始解效果圖

圖8 第30次迭代展開效果圖

圖9 第50次迭代展開效果圖

圖10 第80次迭代展開效果圖

圖11 第100次迭代展開效果圖

圖12 第150次迭代展開效果圖

圖13 第200次迭代展開效果圖

圖14 第300次迭代展開效果圖

通過實際應(yīng)用測試，本文所論述的Quadratic算法結(jié)合均勻展開方式作為布局算法流程，也取得了比較好的結(jié)果。如表1所示，在測試設(shè)備xc5vlx330ff1760的條件下，以線長為布局優(yōu)化目標(biāo)，測試下列17個用例，上文論述的Quadratic結(jié)合均勻展開布局方法比傳統(tǒng)模擬退火布局方法平均線長可以降低6.72%。

表1 布局測試對比表

5 結(jié)論

本文主要論述了Quadratic算法力模型的建立和基于該模型的一種均勻展開的方法。該模型和方法應(yīng)用于自主FPGA設(shè)計工具軟件的布局模塊中。在軟件的實際測試應(yīng)用中，該模型和方法可以快速有效地得到較優(yōu)的布局結(jié)果，從而可以為后續(xù)軟件步驟提供較好的基礎(chǔ)。

[1]虞健.FPGA布局算法應(yīng)用研究[D].武漢：武漢理工大學(xué)，2011.

[2]蔣中華.超大規(guī)模集成電路布圖/布局算法及熱模型研究[D].武漢：武漢理工大學(xué)，2008.

[3]楊維嘉.布局問題求解算法與策略的研究[D].天津：天津大學(xué)，2005.

[4]王凱.FPGA布局算法研究與設(shè)計[D].武漢：武漢理工大學(xué)，2010.

[5]Myung Chul Kim,Dong Jin Lee,Igor L Markov.SimPL:An Effective Placement Algorithm[D].University of Michigan, 2005.

[6]黃鋼.VLSI布圖規(guī)劃和布局算法[D].北京：清華大學(xué)，1999.

Force Mode Setup and a Balance Expansion Method Based on Quadratic

YU Jian1,DONG Zhidan1,HUI Feng1,WANG Xinchen2,HU Kai2
（1.East Technologies,Inc.,Wuxi 214072,China; 2.China Electronics Technology Group Corporation No.58 Research Institute,Wuxi 214072,China）

Placement is a key step in designing FPGA software.As the logic resources surge,obtaining a good placement result under the complicated design constraints is becoming significant.Based on quadratic algorithm,the article regards HPWL as the optimize target and introduces a force module setup and a force-module-based expansion method.

placement;force module;expansion

TN402

A

1681-1070（2017）07-0031-05

虞?。?988—），男，江蘇無錫人，碩士學(xué)歷，軟件工程師，現(xiàn)從事EDA軟件領(lǐng)域工作。

2017-3-29