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

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

Quadratic布局算法力模型的建立和一種均勻展開(kāi)的方法

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

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

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

布局；力模型；展開(kāi)

1 引言

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

2 Quadratic算法模型的建立

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

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

圖2 邊長(zhǎng)等效圖

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

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

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

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

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

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

圖5 均勻展開(kāi)方法示意圖

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

圖6 加力模型示意圖

4 結(jié)果與討論

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

圖7 初始解效果圖

圖8 第30次迭代展開(kāi)效果圖

圖9 第50次迭代展開(kāi)效果圖

圖10 第80次迭代展開(kāi)效果圖

圖11 第100次迭代展開(kāi)效果圖

圖12 第150次迭代展開(kāi)效果圖

圖13 第200次迭代展開(kāi)效果圖

圖14 第300次迭代展開(kāi)效果圖

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

表1 布局測(cè)試對(duì)比表

5 結(jié)論

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

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

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

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

[4]王凱.FPGA布局算法研究與設(shè)計(jì)[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—），男，江蘇無(wú)錫人，碩士學(xué)歷，軟件工程師，現(xiàn)從事EDA軟件領(lǐng)域工作。

2017-3-29