孫鐵力，郭冠男，廉程

（1.北京大學(xué)在職研究生，上海 200433；2.伊利諾伊大學(xué)香檳分校本科生，美國伊利諾伊州；3.上海汽車數(shù)據(jù)業(yè)務(wù)部，上海 200041）

0 引言

FPGA（Field-Programmable Gate Array），即現(xiàn)場可編程門陣列。FPGA的EDA技術(shù)就是以計(jì)算機(jī)為工具，設(shè)計(jì)者在EDA軟件平臺上，用硬件描述語言Verilog/VHDL完成設(shè)計(jì)文件，然后由計(jì)算機(jī)自動地完成邏輯綜合、打包、布局、布線和仿真，直至對于特定目標(biāo)芯片的適配編譯、邏輯映射和編程下載等工作。

FPGA布線是使用布線矩陣（Routing Matrix）來將單元按照線網(wǎng)的連接關(guān)系來實(shí)現(xiàn)具體的連接。FPGA布線要求詳細(xì)布線，無沖突，運(yùn)行時間滿足用戶需求，所有線網(wǎng)無時序違規(guī)，較優(yōu)的FMAX。

其中，要保證FPGA的布線無時序違規(guī)，就需要布線器和靜態(tài)時序分析（STA）工具的協(xié)同工作，每次布線迭代完成之后，STA工具給出當(dāng)前所有不滿足用戶時序約束（SDC）的點(diǎn)，再由布線器對這些點(diǎn)進(jìn)行修復(fù)。

STA工具一般會檢查建立時間（clock setup check），保持時間（clock hold check），恢復(fù)時間和去除時間（recovery and removal time check）,同一點(diǎn)可能會有多種違規(guī)。在現(xiàn)代的FPGA的EDA工具中，我們還要考慮多時鐘周期路徑（multi-cycle path）,時鐘的不確定性（clock uncertainty）和多角（multi-corner）時序分析等。布線器需要去修正時序違規(guī)的點(diǎn)，最重要的是修正兩種違規(guī)，即建立時間違規(guī)和保持時間違規(guī)，前者表示關(guān)鍵路徑的延時大于用戶的約束，后者表示關(guān)鍵路徑的延時小于用戶的約束。前者業(yè)界已經(jīng)有成熟的解決方案，本文主要討論后者的解決方案。

保持時間就是在時鐘沿鎖存到數(shù)據(jù)以后，數(shù)據(jù)需要保持的時間。如圖所示，觸發(fā)器的數(shù)據(jù)輸入端是D，時鐘輸入端是CLK。觸發(fā)器在時鐘的上升沿鎖存數(shù)據(jù)，而數(shù)據(jù)在時鐘的上升沿到來之后還需要保持一段時間才能確保觸發(fā)器能正確的鎖存數(shù)據(jù)，這個數(shù)據(jù)需要保持的時間就是保持時間。一般情況下，數(shù)據(jù)路徑的延時要大于時鐘路徑上的延時的，但是現(xiàn)代的FPGA的陣列在不斷增大，硬件很難保證時鐘樹的平衡，當(dāng)產(chǎn)生數(shù)據(jù)觸發(fā)器的時鐘和接收數(shù)據(jù)觸發(fā)器的時鐘偏斜足夠大時，保持時間的違規(guī)就會產(chǎn)生。

ASIC解決保持時間違規(guī)的主要方法是添加緩沖器（buffer insertion），但是由于結(jié)構(gòu)原因，F(xiàn)PGA解決保持時間違規(guī)的主要方法是在觸發(fā)器數(shù)據(jù)輸入端增加旁路延時單元，或者通過特殊的布線器來增加布線延時，Xilinx的Vertex2的硬件解決方案如圖1所示：

圖1 Xilinx的硬件解決方案

1 修正的A＊算法

現(xiàn)階段FPGA布線器主要采用對線網(wǎng)的每根線用A*算法單獨(dú)布線，整體使用pathfinder算法。由于A*算法屬于求最短路徑的算法，會與pathfinder算法配合求出不沖突的最短路徑，但是由于解決保持時間違規(guī)需要在存在保持時間違規(guī)的路徑上增加一定的延時，即要滿足路徑的延時位于[t1，t2]，其中，t1表示路徑要滿足保持時間需要的最小延時，t2表示路徑要滿足建立時間需要的最大延時。當(dāng)時鐘樹的布線不再發(fā)生變化時，即可消除對應(yīng)的觸發(fā)器上的保持時間違規(guī)。

本文采用修正的A*算法來完成這一目標(biāo)。A*算法是一種在圖中求解最短路徑最有效的直接搜索方法，根據(jù)圖的結(jié)構(gòu)特征、初始點(diǎn)與目標(biāo)點(diǎn)的位置信息以及路徑構(gòu)成等先驗(yàn)知識來對搜索過程加以正確引導(dǎo)，使其沿著目標(biāo)的方向逐步逼近進(jìn)行的搜索方法。代價函數(shù)可表示為：f(n)=g(n)+h(n)，其中g(shù)(n)表示初始點(diǎn)到當(dāng)前點(diǎn)的實(shí)際代價，h(n)即當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的最佳路徑的估計(jì)代價(futurecost)。A*算法的偽代碼如下所示：

