[發(fā)明專利]一種測(cè)試FPGA單長(zhǎng)線及連接開關(guān)的擴(kuò)展布線方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210108006.1
• 申請(qǐng)日: 2012-04-13
• 公開（公告）號(hào): CN102809711A
• 公開（公告）日: 2012-12-05
• 發(fā)明（設(shè)計(jì)）人: 李曉磊;徐彥峰;于大鑫
• 申請(qǐng)（專利權(quán)）人: 中國(guó)電子科技集團(tuán)公司第五十八研究所
• 主分類號(hào): G01R31/08
• 分類號(hào): G01R31/08;G01R31/02;G01R31/327
• 代理公司: 無(wú)錫市大為專利商標(biāo)事務(wù)所 32104
• 代理人: 殷紅梅

技術(shù)領(lǐng)域

本發(fā)明實(shí)現(xiàn)了一種測(cè)試FPGA單長(zhǎng)線及連接開關(guān)的擴(kuò)展布線方法，屬FPGA自動(dòng)化布線范疇。

背景技術(shù)

FPGA芯片是一種布線資源數(shù)量龐大、種類繁多、可重復(fù)編程的超大規(guī)模集成電路，在實(shí)際應(yīng)用中，發(fā)生于互連資源上的故障率遠(yuǎn)大于其它器件的故障率，那么為了解決發(fā)生于互連資源上的故障，尤其為了測(cè)試單長(zhǎng)線及互連開關(guān)的連接情況，并快速有效地對(duì)故障進(jìn)行查找、定位和解決，這里采用了一種FPGA單長(zhǎng)線及直連開關(guān)的測(cè)試方法（專利申請(qǐng)?zhí)?01110125752.7）。

在對(duì)該測(cè)試方法進(jìn)行實(shí)施驗(yàn)證的過(guò)程中發(fā)現(xiàn)，由于手工費(fèi)時(shí)費(fèi)力且錯(cuò)誤率高以及機(jī)時(shí)有限且極其昂貴等系列原因，極需一種更高效的布線算法來(lái)進(jìn)行快速的資源配置和有效配置資源圖生成以進(jìn)行連續(xù)無(wú)間斷的測(cè)試。

近年來(lái)，各國(guó)學(xué)者提出過(guò)許多相關(guān)布線算法，其中迷宮算法是一種比較成熟的算法，其它如蟻群算法、全局尋優(yōu)算法等都有一定的用途和群眾基礎(chǔ)，然而，這些算法在實(shí)施的過(guò)程中不是針對(duì)性不強(qiáng)，如單長(zhǎng)線資源的覆蓋率問(wèn)題，就是理論到實(shí)踐驗(yàn)證轉(zhuǎn)換有一定難度，可操作性不強(qiáng)，另外有的算法在布線效率上的表現(xiàn)也不是很令人滿意。

發(fā)明內(nèi)容

為了解決現(xiàn)有布線方法的不足、針對(duì)性不強(qiáng)以及其它如手工布線效率低下等問(wèn)題，本發(fā)明依據(jù)層次式FPGA的結(jié)構(gòu)特點(diǎn)，提出了一種測(cè)試FPGA單長(zhǎng)線及連接開關(guān)的擴(kuò)展布線方法，是一種基于布通率的高可靠、高適應(yīng)、高效率的布線方法。

按照本發(fā)明提供的技術(shù)方案，所述測(cè)試FPGA單長(zhǎng)線及連接開關(guān)的擴(kuò)展布線方法，步驟如下：

步驟一、設(shè)置輪回行并初始化參數(shù)：確定輪回行的數(shù)目為2，并為后續(xù)布線搜索到的鏈路中間結(jié)果準(zhǔn)備存儲(chǔ)空間，準(zhǔn)備完成后進(jìn)入步驟二；

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

步驟三、線序預(yù)估：在選取完第一組CLB分組連接點(diǎn)后，通過(guò)獲取輪回行所有關(guān)鍵布線CLB分組連接點(diǎn)的方法獲取輪回行所有CLB分組的起始連接點(diǎn)，然后分別對(duì)這些連接點(diǎn)進(jìn)行測(cè)試驗(yàn)證，測(cè)試該分組是否合適，是否可以選出最優(yōu)線序；測(cè)試的方法是：依據(jù)寬度優(yōu)先算法搜索并選取該CLB布線在最大鏈長(zhǎng)下的所有可布通的線網(wǎng)，如能布通則表示該分組暫時(shí)可行，并分別記錄CLB1、CLB2、CLB3、CLB4可布通的組合序號(hào)以便在后續(xù)回退時(shí)調(diào)整該組合序號(hào)選出相應(yīng)線序組合；當(dāng)預(yù)估完成后進(jìn)入步驟四，否則，如果所有組合測(cè)試后均未發(fā)現(xiàn)可布通的線序組合則回退至步驟二重新分組；所述CLB1、CLB2、CLB3、CLB4分別指每個(gè)CLB分組的第一個(gè)CLB、第二個(gè)CLB、第三個(gè)CLB和第四個(gè)CLB；

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

步驟五、線序拼接：在完成所有關(guān)鍵布線CLB分組的布線后，需要對(duì)相鄰關(guān)鍵布線CLB分組的布線進(jìn)行拼接來(lái)完成整個(gè)線網(wǎng)的布線，在拼接過(guò)程中，依據(jù)單個(gè)CLB在線序預(yù)估階段選出的可行線序索引進(jìn)行，當(dāng)拼接成功則進(jìn)入步驟八，否則當(dāng)某個(gè)CLB在重試完所有的可行線序索引后均未拼接成功，則進(jìn)入步驟六進(jìn)行回退判定；

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