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

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

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

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

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

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

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

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

2 導(dǎo)航布局布線的實(shí)現(xiàn)

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

2.1 用戶約束文件

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

布局約束描述邏輯單元塊的位置，即映射過程輸出的網(wǎng)表文件中指定的邏輯單元塊應(yīng)該放置在FPGA 結(jié)構(gòu)中的位置坐標(biāo)(列號、行號). 這些指定的位置坐標(biāo)必須合法，位置坐標(biāo)不能超過FPGA結(jié)構(gòu)的范圍. 同時(shí)，網(wǎng)表文件中被指定的邏輯單元塊的類型必須與FPGA 結(jié)構(gòu)中指定位置處的邏輯單元塊類型匹配. 若用戶指定的位置坐標(biāo)不合法，則導(dǎo)航布局布線工具會(huì)報(bào)錯(cuò)，提示用戶重新指定位置坐標(biāo).

圖2 指定位置的線網(wǎng)描述Fig.2 Description of location-fixed net

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

圖3 開關(guān)盒布線規(guī)則舉例Fig.3 Examples of SB route rule

2.2 三種指定路徑的線網(wǎng)

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

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

3 部分指定路徑線網(wǎng)的布線

在使用時(shí)序驅(qū)動(dòng)算法對部分指定路徑的線網(wǎng)布線時(shí)，是否應(yīng)忽略被指定的源端到漏端的路徑.

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

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

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

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

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

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

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

圖8 優(yōu)化后的部分指定路徑線網(wǎng)布線方法流程圖Fig.8 Flow of optimized partial location fixed net routing

同樣可計(jì)算出這些結(jié)點(diǎn)的總成本，用于時(shí)序驅(qū)動(dòng)布線時(shí)結(jié)點(diǎn)的搜索.

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

4.1 導(dǎo)航布局布線的實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4.2 優(yōu)化的部分指定路徑線網(wǎng)布線實(shí)驗(yàn)結(jié)果與分析

本研究從IWLS、itc 等基準(zhǔn)電路中選取10 個(gè)邏輯復(fù)雜的電路，并指定這些電路網(wǎng)表中部分漏端的路徑，使其成為部分指定路徑線網(wǎng)，來測試優(yōu)化后的部分指定路徑線網(wǎng)的布線方法. 這10 個(gè)電路的邏輯單元塊數(shù)量和部分指定路徑線網(wǎng)的數(shù)量如表2.

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

表2 測試電路Table 2 Test circuit

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

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

結(jié) 語

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

/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 結(jié)構(gòu)與CAD 設(shè)計(jì)［M］. 王伶俐，楊 萌，周學(xué)功，譯. 北京:電子工業(yè)出版社，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 軟硬件協(xié)同技術(shù)的FPGA 芯片測試新方法［J］. 電子科技大學(xué)學(xué)報(bào)，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)趙長虹，陳 建，周 電，等. 基于權(quán)重的超大規(guī)模集成電路布圖規(guī)劃算法［J］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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)隋文濤，董社勤，邊計(jì)年. 島式FPGA 線長驅(qū)動(dòng)快速布局算法［J］. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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 的設(shè)計(jì)與驗(yàn)證:II［D］. 北京:中國科學(xué)院半導(dǎo)體研究所，2011.