X-STRUCTURE-BASED METHOD FOR CONSTRUCTING STEINER TREE BY TAKING INTRA-OBSTACLE WIRING INTO CONSIDERATION

摘要

An X-structure-based method for constructing a Steiner tree by taking intra-obstacle wiring into consideration. The method comprises the following steps: step S1: initializing a particle swarm, wherein each particle represents an X-structure Steiner tree connecting all given pins; step S2: preprocessing the particle swarm, and generating a lookup table including all pieces of connection information between any two pins of all the particles; step S3: carrying out particle swarm flight, and carrying out iteration by means of a mutation strategy, a crossover strategy and a particle fitness value function to obtain excellent particles; step S4: continuing to adjust the obtained excellent particles, introducing an adjustment strategy that an obstacle corner point is a Pseudo-Steiner point, and ensuring that the lengths of connected components of all edges within an obstacle do not exceed a threshold value L, so as to obtain the adjusted excellent particles; and step S5: further refining the adjusted excellent particles to obtain an optimal particle, i.e. an optimal X-structure Steiner tree. By means of the method, wiring can be carried out by making full use of intra-obstacle resources, thereby significantly reducing the total wiring length.