基於空白區重分配的緩衝器規劃方法
2023-05-16 13:50:11 1
專利名稱：基於空白區重分配的緩衝器規劃方法
技術領域：
基於空白區重分配的緩衝器規劃方法屬於集成電路計算機輔助設計領域，尤其涉及BBL(Building Block Layout)領域。
隨著納米技術和高頻技術的應用，互連的設計與優化成為決定系統性能、成本和可靠性的關鍵問題。在過去10年裡，人們已經研究出了多種互連優化技術，例如拓撲的構造，緩衝器插入，器件尺寸的優化，線寬和線間距的優化，以及上述各種優化技術的組合應用。為了確保電路設計的時序特性，在設計的流程中，互連的設計應該儘早加以考慮。緩衝器插入對減少互連時延來說，是一種非常有效的方法。在Elmore時延模型下，長連線的時延與線長的平方成比例增長，而利用緩衝器插入技術，可以控制連線的時延與線長呈線性增長關係。為滿足時延約束，需要插入的緩衝器數目隨工藝尺寸的減小而持續增長。例如，在70nm工藝下，需要插入800,000個緩衝器以滿足性能優化。由於緩衝器需要佔用矽資源，所以在設計過程中，緩衝器應該儘早規劃，尤其在布局階段。本發明就是在BBL布局階段對緩衝器插入的位置和數量進行估計，儘可能改善電路的時延性能。
近年來，緩衝器規劃問題受到廣泛的關注，人們已經提出了很多種緩衝器規劃的方法。由於緩衝器是器件，所以這些方法多數利用布局中的空白區插入緩衝器，在BBL階段也已經有很多相關的工作；例如最早提出的可行區域(feasible region)的概念，用來產生緩衝器模塊；緩衝器的可行區域是指在滿足線網的目標延時的條件下，緩衝器可以放置的可能最大區域。稍後，可行區擴展成為獨立可行區，同時布線擁擠度得到優化。網絡流的方法在假設每個線網只有一個緩衝器的情況下，可以找到最優解。多商品流的方法將緩衝器分配到預先已存在的緩衝器模塊。動態規劃方法假設在宏模塊內部也允許插入緩衝器，因此這種方法會使插入緩衝器的點分配在布局的各個位置。可布性驅動的布圖規劃方法可以為擁擠度約束估計緩衝器的用量和緩衝器資源。集成緩衝器/通道插入的布圖規劃方法用於基於總線的微處理器設計。在眾多的緩衝器規划算法中，還沒有一種方法對布局中的空白區進行優化，以更好的利用空白區來提高電路的時延特性。
本文討論了布局中的空白區的重分配問題，並通過優化空白區的分布改善緩衝器規劃問題的結果，從而達到改善電路時延特性的目的。
設有n個模塊的布局問題模塊集合M＝{Mi(wi，hi)|i∈[1..n}，(wi，hi)為模塊Mi的寬和高；設共有m個引線端，所有引線端集合PIN＝{pji(p_xji，p_yji)|j∈[1...m]，i∈[1…n]}，其中j為引線端標號，i為該引線端所屬的模塊編號，(p_xji，p_yji)為pji相對於其所在模塊i左下角的坐標；NET＝{(pi，…，pk)，…，(pj，…，pl)}，位於同一個括號內的引線端屬於同一個線網，也就是說同一括號內的引腳之間存在連接關係；空白區集合DS＝{Dk((xk1b，yk1b)，(xkur，ykur))|k∈[1...s]}，其中(xk1b，yk1b)為空白區Dk的左下角坐標，(xkur，ykur)為空白區Dk的右上角坐標。
如
圖1所示的布局和空白區的實例M＝{M1(6，3)，M2(2，5)，M3(4，5)，M4(2，8)}，PIN＝{p11(1，3)，p21(2，0)，p32(0，3)，p42(2，1)，p53(2，0)，p63(4，3)，p74(0，1)，p84(2，4)，p94(1，8)}，NET＝{(p1，p3，p9)，(p2，p4，p8)，(p5，p6，p7)}，及四塊空白區。
緩衝器規劃問題就是在給定布局中，對滿足電路時延特性需要的緩衝器的數量進行估算，並給出位置，同時充分利用空白區插入緩衝器資源，改善電路時延性能；對空白區的優化是指改變布局中的空白區的分布，以儘可能更多的增加滿足時延約束的線網數，進一步改善電路性能。對空白區優化的目標是使得滿足時延約束的線網數達到最大。
本發明的特徵在於它是一種在硬體支持下的優化空白區的分布，改善緩衝器規劃的方法，它依次含有以下步驟(1).對於一個給定的布局，計算其中所有空白區，將它們分割成塊並和模塊相關聯，對於大小非零的偽模塊，則它構成的空白區不和任何模塊相關聯；同時，對所有的空白區建立位置數據結構，把空白區細劃分成固定大小的用以放下一個或幾個緩衝器的小矩形；(2).判斷線網N長度是否大於關鍵長度lcrit，若為否則當前線網插入緩衝器數為零lcrit=Rb-Rdr+Cb-Clc+2RbCb+Tbrc]]>其中Rb緩衝器輸出電阻(Ω)，Rd驅動輸出電阻(Ω)，Cb緩衝器輸入電容(fF)，Cl負載電容(fF)，
r單位長度線電容(Ω/μm)，c單位長度線電容(fF/μm)，Tb緩衝器固有延時(ps)；(3).計算每一個兩端線網N因為不滿足時延約束需要插入的緩衝器數及各緩衝器的獨立可行區域(3.1).計算線網滿足時延約束需要的緩衝器數kmin 其中K1＝RbCb+Tb(9)K2=(rCb+cRb)l+Tb+RdCb+RbCl-Tcon---(10)]]>-r2c(Cb-Cl)2-c2r(Rb-Rd)2]]>K3=12rcl2+(rCl+cRd)l+RdCl-Tcon---(11)]]>其中l為線網長度，Rb緩衝器輸出電阻(Ω)，Rd驅動輸出電阻(Ω)，Cb緩衝器輸入電容(fF)，Cl負載電容(fF)，r單位長度線電容(Ω/μm)，c單位長度線電容(fF/μm)，Tb緩衝器固有延時(ps)，Tcon為線網的時延約束；(3.2).計算線網N中每個緩衝器的獨立可行區域長度為l的線網N的第i個緩衝器的獨立可行區域為IFRi=(xopti-Wifr/2,xopti+Wifr/2)(0,l),]]>Wifr為第i個緩衝器的獨立可行區域的寬度，Wifr=2TconN-ToptN(kmin,l)rc(2kmin-1)]]>其中，kmin為緩衝器數，TconN為線網N的時延約束，ToptN為線網N中插入kmin個緩衝器的最優時延，ToptN(kmin,l)=TN(xopt1,xopt2,......,xoptkmin,l)]]>=rl(kminCb+Cl)+cl(Rd+kminRb)+(kminCb+Cl)(kminRb+Rd)kmin+1]]>+kminTb+rcl2-/ckminr(Cb-Cl)2-/rkminc(Rb-Rd)22(kmin+1)]]>xopti為緩衝器相對線網源端的Manhattan距離(只包含水平和垂直線段)，也即第i個緩衝器的位置；xopti=(i-1)yl+xli{1,2,...,kmin}]]>其中 (4).計算滿足目標時延的兩端線網數目Nold；(4.1).計算每一個緩衝器的侯選位置集合(4.1.1).計算緩衝器所在線網的源端和漏端所確定的矩形區域和空白區的交DFol；(4.1.2).計算DFol和緩衝器的獨立可行區域的交，當DFol內某位置的左下角位於緩衝器的獨立可行區域內，則該位置是相應緩衝器的侯選位置；(4.1.3).在上述緩衝器的侯選位置中選擇成為緩衝器侯選位置最少同時尚未放置緩衝器的位置作為緩衝器的位置；(4.2).檢查每一個兩端線網，統計統計所需緩衝器全部插入的線網數N，記為Nold；(5).按以下步驟生成新的空白區分配(5.1).選擇1-2塊和模塊相關聯的空白區，移動相應的模塊改變空白區在模塊周圍的分布；(5.2).更新移動過的模塊的坐標，重新計算所有和移動模塊相關聯的線網的引角坐標；(5.3).重新按(3)中方法計算所移動模塊相關的線網滿足時延約束所需要的緩衝器數目及相應緩衝器的獨立可行區域；(6).重新按上述方法計算滿足時延約束的線網數，記為Nnew；(7).若Nold＜Nnew，則接受新的空白區分配，用Nnew代替Nold；若Nold＞Nnew，則恢復到上一次的空白區分配，即移動模塊至上一次位置，執行操作(5.2)和(5.3)；(8).在給定的次數內重複以上各步驟((5)-(7)步)。
試驗說明它增加了空白區的利用率，同時也增加了滿足時延約束的線網數，改善了電路時延特性。
圖2.本發明所述規劃方法的程序流程圖。
圖3.初始的空白區圖。
圖4.緩衝器獨立可行區域及候選位置計算5.空白區的重分配圖。
圖6.實施前的原始布局圖。
圖7.空白區重新分配後，實施所得布局圖。
具體實施例方式
本發明可以在不同的基於矩形劃分的布圖規劃/布局表示(也就是說該類布圖表示將晶片劃分為數目大於等於模塊數目的矩形區域，同時每一個矩形區域至多有一個模塊)下實現。本部分採用CBL表示的布局結果，作為本發明的一個實例，並採用Elmore時延模型作為時延計算的模型。結合圖2的流程圖用本發明的方法進行基於空白區重分布的布圖規劃。表一為一些變量的定義。
表一
它依次有如下步驟接收CBL表示的布局作為輸入，計算布局中的所有空白區，將它們分割成塊，並和模塊相關聯；方法如下(詳細的表示到布局的轉換算法不屬於本專利申請的內容，故這裡不細述)在CBL布圖表示向布局的轉換過程中，計算每個模塊的坐標時比較用坐標表示其邊界的各模塊，如果兩模塊之間存在空區域，將該空區域和被覆蓋的模塊相關聯；模塊處理完畢，如果位於晶片的上邊界或右邊界的模塊與邊界之間存在空白區，則將空白區和相應的位於邊界的模塊相關聯；檢查所有的偽模塊(在布局中加入的虛擬的模塊，其作用只是參與構造模塊之間的拓撲關係，其大小決定於實際模塊的布局，如圖二所示0即為虛擬模塊，其對應一個空的區域)，如果其大小不為零，則表明在布局中存在空區域；該類空白區不與任何模塊相關聯；對所有的空白區建立片數據結構，即把空白區細劃分成固定大小的可以放下一個緩衝器的小矩形；初始化計算對每個多端線網(有三個或三個以上引腳)按如下方式進行拆分由於測試電路中不包含線網的源端和漏端信息，故任意指定一個引腳作為源端，其他引腳作為漏端；將一個包含n個引腳的線網拆分成n-1個兩端線網；對每個兩端線網完成如下操作根據如下已有公式計算關鍵長度lcrit，如果兩端線網長度大於lcrit，繼續如下步驟，否則當前線網插入緩衝器數為零；lcrit=Rb-Rdr+Cb-Clc+2RbCb+Tbrc---(1)]]>其中，Rb，Cb，Tb，Rd，Cl，r和c意義如表一所示；用如下已有方法計算在插入緩衝器的條件下，最小化時延需要的緩衝器數給定一條長度為l的兩端線網，該線網的Elmore時延可以定義如下T(Rd,Cl,l)=(rc2)l2+(Rdc+rCl)l+RdCl---(2)]]>其中各參量意義如表一所示；對於長度為l，插入了n個緩衝器的線網，要達到最小化線網時延的目的，n個緩衝器的最優位置為說明本文緩衝器的位置及下述可行區的計算涉及到線網內的位置問題，均指相對線網源端的Manhattan距離(只包含水平和垂直線段)，例如線網長度就是指源端到漏端的Manhattan距離。
第i個緩衝器的位置為xioptxopti=(i-1)yl+xli{1,2,...n}---(3)]]>其中 一條長度為l的單源端單漏端的線網(兩端線網)，插入n個緩衝器的時延可以用下列公式計算。TN(x1,x2,...,xn,l)=T(Rd,Cb,x1)+T(Rb,Cl,l-xn)]]>+i=1n-1T(Rb,Cb,xi+1-xi)+nTb,---(5)]]>其中函數T的定一同(2)，各參量意義如表二所示，xi為第i個緩衝器的位置。長度為l插入n個緩衝器的線網N的最優時延可依據公式(2)、(3)、(4)和(5)計算，記為ToptN(n,l)=TN(xopt1,xopt2,......,xoptn,l)]]>=rl(nCb+Cl)+cl(Rd+nRb)+(nCb+Cl)(nRb+Rd)n+1---(6)]]>+nTb+rcl2-/cnr(Cb-Cl)2-/rnc(Rb-Rd)22(n+1)]]>綜上所述，線網N要達到最優時延需要的緩衝器數目，可按如下方式計算在兩端線網的源和漏之間從1開始按每次遞增1個緩衝器的方式插入緩衝器，如果插入第k+1個緩衝器導致線網延時增加，那麼該線網達到最優延時需要k個緩衝器；即緩衝器數k滿足下式ToptN(k,l)ToptN(k+1,l),]]>由該式可解出k的表達式 根據上一步計算的線網達到最優時延時需要的緩衝器數k及(2)、(3)、(4)和(5)計算的最優時延Topt，將線網的時延約束隨機賦值(用已有的隨機函數生成即可)為最優時延Topt的1.05至1.2倍，記為Tcon；對每一個線網完成如下計算根據如下已有公式及1.c中給出時延約束Tcon計算滿足線網約束需要的緩衝器數目； 其中K1＝RbCb+Tb(9)K2=(rCb+cRb)l+Tb+RdCb+RbCl-Tcon---(10)]]>-r2c(Cb-Cl)2-c2r(Rb-Rd)2]]>K3=12rcl2+(rCl+cRd)l+RdCl-Tcon---(11)]]>其中，各參量的意義如表一所示。
對每個兩端線網，根據①中公式計算滿足時延約束需要插入的緩衝器個數kmin，並計算每一個緩衝器的獨立可行區域(緩衝器b的獨立可行區域是指在滿足b所屬線網的時延約束條件下，假設該緩衝器所屬線網的其他緩衝器都被放置在他們各自的獨立可行區域內，可以插入緩衝器b的最大區域，圖4給出示例，線網源端和漏端分別為虛線框的左下角和右上角，緩衝器的獨立可行區為兩條135度斜線和矩形虛線框的交集)；根據如下已有方法計算各個緩衝器的獨立可行區域；長度為l的線網N的第i個緩衝器的獨立可行區域為IFRi=(xopti-Wifr/2xopti+Wifr/2)(0,l)---(12)]]>其中，xopti意義同公式(3)，Wifr代表獨立可行區域的寬度；即插入kmin個緩衝器的最優位置；使得如下公式成立(x1,x2,...,xi,...,xkmin)IFR1IFR2...IFRn,]]>TN(x1,x2,......,xkmin,l)TconN---(13)]]>其中xi為緩衝器相對源端的位置，TconN為與線網N相關的時延約束；Wifr可以按如下公式計算。Wifr=2TconN-ToptN(kmin,l)rc(2kmin-1)----(14)]]>其中TconN和ToptN(kmin，l)為線網N的時延約束和插入kmin個緩衝器的最優時延，r，c的意義如表一所示。ToptN(kmin，l)可由kmin替換公式(6)中的n來計算。
綜上所述，特定線網的緩衝器的獨立可行區域可由(3)、(4)、(12)、(14)計算出來。
按如下方法計算在初始空白區分布下滿足目標時延的兩端線網數目，記為Nold；計算每一個緩衝器的候選tile集合；計算緩衝器所在線網的源端和漏端所確定的矩形區域和空白區的交(即計算兩個矩形的交)；結果記為DFol；(如圖4，矩形粗線框為DFol)；計算DFol與緩衝器的獨立可行區域的交。如果DFol內某tile的左下角位於緩衝器的獨立可行區域內，那麼我們認為該tile是相應緩衝器的候選位置。(圖4所示斜線所覆蓋部分)對每一個緩衝器按如下啟發式方法確定緩衝器的位置在該緩衝器的候選tile中選擇成為緩衝器候選位置次數最少同時尚未放置緩衝器的tile作為該緩衝器的位置；檢查每一個兩端線網，統計所需緩衝器全部插入的線網數N，N作為Nold返回；按如下方法生成新的空白區分配選擇一至兩塊和模塊相關聯的空白區，移動相應的模塊改變空白區在模塊周圍的分布；(圖5給出示例)更新移動過的模塊的坐標，並重新計算所有和移動模塊相關聯的線網的引腳坐標；按照3的方法，重新計算與移動模塊相關的線網滿足時延約束需要的緩衝器數目及相應緩衝器的獨立可行區域；按照4的方法計算重新滿足時延約束的線網數，記為Nnew.
如果Nold＜Nnew，新的空白區分配將被接受，Nold←Nenw；否則恢復到上一次的空白區分配，即移動模塊至上一次位置，執行和5.②，5.③相同的操作；重複第5到第7步100次。
根據下表所示參數值，我們舉例說明部分計算過程(如無特殊說明，長度和坐標的單位均為微米(μm)，時間單位為皮秒(ps)表二
如圖6所示布局的一部分，各模塊右上角坐標如圖所示，空白區D1和空白區D2均被邊界所覆蓋，它們分別和模塊m6和m1相關聯；兩端線網源端為s(6118，7328)，漏端為t(9286，15228)；與線網相關的計算線網長度為(15228-7328)+(9286，6118)＝11068；根據具體實施步驟2.②公式(1)及表二給出的參量值，計算關鍵長度lcrit＝4270；根據具體實施步驟2.②.b公式(7)計算的線網最小化時延需要的緩衝器數為k＝3；根據公式(6)計算相應最優時延Topt＝517；根據具體實施步驟2.②.c，時延約束賦值為Topt的1.05倍，即Tcon＝543.01；
根據具體實施步驟3.①公式(8)計算的kmin＝2；根據具體實施步驟3.②，計算兩個緩衝器的獨立可行區域分別為(2803，4575)和(6493，8265)；如圖五所示，b1，b2所在的虛線所包圍的區域分別為兩個緩衝器的獨立可行區域；由圖中可以直觀看出，雖然緩衝器b2的可行區域與空白區存在交集，b2必然存在侯選位置(tile)，但是緩衝器b1的獨立可行區域與空白區沒有交集，故所給線網中緩衝器b1無法插入，相應的時延約束也就得不到滿足；圖7給出了對空白區優化之後的布局及空白區分布情況，由圖可以看出，與模塊m1和m6相關的空白區D1和D2的分布均被改變，同時所給線網的源端和漏端坐標均未改變，且緩衝器b1和b2的獨立可行區域均和空白區有交集；所給線網的時延約束就可以通過插入緩衝器b1和b2來滿足；最終b1和b2插入了左下角坐標分別為(6120，11060)和(8532，11312)的tile。
附實驗結果表三
其中「met」為滿足時延約束的線網數；「緩衝器」為成功插入空白區緩衝器的總數目；「Nimp」為優化空白區分布後滿足時延約束的線網數相對初始空白區分布的增加；「Riip」為為優化空白區分布後滿足時延約束的線網數相對初始空白區分布的增加的比率。
本發明使用的硬體是一臺Sun公司的v880工作站；使用Unix作業系統。本發明所述的基於空白區重分配的緩衝器規划算法有以下幾個優點(1).將布局中的空白區與模塊相關聯，通過移動模塊來改變空白區的分布；(2).對空白區的分配進行了優化，增加了空白區的利用率，同時增加了滿足時延約束的線網數，改善了電路的時延特性(3).具有工業應用價值，可以用於集成電路設計過程中模塊級布圖規劃/布局中的互連規劃問題。
權利要求
1.基於空白區重分配的緩衝器規劃方法，其特徵在於它是一種在硬體支持下的優化空白區的分布，改善緩衝器規劃的方法，它依次含有以下步驟(1).對於一個給定的布局，計算其中所有空白區，將它們分割成塊並和模塊相關聯，對於大小非零的偽模塊，則它構成的空白區不和任何模塊相關聯；同時，對所有的空白區建立位置數據結構，把空白區細劃分成固定大小的用以放下一個或幾個緩衝器的小矩形；(2).判斷線網N長度是否大於關鍵長度lcrit，若為否則當前線網插入緩衝器數為零lcrit=Rb-Rdr+Cb-Clc+2RbCb+Tbrc]]>其中Rb緩衝器輸出電阻(Ω)，Rd驅動輸出電阻(Ω)，Cb緩衝器輸入電容(fF)，Cl負載電容(fF)，r單位長度線電容(Ω/μm)，c單位長度線電容(fF/μm)，Tb緩衝器固有延時(ps)；(3).計算每一個兩端線網N因為不滿足時延約束需要插入的緩衝器數及各緩衝器的獨立可行區域(3.1).計算線網滿足時延約束需要的緩衝器數kmin 其中K1＝RbCb+TbK2=(rCb+cRb)l+Tb+RdCb+RbCl-Tcon]]>-r2c(Cb-Cl)2-c2r(Rb-Rd)2]]>K3=12rcl2+(rCl+cRd)l+RdCl-Tcon]]>其中l為線網長度，Rb緩衝器輸出電阻(Ω)，Rd驅動輸出電阻(Ω)，Cb緩衝器輸入電容(fF)，Cl負載電容(fF)，r單位長度線電容(Ω/μm)，c單位長度線電容(fF/μm)，Tb緩衝器固有延時(ps)，Tcon為線網的時延約束；(3.2).計算線網N中每個緩衝器的獨立可行區域長度為l的線網N的第i個緩衝器的獨立可行區域為IFRi=(xopti-Wifr/2,xopti+Wifr/2)(0,l),]]>Wifr為第i個緩衝器的獨立可行區域的寬度，Wifr=2TconN-ToptN(kmin,l)rc(2kmin-1)]]>其中，kmin為緩衝器數，TconN為線網N的時延約束，ToptN為線網N中插入kmin個緩衝器的最優時延，ToptN(kmin,l)=TN(xopt1,xopt2,......,xoptkmin,l)]]>=rl(kminCb+Cl)+cl(Rd+kminRb)+(kminCb+Cl)(kminRb+Rd)kmin+1]]>+kminTb+rcl2-/ckminr(Cb-Cl)2-/rkminc(Rb-Rd)22(kmin+1)]]>xopti為緩衝器相對線網源端的Manhattan距離(只包含水平和垂直線段)，也即第i個緩衝器的位置；xopti=(i-1)yl+xli{1,2,...,kmin}]]>其中 (4).計算滿足目標時延的兩端線網數目Nold；(4.1).計算每一個緩衝器的侯選位置集合(4.1.1).計算緩衝器所在線網的源端和漏端所確定的矩形區域和空白區的交DFol；(4.1.2).計算DFol和緩衝器的獨立可行區域的交，當DFol內某位置的左下角位於緩衝器的獨立可行區域內，則該位置是相應緩衝器的侯選位置；(4.1.3).在上述緩衝器的侯選位置中選擇成為緩衝器侯選位置最少同時尚未放置緩衝器的位置作為緩衝器的位置；(4.2).檢查每一個兩端線網，統計統計所需緩衝器全部插入的線網數N，記為Nold；(5).按以下步驟生成新的空白區分配(5.1).選擇1-2塊和模塊相關聯的空白區，移動相應的模塊改變空白區在模塊周圍的分布；(5.2).更新移動過的模塊的坐標，重新計算所有和移動模塊相關聯的線網的引角坐標；(5.3).重新按(3)中方法計算所移動模塊相關的線網滿足時延約束所需要的緩衝器數目及相應緩衝器的獨立可行區域；(6).重新按上述方法計算滿足時延約束的線網數，記為Nnew；(7).若Nold＜Nnew，則接受新的空白區分配，用Nnew代替Nold；若Nold＞Nnew，則恢復到上一次的空白區分配，即移動模塊至上一次位置，執行操作(5.2)和(5.3)；(8).在給定的次數內重複以上各步驟((5)-(7)步)。
全文摘要
基於空白區重分配的緩衝器規劃方法屬於集成電路計算機輔助設計領域，其特徵在於它是一種優化空白區分布以改善緩衝器分配的方法，它首先根據線網時延約束依次求出相應的緩衝器數和滿足線網時延約束的線網數；在給定的迭代次數內，修改空白區的分布，更新相關線網信息，重新計算滿足時延約束的線網數，一旦發現滿足時延約束的線網數有所增加，便用新的空白區分布代替原有的空白區分布。它增加了空白區利用率，同時也增加了滿足時延約束的線網數，改善了電路的時延特性。
文檔編號G06F17/50GK1475945SQ0314817
公開日2004年2月18日 申請日期2003年7月4日 優先權日2003年7月4日
發明者洪先龍, 陳松, 董社勤, 馬昱春 申請人:清華大學