冷 明，孫凌宇，郭 晨

井岡山大學(xué) 計(jì)算機(jī)科學(xué)系，江西 吉安343009

隨著超大規(guī)模集成電路（Very Large Scale Integration Circuit，VLSI）的制造工藝從深亞微米工藝時(shí)代進(jìn)入納米工藝時(shí)代，導(dǎo)致現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）的噪聲容限日益減少[1]，對(duì)高能粒子輻射和噪聲干擾愈發(fā)敏感，軟錯(cuò)誤率（Soft Error Rate，SER）呈指數(shù)增長[2]。XDL（Xilinx Design Language）[3]是Xilinx公司提供的一種描述FPGA設(shè)計(jì)內(nèi)部結(jié)構(gòu)信息的特征化物理設(shè)計(jì)語言，使用巴科斯范式（Backus-Naur Form，BNF）描述FPGA 實(shí)現(xiàn)特定功能硬件設(shè)計(jì)的網(wǎng)表級(jí)電路，其中的邏輯資源配置信息和布線資源互聯(lián)信息，可用于準(zhǔn)確分析SRAΜ（Static Random Access Μemory）型FPGA 器件的單粒子軟錯(cuò)誤敏感性，提升容錯(cuò)可靠性的計(jì)算精確度。本文基于SRAΜ型FPGA 器件的單粒子軟錯(cuò)誤傳播機(jī)理[4]，構(gòu)建XDL 網(wǎng)表級(jí)電路的信號(hào)傳播模型“有向超圖”，進(jìn)而提出了基于有向超圖的XDL網(wǎng)表的前向電路圖生成算法。相比基于功能模塊間近似耦合關(guān)系的單粒子軟錯(cuò)誤傳播特性計(jì)算方法[5]，本文提出的XDL電路網(wǎng)表到前向電路圖生成算法，精細(xì)刻畫了信號(hào)的前向拓?fù)潢P(guān)系，反映了單粒子軟錯(cuò)誤在SRAΜ型FPGA器件中的傳播特性，為計(jì)算軟錯(cuò)誤率提供了必要的傳播模型。

本文采用有向超圖構(gòu)建網(wǎng)表級(jí)電路的信號(hào)傳播模型：電路單元的有效管腳表示為有向超圖中的結(jié)點(diǎn)，電路管腳間的外部連線、電路管腳內(nèi)的電路邏輯功能表示為超圖中的有向超邊。本文闡述了XDL網(wǎng)表的前向電路圖的生成算法步驟：首先，遍歷電路網(wǎng)表的Inst 電路單元，抽取XDL 電路網(wǎng)表的邏輯配置信息以生成超圖結(jié)點(diǎn)和有向超邊；其次，遍歷電路網(wǎng)表的Net電路信號(hào)，抽取XDL 電路網(wǎng)表的互聯(lián)配置信息以生成有向超邊；進(jìn)而，遍歷有向超圖的每個(gè)超圖結(jié)點(diǎn)，生成每個(gè)超圖結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)列表，并通過遞歸遍歷直接前驅(qū)結(jié)點(diǎn)列表中的結(jié)點(diǎn)，生成超圖結(jié)點(diǎn)的間接前驅(qū)結(jié)點(diǎn)列表；最后，在Windows 平臺(tái)下基于RapidSmith 開源軟件[6]和Java 語言設(shè)計(jì)實(shí)現(xiàn)了前向電路圖生成算法，選用基于Virtex-4 型號(hào)FPGA 測試用例的XDL 網(wǎng)表，生成相應(yīng)的前向電路圖以驗(yàn)證前向電路圖生成算法的有效性。

1 XDL網(wǎng)表級(jí)電路描述文件的解析

每個(gè)XDL 網(wǎng)表級(jí)電路描述文件對(duì)應(yīng)一個(gè)FPGA 設(shè)計(jì)的硬件實(shí)現(xiàn)，使用BNF范式詳細(xì)地描述了整個(gè)FPGA設(shè)計(jì)的基本信息以及布局布線信息，包含design、module、instance 和net 等語句，提供了FPGA 設(shè)計(jì)在芯片微觀級(jí)別（網(wǎng)表級(jí)）邏輯資源的配置信息和布線資源的互聯(lián)信息。表1 給出了XDL 網(wǎng)表級(jí)電路描述語言的EBNF 表達(dá)式語法規(guī)則。

定義1 design 語句采用“design”關(guān)鍵字表示，其生產(chǎn) 式 規(guī) 則

定義2 module 語句采用“module”關(guān)鍵字表示，其生產(chǎn)式規(guī)則

