基于分段时延凸函数的最小斯坦纳树方法

针对超大规模集成电路的互连时延问题，提出一种利用互连时延为搜索距离分段凸函数性质建立的最小时延斯坦纳Elmore(Steiner Elmore)布线树的方法，采用扩大搜索空间的方法寻找最佳连接点，同时建立一种有效的查找方法对布线树进行反复修改以减小树的总长度。实验结果表明，该方法可以缩小布线树的搜索空间，加快搜索速度，在阻抗占优的情况下，具有较好的性能。

Method of Minimum Steiner Tree Based on Piecewise Concavity of Delay Function

Aiming at the problem of the interconnection delay in Very Large Scale Integration(VLSI), this paper proposes a method of minimum- delay Steiner Elmore routing tree, which is based on considering the interconnection delay as the piecewise convex function for searching distances. The method expands the searching space so as to find the best connection point, meanwhile, it sets up an effective searching solution to modify the routing tree repeatedly so as to reduce the total length of the tree. Experimental result shows that the improved routing method can dramatically reduce the searching space, increase the search speed, and it has better performance when the impedance has greater impact in delay.