基于SRAM 的FPGA 導航布局布線方法實現與應用

陳 亮，李 艷，李 明，于 芳，劉忠立

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

現場可編程門陣列(field programmable gate array，FPGA)是目前廣泛使用的可編程器件，具有開發周期短和成本低等優點. 在FPGA 設計的CAD軟件流程中，布局布線是關鍵. 布局算法確定了實現電路功能所需的各邏輯單元塊在FPGA 中的位置，其優化目標是把相連的邏輯單元塊靠近放置以最大限度地減少所需布線資源，但有時也要平衡FPGA 中所需布線密度或最大限度提高電路速度.一旦確定了電路中所有邏輯單元塊的位置，布線器即可打通合適的可編程開關以連接電路所需要的所有邏輯單元塊的輸入和輸出引腳. 絕大多數FPGA的布線器有一套避免擁擠的策略，以解決布線資源競爭問題［1］.

為測試FPGA 芯片，用于驗證與測試的碼流文件需由CAD 軟件生成. 然而現有的FPGA CAD 工具，如Xilinx ISE 和Altera Quartus II，不能滿足芯片測試的需求. 這些FPGA CAD 工具不能生成用于驗證與測試的碼流文件. 用戶難以輕易控制傳統布局布線算法的具體執行過程，導致布局布線結果具有一定的不可控性和不可預知性. 執行布局布線前，用戶不知道FPGA 芯片架構中的哪些邏輯單元塊和布線資源將會被使用. 為測試FPGA 芯片，用戶必須在布局布線執行之前指定將要使用的邏輯單元塊和布線資源，以達到測試FPGA 芯片結構中這些邏輯單元塊和布線資源的目的.

為此，本研究提出一種導航布局布線方法，以期控制布局布線結果，即在布局布線過程中，用戶可根據需求指定邏輯單元塊的位置和信號的路徑，達到預期的布局布線結果. 該方法基于VPR［2］算法，即布局采用模擬退火［3-6］算法，布線采用路徑搜索算法［7］. 將該方法應用于FPGA 芯片測試可得到較高的測試覆蓋率. 在導航布線的過程中，會產生一種部分漏端指定路徑的線網. 針對這種線網的布線，本研究提出考慮固定路徑影響的布線方法，相對直接忽略指定路徑的漏端的布線方法，該方法在迭代次數和關鍵路徑延時方面得到了優化.

1 VS1000 FPGA 結構

VS1000 是一款自主研發并已完成流片驗證的輻射加固SOI (silicon-on-insulator)工藝的FPGA芯片，其架構如圖1. FPGA 芯片架構包括邏輯片(logic tile)陣列，可編程輸入輸出單元塊 (IO block)陣列、2 個全局信號單元塊(global signal block). 邏輯片是FPGA 的基本組成單元塊，1 個邏輯片由1 個邏輯單元塊(LB)、1 個X 方向的連接盒(CBX)、1 個Y 方向的連接盒(CBY)和1 個開關盒(SB)組成. 可編程輸入輸出單元塊提供了芯片管腳和內部信號的通道. 全局信號模塊通過專用布線資源將全局信號輸送給每個邏輯單元塊.全局信號可由芯片外部管腳或內部邏輯信號提供［8］.

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

2 導航布局布線的實現

為測試VS1000 FPGA 芯片，本研究提出導航布局布線方法，用以方便FPGA 的陣列化測試，提高測試效率. 在布局布線前，用戶可指定將要使用的邏輯單元塊和布線資源，以期得到用戶預計的布局布線結果.

2.1 用戶約束文件

導航布局布線可根據用戶約束進行布局布線.其約束由用戶寫在用戶約束文件(user constraint file)中. 導航布局布線工具讀取用戶約束文件獲得約束信息，再根據約束執行布局布線. 用戶約束文件包含布局約束和布線約束兩部分.

布局約束描述邏輯單元塊的位置，即映射過程輸出的網表文件中指定的邏輯單元塊應該放置在FPGA 結構中的位置坐標(列號、行號). 這些指定的位置坐標必須合法，位置坐標不能超過FPGA結構的范圍. 同時，網表文件中被指定的邏輯單元塊的類型必須與FPGA 結構中指定位置處的邏輯單元塊類型匹配. 若用戶指定的位置坐標不合法，則導航布局布線工具會報錯，提示用戶重新指定位置坐標.

