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

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

作　　者：吕丽华[1,2] 张红[3,2] 

机构地区：[1]杭州电子科技大学CAD研究所,杭州310018 [2]浙江经贸职业技术学院信息技术系,杭州310018 [3]浙江大学管理学院,杭州310027

出　　处：《计算机工程》2010年第6期64-66,共3页Computer Engineering

基　　金：浙江省教育厅科研基金资助项目(Y200803271)

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

关 键 词：分段时延凸函数 总体布线 超大规模集成电路 

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