摘要
在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接．斯坦纳树（ＳｔｅｉｎｅｒＴｒｅｅ）的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线．根据已有的研究，构造斯坦纳树的问题，是一个ＮＰ完全问题［４］．随着集成电路工艺的发展，人们越来越多地考虑多层布线的问题．本文从多层布线出发，利用在单元或模块内部已有的连线所提供的可用通孔集合作为布线资源，引入浮动端点的概念，提出了一种处理浮动端点的斯坦纳树构造算法ＡＦＬＯＳＴ．该算法能先后生成含浮动端点的最小生成树和含浮动端点的斯坦纳树．根据给定的算法，文中给出了相应的图例来演示构造过程．
The topological positions of modules(or sub circuit units)have been given after placement. Routing is used to connect the modules of circuit in integrated circuit layout procedure. Steiner tree is applied to implement the global routing, of course it is also used to do the detail routing when considering the obstructs between units. It was proved that the problem of constructing an optimal Steiner Tree is NP complete . With the developement of IC technology, multi layer routing is more and more important. In the units or modules, there are some sub trees which may be able to supply routing resources with the via assembles that we define as floating pins. A new algorithm called AFLOST is proposed in this paper. The algorithm is able to construct the minimun spanning tree and Steiner tree of floating pins. Finally some examples are given to explain the procedure of constructing trees according to the algorithm.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
1998年第6期559-565,共7页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金
国家重点科技(攻关)项目
浙江省自然科学基金