圖2 指定位置的線網描述Fig.2 Description of location-fixed net

布線約束描述線網布線要使用的布線資源，即線網的位置. 如圖2，每個指定位置的線網都是按照信號的走向，依次描述每一個經過的布線資源圖中的結點. 每個線網都是從源端出發，依次經過邏輯單元塊輸出引腳結點、互連線段結點、邏輯單元塊輸入引腳結點，最終到達漏端. 每個結點的信息包括該結點的列號、行號、類型、序號4 個部分.然而，用戶列出所有指定路徑線網上的所有結點是非常困難的. 開關盒布線規則可解決該問題，用戶只需寫出開關盒布線規則，導航布局布線工具就可根據開關盒布線規則自動選擇互連線段結點. 圖3列舉了部分開關盒布線規則的例子. 如圖3 所示，根據信號方向，若信號從左邊進入開關盒，則信號從開關盒上邊穿出(圖3a);若信號從右邊進入開關盒，則信號從開關盒左邊穿出(圖3b);若信號從上邊進入開關盒，則信號從開關盒右邊穿出(圖3c);若信號從下邊進入開關盒，則信號從開關盒右邊穿出(圖3d). 用戶可根據自己需要指定開關盒布線規則. 根據開關盒布線規則，大量的互連線段結點不用羅列在用戶約束文件中. 結點與結點間的選擇要符合FPGA 結構的約束，如源端與邏輯單元塊輸出引腳結點的選擇要符合局部布線結構，互連線段結點之間的選擇要符合開關盒結構等.

圖3 開關盒布線規則舉例Fig.3 Examples of SB route rule

2.2 三種指定路徑的線網

映射后輸出網表文件中的所有線網都需布線.一個線網只有一個源端，但漏端數量可能是一個，也可能是多個. 在用戶約束文件中，用戶可指定一個線網中一個源端到該線網的所有或部分漏端的路徑. 因此，網表中的線網可分為3 類:無指定路徑線網、全部指定路徑線網和部分指定路徑線網. 無指定路徑線網的源端到其所有漏端的路徑都是沒有被用戶約束文件指定的. 如圖4(a)，該線網有3個漏端，源端到這3 個漏端的路徑都是沒有被指定的. 這種線網由布線器來布線. 全部指定路徑線網的源端到其所有漏端的路徑都是被用戶約束文件指定的. 如圖4(b)，該線網有3 個漏端，源端到達這3 個漏端的路徑都是被指定的. 這種線網不需要由布線器來布線. 但是如果用戶需要，這種線網的時序分析還是需要執行. 部分指定路徑線網的源端到其一部分漏端的路徑是被用戶約束文件指定的，到另一部分漏端的路徑是未被指定的. 如圖4(c)，該線網有3 個漏端，源端到其中一個漏端的路徑是被指定的，到另外兩個漏端的路徑沒有被指定. 被指定的路徑不需要由布線器來布線，沒有被指定的路徑由布線器來布線.

圖4 三種指定路徑線網舉例Fig.4 Examples of three kinds of location-fixed nets

3 部分指定路徑線網的布線

在使用時序驅動算法對部分指定路徑的線網布線時，是否應忽略被指定的源端到漏端的路徑.

對一個無指定路徑線網布線的流程，如圖5，可根據漏端關鍵度的大小順序，從源端開始，依次對每個漏端進行布線. 對于部分指定路徑線網，只需對用戶約束文中未指定路徑的漏端進行布線，流程如圖6. 在遍歷該線網的所有漏端時，若該漏端路徑是被指定的，則直接跳過，遍歷下一個漏端，這是忽略線網中固定路徑漏端的方法. 但考慮總成本TotalCost 的計算方法，固定路徑上的結點布線成本勢必會影響到線網中其余漏端布線時結點的搜索，從而影響線網的布通率和關鍵路徑延時. 在從源端i 到漏端j 進行布線時，結點n 的總成本為

圖5 無指定路徑線網布線流程圖Fig.5 Flow of no location fixed net routing

其中，PathCost(n)是從當前部分布線樹(routing tree)到結點n 的總路徑成本，即

