[發明專利]一種基于最大流方法的FPGA測試方法

有效

• 申請號: 200910248933.1
• 申請日: 2009-12-30
• 公開（公告）號: CN102116839A
• 公開（公告）日: 2011-07-06
• 發明（設計）人: 楊志家;呂巖;馬繼開;謝闖;張超;趙雪峰
• 申請（專利權）人: 中國科學院沈陽自動化研究所
• 主分類號: G01R31/3185
• 分類號: G01R31/3185
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 許宗富

1.一種基于最大流方法的FPGA測試方法，其特征在于：該測試方法包括如下步驟：

步驟1)根據FPGA結構建立有向圖模型；將FPGA化分為配置單元結構和互連線結構；所述配置單元結構包括邏輯單元、輸入輸出單元及互聯單元中的配置開關形成的互聯開關矩陣；所述互連線結構為各配置單元結構間的引線；

步驟2)將FPGA建立有向圖模型時，所述邏輯單元的基本組成結構對應有向圖模型中的一個頂點，所述互聯開關矩陣的每個端口對應有向圖模型一個頂點；所述互連線對應有向圖模型的一個邊；

步驟3)在步驟1中有向圖模型的基礎上增加“源S”頂點和“匯T”頂點；所述“源S”與輸入輸出單元的輸入端口頂點相連，“匯T”與輸出單元輸出端口的頂點相連；通過所述“源S”頂點及“匯T”頂點將數據路徑轉化為從起點“源S”到終點“匯T”路徑的集合。

步驟4)FPGA測試配置自動生成采用求最大流方法，該方法第一、定義每個邊容量；第二、增流過程中采用路徑搜索算法；第三、在流生成過程中對有向圖的實時檢測動態調整；

步驟5)當步驟4)中達到某一最大流時，將最大流中所有路徑的集合映射到FPGA中構成一個測試配置，記錄測試配置后，模型重新初始化；

步驟6)重復步驟準4)中最大流測試，當連續兩次求最大流操作的結果相同時，將統計所有的頂點和邊在已有測試配置中的使用情況；將始終沒有出現在測試配置中的頂點和邊(不包括雙向連線抽象出的兩條邊有一條未出現的情況)為起點分別向“源S”和“匯T”路徑搜索，最終將所有的頂點和邊都被包含在測試配置中，輸出自動匹配結果。

2.根據權利要求1所述的一種基于最大流方法的FPGA測試方法，其特征在于：所述邏輯單元基本組包括：多路選擇器、查找表、觸發器。

3.根據權利要求1所述的一種基于最大流方法的FPGA測試方法，其特征在于：所述互連線，容量設置為1；配置開關，其容量設置為1；所述多路選擇器的輸出容量設置為1；觸發器的輸出容量設置為1；查找表LUT的輸出容量設置為LUT的輸入數。

4.根據權利要求1所述的一種基于最大流方法的FPGA測試方法，其特征在于：所有在測試配置中出現過的頂點和邊，將在模型中被特殊標注，在下一次操作中優先使用沒有特殊標注的頂點和邊。

5.根據權利要求1所述的一種基于最大流方法的FPGA測試方法，其特征在于：所述路徑搜索算法中增加預測機制的深度優先算法，該預測機制算法在某一數據路徑搜索到某一頂點V1，并從頂點V1向其第二級頂點搜索前，先對第二級頂點進行預測優先排序；所述預測優先排序的原則是第二級頂點所連接的第三級頂點中未被遍歷到的頂點越多，則這個第二級頂點的優先級越高，在進行排序后，選取優先級最高的第二級頂點作為V1的下一級連接。

6.根據權利要求1所述的一種基于最大流方法的FPGA測試方法，其特征在于：所述依據FPGA模型的約束，對模型的結構進行的動態調整，調整包括：輸入端口被選中的輸入輸出單元，其輸出端口的頂點將在模型中被屏蔽掉；對于在建模時被抽象為兩條邊雙線數據連線，在其中某一條邊被使用后，另外一條邊也將在模型中被屏蔽掉。