X-structure Steiner minimum tree construction method considering wiring resource relaxation

Abstract

The invention relates to an X-structure Steiner tree construction method considering wiring resource relaxation. Five effective strengthening strategies are designed on the basis of a traditional right-angle Steiner tree. The method comprises the following steps: (1) changing a traditional wiring structure and adding a new wiring direction; (2) limiting the wiring length of the Steiner tree in theobstacle, and fully using wiring resources in the obstacle; (3) using a special particle swarm optimization algorithm combined with a classical genetic operator; (4) establishing a lookup table for providing rapid information query for the whole algorithm flow, and (5) designing two heuristic strategies of corner selection and refining to further improve the quality of the wiring tree. A simulation experiment of a standard test circuit shows that compared with the similar algorithm, the X-structure Steiner tree construction method considering the relaxation of the wiring resources makes fulluse of the wiring resources in the obstacle, effectively shortens the total wiring length and obtains the optimal total wiring length.

Description

technical field [0001] The invention relates to the technical field of computer-aided design of integrated circuits, in particular to an X-structure Steiner minimum tree construction method considering the relaxation of wiring resources. Background technique [0002] The routing problem in very large scale integration (VLSI) design has always been the focus of researchers. This is one of the most important steps in the VLSI physical design process. At present, the related work on the wiring tree is mainly concentrated on the Manhattan structure, but when optimizing the line length and delay based on the Manhattan structure, due to its limited wiring direction, the wiring area cannot be fully utilized, resulting in redundant interconnection resources. Therefore, its optimization ability is limited. Therefore, it is necessary to start from the root and change the traditional Manhattan structure, so the researchers began to try to use the non-Manhattan structure as the basic ...

AI Technical Summary

Problems solved by technology

[0004] In the model based on the Manhattan structure, there have been many related studies on this kind of problem, that is, the length-restricted rectilinear Steiner minimum tree problem (LRRSMT), while in the model based on the non-Manhattan structure, For such problems, the research on the length-restricted X-architecture Steiner minimum tree problem (LRXSMT) has not yet been carried out.

Images