10/01/1991 09:00 AM
Computer Science
We describe a practical iterative approximation algorithm that can be used for homotopic positioning of Steiner points and vias for minimization of a wiring cost in rubber-band sketches. The algorithm is based on modeling the interconnect as a physical system and iterativly finding it minimum energy state. This method has a wide range of applications including finding Steiner trees, optimization of nets with given topologies, and optimization of constrained nets. It supports multi-layer sketches with obstacles, and can be adapted to various optimization goals by changing the force function. The algorithm can be used to improved the topology or to improve the wiring for a given topology. By controlling, the force functions of the physical system, various aspect of the interconnect such as average or maximal wire length can be improved.
