Construction method for multi-layer-chip efficient X-structure obstacle-avoiding router

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 present invention is an integrated circuit computer -assisted design technology field, which involves a problem of high -efficiency X structured barrier wiring structures for multi -layer chips. Background technique [0002] Stana's smallest tree is one of the most important mathematical models in the field of map theory, and has been widely used to many research fields.Especially in 1966, the right -angle structure proposed by Hanna (RSMT) has been widely applied to multiple stages designed by the design of modern oversized integrated circuits (VLSI).For example, in the early design stage, including division, cloth planning and layout, RSMT can be used to effectively estimate many performance indicators of chips, such as line length, congestion, and extension.During the overall wiring and detailed wiring phase, RSMT can be used to construct the final connection topology of each line network.In addition, with the sharp increase in the density of modern ...

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 structure of the multi-layer obstacle-avoiding X-architecture Steinerminimal tree (ML-OAXSMT) router, the problem will be become very difficult

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

Images