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

在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接。斯坦纳树的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线。

]AN ALGORITHM OF FLOATING PIN STEINER TREE GENERATION

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.