[發明專利]基于關鍵節點選擇和蟻群優化算法的大規模集成電路小時延故障測試通路選擇方法

有效

• 申請號: 201410642109.5
• 申請日: 2014-11-13
• 公開（公告）號: CN104331569A
• 公開（公告）日: 2015-02-04
• 發明（設計）人: 俞洋;彭宇;陳修遠;彭睿
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/00
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 張利明

技術領域

本發明涉及一種大規模集成電路的小時延故障測試通路選擇方法。

背景技術

集成電路制造工藝的進步導致芯片上集成晶體管數目急劇上升，芯片日益趨向高功能密度和高工作頻率。這不僅為設計同樣也為測試帶來了巨大的挑戰，因為特征尺寸降低致使芯片中出現了更多的缺陷。制造中的缺陷包括阻性開路短路、邊緣毛刺、工藝參數偏差、長互連線帶來的耦合電容增加、電源噪聲等因素，這些都會給電路帶來小時延缺陷，從而給電路帶來額外的時序錯誤而導致芯片失效。隨著芯片設計進入45nm時代，小時延缺陷檢測是保證電路高性能和高可靠性必不可少的步驟，因此如何選擇針對小時延缺陷的測試路徑是檢測小時延缺陷的關鍵。

因為無法預測哪條長通路上的小時延缺陷累積后會導致電路輸出端時序失效，這些小時延缺陷的存在時刻威脅著芯片的穩定性和可靠性，會導致芯片早期失效。經研究表明當下最新工藝水平下很大部分的時序失效是由小時延缺陷引起的。在高頻電路對時序要求如此嚴格的今天，只有有效檢測小時延缺陷才能夠保證高集成度電路的可靠性和質量。然而小時延缺陷在普通的針對時延缺陷的測試路徑上存在測試逃脫的現象，因而選擇能夠針對小時延缺陷的測試路徑，是能夠高效快速檢測的關鍵。

因而小時延測試其本質就是測試路徑的選擇問題，不同的測試路徑對小時延缺陷的檢測能力是有差異的。由上文論述可知，要提高測試路徑對小時延缺陷的檢測能力，就要降低測試時鐘周期與通路敏化時延值之差，也就是時延余量(Slack)。因為時延余量的大小決定了能夠檢測到時延缺陷大小的最大值。而當前學術界和工業界的也是從降低測試時鐘周期和增大通路敏化時延這兩個方面進行研究。

而當下的EDA(Electronic?Design?Automation，電子設計自動化)工具中對小時延缺陷的測試通路選擇，大多是基于貪婪算法下對電路選擇長通路作為小時延缺陷的測試通路，貪婪算法雖然基于全局搜索能夠獲得最優解，但是時間復雜度和空間復雜度過高是其缺點。

發明內容

本發明是為了解決現有測試通路選擇方法時間長、速度慢的問題，現提供基于關鍵節點選擇和蟻群優化算法的大規模集成電路小時延故障測試通路選擇方法。

本發明所述的基于關鍵節點選擇和蟻群優化算法的大規模集成電路小時延故障測試通路選擇方法，包括以下步驟：

步驟一：將待選擇通路的大規模集成電路按照節點連接結構轉化為拓撲結構，并將該拓撲結構保存為鄰接矩陣，然后將該鄰接矩陣作為目標電路網絡；

步驟二：在上述目標電路網絡中，選取關鍵度評價標準中，排序前5％的節點作為關鍵節點，根據關鍵度公式設置鏈入關鍵節點的連線上的信息素；

步驟三：利用蟻群優化算法將螞蟻放置在目標電路網絡的輸入節點處；

步驟四：根據目標電路網絡中相鄰節點之間的連接信息，獲得與螞蟻當前所在節點連通的所有節點，并按概率原則在該所有節點中，選擇概率最大的節點作為螞蟻將要到達的下一個節點；

步驟五：判斷步驟四獲得的下一個節點是否為指定輸出節點，是則執行步驟六，否則返回步驟四；

步驟六：將螞蟻從輸入節點至指定輸出接點之間走過的路徑作為待選擇的通路。

在步驟六之后，本發明所述的方法中還包括以下步驟：令迭代次數k的初始值為1，

步驟A：根據關鍵度公式更新信息素，將更新后的信息素分配到精英螞蟻走過的路徑上，重復步驟三至步驟六，并將獲得的通路作為第k次迭代結果；

步驟B：將步驟A獲得的第k次迭代結果中螞蟻走過的節點數目與步驟六獲得的通路中螞蟻走過的節點數目進行比較，將節點數目多的通路作為當前備選結果；

步驟C：令k＝k+1，重復執行步驟A，將第k次迭代結果中螞蟻走過的節點數目與當前備選結果中螞蟻走過的節點數目進行比較，并將節點數目多的通路作為更新后的當前備選結果，并記錄該結果；

步驟D：判斷i的值是否大于2；是則執行步驟E；否則返回執行步驟C；

步驟E：判斷相鄰三次更新后的當前備選結果是否相同，是則將該更新后的當前備選結果作為最優路徑，否則返回執行步驟C。

本發明所述的基于關鍵節點選擇和蟻群優化算法的大規模集成電路小時延故障測試通路選擇方法，通過使用關鍵節點選擇來優化蟻群優化算法的搜索時間，進而快速選擇出小時延缺陷測試通路，使搜索時間減少為原時間的20％至25％。不僅降低了時間復雜度，也降低了空間復雜度。適用于在大規模集成電路小時延故障測試通路的選擇。

附圖說明