A construction method of high-efficiency x-structure obstacle-avoiding router for multi-layer chips

Abstract

The invention relates to the technical field of integrated circuit computer-aided design, in particular to a construction method for a multi-layer-chip efficient X-structure obstacle-avoiding router. The method comprises the following steps: step S1, according to a group of given pin coordinate positions, generating a 3D-OFMST (3D Obstacle-free Minimal Spanning Tree) connected with all pins based on a fast multi-fragmentation minimal spanning tree (MST); step S2, calculating XRPs (X Routing Paths) of all edges in the 3D-OFMST, and saving the calculated information to two records to generate two lookup tables; step S3, based on the lookup tables, transforming each edge of the 3D-OFMST to an XRP to generate an ML-XST (Multi-layer X-architecture Steiner Tree), and transforming the ML-XSTs to an ML-OAXST (Multi-layer Obstacle-avoiding X-architecture Steiner Tree); step S4, further optimizing the ML-OAXST from global and local perspectives so as to generate a final ML-OAXSMT.

Description

technical field [0001] The invention belongs to the technical field of computer-aided design of integrated circuits, and in particular relates to the construction problem of a high-efficiency X-structure obstacle-avoiding router for multi-layer chips. Background technique [0002] The Steiner minimum tree is one of the most important mathematical models in the field of graph theory, and has been widely used in many research fields. In particular, the rectangular Steiner minimal tree (RSMT) proposed by Hanna in 1966 has been widely used in multiple stages of modern very large scale integration (VLSI) design. For example, in the early design stages, including partitioning, floorplanning, and placement, RSMT can be used to effectively predict multiple performance indicators of the chip, such as wire length, congestion, and delay. During the general routing and detailed routing phases, RSMT can be used to construct the final connectivity topology for each net. In addition, wit...

AI Technical Summary

Problems solved by technology

[0005] The problem is that when considering the three factors of multi-layer chip structure, obstacles, and X-structure at the same time, that is, the multi-layer obstacle-avoiding X-architecture Steiner minimal tree (ML-OAXSMT) router construction, the problem becomes very difficult

Because, only a single-layer RSMT router construction has been proved to be an NP-complete problem

Images