李明 李艷 陳亮 于芳 劉忠立

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

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

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

1 VS1000 FPGA的結構

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

圖1 VS1000 FPGA結構簡圖Fig.1 VS1000 FPGA architecture

2 改進的布局延時預測方法

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

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

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

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

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

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

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

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

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

圖3 坐標差值為負時的延時預測示意圖Fig.3 Schematic diagram of timing estimation when coordinate difference is negative

3 針對高扇出電路的布局布線改進方法

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

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

線網(wǎng)終端對齊是指線網(wǎ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)中加入對齊值，結果為

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

3.2 長線連接法

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

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

4 實驗結果與分析

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

表1 測試基準電路信息Table 1 Information of test benchmark circuits

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

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

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

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

5 結語

為了克服布局與布線之間連接松散的缺點，文中針對島式FPGA芯片VS1000的架構，對經(jīng)典的VPR進行了如下改進:在布局過程采用更為準確的延時預測，同時對邏輯模塊引腳的使用做了預測;對于高扇出的線網(wǎng)采用線網(wǎng)終端對齊法，并在布線時優(yōu)先采用長線連接.實驗結果表明，這兩種改進明顯提高了布線資源利用率，降低了電路延時.文中提出的這些改進方法對島式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］.微計算機信息，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］.計算機工程與應用，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］ 隋文濤，董社勤，邊計年.島式FPGA線長驅動快速布局算法［J］.計算機輔助設計與圖形學學報，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.