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.