[發明專利]一種逃逸布線方法

有效

• 申請號: 201711211561.6
• 申請日: 2017-11-28
• 公開（公告）號: CN107992666B
• 公開（公告）日: 2020-08-04
• 發明（設計）人: 姚海龍;翁家翌
• 申請（專利權）人: 清華大學
• 主分類號: G06F30/398
• 分類號: G06F30/398
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

1.一種逃逸布線方法，其特征在于，包括：

S1，基于設定目標布線區域劃分規則，將目標布線區域劃分為若干布線子區域；

S2，設定基于備選連線起點和連線終點的目標布線區域起止點布線規則，以及基于所述目標布線區域內行和列的行列布線規則，所述連線起點表示所述目標布線區域內部的目標布線點，所述連線終點表示所述目標布線區域的邊緣控制引腳；

S3，設定各所述布線子區域內部目標布線點的內部布線規則，以及與所述目標布線區域的中軸線距離在設定范圍內的目標布線點的分界點布線規則；

S4，設定基于所述目標布線區域的整體布線規則；

S5，確定相鄰通道間距擬合公式，并通過最小化所述相鄰通道間距擬合公式，結合所述目標布線區域起止點布線規則、所述目標布線區域內行和列的行列布線規則、所述布線子區域內部目標布線點的內部布線規則、所述與所述目標布線區域的中軸線距離在設定范圍內的目標布線點的分界點布線規則和所述目標布線區域的整體布線規則，獲取最終布線方案；

S6，基于所述最終布線方案，在所述目標布線區域進行布線。

2.根據權利要求1所述的方法，其特征在于，所述S1的步驟進一步具體包括：

S11，根據所述目標布線區域的垂直中軸線和水平中軸線，將所述目標布線區域劃分為四個所述布線子區域；

S12，利用基于連線起點所在行數、連線起點所在列數、所述目標布線區域內目標布線點的總行數和所述目標布線區域內目標布線點的總列數的設定劃分規則，將所述連線起點劃分到對應的布線子區域。

3.根據權利要求1或2所述的方法，其特征在于，步驟S2中設定的所述起止點布線規則進一步具體包括：

S21，設定起止點函數為Rule-1(S′,T)，其中S′表示當前備選連線起點坐標，T表示連線終點坐標；函數Rule-1(S′,T)用于建立一條布線路徑以連接S′和T，或者用于求出更優的連線起點S；

S22，基于所述當前備選連線起點坐標和所述連線終點坐標，確定布線主方向和輔方向，布線方向與x軸平行或與y軸平行；其中，所述主方向為所述當前備選連線起點到連線終點所在邊緣的方向，所述輔方向垂直于所述主方向；

S23，以連線終點為起始點，若布線方向的反方向上無障礙物，且當前位置與S′不共線，則向所述輔方向的反方向移動一格；否則，若所述主方向的反方向上無障礙物，則沿所述主方向的反方向移動一格，直至當前連線起點S是未被連接的，函數Rule-1(S′,T)返回連線起點S；否則返回布線失敗。

4.根據權利要求3所述的方法，其特征在于，步驟S2中設定的所述行列布線規則進一步具體包括：

S24，設定行列函數為Rule-2(flag,n,lim,δ)，其中，flag＝Col表示處理列的情況，flag＝Row表示處理行的情況，n表示要處理的備選連線起點所在的行或列，lim表示最多能處理的連線起點的個數，δ取值0或1，表示是否要取反向；

S25，計算待布線連線終點對應的坐標T_l和T_r，其中，T_l表示靠近原點一側未被連接的連線終點，T_r表示遠離原點一側未被連接的連線終點；

S26，在所述目標布線區域內，按由外向內的順序依次布線；若第i個點S_i滿足(i+δ)為奇數，則調用函數Rule-1(S_i,T_l)，且T_l向原點方向移動一格；否則調用函數Rule-1(S_i,T_r)，且T_r向遠離原點方向移動一格；直至滿足至少一個以下終止條件：

I.ilim；

II.S_i已經被連線；

III.T_l或T_r已經被連線。