计算机工程 ›› 2010, Vol. 36 ›› Issue (06): 64-66.doi: 10.3969/j.issn.1000-3428.2010.06.021

• 软件技术与数据库 • 上一篇    下一篇

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

吕丽华1,3,张 红2,3   

  1. (1. 杭州电子科技大学CAD研究所,杭州 310018;2. 浙江大学管理学院,杭州 310027;3. 浙江经贸职业技术学院信息技术系,杭州 310018)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-03-20 发布日期:2010-03-20

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

LV Li-hua1,3, ZHANG Hong2,3   

  1. (1. CAD Institute, Hangzhou Dianzi University, Hangzhou 310018; 2. College of Management, Zhejiang University, Hangzhou 310027; 3. Department of Information Technology, Zhejiang Economic & Trade Polytechnic, Hangzhou 310018)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-03-20 Published:2010-03-20

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

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

Abstract: 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.

Key words: piecewise concavity of delay function, global-routing, Very Large Scale Integration(VLSI)

中图分类号: