高级检索
马坤, 齐子阳, 周强, 蔡懿慈. 矩形Steiner最小树布线灵活度[J]. 计算机辅助设计与图形学学报, 2014, 26(10): 1909-1914.
引用本文: 马坤, 齐子阳, 周强, 蔡懿慈. 矩形Steiner最小树布线灵活度[J]. 计算机辅助设计与图形学学报, 2014, 26(10): 1909-1914.
Ma Kun, Qi Ziyang, Zhou Qiang, Cai Yici. Flexibility in Rectilinear Steiner Minimal Tree[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(10): 1909-1914.
Citation: Ma Kun, Qi Ziyang, Zhou Qiang, Cai Yici. Flexibility in Rectilinear Steiner Minimal Tree[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(10): 1909-1914.

矩形Steiner最小树布线灵活度

Flexibility in Rectilinear Steiner Minimal Tree

  • 摘要: 矩形Steiner最小树(RSMT)的布线灵活度影响其结构变形能力,直接影响芯片布线的收敛性.文中从树边形态、结构固有变形和拓扑变形3方面对线网的RSMT的布线灵活度进行刻画,给出了更能反映RSMT结构变形能力的计算模型.针对布线灵活度的“瓶颈”问题,提出了拥挤驱动的RSMT布线灵活度挖掘算法:根据树形的最短布线路径布线可能情况,定义了树边的布线灵活度;进而考虑RSMT结构中所有树边布线灵活度的组合情况和RSMT拓扑的变形性,得到RSMT布线灵活度.实验结果表明:将计算模型应用到拥挤驱动的RSMT布线灵活度挖掘算法,良好地改善了布线拥挤;将该挖掘算法应用到FastRoute4.1总体布线算法中,能够缩短14%的运行时间.

     

    Abstract: The flexibility of RSMT strongly affects the distortion ability of a structure of RSMT, becoming one of the key factors affecting the convergence of integrated circuits routing.The flexibility of RSMT is studied in this paper from three aspects, including the shape of a tree edge, inherent distortion of a structure of RSMT, and topological transformation, and a new model reflecting the structural distortion ability of RSMT is proposed.A congestion-driven flexibility exploiting algorithm is proposed to solve the flexibility "bottleneck" problem.Firstly, the flexibility of a tree edge is defined according with the shortest-length routing possibility.Secondly, the flexibility of RSMT is defined considering the combination of all tree edges' flexibility in a structure of RSMT and topological transformation.Experiments show that congestion-driven flexibility exploiting algorithm can generate a routing tree with less congestion using the model.Also, the routing tree generated by the algorithm is applied into Fast Route 4.1, resulting a reduction of 14% in the runtime of global routing.

     

/

返回文章
返回