[發明專利]大規模集成電路設計中基于線長最短優化的繞障布線方法有效
| 申請號： | 201410036947.8 | 申請日： | 2014-01-26 |
| 公開（公告）號： | CN103984789B | 公開（公告）日： | 2017-01-25 |
| 發明（設計）人： | 張浩;葉東毅;陳羽中;余春艷;張棟;楊晶菁 | 申請（專利權）人： | 福州大學 |
| 主分類號： | G06F17/50 | 分類號： | G06F17/50 |
| 代理公司： | 福州元創專利商標代理有限公司35100 | 代理人： | 蔡學俊 |
| 地址： | 350108 福建省福州市*** | 國省代碼： | 福建;35 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 大規模 集成電路設計 基于 線長最短 優化 布線 方法 | ||
1.一種大規模集成電路設計中基于線長最短優化的繞障布線方法，其特征在于，首先根據逃逸圖理論構建布線問題布線圖，然后采用多源并發探索方法選擇頂點標記為必經點，再基于必經點集合構建一個可行解Steiner樹，最后優化可行解。
2.根據權利要求1所述的大規模集成電路設計中基于線長最短優化的繞障布線方法，其特征在于，包括以下步驟：
步驟(1)?初始化，輸入布線問題的線網信息和障礙信息；
步驟(2)?根據線網信息和障礙信息，構造逃逸圖G=(V,E,T,ω)；所述逃逸圖為帶權無向圖，E表示邊集合，V?表示頂點集合，引腳對應的頂點稱為端點，T表示端點集合，???????????????????????????????????????????????表示邊的權重映射函數，邊的權重對應邊在布線區域的實際線長；
步驟(3)?采用多源并發探索方法標記必經點，得到必經點集合PV；
步驟(4)?將必經點集合和端點集合的并集PV∪T中頂點都看成端點，使用Steiner樹構造方法構建一個可行解ST；
步驟(5)?優化可行解ST。
3.根據權利要求2所述的大規模集成電路設計中基于線長最短優化的繞障布線方法，其特征在于，所述步驟(3)中，所述必經點是指期望在構造可行解時經過這些頂點，所述多源并發探索方法包括以下步驟：
步驟(3.1)?初始化過程：用端點集合中各個端點分別構成一個頂點集，并分別作為泰森圖種子也即源點，每個泰森圖種子設置為未標記狀態；
步驟(3.2)?擴展過程：從多個未標記的泰森圖種子出發構建泰森圖，記錄遍歷過程中得到的橋邊，每輪擴展過程頂點遍歷范圍為當前找到橋邊的最小跨度Range，即對當前遍歷頂點u有u.dist?≤?Range，否則進入回溯過程；
步驟(3.3)?回溯過程：從所有遍歷到的橋邊中選出跨度最小且相應泰森圖種子Si和Sj都未標記的一組主橋邊MBs(Si,Sj)，以每個主橋邊上的每個頂點為當前點，采用回溯法遍歷Si和Sj之間的所有最短路徑，每條最短路徑的兩端頂點都添加到必經點集合PV中，該些最短路徑上的所有頂點構成頂點集SPSij，進入更新過程；
步驟(3.4)?更新過程：頂點集Si、Sj和SPSij中所有頂點構成一個新的泰森圖種子Sn，使用Sn替代Si和Sj，Sn設置為標記狀態，繼續執行回溯過程，直到所有的泰森圖種子都為標記狀態；
步驟(3.5)?清除所有泰森圖種子的標記，重復執行步驟(3.2)-?(3.4)，直到只剩下一個泰森圖種子；
所述多源并發探索方法中，用橋邊B(u,v)表示連接兩個鄰接泰森域的邊e(u,v)，橋邊的跨度B(u,v).span由公式計算得到，其中u.dist表示頂點u到所屬泰森域對應的泰森圖種子的最短路徑的總權重；兩個泰森域之間的一組主橋邊MBs(Si,Sj)是指兩個泰森域之間所有橋邊中跨度最小的橋邊集合，Si和Sj表示這兩個泰森域對應的泰森圖種子。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于福州大學，未經福州大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201410036947.8/1.html，轉載請聲明來源鉆瓜專利網。
