李明 李艷 陳亮 于芳 劉忠立

(中國科學(xué)院微電子研究所，北京100029)

自1984年Xilinx公司推出第一款商用現(xiàn)場可編程門陣列(FPGA)產(chǎn)品以來，F(xiàn)PGA芯片便以其靈活性、投入低、周期短及風(fēng)險(xiǎn)小等特性逐步占領(lǐng)中低端電路市場.隨著半導(dǎo)體工藝的發(fā)展以及RAM/ DSP/MCU等硬核資源的嵌入，F(xiàn)PGA芯片的規(guī)模越來越大，功能越來越強(qiáng).但與專用集成電路(ASIC)相比，F(xiàn)PGA在速度、功耗、面積等方面尚有不小的差距［1］.FPGA芯片的性能除了與硬件設(shè)計(jì)有關(guān)外，與布局布線工具的質(zhì)量亦是密不可分的.傳統(tǒng)的布局器主要有3類:基于模擬退火算法的布局器［2-4］、最小割布局器［5］和解析布局器［6］.隨著軟件技術(shù)的發(fā)展，又出現(xiàn)了基于遺傳算法的布局器［7］、基于蟻群算法的布局器［8］，甚至一些基于混合算法的布局器［9］，其中基于模擬退火算法的布局器的運(yùn)行結(jié)果最佳，但運(yùn)行時(shí)間較長.布線器則大多為運(yùn)行Dijkstra算法的迷宮布線器［10］.絕大多數(shù)的布局布線工具將布局和布線分為兩個(gè)階段，它們之間的結(jié)合非常松散，致使布局布線結(jié)果不能達(dá)到最佳.如果能將布局和布線有效地結(jié)合起來，可以極大地提高FPGA性能.例如，布局兼布線器［11］將邏輯模塊與布線資源作為一個(gè)整體考慮，與Xilinx XACT 5.0布局布線器相比，延遲降低了8%～15%，不過需要數(shù)倍的運(yùn)行時(shí)間.

為了能夠在不顯著增加運(yùn)行時(shí)間的條件下提高布局布線質(zhì)量，文中針對一款自主研發(fā)并已經(jīng)完成流片的島式FPGA芯片VS1000，開發(fā)了一種基于VPR［12］的改進(jìn)的布局布線工具IVPR，并在Windows VC2008平臺上實(shí)現(xiàn)了該工具.

1 VS1000 FPGA的結(jié)構(gòu)

如圖1所示，VS1000是一款典型的島式FPGA，芯片架構(gòu)包括24×24的邏輯片陣列、208個(gè)可編程輸入輸出模塊(IOB)、2個(gè)全局信號模塊(GB).邏輯片作為FPGA的基本組成單元，包括1個(gè)邏輯模塊(LB)、1個(gè)X方向的連接模塊(CBX)、1個(gè)Y方向的連接模塊(CBY)和一個(gè)開關(guān)模塊(SB).其中，每個(gè)邏輯模塊包括2個(gè)邏輯單元.輸入輸出模塊提供芯片管腳和內(nèi)部信號的連接通道.全局信號模塊給每個(gè)邏輯單元塊提供時(shí)鐘信號.

圖1 VS1000 FPGA結(jié)構(gòu)簡圖Fig.1 VS1000 FPGA architecture

2 改進(jìn)的布局延時(shí)預(yù)測方法

在基于模擬退火算法的布局過程中，每個(gè)溫度下都會有大量的邏輯模塊交換或移動(dòng)，每次邏輯模塊的交換或移動(dòng)是否被接受，都是由成本函數(shù)差值來決定的.若成本函數(shù)差值為負(fù)，則此次交換或移動(dòng)被接受;若成本函數(shù)差值為正，則此次交換或移動(dòng)有一定幾率被接受.成本函數(shù)差值為

式中，wt為時(shí)序因子，BB_Cost為邊界框值，ΔBB_ Cost為模塊移動(dòng)前后的邊界框差值，timingCost為與延遲相關(guān)的時(shí)序值，ΔtimingCost為模塊移動(dòng)前后的延遲差值.在布局階段，由于無法確定每條線網(wǎng)所使用的互連線和引腳，故無法得出準(zhǔn)確的布局延時(shí)值，從而造成了布局和布線連接非常松散的后果.

假設(shè)邏輯模塊1與2有連接關(guān)系，將邏輯模塊1放置于CLB0(如圖2(a)所示)，對基于VPR算法的布局器來說，CLB1和CLB2與CLB0位置的XY坐標(biāo)差值都是1，因此邏輯模塊2放置于CLB1或CLB2的位置是沒有區(qū)別的，但這需要FPGA結(jié)構(gòu)滿足以下兩個(gè)條件:(1)邏輯單元的源端和漏端都有機(jī)會連接到邏輯模塊4個(gè)方向上的引腳;(2)邏輯單元的源端和漏端有充裕的布線資源可以連接到邏輯模塊4個(gè)方向上的引腳.