圖6 部分指定路徑線網布線方法流程圖Fig.6 Flow of partial location fixed net routing

對于無指定路徑線網，當完成一個漏端布線后，會將該路徑上的所有結點加入到布線樹中. 對下一個漏端進行布線時，計算布線樹中可作為信號分支結點的總成本，即布線樹中可作為信號分支的結點在下一個漏端布線時是可被搜索到的. 對于部分指定路徑線網，如果按照圖6 的流程進行布線，那么固定路徑上的結點沒有加入到布線樹中，在對其他漏端進行布線時，固定路徑上的可作為分支的結點將無法被搜索到，這將大大降低布通率和影響線網的延時. 如圖7 中線網中有3 個漏端sink0、sink1和sink2. 源端到漏端0 和源端到漏端1 的路徑是被用戶約束文件指定的，源端到漏端2 的路徑是需由布線器進行布線的. 如果按照圖6 的流程，在對漏端2 進行布線時，N1、N2、N3和N4這些本可以使用的結點將永遠不會被搜索到，從而影響布通率和線網的延時.

圖7 部分指定路徑線網布線資源圖Fig.7 Routing resource graph of partial location fixed net routing

基于以上原因，對圖6 流程進行修改，如圖8.在對部分指定路徑線網進行布線時，第一步就是將固定路徑上的結點加入到布線樹中，在對其他漏端進行布線時，固定路徑上的可作為分支的結點也可被搜索到. 由于在布線資源圖中，N1、N2、N3和N4擁有眾多子結點，增加一個可選結點后，源端到漏端的可選路徑數量將呈指數增加，因此大大提高了這種線網的布通率，且優化了該線網的延時. 如圖7，對漏端2 進行布線時，可作為分支結點的N1、N2、N3和N4的總路徑成本分別是

圖8 優化后的部分指定路徑線網布線方法流程圖Fig.8 Flow of optimized partial location fixed net routing

同樣可計算出這些結點的總成本，用于時序驅動布線時結點的搜索.

4 實驗結果與分析

4.1 導航布局布線的實驗結果與分析

導航布局布線方法可以生成應用于FPGA 芯片測試的碼流文件. 為測試FPGA 架構中的每個部分，本研究共寫了128 個測試實例，如表1. 這些測試實例經過綜合和映射之后，使用導航布局布線工具生成應用于驗證和測試的布局布線結果. 通過圖形用戶界面(GUI)可以看到布局布線結果. 圖9 給出了應用導航布局布線工具生成的測試長度為1 的互連線段的布局布線結果. 為了測試FPGA 架構中所有長度為1 的互連線段，所有長度為1 的互連線段必須被信號占用. 在用戶約束文件中寫入布線約束和開關盒布線規則，開關盒布線規則為:從開關盒左入，下出;上入，右出;右入，上出;下入，左出. 應用上述開關盒布線規則，FPGA 芯片中每條長度為1 的互連線段就可全部連接起來. 除此以外，導航布局布線還應用于測試FPGA 架構中其他部分，如所有輸入輸出單元塊、全局信號單元塊、邏輯單元塊和其他類型的互連線段等，都成功生成了用于測試的布局布線結果.

圖9 測試長度為1 的互連線段的布局布線結果Fig.9 Result of placement and routing for testing single-length tracks

表1 VS1000 FPGA 芯片的測試實例和測試覆蓋率Table1 Functionality test coverage of total testing cases for VS1000 FPGA chip

由表1 可知，通過使用導航布局布線工具可得到較高的測試覆蓋率. 本研究共128 個測試實例，總測試覆蓋率達85%.

4.2 優化的部分指定路徑線網布線實驗結果與分析

本研究從IWLS、itc 等基準電路中選取10 個邏輯復雜的電路，并指定這些電路網表中部分漏端的路徑，使其成為部分指定路徑線網，來測試優化后的部分指定路徑線網的布線方法. 這10 個電路的邏輯單元塊數量和部分指定路徑線網的數量如表2.