在第26行中，相鄰節(jié)點(diǎn)已經(jīng)在openlist中，如圖所示，這時可分為兩種情況討論，當(dāng)前節(jié)點(diǎn)和相鄰節(jié)點(diǎn)確定的邊為前向邊（Forward edge）或者橫向邊（Cross edge）。由于FPGA的架構(gòu)原因，導(dǎo)致少數(shù)邊為無向邊，多數(shù)邊為有向邊，當(dāng)相鄰節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的祖先時為前向邊，這時添加該邊將構(gòu)成環(huán)路，是應(yīng)該避免的情況；當(dāng)相鄰節(jié)點(diǎn)不是當(dāng)前節(jié)點(diǎn)的祖先時為橫向邊，這時，從初始點(diǎn)到達(dá)相鄰節(jié)點(diǎn)的路徑變成了兩條，為了尋找最短路徑，我們選擇代價較小的路徑繼續(xù)進(jìn)行搜索。

我們尋找較長路徑時，將記錄較長路徑的信息。當(dāng)搜索完成之后，如果最終得到的路徑的代價小于t1，我們將根據(jù)較長的路徑的信息來修正搜索到的路徑，逐漸加大該路徑的代價，來達(dá)到要求的t1。如圖2所示：

圖2 搜索的結(jié)果示例

搜索的順序?yàn)?src->B，B->C，B->D，C->E，src->F，F(xiàn)->G，G->I，E->H，E->F，F(xiàn)->J，I->J，J->dest。其中，src->F->J->dest為搜索到的最短路徑，E->F和I->J為搜索到的橫向邊，通過這兩個橫向邊，我們可以恢復(fù)出三條其他的src到的dest的非最短路徑，分別為：src->B->C->E->F->J->dest，src->F->G->I->J->dest，src->B->C->E->F->G->I->J->dest，這三條路徑的代價均不小于搜索到的最短路徑，如果這三條路徑的代價位于[t1,t2]之間，那么我們就完成了搜索。

修正的A*算法是在A*算法完成搜索之后，對產(chǎn)生的橫向邊繼續(xù)進(jìn)行分析，找到由橫向邊構(gòu)造的代價在[t1,t2]之間的路徑。算法流程如圖3所示。

2 實(shí)驗(yàn)數(shù)據(jù)

我們使用標(biāo)準(zhǔn)測試集中經(jīng)過布局和布線之后依然存在HOLD問題的設(shè)計(jì)進(jìn)行進(jìn)一步的分析，實(shí)驗(yàn)通過調(diào)整A*算法的不同參數(shù)來找到合適的橫向邊來重建路徑。

圖3 算法流程

實(shí)驗(yàn)結(jié)果，如圖4所示。橫坐標(biāo)為A*算法的代價因子，取值范圍0.4～1之間。Size的含義是總共的橫向邊的數(shù)量，branch size的含義是在主要路徑上的橫向邊的數(shù)量，delay的含義是重建后的路徑將要延長的長度，這個值越大。就表明越容易修復(fù)HOLD問題。

圖4 代價因子對結(jié)果的影響

可以看出，當(dāng)代價因子的值大于0.7時，橫向邊的數(shù)量很少，路徑長度很小當(dāng)小于0.7時，橫向邊的數(shù)量按照指數(shù)增長，但是代價因子在小于0.7且大于0.4時，路徑長度無明顯增加，代價因子小于0.4時，橫向邊的數(shù)量急劇增大，但是在主要路徑上的橫向邊的數(shù)量沒有明顯變化（可以看出在代價因子為0.4時，橫向邊數(shù)量為主要路徑上的橫向邊數(shù)量的1000倍），因此沒有列出。

圖5是標(biāo)準(zhǔn)測試集中HOLD問題的設(shè)計(jì)中存在HOLD問題的設(shè)計(jì)，在代價因子設(shè)定為0.5時的橫向邊的數(shù)量，主要路徑的橫向邊的數(shù)量和重建后的路徑將要延長的長度。

圖6 設(shè)計(jì)的詳細(xì)結(jié)果

4 結(jié)語

本文提出了一種采用修正的A*算法來解決HOLD問題的思路，可以解決多數(shù)的HOLD違規(guī)的問題。我們還可以通過調(diào)整代價因子來提高主要路徑的橫向邊的數(shù)量或者減少橫向邊的總數(shù)量。

主要路徑的橫向邊的數(shù)量和橫向邊的總數(shù)量之間的關(guān)系尚不明確，需要進(jìn)一步的實(shí)驗(yàn)和理論分析。從主要路徑的橫向邊到重建后的路徑，是另外的一個較簡單的搜索問題，但是當(dāng)主要路徑的橫向邊數(shù)量較多時，需要一個復(fù)雜度較低的算法來完成。

[1]Betz V,Rose J.VPR:a New Packing,Placement and Routing Tool for FPGA Research[C].International Workshop on Field-Programmable Logic and Applications.Springer-Verlag,1997:213-222.

[2]L.McMurchie，C.Ebeling.PathFinder:A Negotiation-Based Performance-Driven Router for FPGAs.Third International ACM Symposium on Field-Programmable Gate Arrays,1995,pp.111-117.

[3]Virtex-2 FPGA User Guide，UG002：http://download.csdn.net/download/yangguanghaozi/9582746

[4]Guy G Lemieux,Stephen D.Brown.A Detailed Routing Algorithm for Allocating Wire Segments in Field-Programmable Gate Arrays.ACM/SIGDA Physical Design Workshop,1993,pp.215-226

[5]Cong J,Ding Y.Flowmap.An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table based FPGA Designs.IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems,1994,13:1-12.

[6]C.Y.Lee.An Algorithm for Path Connections and its Applications.IRE Trans.Electron.Comput.,01EC=10,1961,pp.346-365.

[7]G.Lemieux,S Brown.A Detailed Router for Allocating Wire Segments in FPGAs.ACM/SIGDA Ph)7sical Design Workshop，1993，pp.215-226.