【摘要】 矩形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.更多还原