一种以电性能优化为目标的Steiner树算法  

A PERFORMANCE-DRIVEN STEINER TREE ALGORITHM FOR GLOBAL ROUTING

作　　者：洪先龙[1] 

机构地区：[1]清华大学计算机科学与技术系

出　　处：《计算机学报》1995年第4期266-272,共7页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文提出了一种以电性能优化为目标的Ｓｔｅｉｎｅｒ树算法，它把从线网的源点到漏点的时间延迟最小作为求解Ｓｔｅｉｎｅｒ树的目标．文中首先给出一种多端线网连线延迟模型，然后导出它的上界，它是线网连线总长和从源点到漏点路径长度的函数．用这个上界作为求解Ｓｔｅｉｎｅｒ树的优化目标．算法采用了非线性优化技术和动态规划方法．实验例子表明，算法是十分有效的．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.

关 键 词：STEINER树 电性能优化 集成电路 布线 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论] TN405.97[自动化与计算机技术—计算机科学与技术]