圖2 邏輯模塊在不同方向上的引腳對布局的影響Fig.2 Effects of pins at different sides of logic block on placement

由于芯片面積的限制，大多數(shù)島式FPGA芯片不能滿足上述兩個(gè)條件.在這些限制條件下，如果邏輯模塊1的輸出引腳是在CLB0的上方，而邏輯模塊2的輸入引腳位在 CLB1或 CLB2左側(cè)，如圖2(b)、2(c)所示，很明顯，當(dāng)將邏輯模塊2放置于CLB1時(shí)，會占用3段互連線和2個(gè)開關(guān)，而放置于CLB2時(shí)，只占用了2段互連線和1個(gè)開關(guān).因此，在布局布線中邏輯模塊引腳方向?qū)Σ季纸Y(jié)果會有顯著的影響.

針對VPR未考慮邏輯模塊引腳方向的缺點(diǎn)，文中在布局過程中加入了改進(jìn)的布局延時(shí)預(yù)測，以使布局階段能得到更為準(zhǔn)確的延時(shí)預(yù)測值，并且在計(jì)算時(shí)序值時(shí)，根據(jù)源、漏端可能使用的引腳方向采用不同的布局延時(shí)值.

要得到更為準(zhǔn)確的延時(shí)預(yù)測值，不僅要考慮XY坐標(biāo)的差值，還需要考慮邏輯模塊引腳的方向.具體實(shí)現(xiàn)方法如下:在計(jì)算延時(shí)預(yù)測值時(shí)，先建立時(shí)序圖與布線資源圖，再建立邏輯模塊1和2，用一條線網(wǎng)連接;將邏輯模塊1放置在CLB坐標(biāo)為(1，1)的位置，邏輯模塊2遍歷其它所有CLB位置，通過布線器計(jì)算線網(wǎng)延時(shí)，此延時(shí)作為布局時(shí)的延時(shí)預(yù)測.偽代碼如下:

在布局階段完成一次邏輯模塊交換或移動(dòng)后計(jì)算ΔtimingCost的偽代碼如下:

在計(jì)算延時(shí)預(yù)測值時(shí)，因?yàn)橛幸粋€(gè)邏輯模塊固定在CLB(1，1)位置，并以該模塊為線網(wǎng)的源端，所以坐標(biāo)差值全部為正值，但在實(shí)際布局過程中，坐標(biāo)差值可能為負(fù).為此，文中進(jìn)行如下處理:如圖3所示，當(dāng)源端在CLB0、漏端在CLB3時(shí)，X坐標(biāo)差值為負(fù)，引腳處于CLB3的左方，此時(shí)延時(shí)為lb_to_lb［－1］［1］［top］［left］.根據(jù)對稱關(guān)系，CLB3的左方引腳對應(yīng)于CLB1的右方引腳，因此實(shí)際延時(shí)為lb_to_lb［1］［1］［top］［right］.

圖3 坐標(biāo)差值為負(fù)時(shí)的延時(shí)預(yù)測示意圖Fig.3 Schematic diagram of timing estimation when coordinate difference is negative

3 針對高扇出電路的布局布線改進(jìn)方法

在FPGA的應(yīng)用中，高扇出是指在打包之后的網(wǎng)表信息中，一個(gè)源端連接多個(gè)(通常超過10個(gè))漏端的情況.高扇出要占用大量的布線資源，給布線過程帶來額外的壓力.在運(yùn)行大量的例子后發(fā)現(xiàn)，除個(gè)別小電路外，絕大多數(shù)電路的關(guān)鍵路徑中都包含高扇出的端點(diǎn)，也就是說高扇出對延時(shí)會有很大的影響.VPR對高扇出沒有做出特殊處理，文中針對高扇出的特點(diǎn)，提出一種線網(wǎng)終端對齊并結(jié)合長線連接的改進(jìn)方法.

3.1 線網(wǎng)終端對齊法

線網(wǎng)終端對齊是指線網(wǎng)的源端和漏端對應(yīng)的邏輯模塊處于水平或垂直方向，而寬松對齊是指在對齊方向上加減一行(或列)，文中在布局過程中加入了線網(wǎng)終端對齊［13］和線網(wǎng)終端寬松對齊.如圖4所示，線網(wǎng)A為線網(wǎng)終端水平對齊，線網(wǎng)C為線網(wǎng)終端垂直對齊，線網(wǎng)B為線網(wǎng)終端水平寬松對齊.為了更有效地利用線網(wǎng)終端對齊和使用長線連接法，文中的寬松對齊特指水平對齊方向上一行或垂直對齊方向右一列的對齊.

