買專利賣專利找龍圖騰，真高效！ 查專利查商標用IPTOP,全免費！專利年費監控用IP管家,真方便！

龍圖騰網獲悉南通大學申請的專利一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法獲國家發明授權專利權，本發明授權專利權由國家知識產權局授予，授權公告號為：CN115114880B 。

龍圖騰網通過國家知識產權局官網在2025-09-05發布的發明授權授權公告中獲悉：該發明授權的專利申請號/專利號為：202210695559.5，技術領域涉及：G06F30/392；該發明授權一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法是由周晨璨;施佺;曹陽設計研發完成，并于2022-06-17向國家知識產權局提交的專利申請。

本一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法在說明書摘要公布了：本發明提供了一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法，首先對多倍行高單元預處理成單倍行高子單元，并放置到最近的與電源線匹配的行上，然后對所有單元建立網絡流模型，對其進行擴散，避免局部擁擠，接著將合法化問題表述為一個凸二次規劃問題，并將二次規劃問題等價地轉換成線性互補問題，然后將線性互補問題等價地表示成廣義絕對值方程，設計了一種加速的牛頓分裂迭代法求解，最后將多倍行高標準單元進行復原并放置到行中的可放置位上，并對余下的非法單元進行處理。與現有技術相比，本發明通過加速的牛頓分裂迭代法對與合法化問題等價的廣義絕對值方程進行求解，無需過多考慮參數的設置，僅需確定一個參數矩陣，且對該參數矩陣的選取給出建議，避免了因參數或參數矩陣的選取不當而無法有效或高效求解的局限。本發明能夠有效加快迭代過程的收斂速度，并快速得到合法化問題的高質量鄰域解。

本發明授權一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法在權利要求書中公布了：1.一種加速的牛頓分裂迭代法應用于混合尺寸單元電路布局方法，其特征在于：包括如下步驟： S1:對標準單元進行預處理，將多倍行高標準單元分割為多個單倍行高標準子單元，并放置到最近的與電源線匹配的行上； 步驟S1的具體實現方式包括：給定一個芯片的矩形布局區域，用0,0和W,H分別表示其左下角坐標和右上角坐標；W表示布局區域的寬度，H表示布局區域的高度；待布局的可移動標準單元集為C＝c1,c2,…cn，其中單元ci從全局階段獲得的初始左下角坐標為單元寬度及高度分別為wi，hi，所求的合法化階段后的坐標用xi,yi表示；對于多倍行高標準單元，將其表示成多個子單元，用ci1,ci2,…cit表示，其中，t表示標準單元的高度是行高的t倍； S2:對所有單元建立網絡流模型，對其進行擴散； S3:將合法化問題表述為一個凸二次規劃問題； S4:將二次規劃問題等價地轉換成線性互補問題； 步驟S4的具體實施方式為：利用Karush-Kuhn-TuckerKKT條件，可將模型寫成如下條件的KKT方程組： 將方程組4改下為如下形式： 令該問題則演變為尋求一對非負且正交的解向量滿足如下條件： w＝Az+q≥0,z≥0andwTz≥0；6 問題6則為線性互補問題，其中 S5:將線性互補問題等價地表示成廣義絕對值方程； 所述步驟S5的具體實施方式為：令z＝|v|-v，w＝|v|+v，則6可轉換成下列等價的廣義絕對值方程： A+Iv-A-I|v|＝q；7 令C＝A+I,E＝A-I，其中I為單位矩陣，則7可重新表述為如下形式： Cv-E|v|＝q；8 S6:利用加速的牛頓迭代法求解廣義絕對值方程； 所述步驟S6的具體實施方式為：令Fv＝Cv-E|v|-q，并令Fv＝0；由于Fv是一個分段線性向量函數，是不可微的，不能直接應用牛頓迭代方法來求解此方程；因此，基于|v|的分量的次梯度，使用|v|的廣義雅可比來獲得廣義絕對值方程8的近似解；可用對角矩陣Dv表示，其中且 對于非線性等式系統Fv，將其分解為可微函數Hv與Lipschitz連續函數Gv之和，即Fv＝Hv+Gv，因此可以利用一種修正的牛頓迭代法求解Fv，即 vk+1＝vk-H'vk-1Hvk+Gvk,k＝0,1,2,…,10 取Hv＝Cv+Ωv，Gv＝-Ωv-E|v|-q，其中Ω為半正定矩陣，利用10求解Fv可得到如下迭代格式： vk+1＝vk-C+Ω-1Cvk-E|vk|-q；11 將11兩邊同時乘以C+Ω可得 C+Ωvk+1＝Ωvk+E|vk|+q；12 由于C＝A+I,E＝A-I，因此矩陣C和E是兩個正定矩陣，令C＝M1-N1為矩陣C的分裂，E＝M2-N2為矩陣E的分裂，并將最新的估計值vk+1替換等式右側的vk，可得到如下迭代格式: M1+Ωvk+1＝N1+Ωvk+M2|vk|-N2|vk+1|+q；13 其中，要求N2是一個下三角矩陣；具體地，根據式5中矩陣A的結構，將M1,N1,M2,N2取值如下： 其中，為單位矩陣；取Ω＝ωI，ω為正常數，令B1＝B+λRTR，因此，利用式13求解合法化問題的過程如下所示： 給定一個任意的初始向量通過迭代地求解線性系統來計算vk+1的值，直到絕對殘差向量的二范數RESvk:＝||zk-zk-1||2小于等于給定的一個常數，此時可認為迭代序列收斂，且zk＝|vk|-vk，k＝0,1,2,…； S7:將多倍行高標準單元進行復原并放置到行中的可放置位上； S8:對剩余的非法單元進行合法化處理。

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人南通大學，其通訊地址為：226000 江蘇省南通市嗇園路9號；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。