毕设相关的布局布线总结内容。
优化最短线长
问题描述
\(n\)个可\(90°\)旋转的硬模块，硬模块\(m_i\)尺寸为\(w_i×h_i\)。一个宽、高分别为\(W\)和\(H\)的电路板，\(p\)个表示模块间连接关系的网络net，每个网络是由若干模块组成的集合。要求所有模块正交、无重叠和完全的放置到电路板上，目标是最小化所有网络的连线长度之和。用\((x_{i1},y_{i1})\)和\((x_{i2},y_{i2})\)分别表示模块\(m_i\)的左下角坐标和右上角坐标，\(w_i\)和\(h_i\)分别表示模块\(m_i\)的宽和高。则该问题的形式化定义如下： \[ 目标：min\sum^{p}_{i=1}HPWL(net_i) \]
\[ St.\\(1)(x_{i2}-x_{i1},y_{i2}-y_{i1})\in\{(w_i,h_i),(h_i,w_i)\}\\(2)max(x_{i1}-x_{j2},x_{j1}-x_{i2},y_{i1}-y_{j2},y_{j1}-y_{i2})\geq0\\(3)0\leq x_{iq}\leq W,0\leq y_{iq}\leq H,q\in\{1,2\} \]
其中\(i\)和\(j\)均取\(\{1,2,...,n\}\)中的任意值，且\(i\neq j\)。约束(1)表示所有模块正交放置，约束(2)表示模块间无重叠，约束(3)表示模块完全处于电路板上。
前人求解算法
启发式搜索算法
当问题中模块规模较小时，启发式搜索算法有高效的性能。而随着模块规模的不断增加，启发式搜索算法速度慢的缺点就逐渐显现出来，很难在有限的时间内给出高质量的解。
(1)评估函数：
经典布图规划问题的评估函数： \[ cost(F)=w× \frac{area(F)}{norm\_area}+(1-w)×\frac{wirelength(F)}{norm\_wire} \] \(w:\)处于区间[0,1]的权重
\(area(F):\)布图F中电路板的面积
\(wirelength(F):\)布图F中网络连线长度
\(norm\_area:\)最优布图中电路板的面积
\(norm\_wire:\)最优布图中网络连线长度
最优布图是未知的，具体实现时用初始布图代替最优布图计算\(norm\_area\)和\(norm\_wire\)。
(2)编码到布图的转换：
二维矩形Packing问题中研究对象主要是硬矩形块（边长确定），基于矩形块向左、向下放置，利用最长路径算法将编码转为布图。
布图规划问题主要处理软模块，要同时确定模块的位置和形状。
层次算法
通过层次地将模块结合在一起，或层次地将问题划分成一组子问题，以减小问题中模块的规模，获得可快速处理大规模模块的布图规划算法。
(1)MB*-Tree:
分为两个阶段：聚类阶段和分离阶段。
通过模块的两两结合，聚类阶段层次地将所有模块结合在一起。结合过程中，聚类因子高的模块将被优先结合。结合后两模块的相对位置也就确定了。所有模块结合后相对位置也会确定。
分离阶段将逐层拆开结合在一起的模块，分离因子高的将被优先拆开。拆开一定数量的模块后会采用模拟退火算法调整模块间相对位置的关系（结合在一起的模块相对位置不变）。所有模块都被拆开后算法停止。 \[ \delta_{ij}=\alpha s_{ij}+\frac{\beta}{d_{ij}} \]
\[ \varphi_{ij}=\lambda s_{ij}+\gamma \omega_{ij} \]
\(\delta_{ij}:\)模块\(m_i\)和\(m_j\)的聚类因子
\(\alpha、\beta:\)常量
\(s_{ij}:\)\(m_i\)和\(m_j\)结合后所产生的闲置空间的大小
\(d_{ij}=c_{ij}/(n_i+n_j):\)\(s_{ij}:\)\(m_i\)和\(m_j\)连接的紧密程度。其中\(c_{ij}\)表示连接\(m_i\)和\(m_j\)的网络数目，\(n_i\)和\(n_j\)表示\(m_i\)和\(m_j\)包含的元模块（已知中的模块）的个数
\(\varphi_{ij}:\)模块\(m_i\)和\(m_j\)的分离因子
\(\gamma、\lambda:\)常量
\(\omega_{ij}:\)当前布图中连接\(m_i\)和\(m_j\)的所有网络的长度之和
(2)IMF：
分为两个阶段：划分阶段和合并阶段
划分阶段将原问题划分成一组子问题。每次划分，首先构造当前问题对应的超图。其中每个节点对应于问题中的一个模块，每条边对应于一个网络。用超图分割算法hMetis分割超图，模块也就分成了两份。然后按照两份模块面积比例，平行于当前电路板的短边，将其分成两个子电路板。当所有子问题中模块数目都足够小时停止划分。
合并阶段：逐层合并子问题，采用模拟退火算法调整合并成的问题中模块间相对的位置来优化问题目标。当所有子问题都被合并在一起时，停止合并过程并返回原问题的解。
(3)PATOMA:
与 IMF 中的划分阶段类似，PATOMA 也采用hMetis递归地划分问题。但与 IMF 持续划分问题直到所有子问题中模块数目足够小不同，PATOMA 每次执行划分之前都要用二维矩形 Packing 算法 ZDS 或 ROB 进行一个判断。其中 ZDS 是处理软模块的算法，ROB 是处理硬模块和混合模块的算法。如果将要生成的两个子问题中的模块，均可以被 ZDS 或 ROB 合法放置到对应的子电路板上，就执行该划分，否则停止划分该问题。当所有子问题都不能被进一步划分时，停止划分过程，并用 ZDS或 ROB 求解所有子问题，进而得到原问题的布图。
综上可知，PATOMA 只在层次转化时，利用 hMetis 优化问题目标。MB*-Tree 和IMF 在第一阶段的层次转化中，分别用模块聚类策略和 hMetis 优化问题目标，同时在第二阶段对于每层的简化问题都用模拟退火算法调整了模块间相对位置关系、优化了问题目标。因此当计算时间足够大时，MB* -Tree 和 IMF 的计算性能优于 PATOMA。但因为 MB*-Tree 和 IMF 使用了计算速度较慢的模拟退火算法，导致了它们实际的性能劣于 PATOMA。
两阶段算法
基本思路是将问题的求解分成两个阶段。第一阶段优化问题目标，目的是得到一种较优的模块间的相对位置关系。模块间相对位置关系可以用一个具体布图或者一种编码表示。在尽量保持第一阶段所得模块间相对位置关系的基础上，第二阶段微调第一阶段所得布图，转换为合法布图。
(1)UFO:
第一阶段：采用凸优化模型Push-Pull(PP)，将模块均匀的放置到电路板上，同时优化连线长度。在PP模型中，任意模块\(m_i\)被视为半径\(r_i=\sqrt{S_i}\)、中心点坐标为\((X_i,Y_i)\)的圆\(C_i\)。对于任意两个圆\(C_i\)和\(C_j\)：（上下两个等式分别是有重叠和无重叠时的作用力） \[ f_{ij}(X_i,X_j,Y_i,Y_j)=\begin{cases} c_{ij}d_{ij}+s_{ij}×\frac{p_{ij}}{d_{ij}},p_{ij}\geq0 \\c_{ij}d_{ij}+1×\frac{p_{ij}}{d_{ij}},p_{ij}<0 \end{cases} \] \(c_{ij}:\)连接它们的网络数目
\(d_{ij}=\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}:\)中心点距离
\(p_{ij}=(r_i+r_j)-d_{ij}\)：嵌入深度，大于等于0表示无重叠，小于0表示有重叠
\(s_{ij}=(r_i×r_j)^2:s_{ij}×\frac{p_{ij}}{d_{ij}}\)和\(1×\frac{p_{ij}}{d_{ij}}\)表示由重叠产生的作用力
将圆之间所有的作用力加在一起作为目标函数，并用凸规划优化该函数，可得到所有圆均匀分布在电路板上，且连接紧密的圆较近放置的布图。
第二阶段：首先用 DT 方法从阶段一所得均匀布图中，提取圆的相邻关系，并进一步地将圆的相邻关系转化为模块间的相对位置关系。接下来，根据模块间的相对位置关系、软模块的形状约束和模块完全处于电路板上的约束，将布图问题转化成一个凸优化模型，用二阶锥规划优化该模型，得到合法布图。
(2)Defer:
第一阶段：采用超图分割算法 hMetis 递归地分割模块，以构造一棵Generalized Slicing Tree（GST）表示模块间的位置关系。GST 是 Slicing Tree 的一种扩展，它是无序的，且在非叶子节点没有标出分割的方向。因此 GST 只记录每次将模块分割成两个子集的情况，并不规定分割的方向和分割后两个子集间的相对位置关系。分割过程中，若当前模块的数目小于一个常数（例如 10），就停止分割该组模块，并将它们记为 GST 的一个叶子节点。给出一棵 Slicing Tree，通过自下而上地布图结合可生成一个分片布图。而由于 GST 只给出了子布图结合的顺序，并没给出子布图的结合（分割）方向与结合后的相对位置关系，所以根据一棵 GST 可以构造出一组分片布图。
第二阶段：首先对 GST 中的任意叶子节点，穷举其对应模块可组成的所有分片布图。在此过程中，对于软模块，只离散地取其若干种可能的形状。对于每个布图，用一个坐标点表示它的宽和高，其中横坐标和纵坐标分别等于布图的宽和高，相应的每个叶子节点可用由若干离散坐标点组成的 Curve 表示。根据 GST 的结构，递归地自下而上结合 Curve，直至所有 Curve 都结合在一起。在 Curve 结合过程中，为了控制Curve 上坐标点的数目，使用了基于对最终布图中闲置空间预测的 Whitespace-Aware Pruning（WAP）策略，适当地删除新生成 Curve 上的点。最终的 Curve 上，横、纵坐标分别小于电路板的宽和高的坐标点，对应就是问题的合法解。选取合法解中最好的若干个，并通过调整结合在一起的兄弟模块间的相对位置关系，进一步优化连线长度。最后，连线长度最短的布图即为 DeFer 所得解。
(3)F-FM:
第一阶段：将所有模块均匀地放置到电路板上，同时优化连线的长度。为了评估模块放置是否均匀，首先将电路板划分成相同大小的格子。利用共轭梯度法优化公式就可将模块均匀放置，且连线长度较短的布图。
第二阶段：首先递归地切割阶段一生成的均匀布图构造一棵 GST，之后采用DeFer 中的第二阶段中的方法，通过自上而下地结合 Curve 生成最终布图。
(4)基于拟牛顿法的布图规划算法：
该算法是一个两阶段布图规划算法。
第一阶段：利用超图分割算法hMetis递归地划分问题，得到一个模块均匀放置，连线长度较短的布图。
第二阶段：通过移动模块的位置和改变软模块的形状，将第一阶段所得布图转化为合法布图。
优化最小面积（二维矩形Packing）
问题描述
已知 \(n\)个可 90°旋转的矩形块，每个矩形块 \(r_i\) 的尺寸为 \(w_i × h_i\)；一个尺寸未知的矩形框。二维矩形 Packing 面积最小化问题（RPAMP）要求将所有矩形块正交、无重叠、完全地放置到矩形框上，目标是最小化矩形框的面积，即 \(min(W × H)\)。对于任意矩形块\(r_i\)，\(t_i\)表示它是否被放置到了矩形框上，\(t_i=1\)表示已放置，\(t_i=0\)表示未放置。\((x_{i1},y_{i1})\)和\((x_{i2},y_{i2})\)分别表示它的左下角坐标和右上角坐标。RPAMP的形式化定义如下：
目标：\(min W×H\) \[ St.\\(1)(x_{i2}-x_{i1},y_{i2}-y_{i1})\in\{(x_i,h_i),(h_i,w_i)\},\\(2)max(x_{i1}-x_{j2},x_{j1}-x_{i2},y_{i1}-y_{i2},y_{j1}-y_{i2})×t_it_j\geq0,\\(3)0\leq x_{ik}\leq W,0\leq y_{ik}\leq H,k\in\{1,2\}. \] 其中\(i\)和\(j\)均取\(\{1,2,...,n\}\)中的任意值，且\(i\neq j\)。约束（1）表示矩形块是正交放置的；约束（2）表示任意两个已放置矩形块无重叠；约束（3）表示已放置的矩形块完全处于矩形框中。把所有已放置矩形块的面积之和与矩形框面积的比例\((\sum^n_{i=1} w_ih_it_i/(WH))\)称为填充率，用来评估解的质量。
求解算法
生成候选框宽的方法
先从已知的\(n\)个矩形块中随机地选取最多\(n_c\)个，并从每个被选取的矩形块的两条边中随机地选取一条边。将所选取的边的长度之和称为一个组合长度，则总共可得\(2c^1_n+2^2c^2_n+...+2^{n_c}c^{n_c}_n\)种由不同边组合而成的组合长度。穷举所有组合长度可能的取值，然后计算每个值出现的频率，频率最大的前\(l\)个组合长度就是生成的候选框宽。
布图紧凑算法
紧凑算法（Compacting Algorithm，CA）通过迭代地向下、向左移动矩形块将矩形块间无重叠的布图转化为紧凑布图，其中紧凑布图的外包络矩形小于等于原布图的外包络矩形。
定义1. 占左下角矩形块: 一个矩形块是占左下角矩形块，当且仅当它的左边界和下边界均与其它占左下角矩形块相贴，其中矩形框的左边界和下边界被视为两个特殊的占左下角矩形块。
定义2. 紧凑布图: 如果一个布图中所有矩形块均是占左下角矩形块，则称该布图为一个紧凑布图。
引理1. 如果一个布图中所有矩形块的左边界和下边界都与其它矩形块相贴，则该布图是紧凑布图。
定义3. 约束图: 约束图是边带权的有向图，它被用来表示矩形块之间的相对位置关系。根据约束图表示的是矩形块间的左右位置关系或上下位置关系，可分为水平约束图\((G_h)\)和竖直约束图\((G_v)\)。假设\(V\)和\(E\)分别表示约束图中的顶点和边，则水平约束图\(G_h(V, E)\)的构造方法如下：
（1）\(V\)：起始点\(s\)，终止点\(t\)，\(n\)个分别以矩形块的名字命名的顶点。
（2）\(E\)：每个矩形块\(r_i\)有两条边\(<s,r_i>\)和\(<r_i,t>\)，任意两个矩形块\(r_i\)和\(r_j\)间存在边\(<r_i,r_j>\)，当且仅当\(r_i\)在\(r_j\)的左边、它们在\(y\)轴上的投影有重叠。
（3）边的权重：边\(<s,r_i>\)的权重等于0，边\(<r_i,t>\)和\(<r_i,r_j>\)的权重均为\(w_i\)。
类似地，可以构造竖直约束图\(G_v(V, E)\)。
将约束图中的顶点分为三类：
（1）稳定顶点，它们对应于占左下角矩形块；
（2）关键顶点，它们的所有前驱节点都是占左下角矩形块；
（3）不稳定节点，前驱节点中存在非占左下角矩形块。
紧凑算法流程：紧凑算法迭代地执行移动动作将布图转化为紧凑布图，每个移动动作包括一个左移动作和一个下移动作。执行左移动作时，先构造当前布图的水平约束图\(G_h\)，然后更新每个矩形块\(r_i\)的左下角\(x\)坐标值为\(s\)到 \(r_i\)的最长路径长度，从而使得每个矩形块的左边界都与其它矩形块相贴。类似地，在执行下移动作时，构造当前布图的竖直约束图\(G_v\)以更新每个矩形块的左下角\(y\)坐标值，使得所有矩形块的下边界都与其它矩形块相贴。当一个移动动作没有改变任何矩形块的位置时，停止以上迭代。最终，所得布图是紧凑布图，\(G_h\) 和\(G_v\)中\(s\)点到\(t\)的的最长路径长度分别为该布图中矩形框的宽和高。
引理2. 如果已知布图是合法的，则CA紧凑所得布图也是合法的。
引理3. CA得到的布图是紧凑布图
引理4. CA的最坏时间复杂度是\(O(n^6)\)。
动态规约算法框架
动态规约算法（DRA）首先初始化一个期望填充率（例如 50%），并用WV3选取若干个矩形块边长的组合长度作为候选框宽。然后进入迭代构造 RKP 问题，用 LIF 求 解 RKP 问题的过程。每次迭代，首先根据当前的期望填充率 \(efr\) 和框宽 \(W_i\)，计算框高 \(H_i = 所有矩形块面积之和/(efr× W_i)\)，从而构造出相应的 RKP 问题。接下来，根据矩形块的数目选取 LIF0 或 LIF1 计算 RKP 问题得到一个布图。如果布图是包括所有矩形块的可行布图，就用紧凑算法继续优化该布图得到紧凑布图，当紧凑布图的填充率大于目前得到的最高填充率时，更新最优布图为该紧凑布图，并更新最高填充率。否则，如果当前框宽下，已无获得更高填充率布图的可能，就取下一个候选框宽作为当前框宽，而如果当前框宽下，仍有获得更高填充率布图的机会，就保持框宽不变，并适当地减小期望填充率。当框宽是最后一个候选框宽，且期望填充率不能再增加时，终止 DRA 的迭代，返回找到的的最好布图。