XDL網表的前向電路圖生成算法

冷 明，孫凌宇，郭 晨

井岡山大學 計算機科學系，江西 吉安343009

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

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

1 XDL網表級電路描述文件的解析

每個XDL 網表級電路描述文件對應一個FPGA 設計的硬件實現，使用BNF范式詳細地描述了整個FPGA設計的基本信息以及布局布線信息，包含design、module、instance 和net 等語句，提供了FPGA 設計在芯片微觀級別（網表級）邏輯資源的配置信息和布線資源的互聯信息。表1 給出了XDL 網表級電路描述語言的EBNF 表達式語法規則。

定義1 design 語句采用“design”關鍵字表示，其生產 式 規 則

定義2 module 語句采用“module”關鍵字表示，其生產式規則

定義3 instance語句采用“inst”關鍵字表示，其生產式規則

定義4 net語句采用“net”關鍵字表示，其生產式規則

2 基于有向超圖的XDL 網表的前向電路圖生成算法

根據定義1～定義5，基于有向超圖的XDL網表的前向電路圖生成算法的主要思想是：（1）電路單元的有效管腳表示為有向超圖中的結點。（2）電路管腳間的外部連線、電路管腳內的電路邏輯功能，表示為超圖中的有向超邊。（3）每條有向超邊可以連接兩個以上的結點，對應于電路單元間的連線可以連接兩個以上的有效管腳，或電路邏輯功能可以連接多輸入管腳。（4）在每條有向超邊中，唯一的輸出管腳對應于有向超邊的尾端結點，其余輸入管腳對應于有向超邊源端子集結點，且有向超邊的源端子集的每個結點屬于該尾端結點的直接前驅結點。（5）通過遞歸遍歷直接前驅結點列表中的結點，生成該超圖結點的間接前驅結點列表。只有超圖結點x的間接前驅結點列表中未包含前驅結點z，才會調用遞歸遍歷生成前驅結點z 的間接前驅結點列表，巧妙地避免XDL電路網表的信號前向拓撲關系中存在有向環導致遞歸循環。

表1 XDL網表級電路描述語言的EBNF表達式

2.1 算法分析

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

第3行到第11行：遍歷電路網表的Inst電路單元模塊信息，依次處理每個Inst電路單元。抽取XDL電路網表的邏輯配置信息，獲取有效管腳信息列表，為每個有效管腳生成一個超圖結點；根據Inst電路單元的不同類型，配合CFG配置信息獲取的底層電路配置狀態，解析每個輸出管腳的邏輯功能表達式，為每個輸出管腳生成一條有向超邊，且該有向超邊的尾端結點為該輸出管腳對應的超圖結點；依據該輸出管腳的邏輯功能表達式，輸入管腳對應的超圖結點加入到該有向超邊的源端子集中。

第12 行到第17 行：遍歷電路網表的Net 電路信號模塊信息，依次處理每個Net 電路信號，為其生成一個超圖結點。讀取其INPUT 端點信息，依據信息中指定的Inst電路單元和管腳信息找到相應的超圖結點，作為該有向超邊的尾端結點；讀取其每個OUTPUT 端點信息，依據信息中指定的Inst電路單元和管腳信息找到相應的超圖結點，加入該有向超邊的源端子集。

第18 行到第24 行：遍歷壓縮存儲格式的有向超圖的每個超圖結點x，生成每個超圖結點的直接前驅結點列表。遍歷超圖結點x 所在的每條有向超邊e，如果超圖結點x 是有向超邊e 的尾端結點，則遍歷有向超邊e的源端子集的每個結點加入到超圖結點x 的直接前驅結點列表中。

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

圖1 XDL網表的前向電路圖生成算法偽代碼

有向超圖在不同的物理存儲結構下會產生不同的算法時間復雜度和空間復雜度[7-8]。因此，本文的前向電路圖生成算法采用壓縮存儲格式（Compressed Storage Format，CSF）[9-10]。CSF 存儲格式使用數組hewgts 存儲有向超邊的信息，使用數組vwgts存儲超圖結點的信息，使用數組eind存儲每條有向超邊的鄰接結點信息，使用數組eptr 存儲每條有向超邊對應鄰接結點列表的起始位置信息。假設數組地址從零開始，結點編號從零開始，則第i 條有向超邊的鄰接結點列表存儲在數組eind中，位置從eptr[i]開始，到eptr[i+1]-1 結束，即從數組eind[eptr[i]]到eind[eptr[i+1]-1]，且有向超邊的尾端結點存儲在數組元素eind[eptr[i]]中。

2.2 時空復雜度分析

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

3 基于有向超圖的XDL 網表的前向電路圖生成算法的實驗及結果分析

3.1 實驗設計

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

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

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

圖2 FPGA設計映射到XDL網表文件的流程圖

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

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

圖5 SLICE電路結點gen0/lfsr_data的XDL網表控制配置位信息

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

3.2 實驗結果分析

讀取XDL 電路網表的10 個Inst 電路單元，抽取邏輯配置信息進行分析，獲取29 個有效管腳生成29 個超圖結點，并為其中的11 個輸出管腳生成第1～11 條有向超邊。讀取XDL電路網表的9個Net電路信號，抽取互聯配置信息進行分析，生成第12～20條有向超邊。

該實驗生成對應的有向超圖文件通過了hΜeTiS超圖優化劃分軟件包對有向超圖的檢測[9]。有向超圖文件第1行顯示超圖結點數是29，有向超邊數是20。第2～21行輸出有向超邊的結點信息，其中每行第1個編號為該有向超邊的尾端結點，后續編號為其源端子集的結點。

該實驗生成的前向電路圖文件中超圖結點數是29，文件中的每一行包含當前超圖結點x 的編號、“：”分隔符、超圖結點x 直接前驅結點列表中每個結點的編號、“||”分隔符、超圖結點x 間接前驅結點列表中每個結點的編號。以生成的前向電路圖的第一行為例，01表示當前結點，映射至輸出信號管腳XQ；01 結點的直接前驅結點的編號映射至輸入信號管腳F1～F3 和時鐘信號管腳CLΚ，其敏感位翻轉將直接導致信號管腳XQ的輸出出現軟錯誤。分析表明：前向電路圖文件每一行，精細刻畫了與當前結點存在直接和間接前向拓撲關系的信號，其敏感位翻轉將直接或間接導致當前結點的映射信號出現軟錯誤，反映了單粒子軟錯誤在SRAΜ型FPGA器件中的傳播特性，為計算軟錯誤率提供了必要的傳播模型。

4 結束語

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