定義3 instance語句采用“inst”關(guān)鍵字表示，其生產(chǎn)式規(guī)則

定義4 net語句采用“net”關(guān)鍵字表示，其生產(chǎn)式規(guī)則

2 基于有向超圖的XDL 網(wǎng)表的前向電路圖生成算法

根據(jù)定義1～定義5，基于有向超圖的XDL網(wǎng)表的前向電路圖生成算法的主要思想是：（1）電路單元的有效管腳表示為有向超圖中的結(jié)點(diǎn)。（2）電路管腳間的外部連線、電路管腳內(nèi)的電路邏輯功能，表示為超圖中的有向超邊。（3）每條有向超邊可以連接兩個(gè)以上的結(jié)點(diǎn)，對(duì)應(yīng)于電路單元間的連線可以連接兩個(gè)以上的有效管腳，或電路邏輯功能可以連接多輸入管腳。（4）在每條有向超邊中，唯一的輸出管腳對(duì)應(yīng)于有向超邊的尾端結(jié)點(diǎn)，其余輸入管腳對(duì)應(yīng)于有向超邊源端子集結(jié)點(diǎn)，且有向超邊的源端子集的每個(gè)結(jié)點(diǎn)屬于該尾端結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。（5）通過遞歸遍歷直接前驅(qū)結(jié)點(diǎn)列表中的結(jié)點(diǎn)，生成該超圖結(jié)點(diǎn)的間接前驅(qū)結(jié)點(diǎn)列表。只有超圖結(jié)點(diǎn)x的間接前驅(qū)結(jié)點(diǎn)列表中未包含前驅(qū)結(jié)點(diǎn)z，才會(huì)調(diào)用遞歸遍歷生成前驅(qū)結(jié)點(diǎn)z 的間接前驅(qū)結(jié)點(diǎn)列表，巧妙地避免XDL電路網(wǎng)表的信號(hào)前向拓?fù)潢P(guān)系中存在有向環(huán)導(dǎo)致遞歸循環(huán)。

表1 XDL網(wǎng)表級(jí)電路描述語言的EBNF表達(dá)式

2.1 算法分析

基于有向超圖的XDL網(wǎng)表的前向電路圖生成算法偽代碼如圖1所示，其詳細(xì)步驟如下：

第3行到第11行：遍歷電路網(wǎng)表的Inst電路單元模塊信息，依次處理每個(gè)Inst電路單元。抽取XDL電路網(wǎng)表的邏輯配置信息，獲取有效管腳信息列表，為每個(gè)有效管腳生成一個(gè)超圖結(jié)點(diǎn)；根據(jù)Inst電路單元的不同類型，配合CFG配置信息獲取的底層電路配置狀態(tài)，解析每個(gè)輸出管腳的邏輯功能表達(dá)式，為每個(gè)輸出管腳生成一條有向超邊，且該有向超邊的尾端結(jié)點(diǎn)為該輸出管腳對(duì)應(yīng)的超圖結(jié)點(diǎn)；依據(jù)該輸出管腳的邏輯功能表達(dá)式，輸入管腳對(duì)應(yīng)的超圖結(jié)點(diǎn)加入到該有向超邊的源端子集中。

第12 行到第17 行：遍歷電路網(wǎng)表的Net 電路信號(hào)模塊信息，依次處理每個(gè)Net 電路信號(hào)，為其生成一個(gè)超圖結(jié)點(diǎn)。讀取其INPUT 端點(diǎn)信息，依據(jù)信息中指定的Inst電路單元和管腳信息找到相應(yīng)的超圖結(jié)點(diǎn)，作為該有向超邊的尾端結(jié)點(diǎn)；讀取其每個(gè)OUTPUT 端點(diǎn)信息，依據(jù)信息中指定的Inst電路單元和管腳信息找到相應(yīng)的超圖結(jié)點(diǎn)，加入該有向超邊的源端子集。

第18 行到第24 行：遍歷壓縮存儲(chǔ)格式的有向超圖的每個(gè)超圖結(jié)點(diǎn)x，生成每個(gè)超圖結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)列表。遍歷超圖結(jié)點(diǎn)x 所在的每條有向超邊e，如果超圖結(jié)點(diǎn)x 是有向超邊e 的尾端結(jié)點(diǎn)，則遍歷有向超邊e的源端子集的每個(gè)結(jié)點(diǎn)加入到超圖結(jié)點(diǎn)x 的直接前驅(qū)結(jié)點(diǎn)列表中。

