论文部分内容阅读
在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接．斯坦纳树（ＳｔｅｉｎｅｒＴｒｅｅ）的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线．根据已有的研究，构造斯坦纳树的问题，是一个ＮＰ完全问题［４］．随着集成电路工艺的发展，人们越来越多地考虑多层布线的问题．本文从多层布线出发，利用在单元或模块内部已有的连线所提供的可用通孔集合作为布线资源，引入浮动端点的概念，提出了一种处理浮动端点的斯坦纳树构造算法ＡＦＬＯＳＴ．该算法能先后生成含浮动端点的最小生成树和含浮动端点的斯坦纳树．根据给定的算法，文中给出了相应的图例来演示构造过程．
In the automatic layout technology of the integrated circuit, after completing the layout process, that is, determining the topological position of each module (or sub-circuit unit), the wiring needs to complete the connection between the circuit modules. The construction of the SteinerTree can be applied to the overall cabling; it can also be used for detailed wiring if one considers the barriers to existing cells or wiring. According to the existing research, the problem of constructing a Steiner tree is an NP-complete problem [4]. With the development of integrated circuit technology, people increasingly consider the issue of multi-layer wiring. In this paper, starting from multi-layer routing, the concept of floating endpoints is introduced by using the available vias provided by the existing connections in the cell or module as the routing resources, and a Steinna tree construction algorithm AFLOST for handling floating endpoints is proposed. The algorithm can generate a minimum spanning tree with floating end points and a Steiner tree with floating end points. According to the given algorithm, the article gives the corresponding legend to demonstrate the construction process.