This paper proposes a genetic algorithm for generating a set of rectilinear Steiner trees for the interconnect optimization problem in VLSI layout design. The algorithm produces a set of rectilinear Steiner trees, whose geometrical and timing characteristics are different each other. In the proposed genetic algorithm, each chromosome represents the topological structure of a Steiner tree. An evaluation function is given to map it into the layout of a Steiner tree. Steiner trees produced by the algorithm are Pareto-optimal with respect to the total wire length and the maximum propagation delay, and the user can choose any tree among those solutions as a final routing solution. Experimental results show that the algorithm efficiently produces a set of alternative routes in VLSI interconnect optimization.
展开▼