第25 行到第39 行：遍歷壓縮存儲(chǔ)格式的有向超圖的每個(gè)超圖結(jié)點(diǎn)x，生成每個(gè)超圖結(jié)點(diǎn)x 的間接前驅(qū)結(jié)點(diǎn)列表。遍歷超圖結(jié)點(diǎn)x 直接前驅(qū)結(jié)點(diǎn)列表中的每個(gè)前驅(qū)結(jié)點(diǎn)y，依次處理前驅(qū)結(jié)點(diǎn)y 的直接前驅(qū)結(jié)點(diǎn)列表中的每個(gè)前驅(qū)結(jié)點(diǎn)z；如果超圖結(jié)點(diǎn)x 的間接前驅(qū)結(jié)點(diǎn)列表中未包含前驅(qū)結(jié)點(diǎn)z，則將前驅(qū)結(jié)點(diǎn)z 加入到超圖結(jié)點(diǎn)x 的間接前驅(qū)結(jié)點(diǎn)列表中，遞歸生成前驅(qū)結(jié)點(diǎn)z的間接前驅(qū)結(jié)點(diǎn)列表，且遍歷該超圖結(jié)點(diǎn)z 直接前驅(qū)結(jié)點(diǎn)列表和間接前驅(qū)結(jié)點(diǎn)列表中的每個(gè)前驅(qū)結(jié)點(diǎn)p，如果超圖結(jié)點(diǎn)x 間接前驅(qū)結(jié)點(diǎn)列表中未包含前驅(qū)結(jié)點(diǎn)p，則將前驅(qū)結(jié)點(diǎn)p 加入到超圖結(jié)點(diǎn)x 間接前驅(qū)結(jié)點(diǎn)列表中。

圖1 XDL網(wǎng)表的前向電路圖生成算法偽代碼

有向超圖在不同的物理存儲(chǔ)結(jié)構(gòu)下會(huì)產(chǎn)生不同的算法時(shí)間復(fù)雜度和空間復(fù)雜度[7-8]。因此，本文的前向電路圖生成算法采用壓縮存儲(chǔ)格式（Compressed Storage Format，CSF）[9-10]。CSF 存儲(chǔ)格式使用數(shù)組hewgts 存儲(chǔ)有向超邊的信息，使用數(shù)組vwgts存儲(chǔ)超圖結(jié)點(diǎn)的信息，使用數(shù)組eind存儲(chǔ)每條有向超邊的鄰接結(jié)點(diǎn)信息，使用數(shù)組eptr 存儲(chǔ)每條有向超邊對(duì)應(yīng)鄰接結(jié)點(diǎn)列表的起始位置信息。假設(shè)數(shù)組地址從零開始，結(jié)點(diǎn)編號(hào)從零開始，則第i 條有向超邊的鄰接結(jié)點(diǎn)列表存儲(chǔ)在數(shù)組eind中，位置從eptr[i]開始，到eptr[i+1]-1 結(jié)束，即從數(shù)組eind[eptr[i]]到eind[eptr[i+1]-1]，且有向超邊的尾端結(jié)點(diǎn)存儲(chǔ)在數(shù)組元素eind[eptr[i]]中。

2.2 時(shí)空復(fù)雜度分析

設(shè)XDL 網(wǎng)表電路中#Instances 數(shù)為m ，#Pins 數(shù)為n，#Nets數(shù)為t。該前向電路圖生成算法中第3行到第11行為每個(gè)Inst電路單元建立超圖結(jié)點(diǎn)和有向超邊，其循環(huán)次數(shù)為m，第6 行為每個(gè)管腳建立超圖結(jié)點(diǎn)，其循環(huán)次數(shù)為n；第12 行到第17 行為每個(gè)Net 電路信號(hào)模塊生成有向超邊，其循環(huán)次數(shù)為t ，第15行到第16行為每個(gè)管腳建立超圖結(jié)點(diǎn)，其循環(huán)次數(shù)最壞情況為t×n ；第18行到第24行為每個(gè)超圖結(jié)點(diǎn)建立直接前驅(qū)結(jié)點(diǎn)列表，其循環(huán)次數(shù)為n，第19行到第23行為每個(gè)超圖結(jié)點(diǎn)遍歷所在的超邊，其循環(huán)次數(shù)為(m+t)×n；第25 行到第39 行為每個(gè)超圖結(jié)點(diǎn)建立間接前驅(qū)結(jié)點(diǎn)列表，其循環(huán)次數(shù)為n，第26 行到第38 行為每個(gè)超圖結(jié)點(diǎn)遍歷其直接前驅(qū)結(jié)點(diǎn)，第27 行到第37 行為每個(gè)直接前驅(qū)結(jié)點(diǎn)遍歷其直接前驅(qū)結(jié)點(diǎn)，其循環(huán)次數(shù)最壞情況為n×n×n；因此算法總時(shí)間復(fù)雜度為Θ(m+n+2×t×n+m×n+t3)。該前向電路圖生成算法的空間復(fù)雜度取決于有向超圖的CSF存儲(chǔ)空間。基于CSF存儲(chǔ)結(jié)構(gòu)，包含大小為m 的數(shù)組vwgts，大小為n 的數(shù)組eind，大小為t的數(shù)組hewgts和eptr，因此空間復(fù)雜度為Ω(m+n+2×t)。

