An X-structure Steiner Minimum Tree Construction Method Considering Routing Resource Relaxation

Abstract

The invention relates to an X-structure Steiner tree construction method considering the relaxation of wiring resources. On the basis of the traditional right-angle Steiner tree, five effective strengthening strategies are designed, including (1) changing the traditional wiring structure and adding new wiring direction; (2) limit the routing length of the Steiner tree in the obstacle, and make full use of the routing resources in the obstacle; (3) use a special particle swarm optimization algorithm combined with classical genetic operators; (4) establish a network for the entire The algorithm flow provides a lookup table for fast information query. (5) Two heuristic strategies, corner selection and refinement, are designed to further improve the quality of the wiring tree. The simulation experiment of the standard test circuit shows that compared with similar algorithms, the X-structure Steiner tree construction method that considers the slackness of routing resources makes full use of the routing resources in the obstacle, effectively shortens the total routing length, and obtains the best total routing 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