基于最小自由度优先原则的非线性规划布局方法

摘要

基于最小自由度优先原则的非线性规划布局方法属于集成电路计算机辅助设计领域，具体特征在于：它结合了最小自由度优先原则和非线性规划方法的优点，同时优化面积和线长。它首先使用非线性规划方法，优化总线长，得到具有最有总线长的初始解；然后根据用户给定的长宽比和面积利用率，利用最小自由度优先原则，优化布局。它具有较快的速度、较高的面积利用率，同时使总线长得到优化。

主权项

1.基于最小自由度优先原则的非线性规划布局方法，其特征在于，它依次含有以下步骤：(1).计算机初始化读入所有的模块的长宽和它们之间连线的信息；输入用户给定的面积利用率和长宽比；设定下列参数：布局空白区域的自由度：角部的自由度定义为P_c^f，P_c^f＝1/2边上的自由度定义为P_s^f，P_s^f＝3/4中间的自由度定义为P_h^f，P_h^f＝1模块的自由度定义为R_i^f：R_i^f＝{r₁*(1-B_i/A_a)+r₂*(1-max(w_i，h_i)/min(W，H))}；其中：r₁+r₂＝1，      w_i、h_i分别是模块i的宽和高，B_i是模块i的面积，      A_a是放置空间的面积，W、H分别是它的宽和高；互连自由度定义为C_i^f，即模块i的互连自由度，t_ij是模块i与相邻模块j连线数，ω_ij为模块i与相邻模块j连线长度，用半周长法估计；初始解自由度S_i^f， $S_i^f={|x_{\mathrm{icur}}-x_{\mathrm{iori}}|}^2+{|y_{\mathrm{icur}}-y_{\mathrm{iori}}|}^2$x_icur，y_icur分别为模块当前所在网格的坐标，x_iori，y_iori分别为模块初始解中所在网格的坐标；(2).使用近似模型求具有最小线长的初始布局结果并记录每个圆的最终坐标，它依次含有以下步骤：(2.1).把所有的矩形模块近似成与之面积相等的圆，所有的连线都从圆心发出，各圆之间不重叠；(2.2).使用二次线长法近似每条连线的长度并使总线长目标函数W(x，y)最小： $W(x,y)=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{\omega }_{\mathrm{ij}}·\frac{1}{2}\left[({(x_i-x_j)}^2+{(y_i-y_j)}^2)\right]$约束条件：g(x，y)＝(r_i+r_j)²-[(x_i-x_j)²+(y_i-y_j)²]≤0其中：n为模块数，(x_i，y_i)为第i个模块圆心的坐标，      ω_i，j为模块i，j间的连线数      r_i、r_j分别为模块i，j的半径(2.3).使用罚函数的方法把问题转化成无约束目标函数P(x，y，c_k) $P(x,y,c_k)=W(x,y)+c_k\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}\mathrm{Max}(0,g(x,y))$其中c₀＝1，c_k+1＝10c_k，k是迭代次数计数器，从0→∞(2.4).固定其中一个模块，通过软件包matlab中的函数fmincon使用逐步二次规划法求出具有全局最优线长的初始解，即收敛子序列{(x，y)^k}的极限；(2.5).把初始解的布局区域划分成m*m个网格，m＝4~12，记录每个圆心所在的网格；(3).根据用户给定的面积利用率和长宽比，计算出布局区域的长宽，结合初始解，使用最小自由度优先原则进行布局，它依次含有如下步骤：(3.1).设：UBS为未放置的模块集合，          PBS为放置好的模块集合，          PL为当前的放置状况；(3.2).把所有的模块按它们的模块自由度R_i^f排序，找到R_i^f最小的模块，先尝试放置该模块，从4个角开始，共有8种放置方案，对于每一种放置方案，在放置好第一个模块后，对于剩余模块采用已知的贪婪算法放置；(3.3).计算步骤(3.2)所述8种方案按下式计算各自的总自由度F_k，共8个值：F_k＝αP+βR_kf+γC_k^f+λS_k^fP为布局空白区域自由度(3.4).选取其中F_k最小的放置方案作为上述第一个放置的模块的放置方案；(3.5).把上述已放置好的第一个模块从UBS中去除，放入PBS中；(3.6).重复步骤(3.2)～(3.6)直到UBS空为止；(4).使用已知的模拟退火的方法调整布局，优化总线长。(5).以图形和文件两种形式输出最终布局结果。