一個快速的集成電路可布性分析方法
2023-05-22 09:32:51 1
專利名稱：一個快速的集成電路可布性分析方法
技術領域：
集成電路計算機輔助設計(IC CAD)領域，尤其涉及標準單元(SC)總體布線領域。
背景技術：
在傳統計算機輔助IC設計的流程中，當完成布局、布線後，通過反饋走線密度信息給布局/布線器，可以通過拆線重布來一定程度上解決布線擁擠問題。然而，如果拆線重布過程仍然解決不了擁擠，設計者則不得不修改已有的布局。上述傳統設計流程的問題在於，在布線之後才去獲取最後的擁擠信息，而布線過程已接近設計尾聲，又是一個非常耗時的過程，因此，如果修改已有的布局，意味了大部分的設計過程需要重做。
不難想像，如果在設計流程的較早階段便可快速獲取準確的擁擠信息，有助於指導布局/布線的進行，從而提前預見擁擠問題，並在它真正出現前就採取有效的處理措施。因此，如果修改傳統流程，在布圖過程中加入快速有效的功能模塊，針對布局結果進行有效的擁擠評估，以作為布局的反饋信息，並指導後續的布線工作。這就避免了當後續布線最後無法完成時，再回到前面布局階段進行重新改進的情況，從而使整個設計能夠在合理的時間裡完成，並減少整個物理設計中不必要的迭代。像這樣，能快速有效地針對布局結果進行擁擠評估，反饋給布局並指導後續的布線工作，我們稱之為可布性分析，完成可布性分析的功能模塊稱之為可布性分析器。
在已報導和所能查閱到的國內外相關研究中，關於「針對布局後的擁擠估計的方法」的研究情況可列舉、分析、總結如下在介紹擁擠估計的方法之前，首先介紹一下擁擠的估計的意義。
文獻[P.N.Parakh，R.B.Brown and K.A.Sakallah，」Congestion Driven Quadratic Placement」，Design Automation Conference，pages 275-278，1998.][M.Wang，X.Yang，K.Egoru andM.Sarrafzadeh，「Multi-center congestion estimation and minimization during placement」，Intemational Symposium on Physical Design，pages 147-152，2000.]將擁擠信息用於改進布局質量，[Olivier Coudert，Jason Cong，Sharad Malik，Majid Sarrafzadeh，「INCREMENTAL CAD，」ICCAD 2000，pp.236-243]將擁擠信息作為反饋來進行增量式布局，文獻[R.T.Hadsell andP.H.Madden，「Improved Global Routing through Congestion Estimation」，Design AutomationConference，pages 28-31，2003.][J.Cong and P.H.Madden，「Performance Driven Multi-LayerGeneral Area Routing tot PCB/MCM Designs」，Design Automation Conference，pages 356-361，1998.][Jinjun Xiong，Lei He，「Probabilistic Congestion Model Considering Shielding for CrosstalkReduction，」ASP-DAC 2005 pp.739-742.][T.Jing，X.L.Hong，H.Y.Bao，et al，「SSTTEfficientLocal Search for GSI Global Routing」，J.Comput.Sci. Technol.，2003，18(5)pp.632-639.]將擁擠估計的信息用於改進布線。而[H-M.Chen et al.，「Integrated Floorplanning and InterconnectPlannig」，International Conference on Computer Aided Design，pages 354-357，1999.][Y.Ma et al，「Dynamic global buffer planning optimization based on detail block locating and congestionanalysis」，Design Automation Conference，pages 806-811，2003.]在floorplanning中進行了擁擠驅動的優化。
通過對目前已報導和所能查閱到的國內外相關研究，關於布局後擁擠估計的方法大致可分為三類●實驗估計模型●布線器估計模型●概率估計模型實驗估計模型文獻[C.-L.E.Cheng，「RISAAccurate and efficient placement routability modeling，」in Proc.Int.Conf.Computer-Aided Design，June 1994，pp.690-695.]利用了大量實驗得出的走線分布圖(WDMwire distribution map)來進行擁擠估計；[M.Wang and M.Sarrafzadeh，「On the behaviorof congestion minimization during placement，」in Proc.Int.Symp.Physical Design，Apr.1999，pp.145-150.]也利用了一種實驗得出的擁擠估計模型。
這種模型，雖然能夠對擁擠度進行快速估計，但是由於它們是實驗得出的模型，因此它們對例子的特性依賴過強，某種程度上，可能會喪失擁擠估計的客觀性。
布線器估計模型文獻[S.Mayrhofer and U.Lauther，「Congestion-driven placement using a newmultipartitioning heuristic，」in Proc.Int.Conf.Computer-Aided Design，Nov.1990，pp.332-335.][P.N.Parakh，R.B.Brown，and K.A.Sakallah，「Congestion driven quadratic placement，」in Proc.35th Design Automation Conf.，June 1998，pp.275-278.][R.S.Tsay，S.C.Chang，and J.Thorvaldson，「Early wireability checking and 2-D congestion-driven circuit placement，」in Proc.5th Annu.IEEE Int.ASIC Conf.and Exhibit，Sept.1992，pp.50-53.]採用了簡化的總體布線器來估計擁擠。
這種模型，雖然使用了經過簡化的總體布線模型，但是往往會面臨在準確性和效率上的取捨問題。另一方面，由於不同的簡化總體布線器的布線策略和繞線能力不同，而可能導致不同的簡化總體布線器對擁擠度的估計產生不同的結果。而且，簡化的擁擠估計的布線器，可能會與隨後的真正布線器的結果發生不一致的情況。
概率估計模型文獻[J.Lou，S.Krishnamoorthy and H.S.Sheng，「Estimating Routing Congestion usingProbabilistic Analysis」，International Symposium on Physical Design，pages 112-117，2001.][H-M.Chen et al.，「Integrated Floorplanning and Interconnect Plannig」，InternationalConference on Computer Aided Design，pages 354-357，1999.]則為了更好滿足客觀性和一致性方面的要求，提出的概率估計的方法。前者，使用了經典的組合模型(格路模型)，來求解線網走線的分布情況(與實驗估計模型不同)。後者，則是在只考慮簡單的L型和Z型線網的前提下，對線網的走線分布進行概率的估計(結合了一些經驗的估計)。
此模型，能夠較快速地對布局後的結果進行擁擠分析，擁擠估計值和實際布線後的情況有較好的吻合，並且能夠保持良好客觀性和一致性。
然而，[J.Lou]概率估計模型局限在於，採用組合概率模型在邊界框(bounding box)內所有可能路徑上平均分布走線，導致分數解，故而無法得到線網精確的走線情況。而同時，對於兩個引腳在同一行或列上的情況，單純的組合模型限制了它們選擇其他可能路線的空間。針對上述局限，我們提出了新的基於概率模型的估計算法。首先，利用邊界框進行擁擠度的預估，對於兩點共線的線網分布，採用擴展的邊界框(extended bounding box)允許一定程度的合理繞線，從而能夠繞過附近的過於擁擠的區域。最後在概率指導下進行實際快速布線，不使用任何迭代和優化(避免擁擠估計的不一致和客觀性)。在預估擁擠度的指導下，我們以擁擠度的反比，作為隨機走線的選擇概率來進行實際布線。這樣，可以使得各個可選範圍內的路徑上經過的走線數目在概率上趨於均勻，從而在局部小範圍內，避免出現一部分發生高度擁擠，而另一鄰近部分則比較疏鬆的不合理的擁擠估計情況。
已進行過「新穎性檢索」，檢索報告見附件2。
發明內容
本發明的目的在於提出一種快速的集成電路可布性分析方法。本發明的總體思路是通過快速完成估計擁擠，使可布性分析方法能夠服務於增量式布局或者指導布線，從而縮短整個物理設計的周期。本發明即可布性分析方法，首先，我們擴展了現有的一種概率估計模型的技術，對問題的模型進行擁擠的預估計。其中，主要針對兩個引腳處於同一行或列上的估計方法，利用本發明提出的擴展邊界框(extended bounding box)的技術進行了改進。然後，對所有的線網利用預估擁擠信息並在概率的指導下，進行了本發明提出的快速的布線。為了保證可布性分析方法的客觀性和一致性，此布線被限制在邊界框中並且沒有任何迭代和擁擠優化。這一步目的是為了使可布性分析方法得到更加精確和有實際意義的擁擠估計。
本發明的總體流程圖如圖1所示。
本發明的特徵在於，它依次包含如下步驟步驟1初始化並建立總體布線圖步驟1.1計算機讀入在一個多層布線晶片上劃分總體布線單元GRC網格所必需的行數Nrow、列數Ncol；步驟1.2求GRC的對偶圖以GRC中每個網格的中心為新的頂點，重連接各相鄰網格的中心點形成新的邊，從而得到總體布線圖GRG；步驟1.3在步驟1.1所述的多層布線晶片上，以晶片中心為原點建立笛卡兒平面直角坐標系，並把各個布線層投影到該坐標平面上；步驟1.4標記步驟1.2中所述各新頂點的坐標為vrow，col(x，y)，並把這些新頂點的集合記為V，其中row，col分別代表該新頂點所在GRG的行和列，x，y是步驟1.3所建坐標平面的坐標；步驟1.5為所述GRG頂點vrow，col以及連接每兩個相鄰頂點的GRG邊ek分別編號，頂點用公式(row-1)×Ncol+col-1編號，邊ek則先按行從下向上從左向右編號，再按列從左向右從下向上排號；步驟1.6計算機讀入每條GRG邊ek的容量ck，給邊ek的通道使用量λk賦初始值為0；步驟2計算機讀入表徵電路詳細的連接的網表步驟2.1讀入電路中線網的總數Mnet；步驟2.2計算機對每一條線網執行步驟2.2.1讀入線網的源點s和漏點集T；步驟2.2.2把線網的源點s和漏點集T中所有點，映射到所述GRG的各頂點上，並用頂點編號對該點標記；步驟2.2.3按讀入順序，為每條線網編號；步驟3拆分所述線網中的多端線網，但兩端線網保持原狀；對於每一條多端線網執行如下操作利用Prim算法求得曼哈頓距離下的最小生成樹來劃分兩引腳端，形成按兩引腳段劃分順序所構成的兩引腳段序列，從而把一個多端線網劃分成為一個兩引腳段序列，所述的兩引腳段是指該多端線網的頂點集合中，由相距近的兩點構成的點對集合，在由該點對構成的路徑上不存頂點集合的其它點；步驟4預估計GRG各邊的走線概率；步驟4.1設定GRG每條邊ek所對應的走線概率值pk的初始值為0；步驟4.2對每條兩端線網或多端線網的每個兩引腳段做如下操作步驟4.2.1若兩個引腳u，v分別處於GRG圖的左下角和右上角的位置，u為左下角引腳，v為右上角引腳；如圖3所示，以u作為原點建立參考用笛卡兒平面直角坐標系，橫軸以列為單位，並以水平向左為正方向，若經過m段水平網格，縱軸以行為單位，以垂直向上為正方向，若經過n段垂直網格，點v(m，n)處於第I象限，原點為u(0，0)，以u(0，0)，v(m，n)為對頂點構成矩形框稱為為邊界框u-v，從u點到v點任何一條可能路徑的長度等於邊界框u-v的半周長；從而，按下式得到經過邊界框u-v裡某條設定水平邊AB(B點在A點右面)或垂直邊AC(C點在A點的上面)的走線概率經過水平邊AB的走線概率為Pk1＝H(x，y)/T(m，n) 0≤x≤m-1，0≤y≤n，其中，T(m，n)表示從u(0，0)出發到點v(m，n)間可能存在的路徑數，表達式為T(m,n)=(m+n)!m!n!,m>0,n>0;]]>H(x，y)表示從原點u(0，0)出發到點A(x，y)，並經過以點A(x，y)為左端點的某一特定水平邊AB的路徑數，用下式表示H(x，y)＝T(x，y)T(m-x-1，n-y)，0≤x≤m-1，0≤y≤nT(x，y)表示從原點u(0，0)到點A(x，y)間可能存在的路徑數，按下式得出T(x,y)=(x+y)!x!y!,x>0,y>0,]]>T(m-x-1，n-y)表示從點B(x+1，y)出發到點v(m，n)間可能存在的路徑數，用下式表示T(m-x-1,n-y)=[(m-x-1)+(n-y)]!(m-x-1)!(n-y)!,m>x+1,n>y;]]>經過垂直邊AC的走線概率為Pk2＝V(x，y)/T(m，n)，0≤x≤m，0≤y≤n-1，
其中，V(x，y)表示從原點u(0，0)出發到點A(x，y)間經過以點A(x，y)為下端點的某一特定垂直邊AC的路徑數，用下式表示V(x，y)＝T(x，y)T(m-x，n-y-1)，0≤x≤m，0≤y≤n-1，其中，T(m-x，n-y-1)表示從點C(x，y+1)出發到達點v(m，n)間可能存在的路徑數，用下式表示T(m-x,n-y-1)=[(m-x)+(n-y-1)]!(m-x)!(n-y-1)!,m>x,n>y+1,]]>再把所得的Pk1，pk2分別累加到邊AB，AC上的走線概率，k1，k2分別為邊AB，AC的編號；步驟4.2.2若兩個引腳u，v分別處於GRG圖的右下角和左上角的位置，u為右下角引腳，v為右上角引腳；則以右下角的引腳u作為原點建立參考用笛卡兒平面直角坐標系，橫軸以列為單位，並以水平向左為正方向，若向左經過m*段水平網格，縱軸以行為單位，以垂直向上為正方向，若經過n*段垂直網格，點v(m*，n*)處於第I象限，原點為u(0，0)，以u(0，0)，v(m*，n*)為對頂點構成矩形框稱為為邊界框u-v，從u點到v點任何一條可能路徑的長度等於邊界框u-v的半周長；從而，按照步驟4.2.1中的方法計算經過邊界框u-v裡某條設定水平邊AB(B點在A點左面)或垂直邊AC(C點在A點的上面)的走線概率，其中，只要把步驟4.2.1中的公式裡的m，n分別換成m*，n*即可；最後，再把所得的Pk1，Pk2分別累加到邊AB，AC上的走線概率，k1，k2分別為邊AB，AC的編號；步驟4.2.3若兩個引腳u，v分別處於GRG圖的同一行或列時，稱兩引腳點為平點對，以一個引腳為原點建立參考用笛卡兒平面直角坐標系，並使另一個引腳落在橫軸或縱軸的正半軸，當處於同一行，另一個引腳落在橫軸的正半軸，當處於同一列，另一個引腳落在縱軸的正半軸，然後，用擴展邊界框估計法，按下面方法計算邊ek上的相應走線概率步驟4.2.3.1按照下面方法建立擴展邊界框使同一行(列)的平點對的邊界框，向垂直(水平)方向各擴展一行(列)；步驟4.2.3.2在邊界框內，在邊界框擴展方向上，最多最允許一次背離所述兩引腳u，v所處的同一行或列的條件下，按下式計算經過的點(x，y)為左端點的某一特定的水平邊的走線概率pk1和計算經過點(x，0)向上或向下的垂直邊的走線概率pk2當u，v處於同一行時，如圖4所示，Pk1＝H*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，其中，m』為點u，v間的列數，F(m』)表示在擴展邊界框u-v中從u到v的可能路徑數，按下面公式計算F(m』)＝m』2+m』+1，m』是u和v之間相隔的列數，H*(x，0)表示從點u(0，0)到點(x，0)間經過以該點(x，0)為左端點的水平邊的可能路徑數目，用下式計算H*(x，0)＝F(x)+F(m′-x-1)-1，0≤x≤m′-1，H*(x，±1)表示從點u(0，0)到點(x，±1)間經過以該點(x，±1)為左端點的水平邊的可能路徑數目，用下式計算H*(x，±1)＝(x+1)(m′-x)，0≤x≤m′-1，其中，F(x)表示在擴展邊界框u-v中從u到(x，0)的可能路徑數，表達式為F(x)＝x2+x+1，F(m′-x-1)表示在擴展邊界框u-v中從(x+1，0)到v(m』，0)的可能路徑數，表達式為F(m′-x-1)＝(m′-x-1)2+(m′-x-1)+1；Pk2＝V*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，其中，m』為點u，v間的列數，V*(x，0)表示從u(0，0)到點(x，0)，並經過與點(x，0)向上(或向下)所連的垂直邊的路徑數，用下列表達式計算V*(x，0)＝m′，0≤x≤m′，當u，v位於同一列時，設u，v之間的行數為m」，將上述表達式中m』的值用m」代入便計算出相應的pk1，Pk2，然後，再將Pk1，Pk2累加到各邊對應的pk上，k1，k2分別為各邊的編號；步驟5快速布線步驟5.1對每一條線網進行布線，流程圖參見圖5，具體操作如下步驟5.1.1讀入用Prim算法劃分後，並按劃分順序標過序號的兩引腳段序列；
步驟5.1.2標記第一個兩引腳段中的任一個引腳點；步驟5.1.3從5.1.2中所指的引腳段開始，按標號順序依次對於兩引腳段序列中的每一個兩引腳段，執行下列操作步驟5.1.3.1檢查當前的兩引腳段的兩個引腳是否都被標記；步驟5.1.3.2如果是，那麼取下一個兩引腳段，並重新轉到步驟5.1.3.1；否則，將未標記的引腳作為起點，並執行下面步驟；步驟5.1.3.3將起點設為當前點u*，並對其標記被訪問過；步驟5.1.3.4按照邊界框布線的約定，找到與u*相鄰的兩個可行頂點集合Vp和兩條可行邊的集合Ep＝{ek1，ek2}，按如下方法選擇一條邊利用C/C++程式語言中公知的rand函數，通過rand/RAND_MAX產生
之間的隨機數，其中RAND_MAX是公知的被定義的rand產生隨機數的最大值；如上方法產生一個隨機數，如果這個隨機數不大於pk2ck1/(pk1ck2+pk2ck1)，那麼選擇與分子ck1對應的邊ek1，即i＝k1，否則選擇邊ek2，即i＝k2；步驟5.1.3.5將被選邊ei的另一個端點vi作為新的當前點u*；步驟5.1.3.6檢查當前點是否被標記，如果不是，則標記該點並依照步驟5.1.3.4的方法選擇下一個點；如果是，則記錄所有經過路徑；步驟5.2所有線網布好線後，對每條線網經過的邊的通道使用量λk累加1，統計每條邊上的使用量；步驟5.3計算各個邊的擁擠度值ηk＝λk/ck；步驟6輸出步驟6.1將擁擠估計結果和快速布線結果寫入Si2推出的工業界標準的資料庫平臺OpenAccess；步驟6.2輸出評測報告。
為了測試可布性分析算法的準確性與客觀性，我們將其與另外兩個擁擠估算相關方法進行比較。一個是現有的擁擠驅動的SSTT布線器[T.Jing，X.L.Hong，H.Y.Bao，et al，「SSTTEfficient Local Search for GSI Global Routing」，J.Comput.Sci. Technol.，2003，18(5)pp.632-639.]，能夠提供實際布線的結果以供比較。另一個是我們依現有技術[J.Lou，S.Krishnanioorthy，and H.S.Sheng，」Estimating routing congestion using probabilistic analysis，」inPTOC.Int.Symp.on Phgsacal Design，2001]實現的傳統的擁擠估計器，我們暫時稱為EOPA，它採用的是概率分析模型。我們採用了6個不同大小和擁擠程度的測試例子，如表1所示。實驗環境為具有3.0GHz CPU和4GB內存的Linux伺服器。所有測試的方法均使用了公知的[Andrew B.Kahng，Stefanus Mantik，and Dirk Stroobandt，「Toward accurate models of achievablerouting」IEEE Tran.Computer-Aided Design，vol.20，Issue 5，May 2001 pp.648-659.]中的資源估計方法輸出的結果。
我們使用FREe布線後的走線長度來近似估計每一個例子的線長的下界(如果我們能得出SMT，steiner minimal tree，那麼變能夠得到一個精確線長的下界)。於是我們定義minimumusage ratio(MUR)為FREe布線的總線長與
的比值，其中ce和le分別為邊e的容量和長度。於是，MUR可用來近似估計每一個例子的擁擠度值的下界，並依此較客觀地說明測試例子本身的擁擠情況。表2a)的第2列和第3列分別列出了MUR和估計的近似極小總線長，第4列，則給出了SSTT布線的總線長。
表1 測試例子的描述
在表2b)中的2，3和5列分別列出了EOPA，FREe和SSTT的運行時間。可見，EOPA和FREe作為專門的擁擠估計器，比實際擁擠驅動的布線器SSTT會快很多。這樣就能為布局提供比較快速的反饋。
我們對布好線網的晶片定義sigma為各個走線道擁擠度的標準差。即Sigma=eE(e-)2,]]>其中=1|E|eEe,]]>ηe為邊e的擁擠度值。
sigma可以用來反映布線後的擁擠區的分布情況，並可衡量GRG各邊上布線資源被使用的均勻程度。sigma的值越接近於零，說明布線資源利用得越均勻，布線的質量也就越好。
由於FREe和SSTT分別對線網進行了實際的布線，所以表2b)的4和6列分別給出了他們的sigma值。可以看出，FREe的sigma值和SSTT比較接近，但是略大於SSTT的sigma。說明，從某種程度上來講，繞線優化性能越好，布出的線會越均勻。但是，作為擁擠估計器，這樣的繞線優化擁擠會使它失去客觀評價的意義。所以，我們能夠在沒有過量的繞線和優化的基礎上，既保持了線長的近似極小，又能夠在這樣約束下達到布線資源較均勻地利用，從而較客觀、準確地評價了布局後的擁擠狀況，並且和SSTT結果有較好的一致性。
為了進一步能說明，FREe擁擠估計的能力。不失一般性，我們以u05614為例，分別給出了EOPA，FREe和SSTT的擁擠度圖，如圖6a)，b)，c)所示。可見，圖6b)和c)特徵比較相近，這正是由於擁擠預估概率指導下的快速布線能帶來和SSTT一致性較好的擁擠估計。與此同時，FREe又沒有失去其客觀性的要求。
表2實驗結果a)FREe和SSTT總的資源使用比較
Estimated Minimum Total Length是指由FREe布線後的總線長.
b)性能比較
比較圖6a)和b)可以看出，EOPA僅給出一些區域會產生平均意義上的擁擠，而FREe增加了實際布線後，便能精確的給出，究竟對應於GRG邊的那些區域在多大程度上會出現走線擁擠。
另外，FREe同時給出了擁擠估計後的詳細報告。其中包含水平邊和垂直邊分別的最大擁擠度值，以及水平邊和垂直邊分別的超容量的和，等等。
圖1本發明的總體流程圖。
圖2總體布線的示意圖。
圖3引腳處於左下角-右上角的兩引腳段u-v及其邊界框的坐標圖。
圖4平點對的兩引腳段u-v及其擴展邊界框的坐標圖。
圖5對單個線網布線的流程圖。
圖6測試例子u05614的擁擠度圖。
圖7例子u05614的GRG中的一個方框。
圖8例子u05614中control線網在GRG上的走線情況。
圖9例子u05614中m1/n7630線網在GRG上的走線情況。
圖10例子u05614中m2/n7766線網在GRG上的走線情況。
圖11例子u05614中線網在GRG上的走線情況(m1/U2∨mult1∨ADD1∨pog_array[2][32])。
具體實施例方式
首先，在我們抽象出的問題模型上，利用經典的Prim算法求得最小生成樹(MST)。並按照最小生成樹的樹枝生成的先後順序，將每個多端線網劃分成兩引腳段(two-pin section)序列。本身是兩端線網的，保持不變。其次，對於處於兩個引腳處於斜對角位置的兩端線網或引腳段利用現有的技術求出兩引腳之間的走線分布；對於處於同一行或列的兩個引腳，採用本發明提出的擴展的邊界框技術求出兩引腳之間的走線分布。它可以幫助其繞過過於擁擠的區域。然後，對所有的線網利用預估擁擠信息並在概率的指導下，進行了本發明提出的快速的布線。該布線技術不但可以避免布線擁擠，還可以使得各個可能路徑上經過的走線數目基本均勻。
對於目前IC設計中的多層布線技術，可布線區域不再是單元間的一條條的布線通道，而是一個完整的晶片平面。可採用網格方式，把整個晶片平面按行和列劃分為若干個稱為總體布線單元GRC的區域，然後生成GRC的對偶圖，即如圖2所示的總體布線圖GRG。GRG由Nrow×Ncol個節點和連接這些節點的邊構成。與GRCrow，col對應的節點vrow，col的坐標為GRCrow，col的中心點。連接兩節點vrow1，col1和vrow2，col2的邊稱為ek；lk表示兩節點vrow1，col1和vrow2，col2之間的曼哈頓距離，稱為ek的長度；ck表示ek的容量，表示兩節點vrow1，col1和vrow2，col2對應的兩個GRC之間能夠通過的線網的連線數。於是，線網中要連通的引腳點Pin就映射成為其所在的GRG中對應的一系列節點。這樣，擁擠估計便可形式化為在此模型上求解每一條GRG邊的容量被佔用的情況，並映射到對偶圖GRC的網格區域中的問題。另外，在這個過程中還要得到每個線網的布線樹。
本可布性分析方法的總體流程框圖如圖1所示。
為了實現，或者說是具體實施本項發明，我們給出以下關於發明實施的描述。
實施本發明的計算機系統本發明所設計的可布性分析方法要在一個具體的計算機系統上得以實施，該計算機系統具體描述如下一臺Linux工作站；Linux作業系統；Si2推出的工業界標準的資料庫平臺OA(OpenAccess)；標準C/C++程式語言；Vim編輯器、gcc/g++編譯和連結器、gdb調試工具等。
現在採用一個MCNC電路實例u05614作為本發明的一個實施例，結合本發明的算法，對其進行可布性分析。該例子的規模如下386個壓焊塊，32498個標準單元，36452個線網；GRC網格劃分205行，205列；
左下角點坐標(-82000，-82000)；右上角點的坐標(82080，82080)。
步驟1初始化並建立GRG打開資料庫OA，讀入在多層布線晶片上劃分GRC網格所必需的行數Nrow＝205，列數Ncol＝205。生成GRC的對偶圖GRG。
以晶片中心為原點建立坐標系，左下角點坐標為(-82000，-82000)，右上角點坐標為(82080，82080)。此時，GRG圖中共有42025個頂點。每個頂點都有一個對應的位置坐標(x，y)，例如左下角頂點v1，1(-81580，-81580)，其左邊頂點v1，2(-80760，-81580)，其上面頂點v2，1(-81580，-80760)，以及晶片右上角頂點v205，205(81660，81660)。可用vrow，col(x，y)表示各個頂點，其中row表示該點在GRG第幾行，col表示該點在GRG第幾列，(x，y)則表示在該坐標系位置。GRG上共有83640條邊。
為了能更好地說明問題，我們取以100行，100列的頂點為左下角的這個GRG上的方格，如圖7所示。如同邊一樣，每個頂點都有一個唯一的編號來標誌v50，100，v51，100，v51，101，v50，101的編號分別為10144，10349，10350，10145。連接四個頂點的邊的編號如圖7所示。
讀入布線資源。這樣，每條GRG邊便會有一個非負數作為該邊的容量。例如e1對應的容量c1＝15，e2對應的容量c2＝15，e83601對應的容量c83601＝9，最後一條邊e83640對應的容量c83640＝6。
仍考察圖7，其中各邊對應容量為c62066＝12，c10300＝15，c62270＝12，c10096＝15。
步驟2讀入網表從OA中讀出網表的坐標，並將落在某個GRC中的引腳，映射為該GRC的中心點坐標，即GRG的相應頂點，並用頂點的編號表示。該例子中共有線網數為Mnet＝36452，但1到257號線網為特殊線網在此設計流程中我們暫不做處理。下面枚舉幾個線網的情況258號線網源點編號為19967，38個漏點(26281，28537，28541，...，19517)。
36451號線網源點編號為21895，2個漏點(21889，21479)。
18355號線網源點編號為16977，2個漏點(16976，16990)。
36452號線網源點編號為21480，3個漏點(21476，21886，21890)。
步驟3多端線網拆分利用Prim的MST拆分算法結果如下258號線網共有39個引腳，被分為38個有序段。下面列舉幾個，並用引腳所對應的頂點的編號對依次表示。(19967，20371)，(20371，18732)，(18732，16881)，...，(8654，8228)，(8228，7206)分別為第1，2，3，...，37，38個兩引腳段。
36451號線網共有3個引腳，被分為2個有序段，依次為(21895，21889)，(21889，21479)。
18355號線網共有3個引腳，被分為2個有序段，依次為(16977，16976)和(16977，16990)。
36452號線網共有4個引腳，被分為3個有序段，依次為(21480，21890)，(21890，21886)和(21886，21476)。
步驟4預估計經過預估計得出每條邊上對應的使用概率分布值。其中，兩引腳共行/列的兩端線網和兩引腳段共有26296個，並對其使用擴展邊界框的估計模型技術。例如，e1對應的使用概率分布值p1＝1.16，e2對應的p2＝1.16，e83601對應的P83601＝3.40，最後一條邊e83640對應的P83640＝0.78。
考察圖7，可得P62066＝6.85，P10300＝11.21，P62270＝8.41，P10096＝11.39。
步驟5快速實際布線對每一條線網按照流程圖5的方法來布線。例如，在圖7中以v50，100為當前點出發，產生
之間的隨機數0.43，並與P10096c62066/(p62066c10096+p10096c62066)＝0.57比較，前者小，那麼選擇c62066對應的邊e62066；通過被選擇的邊到達下一個頂點，並將此頂點作為新的當前點。按同樣的方法循環執行，直到所有線網布完為止。
列舉幾個線網的布線情況如下258號線網名字為control，布線情況如圖8中的粗連線。
36451號線網名字為m1/n7630，布線情況如圖9中的粗連線。
18355號線網名字為m2/n7766，布線情況如圖10中的粗連線。
36452號線網名字為m1/U2∨mult1∨ADD1∨pog_array[2][32]，布線情況如圖11中的粗連線。
對所有線網布好線後，統計各個GRG邊對應的通道使用量並計算擁擠度值。例如，e1對應的通道使用量λ1＝1，擁擠度η1＝0.07(ηk＝λk/ck)，e2對應的λ2＝1，η2＝0.07，e83601對應的λ83601＝5，η83601＝0.56，最後一條邊e83640對應的λ83640＝0，η83640＝0.00。
考察圖7，可得λ62066＝6，η62066＝0.50，λ10300＝4，η10300＝0.27，λ62270＝8，η62270＝0.67，λ10096＝17η10096＝1.13。
步驟6輸出將結果寫入OA，並輸出報告文件。從報告中，可得maxH2.9917 maxV5.8980 O_H17073.59 O_V34288.23 B_H1290.2151 B_V4274.4438 Sigma2.1634。
其中，maxH水平邊最大擁擠度；maxV垂直邊最大擁擠度；O_H 水平邊擁擠度平方和；O_V 垂直邊擁擠度平方和；B_H 水平邊的超容(減1)擁擠度和；B_V 垂直邊的超容(減1)擁擠度和；Sigma各邊擁擠度的標準差，用來衡量是否布線資源(各邊的容量)佔用均勻。
為了實現，或者說是具體實施本項發明，我們給出以下關於發明實施的描述。
實施本發明的計算機系統本發明所設計的可布性分析方法要在一個具體的計算機系統上得以實施，該計算機系統具體描述如下。
一臺Linux伺服器；Linux作業系統；Si2推出的工業界標準的資料庫平臺OA(OpenAccess)；標準C/C++程式語言；Vim編輯器、gcc/g++編譯和連結器、gdb調試工具等。
定理在擴展邊界框u-v中的從u到v的可能路徑數目為F(m)＝m2+m+1，其中m是u和v之間相隔的列數或行數。
證明不失一般性，我們假設兩個頂點在坐標系中的位置分別為u(0，0)和v(m，0)，如圖4所示。在擴展邊框中我們允許最多有一次背離(directed away)和折返(turning back)走線。因此，從v到u有三種可能方式。第一種是從v出發向上、再向右至A。而此後的連接情況則與左上-右下的相對位置一樣，可能路徑總數為T(m-1，1)。第二種是從v出發向下、再向右至B。根據前面的分析，其可能路徑總數也為T(m-1，1)。第三種是從v直接水平向右前進至C，而可能的路徑數為F(m-1)。由此可知F(m)＝2T(m-1，1)+F(m-1)，且有F(1)＝3。
對前面的遞推式求解可得F(m)＝m2+m+1，證畢。
權利要求
1.一種快速的集成電路可布性分析方法，其特徵在於，在計算機中該方法依次按以下步驟實現步驟1初始化並建立總體布線圖步驟1.1計算機讀入在一個多層布線晶片上劃分總體布線單元GRC網格所必需的行數Nrow、列數Ncol；步驟1.2求GRC的對偶圖以GRC中每個網格的中心為新的頂點，重連接各相鄰網格的中心點形成新的邊，從而得到總體布線圖GRG；步驟1.3在步驟1.1所述的多層布線晶片上，以晶片中心為原點建立笛卡兒平面直角坐標系，並把各個布線層投影到該坐標平面上；步驟1.4標記步驟1.2中所述各新頂點的坐標為vrow，col(x，y)，並把這些新頂點的集合記為V，其中row，col分別代表該新頂點所在GRG的行和列，x，y是步驟1.3所建坐標平面的坐標；步驟1.5為所述GRG頂點vrow，col以及連接每兩個相鄰頂點的GRG邊ek分別編號，頂點用公式(row-1)×Ncol+col-1編號，邊ek則先按行從下向上從左向右編號，再按列從左向右從下向上排號；步驟1.6計算機讀入每條GRG邊ek的容量ck，給邊ek的通道使用量λk賦初始值為0；步驟2計算機讀入表徵電路詳細的連接的網表步驟2.1讀入電路中線網的總數Mnet；步驟2.2計算機對每一條線網執行步驟2.2.1讀入線網的源點s和漏點集T；步驟2.2.2把線網的源點s和漏點集T中所有點，映射到所述GRG的各頂點上，並用頂點編號對該點標記；步驟2.2.3按讀入順序，為每條線網編號；步驟3拆分所述線網中的多端線網，但兩端線網保持原狀；對於每一條多端線網執行如下操作利用Prim算法求得曼哈頓距離下的最小生成樹來劃分兩引腳端，形成按兩引腳段劃分順序所構成的兩引腳段序列，從而把一個多端線網劃分成為一個兩引腳段序列，所述的兩引腳段是指該多端線網的頂點集合中，由相距近的兩點構成的點對集合，在由該點對構成的路徑上不存頂點集合的其它點；步驟4預估計GRG各邊的走線概率；步驟4.1設定GRG每條邊ek所對應的走線概率值pk的初始值為0；步驟4.2對每條兩端線網或多端線網的每個兩引腳段做如下操作步驟4.2.1若兩個引腳u，v分別處於GRG圖的左下角和右上角的位置，u為左下角引腳，v為右上角引腳；則以u作為原點建立參考用笛卡兒平面直角坐標系，橫軸以列為單位，並以水平向左為正方向，若經過m段水平網格，縱軸以行為單位，以垂直向上為正方向，若經過n段垂直網格，點v(m，n)處於第I象限，原點為u(0，0)，以u(0，0)，v(m，n)為對頂點構成矩形框稱為為邊界框u-v，從u點到v點任何一條可能路徑的長度等於邊界框u-v的半周長；從而，按下式得到經過邊界框u-v裡某條設定水平邊AB(B點在A點右面)或垂直邊AC(C點在A點的上面)的走線概率經過水平邊AB的走線概率為pk1＝H(x，y)/T(m，n) 0≤x≤m-1，0≤y≤n，其中，T(m，n)表示從u(0，0)出發到點v(m，n)間可能存在的路徑數，表達式為T(m,n)=(m+n)!m!n!,]]>m＞0，n＞0；H(x，y)表示從原點u(0，0)出發到點A(x，y)，並經過以點A(x，y)為左端點的某一特定水平邊AB的路徑數，用下式表示H(x，y)＝T(x，y)T(m-x-1，n-y)，0≤x≤m-1，0≤y≤nT(x，y)表示從原點u(0，0)到點A(x，y)間可能存在的路徑數，按下式得出T(x,y)=(x+y)!x!y!,]]>x＞0，y＞0，T(m-x-1，n-y)表示從點B(x+1，y)出發到點v(m，n)間可能存在的路徑數，用下式表示T(m-x-1,n-y)=[(m-x-1)+(n-y)]!(m-x-1)!(n-y)!,]]>m＞x+l，n＞y；經過垂直邊AC的走線概率為pk2＝V(x，y)/T(m，n)，0≤x≤m，0≤y≤n-1，其中，V(x，y)表示從原點u(0，0)出發到點A(x，y)間經過以點A(x，y)為下端點的某一特定垂直邊AC的路徑數，用下式表示V(x，y)＝T(x，y)T(m-x，n-y-1)，0≤x≤m，0≤y≤n-1，其中，T(m-x，n-y-1)表示從點C(x，y+1)出發到達點v(m，n)間可能存在的路徑數，用下式表示T(m-x,n-y-1)=[(m-x)+(n-y-1)]!(m-x)!(n-y-1)!,]]>m＞x，n＞y+1，再把所得的pk1，pk2分別累加到邊AB，AC上的走線概率，k1，k2分別為邊AB，AC的編號；步驟4.2.2若兩個引腳u，v分別處於GRG圖的右下角和左上角的位置，u為右下角引腳，v為右上角引腳；則以右下角的引腳u作為原點建立參考用笛卡兒平面直角坐標系，橫軸以列為單位，並以水平向左為正方向，若向左經過m*段水平網格，縱軸以行為單位，以垂直向上為正方向，若經過n*段垂直網格，點v(m*，n*)處於第I象限，原點為u(0，0)，以u(0，0)，v(m*，n*)為對頂點構成矩形框稱為為邊界框u-v，從u點到v點任何一條可能路徑的長度等於邊界框u-v的半周長；從而，按照步驟4.2.1中的方法計算經過邊界框u-v裡某條設定水平邊AB(B點在A點左面)或垂直邊AC(C點在A點的上面)的走線概率，其中，只要把步驟4.2.1中的公式裡的m，n分別換成m*，n*即可；最後，再把所得的pk1，pk2分別累加到邊AB，AC上的走線概率，k1，k2分別為邊AB，AC的編號；步驟4.2.3若兩個引腳u，v分別處於GRG圖的同一行或列時，稱兩引腳點為平點對，以一個引腳為原點建立參考用笛卡兒平面直角坐標系，並使另一個引腳落在橫軸或縱軸的正半軸，當處於同一行，另一個引腳落在橫軸的正半軸，當處於同一列，另一個引腳落在縱軸的正半軸，然後，用擴展邊界框估計法，按下面方法計算邊ek上的相應走線概率步驟4.2.3.1按照下面方法建立擴展邊界框使同一行(列)的平點對的邊界框，向垂直(水平)方向各擴展一行(列)；步驟4.2.3.2在邊界框內，在邊界框擴展方向上，最多最允許一次背離所述兩引腳u，v所處的同一行或列的條件下，按下式計算經過的點(x，y)為左端點的某一特定的水平邊的走線概率pk1和計算經過點(x，0)向上或向下的垂直邊的走線概率pk2當u，v處於同一行時，pk1＝H*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，其中，m』為點u，v間的列數，F(m』)表示在擴展邊界框u-v中從u到v的可能路徑數，按下面公式計算F(m』)＝m』2+m』+1，m』是u和v之間相隔的列數，H*(x，0)表示從點u(0，0)到點(x，0)間經過以該點(x，0)為左端點的水平邊的可能路徑數目，用下式計算H*(x，0)＝F(x)+F(m′-x-1)-1，0≤x≤m′-1，H*(x，±1)表示從點u(0，0)到點(x，±1)間經過以該點(x，±1)為左端點的水平邊的可能路徑數目，用下式計算H*(x，±1)＝(x+1)(m′-x)，0≤x≤m′-1，其中，F(x)表示在擴展邊界框u-v中從u到(x，0)的可能路徑數，表達式為F(x)＝x2+x+1，F(m′-x-1)表示在擴展邊界框u-v中從(x+1，0)到v(m』，0)的可能路徑數，表達式為F(m′-x-1)＝(m′-x-1)2+(m′-x-1)+1；pk2＝V*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，其中，m』為點u，v間的列數，V*(x，0)表示從u(0，0)到點(x，0)，並經過與點(x，0)向上(或向下)所連的垂直邊的路徑數，用下列表達式計算V*(x，0)＝m′，0≤x≤m′，當u，v位於同一列時，設u，v之間的行數為m」，將上述表達式中m』的值用m」代入便計算出相應的pk1，pk2，然後，再將pk1，pk2累加到各邊對應的pk上，k1，k2分別為各邊的編號；步驟5快速布線步驟5.1對每一條線網進行布線，具體操作如下步驟5.1.1讀入用Prim算法劃分後，並按劃分順序標過序號的兩引腳段序列；步驟5.1.2標記第一個兩引腳段中的任一個引腳點；步驟5.1.3從5.1.2中所指的引腳段開始，按標號順序依次對於兩引腳段序列中的每一個兩引腳段，執行下列操作步驟5.1.3.1檢查當前的兩引腳段的兩個引腳是否都被標記；步驟5.1.3.2如果是，那麼取下一個兩引腳段，並重新轉到步驟5.1.3.1；否則，將未標記的引腳作為起點，並執行下面步驟；步驟5.1.3.3將起點設為當前點u*，並對其標記被訪問過；步驟5.1.3.4按照邊界框布線的約定，找到與u*相鄰的兩個可行頂點集合Vp和兩條可行邊的集合Ep＝{ek1，ek2}，按如下方法選擇一條邊產生
之間的一個隨機數，如果這個隨機數不大於pk2ck1/(pk1ck2+pk2ck1)，那麼選擇與分子ck1對應的邊ek1，即i＝k1，否則選擇邊ek2，即i＝k2；步驟5.1.3.5將被選邊ei的另一個端點vi作為新的當前點u*；步驟5.1.3.6檢查當前點是否被標記，如果不是，則標記該點並依照步驟5.1.3.4的方法選擇下一個點；如果是，則記錄所有經過路徑；步驟5.2所有線網布好線後，對每條線網經過的邊的通道使用量λk累加1，統計每條邊上的使用量；步驟5.3計算各個邊的擁擠度值ηk＝λk/ck；步驟6輸出步驟6.1將擁擠估計結果和快速布線結果寫入Si2推出的工業界標準的資料庫平臺OpenAccess；步驟6.2輸出評測報告。
全文摘要
本發明屬於IC CAD領域，其特徵在於，一次含有以下步驟計算機初始化，並建立GRG圖，讀入布線資源和電路網表；用Prim算法拆分多端線網，得到曼哈頓距離下的最小生成樹；預估計各邊的走線概率若兩個引腳段的引腳處在邊界框的對角處，用格路模型，若出在同一行或列時，用擴展邊界框估計模型；快速布線採用按走線概率反比結合隨機選擇等方式，選擇布線路徑。本發明通過快速完成擁擠估計，使可布性分析能服務於增量式布局或者指導布線。
文檔編號G06F17/50GK1862546SQ20061001227
公開日2006年11月15日 申請日期2006年6月15日 優先權日2006年6月15日
發明者洪先龍, 經彤, 劉盛華, 許靜宇 申請人:清華大學