FPGA布線的保持時間違規的解決方法

孫鐵力，郭冠男，廉程

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

0 引言

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

FPGA布線是使用布線矩陣（Routing Matrix）來將單元按照線網的連接關系來實現具體的連接。FPGA布線要求詳細布線，無沖突，運行時間滿足用戶需求，所有線網無時序違規，較優的FMAX。

其中，要保證FPGA的布線無時序違規，就需要布線器和靜態時序分析（STA）工具的協同工作，每次布線迭代完成之后，STA工具給出當前所有不滿足用戶時序約束（SDC）的點，再由布線器對這些點進行修復。

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

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

ASIC解決保持時間違規的主要方法是添加緩沖器（buffer insertion），但是由于結構原因，FPGA解決保持時間違規的主要方法是在觸發器數據輸入端增加旁路延時單元，或者通過特殊的布線器來增加布線延時，Xilinx的Vertex2的硬件解決方案如圖1所示：

圖1 Xilinx的硬件解決方案

1 修正的A＊算法

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

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

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

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

圖2 搜索的結果示例

搜索的順序為 src->B，B->C，B->D，C->E，src->F，F->G，G->I，E->H，E->F，F->J，I->J，J->dest。其中，src->F->J->dest為搜索到的最短路徑，E->F和I->J為搜索到的橫向邊，通過這兩個橫向邊，我們可以恢復出三條其他的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*算法完成搜索之后，對產生的橫向邊繼續進行分析，找到由橫向邊構造的代價在[t1,t2]之間的路徑。算法流程如圖3所示。

2 實驗數據

我們使用標準測試集中經過布局和布線之后依然存在HOLD問題的設計進行進一步的分析，實驗通過調整A*算法的不同參數來找到合適的橫向邊來重建路徑。

圖3 算法流程

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

圖4 代價因子對結果的影響

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

圖5是標準測試集中HOLD問題的設計中存在HOLD問題的設計，在代價因子設定為0.5時的橫向邊的數量，主要路徑的橫向邊的數量和重建后的路徑將要延長的長度。

圖6 設計的詳細結果

4 結語

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

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

[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.