表3 比較了優化前后部分指定路徑線網布線的方法. 實驗中FPGA EDA 流程中的映射，布局布線都是在自主研發并已完成流片驗證的輻射加固SOI工藝的FPGA 芯片VS1000 的架構上進行的. 從表3可見，優化的部分指定路徑線網布線方法的迭代次數平均減少22.6%，關鍵路徑延時平均減少20.9%. 電路的邏輯越復雜，優化后的部分指定路徑線網布線方法的優化率越高. 如表4，在優化迭代次數和關鍵路徑的同時，并沒有影響布線資源利用率.

表2 測試電路Table 2 Test circuit

表3 優化前后部分指定路徑線網布線方法的對比Table 3 Comparison between un-optimized and optimized methods for partial location-fix neted routing

表4 未優化與優化的部分指定路徑線網布線方法的布線資源利用率對比Table4 Comparison of routing resource utilization rate between un-optimized and optimized methods for partial location-fixed net routing%

結 語

本研究針對FPGA 芯片開發過程中的驗證和測試提出了導航布局布線方法，適用于任何架構的島式FPGA 芯片的驗證和測試. 對自行研發的基于SOI 的輻射加固FPGA 芯片VS1000 的驗證和測試結果表明，該導航布局布線方法可獲得較高的測試覆蓋率. 所提出的針對部分漏端指定路徑的線網布線方法，比直接忽略指定路徑的布線方法，平均可減少迭代次數22.6%，關鍵路徑延時可減少20.9%，能有效提高FPGA 驗證和測試過程中布局布線的性能.

/References:

［1］Betz V. Architecture and CAD for Deep-Submicron FPGAs［M］. Toronto (Canada):Kluwer Academic Publishers，1999:22-26.

［2］Vaughn B. Architecture and CAD for Deep-Submicron FPGAs ［M］. WANG Ling-li，YANG Meng，ZHOU Xuegong，tran. Beijing:Publishing House of Electronics Industry 1999:41.(in Chinese)Betz V. 深亞微米FPGA 結構與CAD 設計［M］. 王伶俐，楊 萌，周學功，譯. 北京:電子工業出版社，2008:41.

［3］LIAO Yong-bo，LI Ping，RUAN Ai-wu，et al. A HW/SW co-verification technique for field programmable gate array(FPGA)test ［C］ // IEEE Circuits and Systems International Conference on Testing and Diagnosis (ICTD '09).Chengdu (China):IEEE Press，2009:1-4

［4］LI Ping，LIAO Yong-bo，RUAN Ai-wu，et al. Novel Approach to Test Field Programmable Gate Array Based on SoC HW/SW Co-Verification Technology ［J］. Journal of University of Electronic Science and Technology of China，2009，38(5):716-720.(in Chinese)李 平，廖永波，阮愛武，等. SoC 軟硬件協同技術的FPGA 芯片測試新方法［J］. 電子科技大學學報，2009，38(5):716-720.

［5］ZHAO Chang-hong，CHEN Jian，ZHOU Dian，et al. A VLSI floorplanning algorithm based on weight ［J］. Journal of Computer-Aided Design ＆ Computer Graphics，2006，18(7):994-998.(in Chinese)趙長虹，陳 建，周 電，等. 基于權重的超大規模集成電路布圖規劃算法［J］. 計算機輔助設計與圖形學學報，2006，18(7):994-998.

［6］SUI Wen-tao，DONG She-qin，BIAN Ji-nian. Wirelengthdriven fast placement algorithm for island style FPGAs［J］. Journal of Computer-Aided Design ＆ Computer Graphics，2009，21(9):1275-1282.(in Chinese)隋文濤，董社勤，邊計年. 島式FPGA 線長驅動快速布局算法［J］. 計算機輔助設計與圖形學學報，2009，21(9):1275-1282.

［7］JI Guo-fan，ZHAO Zhi-hao，YANG Song. ATE-based FPGA test approach ［J］. Electronic Test，2007(12):43-46.(in Chinese)吉國凡，趙智昊，楊 嵩. 基于ATE 的FPGA 測試方法［J］. 電子測試，2007(12):43-46.

［8］HAN Xiao-wei. Design and Verification of Radiation-Hardened SOI-Based FPGA:II ［D］. Beijing:Chinese Academy of Science. Institute of Semiconductors，2011.(in Chinese)韓小煒. 輻射加固SOI 工藝FPGA 的設計與驗證:II［D］. 北京:中國科學院半導體研究所，2011.