[發明專利]基于交錯型引腳結構的等長差分對逃逸布線方法

有效

• 申請號: 201410123077.8
• 申請日: 2014-03-28
• 公開（公告）號: CN103902772B
• 公開（公告）日: 2017-01-18
• 發明（設計）人: 董社勤;王華溪;王侃
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京思海天達知識產權代理有限公司11203
• 代理人: 樓艮基

1.一種基于交錯型引腳結構的等長差分對逃逸布線方法，其特征在于，是在計算機中依次按以下幾個步驟實現的：

步驟（1），計算機初始化，設定以下變量及參數：

差分對，是指差分對信號的兩個交錯型引腳，以下簡稱引腳，兩個引腳連接出來的信號線要先匯聚到一起，然后再作為一個整體向引腳陣列的外框傳輸，此外，差分對信號要滿足等長約束，就是從兩個引腳出來的信號線到匯聚點的長度要相同；

布線網絡單元：呈六邊形結構，由彼此相鄰的節點相連而成，所有的布線網絡單元組成布線網絡；從每個引腳開始布線，先連接到最近的一個布線節點，所述布線節點是指以每三個相鄰的引腳構成的三角形的中心點，再通過布線網絡連接到芯片的邊框；

引腳六邊形：由每個引腳周圍最臨近的6個引腳連接組成，大小為1，由所述引腳六邊形單元中心的引腳向外擴展的引腳六邊形形狀相似，大小為1的倍數；

最小相鄰或相交引腳六邊形是指由兩個中心引腳向外擴展成的兩個引腳六邊形在發生重疊或者交叉時變長最小的引腳六邊形；

中間點，是差分對信號匯聚的節點，中間點的位置將影響等長約束條件以及總線長的大小，因此中間點的選擇至關重要；一對差分對的最小代價中間點就是它們之間的一個中間點，而這中間點到這差分對的兩引腳的曼哈頓距離是一樣而且是最短的；其中，布線的路徑是由線節點組成的；

設：差分對p的兩引腳a和b的坐標分別為和則根據所述兩個引腳a和b的不同位置，分別按以下情況查找：

若：則最小代價中間點位于引腳a和b中間的引腳c的上下布線節點；

若：與間的節點個數為非4的倍數，則最小代價中間點位于兩引腳a和b連線中間的兩個布線節點；

若：與間的節點個數為4的倍數，則最小代價中間點位于兩引腳a和b中間的引腳c周圍的4個布線節點；

若：最小相交六邊形的最小代價中間點為相交區域中的布線節點；

若：最小相鄰六邊形相鄰邊完全重合，最小代價中間點為重合邊兩側的布線節點；

若：最小相鄰六邊形相鄰邊不完全重合，最小代價中間點為重合部分兩側的布線節點加上兩側都與最小相鄰六邊形相鄰的兩個布線節點；

步驟（2），找出一對差分對的所有最小代價中間點，從中找出從一個引腳經過中間點到另一引腳的所有的最短路徑，定義為引腳間候選路徑；

步驟（3），按以下步驟劃分布線區域：

步驟（3.1），針對每個引腳對，劃出引腳對的布線區域，該布線區域是指以此引腳對為對角線的四邊形區域；

步驟（3.2），根據每個引腳對的布線區域的交疊情況，將引腳對劃分為不同的組，方式如下：

步驟（3.2.1），對于布線區域重疊或相交的兩個引腳對，劃分為同一組，對于與其他引腳對的布線區域無相交的引腳對，獨自作為一個組，劃分的組稱之為引腳對組；

步驟（3.2.2），如果某一引腳對組中差分對的個數大于用戶定義的數量N_max，則把這組分割成更小的組，方式如下：

對于每對引腳對組G里的差分對p，如果p至少有一條引腳間候選路徑沒有與其他布線范圍相交，就把p和其相應的引腳到引腳路徑從G中移除，并將p中的所有引腳間候選路徑中與其他布線范圍存在相交的候選路徑刪除，將修改后的p單獨組成一組，并重復這一過程直至差分對數量少于N_max或者再也沒有差分對從G中移除；

