买专利卖专利找龙图腾，真高效！ 查专利查商标用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或微信搜索“龙图腾网”。