劉沛文，付宇卓，董宜平

（1.上海交通大學微電子學院，上海 200240；

2.中國電子科技集團公司第五十八研究所，江蘇無錫 214072）

1 引言

前些年，FPGA產品中的開關盒結構限定在Universal[2]、Disjoint和Wilton[3]3種類型中。當時測試工程師們針對這3種結構類型研究出了許多的測試方法[2～3]，但隨著FPGA的技術發(fā)展，開關盒的結構已經不再限定在這3種結構之中[4]。之前對開關盒測試方法的研究已經不再適用于目前的FPGA產品，如Xilinx公司的Virtex4系列、Virtex5系列FPGA[1]。由于新的開關盒結構變得更加復雜，開關盒的扇出系數已經遠遠超出早期開關盒的3或者4，并且出現多種倍數線端口以及這些端口之間的互連[4]。同時芯片廠商也不再對外提供詳細布線工具的技術手冊，對于開關盒的測試成為一個十分困難的問題。

目前已有很多文獻在研究對新型開關盒的測試，取得了一定的成果[5～6]，但都是基于圖論的原理對建模方法進行研究，并沒有深入研究開關盒的具體結構和在布線資源中與各硬件資源之間的連接關系。

本文以Xilinx公司的XC5VSX95T（后文以95T簡稱）為目標器件，借助工程數學中圖論的理論，并結合文獻 [4]的分層思想對95T的開關盒進行分層、建模，并對模型進行分析。得到的模型在開關盒的結構解析方面比文獻[6]的模型層次更清晰。該模型可應用在基于圖論搜索測試路徑圖形的研究中。

2 互連資源的結構

95T中的布線資源主要由長線資源、2倍線資源、5倍線資源、局部連線資源、開關盒和局部連線盒構成，如圖1所示。布線資源起著連接各個CLB單元、BRAM單元、DSP單元以及其他邏輯、時鐘、存儲等功能單元的作用，是實現FPGA可編程能力最重要的組成部分。各項資源按照Tile的方式平鋪在電路中，各個Tile之間通過布線資源連接在一起，再通過編程邏輯將各個Tile連接，從而實現程序設計出來的功能電路。

圖1 互連資源結構

1個開關盒、1個局部連線盒和2個SLICE構成了FPGA內部1個基本單元Tile。每個開關盒之間由布線通道中的連線資源進行連接，包括2倍線資源、5倍線資源和長線資源。2倍線資源是指從某個開關盒起始，跨過2個開關盒后結束的連線資源。5倍線資源是指從某個開關盒起始，跨過5個開關盒后結束的連線資源。長線資源是指從某個開關盒起始，跨過18個開關盒后結束的連線資源。這3種連線資源的存在使得各個Tile之間的連通變得更加靈活。開關盒中各開關量(Programmable Interconnect Points,PIPs)的通斷是由配置單元中對應的bit位來控制的。通過這些布線資源構成的全局布線系統(tǒng)，各SLICE和各硬件資源之間便得以互聯互通，形成一套完整的電路。

3 建立開關盒的圖模型

3.1 開關盒的結構分析

通過ISE指令窗口生成的95T全資源報表中能夠看到布線資源中2倍線資源和5倍線資源均存在3個端點，分別是以BEG開始，以END結束，中間會出現MID端作為中間點。2倍線資源的MID端連接到布線通道中的第2個開關盒。5倍線資源的MID端連接到布線通道中的第3個開關盒。長線資源存在4個端點，分別是布線通道中的0號端、6號端、12號端和18號端。長線資源可分為2類，一類是水平方向上的長線資源，另一類是豎直方向上的長線資源。

95T的開關盒總共含有479個IO端口，各端口之間有3992個連接關系，按照東南西北的連線方向可以分為N、E、S、W 4類，另外還有連接CLB的邏輯輸入輸出端口以及連接長線、時鐘線的2類端口。

論文主要研究東南西北方向上4類端口的數學圖模型。如表1所示，按照端口方位和方向類型劃分，這4 類端口又可繼續(xù)劃分為 NW、NL、NR、NE、EN、EL、ER、ES、SW、SL、SR、SE、WN、WL、WR、WS 總共 16 類端口。從95T的全資源報表中可以看到開關盒的端口名稱是按照 NL5BEG0、NL2MID1、EN5END2 這樣的方式表示的。其第一個字母表示下一個連通的開關盒相對于本開關盒的方位；第二個字母表示端口對應的布線通道，即驅動方向；第三個數字表示該端口為2倍線端口或者5倍線端口；再后面的3個字母表示倍數線的端點名稱；最后的數字表示該類線的編號，只包含0～2共3根線。如圖2所示，在開關盒的16類端口上，每1類端口可以按布線通道上的引線端口繼續(xù)分出BEG、MID、END 3類端口。這樣總共有48種端口。每1個端口繼續(xù)按照線的標號0、1、2往下分，即能夠得到所有的連線端口。2倍線端口和5倍線端口均有144個端口。