步驟（4），按以下步驟確定每個差分對最終選擇的中間點以及通過中間點的最短路徑：

步驟（4.1），設定G_k為一個差分信號組，含有α_k條差分信號，對于每一條差分信號i，有n_ki條引腳間候選路徑；

對任何一條差分信號i，分配有且僅有一條引腳間路徑，表示為：

Σp=1nkixip=1,1≤i≤ak,1≤p≤nki]]>?????公式（1）

x_ip表示差分對信號i是否選擇了第p條路徑作為布線方案，x_ip=1表示差分對i選擇了第p條候選路徑；表示差分信號i只選擇n_ki中的一條作為布線方案；

步驟（4.2），設用PCC_k表示G_k中所有出現交叉的引腳間候選路徑集合，那么對于任意兩條出現交叉的路徑path_ip和path_jp，只能存在一條，因此x_ip和x_jp需要滿足：

x_ip+x_jq≤1，(ip，jq)∈PCC_k?????公式（2）

步驟（4.3），確定目標函數為：

MinΣi=1akΣp=1nkixip·lp]]>?????公式（3）

l_p表示路徑p的長度，表示所有α_k個差分對信號所選擇的路徑之和最小；

步驟（4.4），求解步驟（4.3）中所述的整數線性規劃問題，得到滿足優化需求的各差分對信號的中間點以及引腳到中間點的最短路徑，如出現多條可以滿足的解，則選擇中間點距離邊框最近的作為最終解；

步驟（5），按以下步驟進行中間點到邊框的逃逸布線路徑的選擇

步驟（5.1），更新布線網絡，將在步驟（4）中用過的布線節點從網絡中去掉；

步驟（5.2），建立布線網絡流圖，圖中節點表示沒有被最短引腳間路徑占據的布線節點，圖中的邊連接兩相鄰的布線節點，容量為1，代價為1；

步驟（5.3），新增一個源點s和匯點t，用容量為1和代價為0的從源點s流出的有向邊連接源點s和所有的中間點，并用容量為1和代價為0的流入匯點t的有向邊連接靠近芯片邊框的布線節點和匯點t；

步驟（5.4），建立下述整數線性規劃模型，找出所有中間點可能到達芯片邊框時的最短路徑：

Σeij∈Ef(eij)·l(eij)]]>?????公式（4）

e_ij表示布線節點i到節點j的邊，E為所有邊e_ij的集合，f(e_ij)表示邊e_ij上的走線數量，為整形變量，l(e_ij)表示邊e_ij的長度；目標函數表示：圖中所有從中間點到邊框節點的布線路經的總長度；

約束條件如下：

Σeij∈Ef(eij)=1,∀i∈MP]]>?????公式（5）

Σeij∈Ef(eij)=|MP|,∀i∈s]]>?????公式（6）

Σeij∈Ef(eij)=|MP|,∀j∈t]]>?????公式（7）

Σeij∈Ef(eij)=Σejk∈Ef(ejk),∀j∈T]]>?????公式（8）

f(eij)≤c(eij),∀eij∈E]]>?????公式（9）

f(eij)≥0,∀eij∈E]]>?????公式（10）

MP表示中間點的集合，s表示添加源點，t表示添加的匯點，T表示所有布線節點集合，E則表示所有布線網絡邊的集合，c(e_ij)表示邊e_ij容許的走線數量；公式（5）所有邊e_ij上無交叉的布線；公式（6）表示以源點s為出度的邊e_ij的總數為|MP|，|MP|為中間點的個數；公式（6）表示以源點t為入度的邊e_ij的總數為|MP|；公式（8）表示任意一個布線節點的入度等于出度，即滿足流量守恒；公式（9）表示每條邊e_ij上容許的走線數量不超過給定的容量；公式（10）表示每條邊e_ij走線數量非負；

步驟（5.5），求解這個整數線性規劃問題，得到從中間點到邊框的逃逸布線方案。