布线拥塞的概率估计

• 作 者: 林志耀
• 出 处: 福州大学
• 发表日期: 2009年01期
• 关键词: 拥塞 概率估计 布线

准确的线长和拥塞估计已经成为VLSI物理设计自动化的重要问题。过度的拥塞将导致局部布线资源的短缺，这将使得必须扩大布线区域或者产生一个不可布线的设计结果。在这种情况下，整个设计程序必须从一个比较早的阶段重新开始，比如返回到版图规划或者布局阶段。因此，在物理设计的早期阶段就非常需要一个有效的拥塞分析和移除技术，以便尽早对互联信息进行准确的分析和预测，从而节约设计的时间成本。此外，目前主流的全局布线主要采用拆线重布技术，而这个技术也主要依赖于对拥塞的估计，以便避开拥挤区域。在相关的文献中已经提出了许多拥塞估计的算法，这些算法主要是根据布线的估计模型的不同来区分。到现在为止，在布局阶段的布线估计方法主要有两种，一种是基于随机模型，另一种是基于实验模型。基于随机模型是考虑每个网的所有可能合法的布线线路，且在不同假设下规定每条线路的发生概率；而基于实验模型是用布局参数来估计线长和可布线性。但他们未能产生精确的结果，因为它们都忽略了和拥塞有关的迂回以及通孔和一些拐弯的影响。本论文的贡献主要有两个方面：其一是提出一种新的理论模型，这个模型考虑不多于三个拐弯和两个引脚网的情况，这与实际的布线相符。依据芯片上含有一个、两个、三个拐弯布线的一定比例关系，计算出每条单位线段被使用的“概率”，进而产生了一种快速准确的拥塞估计算法。但是这种方法暂时还没有实验数据来验证其有效性。我们提出的另一种模型与文献[1]的方法非常接近，也只考虑不多于两个拐弯的布线模型，但是过程简单得多，相比之下速度也更快，通过与07年ISPD全局布线的比赛结果进行实验比对，结果显示它具有较好的估计精确度。