表1 開關盒端口類型劃分

圖2 開關盒端口名稱示意圖

通過軟件求解開關盒的測試路徑需要先對開關盒的結構進行數學建模，通過對模型的運算能夠求解出開關盒的測試用例，從而確定開關盒的測試方案。

由于Xilinx官方并不提供布線資源的結構信息，所以需要對開關盒進行分析與研究。參考C.Beckhoff的工作[8]能夠了解xdl文件的語法，并參照95T的資源報表進行分析，可知在開關盒內部，端口之間的驅動關系并不是任意的，而是存在一定的規(guī)律，且開關盒的端口之間都是單向驅動的。END類端口可以驅動MID類端口和BEG類端口。2倍線端口之間、5倍線端口之間存在驅動關系。5倍線END端口可以驅動2倍線的MID類端口和BEG類端口，但是2倍線END端口卻不可以驅動5倍線的MID類端口和BEG類端口。同時2倍線端口能夠驅動長線的端口，長線的端口又可以驅動5倍線端口。而只有2倍線端口和5倍線端口以及CLB的輸入輸出端口存在驅動關系。

3.2 開關盒的層次劃分

由于開關盒內部的端口數量太大，相互之間的驅動關系錯綜復雜。按照前人對開關盒端口分類和建模的方法會太復雜，建出來的模型也會過于復雜，不利于數學分析和路徑求解。于是參考文獻[4]中分層的思想，將開關盒內各倍數線端口、長線端口和局部連線端口各自分為一層，通過分層降低建模的復雜度。具體驅動關系如圖3所示。

圖3開關盒的層次化結構

圖3 中CLB線層為連接CLB與開關盒之間端口的集合。5倍線層為全部5倍線端口的集合，表示各個5倍線端口之間的驅動關系。2倍線層為全部2倍線端口的集合，表示各個2倍線端口之間的驅動關系。長線層為全部長線端口的集合，表示各個長線端口之間的驅動關系。這些驅動線用黑色帶箭頭的實線表示。這3個線層之間也存在互相驅動的關系。經過對報表的分析得出：2倍線層能夠驅動長線層，長線層能夠驅動5倍線層，5倍線層能夠驅動2倍線層。但是2倍線層卻不能驅動5倍線層，同時與CLB線層存在驅動關系的只有2倍線層和5倍線層。層與層之間的驅動線用空心箭頭表示。通過這樣的分層劃分之后，就可以對開關盒內的開關量進行分組討論和建模，也能夠分組進行測試。文章以開關盒的2倍線端口為例描述開關盒模型的建立。5倍線端口、長線端口和CLB線端口的建模方法與2倍線端口的建模方法類似，在此不再贅述。

文章采用圖模型的理論對開關盒內開關量進行建模，將開關盒的端口定義為圖模型的頂點A，將開關量定義為邊V。最終形成一幅以開關盒端口和開關量構成的圖模型G(A,V)[7]。首先對2倍線層的連線關系進行梳理。按照圖2中所示的端口畫出開關盒模型的端口示意圖。再參照資源報表中的驅動關系進行分析和總結，得出結論：每個端口之間有著固定的驅動關系。

以S方向的端口為驅動端為例，如L、R類端口（SL、SR）可以驅動同側的轉向端口（如SW、SE）以及左側的R類端口（WR）和右側的L類端口（EL），如圖4所示。而轉向端口可以驅動同側的所有端口，包括自己同類的轉向端口以及左側的R類端口（WR）、左側最近的轉向端口（WS）、右側的L類端口（EL）和右側最近的轉向端口（ES），如圖5所示。其他3個方向上的端口作為驅動端時的驅動關系都與上述關系類似。另外，5倍線端口之間的驅動關系與2倍線端口之間的驅動關系相同。

圖5 開關盒SW、SE端的驅動關系

3.3 開關盒模型的建立

通過C語言對開關盒的圖模型進行描述，并將模型建立成模板供程序中其他資源調用。有向圖模型的描述方法有兩種：一種是通過鄰接矩陣對有向圖進行描述，另一種是采用鄰接鏈表對圖模型進行描述。從數學的角度來說，二者沒有太多的差異。但是從計算機運算的角度來說，鄰接矩陣對內存的要求更高，一個n端口的有向圖，采用鄰接矩陣進行存儲時，消耗的內存空間是n2個存儲單元，即空間復雜度為o(n2)。而采用鄰接鏈表對一個n端口的有向圖進行存儲時，消耗的內存空間等于端口之間的連接數，而這個連接數小于n2，其空間復雜度為o(n)。

