一种含浮动端点的斯坦纳树的构造算法

作     者：黄林 赵文庆 唐璞山 〖HJ*] HUANG LIN ZHAO WEN QING\ TANG PU SHAN

作者机构：上海复旦大学电子工程系CAD研究室 

基　　金：国家自然科学基金 国家重点科技(攻关)项目 浙江省自然科学基金 

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：1998年第10卷第6期

页      码：559-565页

摘      要：在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接．斯坦纳树（ＳｔｅｉｎｅｒＴｒｅｅ）的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线．根据已有的研究，构造斯坦纳树的问题，是一个ＮＰ完全问题［４］．随着集成电路工艺的发展，人们越来越多地考虑多层布线的问题．本文从多层布线出发，利用在单元或模块内部已有的连线所提供的可用通孔集合作为布线资源，引入浮动端点的概念，提出了一种处理浮动端点的斯坦纳树构造算法ＡＦＬＯＳＴ．该算法能先后生成含浮动端点的最小生成树和含浮动端点的斯坦纳树．根据给定的算法，文中给出了相应的图例来演示构造过程．

主 题 词：VLSI 布图 多层布线 斯坦纳树 集成电路 

学科分类：080903[080903] 0809[工学-计算机类] 08[工学] 

核心收录：

馆 藏 号：203887268...