论文部分内容阅读
随着集成电路工艺制造技术的迅速发展,芯片的特征尺寸不断减少,互连线的结构变得越来越复杂。互连线的RC延时已经成为了芯片的主要延时,极大地影响着芯片的性能。针对传统的Manhattan互连结构受限于布线走向只能水平、竖直两个方向、无法充分利用布线空间资源而造成互连线的延时难以被进一步优化,产生了一系列新型的非直角的互连结构,尤其是X互连结构因其减少线长的潜力而引起了广泛的研究兴趣。本文主要研究X互连结构的快速启发式的布线算法,将实际非常复杂的X互连结构的布线问题简化为构建绕过障碍物的八叉Steiner最小树(OAOSMT)的计算几何问题。通过研究学习国内外相关学术成果,本文提出了构建图的Steiner最小树(GSMT)的新启发式算法,并运用该算法和几类简单的几何变换来实现绕过障碍物的八叉Steiner最小树的构建。针对经典的图的Steiner最小树问题,本文提出了包含四步骤的新启发式算法。首先对原始输入图进行连通子图的分解并简化,来减少求解问题的规模。然后在每个连通子图中按照三源最短路径扩展的思想来构建Steiner树。接着利用Steiner点插入和边变换的操作来进一步优化连通子图的Steiner树。最后,合并各个子图中的Steiner树来获得原始图完整的Steiner最小树。实验结果表明,该算法相比传统的GSMT启发式算法,能获得更高质量的Steiner树,67%的测试例子获得的Steiner树跟最优Steiner树相比误差不超过1%。本文将此GSMT的求解方法应用到X型互连结构的布线问题中,提出了构建绕过障碍物的八叉Steiner最小树(OAOSMT)的新启发式算法。首先引入改进型Escape图的概念,然后将构建绕过障碍物的直角Steiner最小树问题(OARSMT)转化为改进型Escape图的GSMT问题并求解。最后在OARSMT的基础上,引入了5类简单的几何变换来快速得到用于X型互连结构的OAOSMT。实验结果表明,本文提出的构建OAOSMT的新启发式算法,获得的OAOSMT相比OARSMT,总线长能减少8%～17%,初步验证了X型互连结构减少线长的潜力。