摘要
本文提出了一种以电性能优化为目标的Ｓｔｅｉｎｅｒ树算法，它把从线网的源点到漏点的时间延迟最小作为求解Ｓｔｅｉｎｅｒ树的目标．文中首先给出一种多端线网连线延迟模型，然后导出它的上界，它是线网连线总长和从源点到漏点路径长度的函数．用这个上界作为求解Ｓｔｅｉｎｅｒ树的优化目标．算法采用了非线性优化技术和动态规划方法．实验例子表明，算法是十分有效的．
This paper presents a performance-driven Steiner tree algorithm for global routing which takes the minimization of timing delay during the tree construction as the goal. A timing model is established which includes both total wire length of the net and critical path between the source and sink of the net in delay formulation, and an upper bound for timing delay is deducted and used to guide the algorithm. The nonlinear optimization and the dynamic programming techniques are used in this algorithm. Experimental results are given to demonstrate the effectiveness of the algorithm.
出处
《计算机学报》
EI
CSCD
北大核心
1995年第4期266-272,共7页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
STEINER树
电性能优化
集成电路
布线
Steiner tree, timing model, nonlinear optimization, global routing,dynamic programming