圖4 線網(wǎng)終端對齊示意圖Fig.4 Schematic diagram of net terminal alignment

在布局算法中，文中在成本函數(shù)(1)中加入對齊值，結(jié)果為

式中:wa為對齊因子，其值是經(jīng)過運(yùn)行多個(gè)例子后估算出來的;Alignment_Cost(vi)=∑δ(e)，δ(e)為邏輯模塊i和j之間的對齊值，

3.2 長線連接法

VPR的布線使用了路徑搜索算法［14］，為了加快布線速度，VPR還使用了波前擴(kuò)展方法［12］:當(dāng)?shù)竭_(dá)一條線網(wǎng)的漏端時(shí)，布線器將所有連接到漏端的布線資源以0成本加入到波前優(yōu)先隊(duì)列，且不清空已有的波前，然后繼續(xù)正常的擴(kuò)展，由于波前的路徑成本為0，所以布線器會圍繞它來擴(kuò)展，這樣能夠更快地找到下一個(gè)漏端，直到當(dāng)前線網(wǎng)的所有漏端均找到為止.因?yàn)椴ㄇ皵U(kuò)展方法采用逐步擴(kuò)展的方式，所以當(dāng)某條線網(wǎng)的多個(gè)終端處于對齊狀態(tài)時(shí)，布線算法仍可能采用短線逐個(gè)連接，而不是用長線連接.

針對這種情況，文中動(dòng)態(tài)評估長線連接的成本.如果一條線網(wǎng)是高扇出的，那么它要連接的下一個(gè)漏端位于線網(wǎng)終端對齊方向，此時(shí)先計(jì)算此方向上的漏端數(shù)目(該值越大，長線連接的成本越小且隨著邊界框值的增大而減小)，當(dāng)對齊方向上的漏端數(shù)目大于定值(一般大于等于4)時(shí)，長線連接的成本便小于短線連接的成本.此時(shí)，布線器在連接選擇布線資源時(shí)便可以選擇長線來連接源端和漏端，然后繼續(xù)進(jìn)行波前擴(kuò)展以連接其它漏端.

4 實(shí)驗(yàn)結(jié)果與分析

在2.93GHz Intel(R)Core(TM)處理器、500GB硬盤、Windows XP操作系統(tǒng)的實(shí)驗(yàn)室環(huán)境下，根據(jù)VS1000芯片24×24的邏輯陣列規(guī)模，從IWLS和MCNC標(biāo)準(zhǔn)測試電路中選取了11個(gè)不同規(guī)模及類型的基準(zhǔn)電路(見表1)進(jìn)行測試，比較了經(jīng)典VPR［12］、使用改進(jìn)延時(shí)預(yù)測方法的VPR(IVPR1)、使用線網(wǎng)終端對齊法的VPR(IVPR2)、使用改進(jìn)延時(shí)預(yù)測與線網(wǎng)終端對齊法的VPR(IVPR3)的布局布線質(zhì)量，結(jié)果如表2所示，其中延時(shí)改進(jìn)量和通道寬度改進(jìn)量均是相對于經(jīng)典VPR［12］的改進(jìn)百分比.測試過程中，F(xiàn)PGA CAD流程中的綜合、映射、布局布線都是針對VS1000 FPGA芯片架構(gòu).從表2可知:

表1 測試基準(zhǔn)電路信息Table 1 Information of test benchmark circuits

表2 IVPR1、IVPR2、IVPR3與經(jīng)典的VPR［12］的布局布線質(zhì)量比較Table 2 Comparison of placement and routing qualities among IVPR1，IVPR2，IVPR3 and typical VPR

1)在采用改進(jìn)的延時(shí)預(yù)測方法后，IVPR1的平均電路延時(shí)降低了11.8%，布線資源利用率提高了4.9%，平均運(yùn)行時(shí)間增加了近5%.改進(jìn)的延時(shí)預(yù)測方法對布線資源利用率的改善效果良好，這是因?yàn)樵诓季蛛A段考慮布線可能使用的引腳方向后，減少了互連線的轉(zhuǎn)彎，提高了布線資源利用率.在電路規(guī)模較小時(shí)，由于布線資源十分充裕，改進(jìn)的延時(shí)預(yù)測方法對延時(shí)的改善效果較差，但隨著電路規(guī)模的增大，改善效果也逐漸變得更好.