3 基于有向超圖的XDL 網(wǎng)表的前向電路圖生成算法的實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

針對(duì)XDL 網(wǎng)表生成前向電路圖的轉(zhuǎn)換實(shí)驗(yàn)，本文基于Xilinx公司Virtex-4型號(hào)XC4VSX55 FPGA芯片對(duì)測試用例進(jìn)行綜合xst、轉(zhuǎn)譯ngdbuild、映射map、布局par（-r）、布線par（-p）、配置流生成bitgen 和網(wǎng)表轉(zhuǎn)換xdl，實(shí)現(xiàn)硬件設(shè)計(jì)到FPGA 配置流的全步驟，并通過網(wǎng)表轉(zhuǎn)換工具xdl 將布局布線后的NCD 二進(jìn)制格式網(wǎng)表文件，轉(zhuǎn)換為XDL 文本格式網(wǎng)表文件，具體流程如圖2所示。進(jìn)而，本文設(shè)計(jì)實(shí)現(xiàn)了基于有向超圖的XDL 網(wǎng)表的前向電路圖生成算法，將XDL 網(wǎng)表文件生成前向電路圖并保存為前向電路圖文件。

圖3和圖4分別給出了測試用例綜合前和綜合后的寄存器傳輸級(jí)電路原理圖。圖4保留了圖3時(shí)序邏輯電路的寄存器FD 器件和組合邏輯電路的INV 求反器件，為輸入輸出信號(hào)pin增加了IBUF或OBUF器件，為時(shí)鐘信號(hào)pin增加了BUFGP器件，并將組合邏輯電路映射到查找表LUT3器件。

Virtex-4 型號(hào)XC4VSX55 FPGA 芯片中每個(gè)CLB資源有兩個(gè)TITLE，每個(gè)TITLE 資源中有兩個(gè)SLICE，每個(gè)SLICE 資源有兩個(gè)LUT。測試用例生成的FPGA電路網(wǎng)表，將綜合后的gen0/lfsr_data_0_rspot和gen0/lfsr_data_1_rspot 兩個(gè)三位查找表LUT3，gen0/lfsr_data_0 和gen0/lfsr_data_1兩個(gè)一位寄存器器件FD整合后映射至電路結(jié)點(diǎn)gen0/lfsr_data，并布局布線在CLB_X33Y0 資源的SLICE_X46Y0器件中。

圖2 FPGA設(shè)計(jì)映射到XDL網(wǎng)表文件的流程圖

圖3 FPGA測試用例的電路原理圖（綜合前）

圖4 FPGA測試用例的電路原理圖（綜合后）

圖5 SLICE電路結(jié)點(diǎn)gen0/lfsr_data的XDL網(wǎng)表控制配置位信息

圖5 給出了器件SLICE_X46Y0 的cfg 控制配置位信息，映射至SLICE_X46Y0 內(nèi)部信號(hào)傳播路徑圖。其中，邏輯單元G 被配置為gen0/lfsr_data_1_rstpot:#LUT:D=（A3+（A2+A1）），即G 功能配置成gen0/lfsr_data_1_rspot的等價(jià)查找表LUT且連接輸入信號(hào)管腳G1～G3；邏輯單元DYΜUX被配置為Y，即從Y端口將LUT輸出信號(hào)D輸出給后續(xù)寄存器FFY器件；邏輯單元FFY被配置為FF，即受時(shí)鐘信號(hào)CLΚ 控制的flip-flop 將LUT 輸出信號(hào)D輸出給YQ。同時(shí)，邏輯單元F被配置為gen0/lfsr_data_0_rstpot:#LUT:D=（～A3*（A1*A2）），即F 功能配置成gen0/lfsr_data_0_rspot 的等價(jià)查找表LUT 且連接輸入信號(hào)管腳F1～F3；邏輯單元DXΜUX被配置為X，即從X 端口將LUT 輸出信號(hào)D 輸出給后續(xù)寄存器FFX器件；邏輯單元FFX被配置為FF，即受時(shí)鐘信號(hào)CLΚ控制flip-flop將LUT輸出信號(hào)D輸出給XQ。

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

