矩形Steiner最小树布线灵活度  

Flexibility in Rectilinear Steiner Minimal Tree

作　　者：马坤[1] 齐子阳 周强[1] 蔡懿慈[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《计算机辅助设计与图形学学报》2014年第10期1909-1914,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61176035)

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

关 键 词：总体布线 矩形Steiner最小树 布线灵活度 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构]