[發明專利]基于拓撲優化和啟發式搜索的總體布線方法

有效

• 申請號: 202010559386.5
• 申請日: 2020-06-18
• 公開（公告）號: CN111814420B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 劉耿耿;朱偉大;黃輝煌;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/394
• 分類號: G06F30/394
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 陳明鑫;蔡學俊

本發明涉及一種基于拓撲優化和啟發式搜索的總體布線方法，包括以下步驟：步驟S1:根據結合Prim和分治法的混合拓撲優化策略為每個線網構建拓撲結構；步驟S2:根據得到的每個線網構建拓撲結構，基于引腳的連接情況將其分解成一系列兩端線網；步驟S3:對每個線網使用L型布線,并按擁塞程度識別出最擁塞的區域；步驟S4:對擁塞區域內所有的兩端線網使用同時考慮擁塞程度和線長的啟發式搜索算法；步驟S5:判斷所有處理后的兩端線網，是否還存在溢出；步驟S6:若存在溢出的兩端線網，則進一步采用只考慮擁塞的啟發式搜索算法處理后輸出布線結果；若不存在則直接輸出布線結果。本發明能夠構建一個優質的拓撲結構，減少擁塞程度和溢出數。

技術領域

本發明涉及超大規模集成電路設計領域，具體涉及一種基于拓撲優化和啟發式搜索的總體布線方法。

背景技術

隨著超大規模集成電路技術(VLSI)的成熟發展，芯片的集成程度越來越高，其中所包含的電路元器件越來越多，電路的邏輯結構也更加復雜，因此電路的物理設計變得更為重要。同時，在整個流程中，布線階段所消耗的時間又占有很大的比重。因此，性能優越的布線算法對尋找優質的布線方案和縮減整個VLSI設計流程的耗時都是非常重要的。

VLSI的物理設計過程被分為以下幾個步驟：電路劃分、布圖規劃、布局和布線。隨著設置尺寸的縮小，芯片的互連變得更加復雜，從而布線成為了整個物理設計中極其重要的一個環節。由于問題的復雜性，布線通常可以分為兩個步驟：總體布線和詳細布線。總體布線將布線區域建模成一個具有容量限制的粗粒度網格圖，線網在該網格圖上實現互連。詳細布線則在總體布線結果的引導下，找到線網中各引腳確切的布線解決方案。總體布線的結果決定詳細布線的質量，從而最終影響芯片區域的時序，功率和密度。因此，總體布線是芯片設計流程中非常重要的階段。

發明內容

有鑒于此，本發明的目的在于提供一種基于拓撲優化和啟發式搜索的總體布線方法，根據線網特點，高效地為每個線網構建一個優質的拓撲結構，從而減少擁塞程度，實現減少溢出數。

為實現上述目的，本發明采用如下技術方案：

一種基于拓撲優化和啟發式搜索的總體布線方法，包括以下步驟：

步驟S1:根據結合Prim和分治法的混合拓撲優化策略為每個線網構建拓撲結構；

步驟S2:根據得到的每個線網構建拓撲結構，基于引腳的連接情況將其分解成一系列兩端線網；

步驟S3:對每個線網使用L型布線,并按擁塞程度識別出最擁塞的區域；

步驟S4:對擁塞區域內所有的兩端線網使用同時考慮擁塞程度和線長的啟發式搜索算法；

步驟S5:判斷所有處理后的兩端線網，是否還存在溢出；

步驟S6:若存在溢出的兩端線網，則進一步采用只考慮擁塞的啟發式搜索算法處理后輸出布線結果；若不存在則直接輸出布線結果，所述布線結果即為最優布線方案。

進一步的，所述結合Prim算法和分治法的混合拓撲優化策略具體為：設給定線網中的待布線節點數量為x，引入引導因子n，若x≤n，則該線網使用Prim算法進行布線，否則使用中的基于分治法的RMST構建算法進行布線。

進一步的，所述Prim算法進行布線具體為使用基于節點選擇的Prim算法生成線網的拓撲結構。

進一步的，所述基于分治法的RMST構建算法進行布線具體為：運用分治算法剔除若干邊，將原圖里的|V|*(|V|?1)/2條邊減少到O(|V|)條較為分散的邊，然后調用最小生成樹構建算法生成RMST。