讀取XDL 電路網(wǎng)表的10 個(gè)Inst 電路單元，抽取邏輯配置信息進(jìn)行分析，獲取29 個(gè)有效管腳生成29 個(gè)超圖結(jié)點(diǎn)，并為其中的11 個(gè)輸出管腳生成第1～11 條有向超邊。讀取XDL電路網(wǎng)表的9個(gè)Net電路信號(hào)，抽取互聯(lián)配置信息進(jìn)行分析，生成第12～20條有向超邊。

該實(shí)驗(yàn)生成對(duì)應(yīng)的有向超圖文件通過了hΜeTiS超圖優(yōu)化劃分軟件包對(duì)有向超圖的檢測[9]。有向超圖文件第1行顯示超圖結(jié)點(diǎn)數(shù)是29，有向超邊數(shù)是20。第2～21行輸出有向超邊的結(jié)點(diǎn)信息，其中每行第1個(gè)編號(hào)為該有向超邊的尾端結(jié)點(diǎn)，后續(xù)編號(hào)為其源端子集的結(jié)點(diǎn)。

該實(shí)驗(yàn)生成的前向電路圖文件中超圖結(jié)點(diǎn)數(shù)是29，文件中的每一行包含當(dāng)前超圖結(jié)點(diǎn)x 的編號(hào)、“：”分隔符、超圖結(jié)點(diǎn)x 直接前驅(qū)結(jié)點(diǎn)列表中每個(gè)結(jié)點(diǎn)的編號(hào)、“||”分隔符、超圖結(jié)點(diǎn)x 間接前驅(qū)結(jié)點(diǎn)列表中每個(gè)結(jié)點(diǎn)的編號(hào)。以生成的前向電路圖的第一行為例，01表示當(dāng)前結(jié)點(diǎn)，映射至輸出信號(hào)管腳XQ；01 結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的編號(hào)映射至輸入信號(hào)管腳F1～F3 和時(shí)鐘信號(hào)管腳CLΚ，其敏感位翻轉(zhuǎn)將直接導(dǎo)致信號(hào)管腳XQ的輸出出現(xiàn)軟錯(cuò)誤。分析表明：前向電路圖文件每一行，精細(xì)刻畫了與當(dāng)前結(jié)點(diǎn)存在直接和間接前向拓?fù)潢P(guān)系的信號(hào)，其敏感位翻轉(zhuǎn)將直接或間接導(dǎo)致當(dāng)前結(jié)點(diǎn)的映射信號(hào)出現(xiàn)軟錯(cuò)誤，反映了單粒子軟錯(cuò)誤在SRAΜ型FPGA器件中的傳播特性，為計(jì)算軟錯(cuò)誤率提供了必要的傳播模型。

4 結(jié)束語

本文采用有向超圖的形式來構(gòu)建XDL 網(wǎng)表級(jí)電路，描述Inst電路單元和Net電路信號(hào)，其中電路單元的有效管腳表示為有向超圖中的結(jié)點(diǎn)，電路管腳間的外部連線、電路管腳內(nèi)的電路邏輯功能表示為超圖中的有向超邊。本文解析XDL 網(wǎng)表級(jí)電路描述文件以獲得FPGA設(shè)計(jì)的邏輯配置和互聯(lián)配置信息：遍歷電路網(wǎng)表的Inst電路單元，抽取XDL電路網(wǎng)表的邏輯配置信息以生成超圖結(jié)點(diǎn)和有向超邊；遍歷電路網(wǎng)表的Net電路信號(hào)，抽取XDL 電路網(wǎng)表的互聯(lián)配置信息以生成有向超邊。進(jìn)而，本文給出了XDL 網(wǎng)表級(jí)電路描述文件編譯所需的EBNF表達(dá)式，提出了基于有向超圖的XDL網(wǎng)表的前向電路圖生成算法，并進(jìn)行了算法的時(shí)空復(fù)雜度分析。最后，本文在Windows平臺(tái)下基于RapidSmith開源軟件和Java語言實(shí)現(xiàn)了前向電路圖生成算法，并選用基于Virtex-4 型號(hào)FPGA 測試用例的XDL 網(wǎng)表，生成相應(yīng)的前向電路圖以驗(yàn)證前向電路圖生成算法的有效性。