2)在加入線網(wǎng)終端對齊后，IVPR2的平均電路延時(shí)降低了16.9%，但布線資源利用率降低了2.9%，平均運(yùn)行時(shí)間略有下降.線網(wǎng)終端對齊對電路延時(shí)的改善效果顯著的主要原因有:(1)高扇出的特殊性，絕大多數(shù)電路在經(jīng)過布局布線階段后的關(guān)鍵路徑中都包含高扇出的端點(diǎn)，而線網(wǎng)終端對齊及長線連接能夠有效地減小高扇出線網(wǎng)的延時(shí)，因此能夠有效地改善電路延時(shí);(2)布局階段的關(guān)鍵路徑和次關(guān)鍵路徑在布線階段會優(yōu)先使用最快的互連線連接，因此布線后的關(guān)鍵路徑在布局階段是次關(guān)鍵路徑或非關(guān)鍵路徑，在布局階段，線網(wǎng)終端對齊能夠在不影響關(guān)鍵路徑的情況下有效地改善次關(guān)鍵路徑和非關(guān)鍵路徑的延時(shí).

3)使用改進(jìn)的延時(shí)預(yù)測和線網(wǎng)終端對齊后，IVPR3的平均電路延時(shí)降低了16.4%，布線資源利用率提高了1.9%，平均運(yùn)行時(shí)間增加了近5%.

5 結(jié)語

為了克服布局與布線之間連接松散的缺點(diǎn)，文中針對島式FPGA芯片VS1000的架構(gòu)，對經(jīng)典的VPR進(jìn)行了如下改進(jìn):在布局過程采用更為準(zhǔn)確的延時(shí)預(yù)測，同時(shí)對邏輯模塊引腳的使用做了預(yù)測;對于高扇出的線網(wǎng)采用線網(wǎng)終端對齊法，并在布線時(shí)優(yōu)先采用長線連接.實(shí)驗(yàn)結(jié)果表明，這兩種改進(jìn)明顯提高了布線資源利用率，降低了電路延時(shí).文中提出的這些改進(jìn)方法對島式FPGA芯片的布局布線具有一定的通用性.

［1］ Kuon Ian，Rose Jonathan.Measuring the gap between FPGAs and ASICs［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2007，26(2): 203-215.

［2］ LeeSang-Joon，RaahemifarKaamran.FPGA placement optimization methodology survey［C］∥Proceedings of Canadian Conference on Electrical and Computer Engineering.Ottawa:IEEE，2008:1981-1986.

［3］ Vorwerk Kristofer，Kennings Andrew，Greene Jonathan W.Improving simulated annealing-based FPGA placement with directed moves［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2009，28(2):179-192.

［4］ 劉戰(zhàn)，須自明，王國章.一種用于FPGA布局的模擬退火算法［J］.微計(jì)算機(jī)信息，2007，24(5):184-186.Liu Zhan，Xu Zi-ming，Wang Guo-zhang.An efficient simulate annealing algorithm for the placement of FPGA［J］.Control and Automation，2007，24(5):184-186.

［5］ Huang D J H，Kahng A B.Partitioning-based standard-cell global placement with an exact objective［C］∥Proceedings of International Symposium on Physical and Design.New York:ACM，1997:18-25.

［6］ Sigl G，Doll K，Johannes F.Analytical placement:a linear or a quafratic objective function［C］∥Proceedings of the 28th ACM/IEEE Design Automation Conference.San Francisco:IEEE，1991:427-432.

［7］ Yang M，Almaini A E A，Wang L，et al.FPGA placement using genetic algorithm with simulated annealing［C］∥Proceedings of the 6th International Conference on ASIC.Shanghai:IEEE，2005:808-811.

［8］ 趙軍，賈智平.蟻群與粒子群混合的FPGA布局算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(18):70-72.Zhao Jun，Jia Zhi-ping.Mixed ant colony and particle swarm FPGA placement algorithm［J］.Computer Engineering and Application，2009，45(18):70-72.

［9］ 隋文濤，董社勤，邊計(jì)年.島式FPGA線長驅(qū)動(dòng)快速布局算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21 (9):1275-1282.Sui Wen-tao，Dong She-qin，Bian Ji-nian.Wirelengthdriven fast placement algorithm for island style FPGAs［J］.Journal of Computer-Aided Design and Computer Graphics，2009，21(9):1275-1282.

［10］ Lee C Y.An algorithm for path connections and its applications［J］.IRE Transactions on Electronic Computers，1961，10(3):346-365.

［11］ Nag Sudip K，Rutenbar Rob A.Performance-driven simultaneous placement and routing for FPGA’s［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，1998，17(6):499-518.

［12］ Betz V，Rose J.VPR:a new packing，placement and routing tool for FPGA research［C］∥Proceedings of the 7th International Workshop on Field Programmable Logic and Applications.London:Springer，1997:213-222.

［13］ Maidee Pongstorn，Ababei Cristinel，Bazargan Kia.Timing-driven partitioning-based placement for island style FPGAs［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2005，24(3): 395-406.

［14］ McMurchie L，Ebeling C.PathFinder:a negotiation-based performance-driven router for FPGAs［C］∥Proceeding of the ACM/SIGDA Third International Symposium on Field-Programmable Gate Arrays.New York:ACM，1995: 111-117.