1拥挤度估计
以往的拥挤度估计方法分为两类：边界框方法和总体布线方法。由于布线模型没有确定，边界框方法是一种粗略的估计方法。总体布线是一种基于拓扑结构的方法，通常是L型布线或Z型布线。本文采用总体布线的方法来进行拥挤度的估计，模块的边的移动通过总体布线来控制。
2拥挤度驱动的模块边的移动
2.1确定布局区域的大小
改变布局区域的大小的目的是使其能够满足布线需求。首先，将整块电路板划分成m×n个布局区域，用Bij代表每个布局区域，i代表行（i=1…m），j代表列（j=1…n）。如图3所示，xij和xij+1分别代表布局区域Bij的左边和右边，yij和yij+1分别代表布局区域Bij的上边和下边。uijl、uijr、uijt和uijb分别代表通过总体布线得到的布局区域左边、右边、上边和下边布线的数量。H、W、hTile和wTile分别代表电路板的高度、宽度、布局区域原始高度和原始宽度。（1）布通率约束。布线的容量与布局区域边的长度相关联，理想情况下，如果布局区域的边足够大，布线时就不会产生重叠。在布通率约束公式中，用xi,j+1-xij代表布局区域Bij的宽度，用f1（u）表示容纳下u条线所需要的长度，u是通过总体布线得出的。（2）面积约束。此约束是用来确保布局区域可以容纳下其中的所有单元，如果没有此约束，假设布局区域的高是固定的，当布局区域的边不拥挤时，在X方向布局区域内的单元就会产生大量的重叠。（3）移动约束。算法输入的结果是一个已经合法化的布局，所以优化过程有必要不过多的影响原有布局结果，因此需要设置移动约束来限制边的移动。在公式中，C代表边移动的限度，设定C的大小为布局区域宽度的一半。（4）电路板大小约束。最后设定电路板约束来限制边在移动时不要超出电路板之外，保证结果的合理性。
2.2基于最长路径的解决方法
快速有效的解决拥挤问题的方法是基于最长路径技术。为了计算最长路径，需要建立一个有向无环图G（V，E），对于每一条布局区域边Xij用顶点Vij来代替，对于每一种不同的约束这里用有向边来代替，用边Er代替布通率约束，用边Ea代替面积约束，用边Em代替移动约束，就可以找到从左至右最长的一条路径，如图4所示。因为在两个顶点之间有三种约束，所以采用以下的方法计算出两点间的最长路径。其步骤如下：（1）按照布通率约束移动边的时候，边同时受到面积约束和移动约束，如果布通率约束得出的值同时满足面积约束和移动约束，此时就将两点间的距离设置为经布通率约束得出的值（||Er||）。（2）如果得到的值仅满足移动约束而不满足面积约束，此时将两点间的距离设置为有面积约束得到的值（||Ea||）。（3）如果经布通率计算得到的值满足面积约束而不满足移动约束，此时将两点间的距离设置为有移动约束得到的值（||Em||）。（4）如果由布通率计算得到的值对于其他两种约束都不满足，此时先将两点间的距离设置为由移动约束计算得到的值（||Em||），如果同时也满足面积约束，则此值被确定下来，如果不满足面积约束，两点间的距离设置为由面积约束计算得到的值（||Ea||）。基于以上的理论，可以计算出任意两点间的距离，最终确定出一行的长度：（L=Σ||E||）。选出所有行中最长的一行为最长路径（LP）。如果该长度大于电路板的宽度（LP>W），需要压缩此长度使其在电路板之内。因为两点间的距离有三种可能的值，定义经布通率约束和移动约束得到的值（||Er||）、（||Em||）为可压缩值，经面积约束计算得到的值（||Ea||）为不可压缩值。通过定义，将所有（||Er||）、（||Em||）乘以压缩比例s（s=W/(LP-||Ea||）），就得到了满足所有条件的结果。经过上述操作，所有单元会整体向左偏移，并挤压在原本不拥挤的区域，如图5所示。为了避免这种情况，设布局区域边未移动时的坐标为Xi，j，经过从左至右的最长路径操作后得到的坐标为Xli，j，然后将原本输入的需要移动。根据布局区域改变前单元到区域左边和区域右边的比例确定新单元的位置，如图6所示，L1/R1=L2/R2。
3实验验证
实验验证是在一台CPU为2.4GHzIntelXeon，内存4G的机器上完成，采用的ISPD2011比赛实例。选取的7个比赛实例以及由清华大学、国立交通大学、密歇根大学处理的结果，用总体布线工具NCTURouter2.0[11]确定估计的拥挤信息和评估实验结果，对各院校比赛得出的布局结果进行处理优化。实验结果统计在表1中，前缀如SC代表清华大学，VDA代表国立交通大学，simpl代表密歇根大学，后接的如superblue4为比赛中的实例名称，组合在一起表示各大学对不同实例处理的结果。通过数据得出经过优化处理之后的结果在布线线长、布线重叠度、布线时间上都有很好的优化，特别是经清华大学处理的实例superblue4，提高极为明显，由国立交通大学大学处理的结果也有很大的提高。
4结论
本文提出了一种针对超大型集成规模电路的拥挤度优化技术，本技术独立于任何布局器之外，并可以适用于各种不同的模型中，通过实验验证，该方法对于布局的布通率提高效果显著，为以后实际工业应用奠定了很好的大学学报基础。
作者：赵彦 赵殷瑶 乔旭 钱旭 单位：中国矿业大学（北京）机电与信息工程学院 国家认证认可监督管理委员会
