[發明專利]一種測試FPGA單長線及連接開關的擴展布線方法

有效

• 申請號: 201210108006.1
• 申請日: 2012-04-13
• 公開（公告）號: CN102809711A
• 公開（公告）日: 2012-12-05
• 發明（設計）人: 李曉磊;徐彥峰;于大鑫
• 申請（專利權）人: 中國電子科技集團公司第五十八研究所
• 主分類號: G01R31/08
• 分類號: G01R31/08;G01R31/02;G01R31/327
• 代理公司: 無錫市大為專利商標事務所 32104
• 代理人: 殷紅梅

1.?一種測試FPGA單長線及連接開關的擴展布線方法，其特征是，步驟如下：

步驟一、設置輪回行并初始化參數：確定輪回行的數目為2，并為后續布線搜索到的鏈路中間結果準備存儲空間，準備完成后進入步驟二；

步驟二、快速分組：依據分組算法依次將CLB和單長線進行分組，獲取輪回行所有CLB分組和第一組CLB分組對應單長線起始組合點；分組完成后進入步驟三，如果失敗則退出算法，返回失敗代碼；

步驟三、線序預估：在選取完第一組CLB分組連接點后，通過獲取輪回行所有關鍵布線CLB分組連接點的方法獲取輪回行所有CLB分組的起始連接點，然后分別對這些連接點進行測試驗證，測試該分組是否合適，是否可以選出最優線序；測試的方法是：依據寬度優先算法搜索并選取該CLB布線在最大鏈長下的所有可布通的線網，如能布通則表示該分組暫時可行，并分別記錄CLB1、CLB2、CLB3、CLB4可布通的組合序號以便在后續回退時調整該組合序號選出相應線序組合；當預估完成后進入步驟四，否則，如果所有組合測試后均未發現可布通的線序組合則回退至步驟二重新分組；所述CLB1、CLB2、CLB3、CLB4分別指每個CLB分組的第一個CLB、第二個CLB、第三個CLB和第四個CLB；

步驟四、二次過濾：經過步驟3預估過濾后，確定了所有關鍵布線CLB分組的起始連接點和所有可行的線序組合后，再做進一步進行過濾排除：從第一個CLB分組的CLB1和CLB2開始，依次選取相鄰下個分組的CLB1和CLB2，在選取CLB1和CLB2的過程中過濾水平六長線的占用，并同時采用線序選優的策略選取最優線序組合，以降低CLB1和CLB2分別對CLB4和CLB3布線線網的影響；在選取CLB1、CLB2、CLB3和CLB4的過程中，考慮相互之間水平六長線和行間單長線的占用影響，當過濾完成后進入步驟五，否則失敗回退至步驟二重新分組；

步驟五、線序拼接：在完成所有關鍵布線CLB分組的布線后，需要對相鄰關鍵布線CLB分組的布線進行拼接來完成整個線網的布線，在拼接過程中，依據單個CLB在線序預估階段選出的可行線序索引進行，當拼接成功則進入步驟八，否則當某個CLB在重試完所有的可行線序索引后均未拼接成功，則進入步驟六進行回退判定；

步驟六、回退判定：在線序拼接失敗后，進行布線CLB回退位置的選擇，首先選擇拼接失敗CLB的頂部CLB，調整頂部CLB選取的線序組合對底部CLB布線有影響的占用集合，同時測試底部CLB是否可以布通；如果可以則記錄該線序索引值，進入步驟七進行拆除重布；如果調整完所有線序索引仍未布通，則回退至該拼接失敗CLB的上一相鄰關鍵布線CLB分組內具有相同組內索引的CLB，同樣重試該CLB選出的可行線序索引進行，同時測試是否可以布通，如是，則記錄該線序索引值，進入步驟七進行拆除重布，如果重試完所有的可行線序索引后仍未布通，則繼續按照上述方法循環回退，直至回退位置為首行的首個分組為止；如果仍未成功則回退至步驟二重新分組；

步驟七、拆除重布：對已布線網進行部分拆除，拆除部分為布線失敗CLB位置至回退CLB位置，拆除這之間所有已布的線網，并在拆除過程中分析造成失敗的沖突占用點和線序索引，為回退重布提供依據，拆除完成后根據回退CLB位置記錄的可行線序索引值進行資源重建即重布，重建完成則回退至步驟五，從該回退CLB位置開始繼續未完成的線序拼接；

步驟八、結果擴展：完成拼接后的鏈路即為完整鏈路，即已完成了輪回行布線，覆蓋了輪回行的所有CLB；此時輪回行以外的CLB部分，將搜索到的鏈路中間結果按照行奇偶對應的原則擴展至整個芯片，在擴展的過程中嚴格遵守XDL的描述規則；

步驟九、結果驗證：擴展完成后，即實現了整個FPGA的布線，將此時的中間結果直接導出為XDL格式文件，然后利用XDL命令，將導出文件轉化為NCD網表進行結果驗證。