采用鄰接矩陣存儲開關盒模型，在求取路徑的過程中對內存的消耗非常大，計算效率較低。而采用鄰接鏈表對開關盒模型進行描述和存儲，在計算過程中消耗的內存空間比較小。在C語言中通過使用類對開關盒進行定義。開關盒定義的偽代碼如圖6所示。

圖6 開關盒定義的偽代碼

將開關盒圖模型放入95T整體的布線資源結構中，結合布線資源在各個開關盒端口之間的連接關系，能夠得到95T整個互連結構的圖模型。為使得示意圖清晰可讀，圖7中只畫出開關盒內的L端驅動線和布線資源的2倍線結構，其他端口的驅動關系與此相似。

圖7 開關盒模型在布線資源結構中的示意圖

4 開關盒圖模型的驗證

對開關盒圖模型的驗證為功能驗證。參照建立的開關盒模型，通過xdl語言強行打開開關盒中的一條PIP，然后導入FPGA Editor中，檢測實際打開的PIP是否是開關盒模型中對應的PIP，以此來檢測模型中的PIP是否正確。由于開關盒中PIP的數量是有限的，因此可以通過窮舉法對開關盒模型的正確性進行驗證。

例如，取開關盒模型中的一條PIP：EL2MID0→EN2BEG0。對應地，在xdl文件中，強行布一條PIP。以坐標為X0Y0的開關盒為例。xdl文件的部分代碼如下。

net"int_EL2MID0_EN2BEG0",

outpin"test_in"I,

inpin"test_out"O,

PIP INT_X0Y0 EL2MIDO-＞EN2BEG0,

;

通過ISE的指令工具將該xdl文件轉成ncd文件，并導入FPGA Editor，得到實際打開的路徑，見圖8。

圖8 X0Y0開關盒中被強行打開的PIP路徑

圖8 中圓圈標識的地方為開關盒內部被強行打開的EL2MID0→EN2BEG0路徑。與開關盒模型中的PIP：EL2MID0→EN2BEG0對應，模型中該條PIP與開關盒中的PIP是一一對應的關系，且滿足開關盒在95T布線資源圖中的電氣規(guī)則。該條PIP模型成立。由于開關盒和模型中的PIPs數量是有限的，可以通過窮舉，用相同的方法對其他PIP依次進行檢測，從而驗證開關盒模型的正確性。檢測結果如表2所示。

從表2中可以得出，開關盒的圖模型與實際電路中的PIPs存在一一對應的關系，且模型結構與開關盒的實際結構相同，模型正確。

5 總結

本文通過對XC5VSX95T的開關盒端口進行分類整理和分析，結合開關盒在電路互連資源中的結構布局，提出對開關盒進行層次化分解，并采用有向圖理論的概念對分層后的開關盒結構進行理論抽象，得到每一層開關盒的圖模型。然后通過腳本文件依次對每一條PIP進行檢驗，驗證開關盒模型的正確性。驗證結果表明該模型符合開關盒的連接行為。該圖模型比文獻[6]中的圖模型更具有層次化結構，在開關盒的同類端口、不同類端口之間的PIP測試時具有更清晰的指向性，在故障定位時具有很強的引導性。該開關盒的圖模型可用于基于圖論的路徑搜索算法，能夠快速求解出合適的布線路徑和布線資源圖，實現開關盒的計算機自動化測試。

表2 各個方向上檢測的PIPs

[1]Virtex-5 FPGAUser Guide[P].Xilinx Inc,2012.

[2]G Lemieux,S Brown,D Vranesic.On Two-Step Routing for FPGAs[C].ACM Symposium on Physical Design,1997:60-66.

[3]S Wilton.Architectures and Algorithms for Field-Programmable Gate Arrays with Embedded Memories[D].Toronto Canada:University of Toronto,1997.

[4]A W Ruan,W Tian,B Ni,K Wu.A Hierarchical Switch Matrix and Interconnect Resources Test in Virtex-5 FPGA[J].International Symposium on Integrated Circuits,2014:111-114.

[5]B E Dixon.Built-In Self-Test of the Programmable Interconnectin Field Programmable Gate Arrays[D].Alabama:Auburn University,2008.

[6]Z Yang,C Liang,J Wang,J Lai.A new automatic method for testing interconnect resources in FPGAs based on general routing matrix[C].IEICE Electronics Express,Oct 8,2015:1-12.

[7]J邦詹森,G古廷.有向圖的理論、算法及其應用[M].姚兵，張忠輔，譯.北京：科學出版社，2009.

[8]C Beckhoff,D Koch,J Torresen.The Xilinx Design Language(XDL):Tutorial and Use Cases[C].International Workshop on Reconfigurable Communication-centric Systems-on-chip,2011:1-8.